مشاكل البائع المتجول تلتزم بائع ومجموعة من المدن. يجب على البائع أن يزور كل مدينة بدءًا من مدينة معينة (على سبيل المثال، مسقط رأسه) ثم يعود إلى نفس المدينة. التحدي المتمثل في المشكلة هو أن البائع المتجول يحتاج إلى تقليل إجمالي طول الرحلة.
لنفترض أن المدن هي x1س2..... سنحيث التكلفة جاي جاييدل على تكلفة السفر من المدينة xأناإلى العاشري. تتمثل مشكلة البائع المتجول في العثور على طريق يبدأ وينتهي عند x1والتي سوف تأخذ في جميع المدن بأقل تكلفة.
الهاشماب في جافا
مثال: يقوم وكيل الصحف بإسقاط الصحيفة يوميًا إلى المنطقة المخصصة بحيث يتعين عليه تغطية جميع المنازل في المنطقة المعنية بأقل تكلفة سفر. حساب الحد الأدنى لتكلفة السفر.
المنطقة المخصصة للوكيل حيث يجب عليه إسقاط الصحيفة موضحة في الشكل:
الحل: مصفوفة التكلفة المجاورة للرسم البياني G هي كما يلي:
نوع سريع
يكلفاي جاي=
تبدأ الجولة من منطقة H1ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H1.
منطقة العلامة H6لأنها أقل منطقة تكلفة يمكن الوصول إليها من H1ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H6.
منطقة العلامة H7لأنها أقل منطقة تكلفة يمكن الوصول إليها من H6ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H7.
وظائف في ج
منطقة العلامة H8لأنها أقل منطقة تكلفة يمكن الوصول إليها من H8.
منطقة العلامة H5لأنها أقل منطقة تكلفة يمكن الوصول إليها من H5.
منطقة العلامة H2لأنها أقل منطقة تكلفة يمكن الوصول إليها من H2.
منطقة العلامة H3لأنها أقل منطقة تكلفة يمكن الوصول إليها من H3.
منطقة العلامة H4ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H4إنه ح1لذلك، باستخدام استراتيجية الجشع، نحصل على ما يلي.
آلة جافا الافتراضية
4 3 2 4 3 2 1 6 H<sub>1</sub> → H<sub>6</sub> → H<sub>7</sub> → H<sub>8</sub> → H<sub>5</sub> → H<sub>2</sub> → H<sub>3</sub> → H<sub>4</sub> → <sub>H<sub>1</sub></sub>.
وبالتالي فإن الحد الأدنى لتكلفة السفر = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
ماتريدس:
الماتويد هو زوج مرتب M(S,I) يحقق الشروط التالية:
- S هي مجموعة محدودة.
- I هي عائلة غير فارغة من مجموعات فرعية من S، تسمى المجموعات الفرعية المستقلة من S، بحيث إذا كانت B ∈ I و A ∈ I. نقول إنني وراثي إذا استوفى هذه الخاصية. لاحظ أن المجموعة الفارغة ∅ هي بالضرورة عضو في المجموعة I.
- إذا كانت A ∈ I وB ∈ I و|A|<|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property.< li>
نقول أن المصفوفة M (S, I) يتم ترجيحها إذا كانت هناك دالة وزن مرتبطة بها w والتي تعين وزنًا موجبًا تمامًا w (x) لكل عنصر x ∈ S. تمتد وظيفة الوزن w إلى مجموعة فرعية من S عن طريق الجمع :
w (A) = ∑<sub>x∈A</sub> w(x)
لأي A ∈ S.