مشاكل البائع المتجول تلتزم بائع ومجموعة من المدن. يجب على البائع أن يزور كل مدينة بدءًا من مدينة معينة (على سبيل المثال، مسقط رأسه) ثم يعود إلى نفس المدينة. التحدي المتمثل في المشكلة هو أن البائع المتجول يحتاج إلى تقليل إجمالي طول الرحلة.

لنفترض أن المدن هي x₁س₂..... س_نحيث التكلفة ج_{اي جاي}يدل على تكلفة السفر من المدينة x_أناإلى العاشر_ي. تتمثل مشكلة البائع المتجول في العثور على طريق يبدأ وينتهي عند x₁والتي سوف تأخذ في جميع المدن بأقل تكلفة.

الهاشماب في جافا

مثال: يقوم وكيل الصحف بإسقاط الصحيفة يوميًا إلى المنطقة المخصصة بحيث يتعين عليه تغطية جميع المنازل في المنطقة المعنية بأقل تكلفة سفر. حساب الحد الأدنى لتكلفة السفر.

المنطقة المخصصة للوكيل حيث يجب عليه إسقاط الصحيفة موضحة في الشكل:

الحل: مصفوفة التكلفة المجاورة للرسم البياني G هي كما يلي:

نوع سريع

يكلف_{اي جاي}=

تبدأ الجولة من منطقة H₁ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H₁.

منطقة العلامة H₆لأنها أقل منطقة تكلفة يمكن الوصول إليها من H₁ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H₆.

منطقة العلامة H₇لأنها أقل منطقة تكلفة يمكن الوصول إليها من H₆ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H₇.

وظائف في ج

منطقة العلامة H₈لأنها أقل منطقة تكلفة يمكن الوصول إليها من H₈.

منطقة العلامة H₅لأنها أقل منطقة تكلفة يمكن الوصول إليها من H₅.

منطقة العلامة H₂لأنها أقل منطقة تكلفة يمكن الوصول إليها من H₂.

منطقة العلامة H₃لأنها أقل منطقة تكلفة يمكن الوصول إليها من H₃.

منطقة العلامة H₄ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H₄إنه ح₁لذلك، باستخدام استراتيجية الجشع، نحصل على ما يلي.

آلة جافا الافتراضية

 4 3 2 4 3 2 1 6 H<sub>1</sub> &#x2192; H<sub>6</sub> &#x2192; H<sub>7</sub> &#x2192; H<sub>8</sub> &#x2192; H<sub>5</sub> &#x2192; H<sub>2</sub> &#x2192; H<sub>3</sub> &#x2192; H<sub>4</sub> &#x2192; <sub>H<sub>1</sub></sub>. 

وبالتالي فإن الحد الأدنى لتكلفة السفر = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25

ماتريدس:

الماتويد هو زوج مرتب M(S,I) يحقق الشروط التالية:

1. S هي مجموعة محدودة.
2. I هي عائلة غير فارغة من مجموعات فرعية من S، تسمى المجموعات الفرعية المستقلة من S، بحيث إذا كانت B ∈ I و A ∈ I. نقول إنني وراثي إذا استوفى هذه الخاصية. لاحظ أن المجموعة الفارغة ∅ هي بالضرورة عضو في المجموعة I.
3. إذا كانت 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) = &#x2211;<sub>x&#x2208;A</sub> w(x) 

لأي A ∈ S.