مشكلة مندوبي المبيعات المتنقلين
مشاكل البائع المتجول تلتزم بائع ومجموعة من المدن. يجب على البائع أن يزور كل مدينة بدءًا من مدينة معينة (على سبيل المثال، مسقط رأسه) ثم يعود إلى نفس المدينة. التحدي المتمثل في المشكلة هو أن البائع المتجول يحتاج إلى تقليل إجمالي طول الرحلة.
لنفترض أن المدن هي x 1 س 2 ..... س ن حيث التكلفة ج اي جاي يدل على تكلفة السفر من المدينة x أنا إلى العاشر ي . تتمثل مشكلة البائع المتجول في العثور على طريق يبدأ وينتهي عند x 1 والتي سوف تأخذ في جميع المدن بأقل تكلفة.
مثال: يقوم وكيل الصحف بإسقاط الصحيفة يوميًا إلى المنطقة المخصصة بحيث يتعين عليه تغطية جميع المنازل في المنطقة المعنية بأقل تكلفة سفر. حساب الحد الأدنى لتكلفة السفر.
المنطقة المخصصة للوكيل حيث يجب عليه إسقاط الصحيفة موضحة في الشكل:
الحل: مصفوفة التكلفة المجاورة للرسم البياني G هي كما يلي:
يكلف اي جاي =
تبدأ الجولة من منطقة H 1 ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H 1 .
منطقة العلامة H 6 لأنها أقل منطقة تكلفة يمكن الوصول إليها من H 1 ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H 6 .
منطقة العلامة H 7 لأنها أقل منطقة تكلفة يمكن الوصول إليها من H 6 ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H 7 .
منطقة العلامة H 8 لأنها أقل منطقة تكلفة يمكن الوصول إليها من H 8 .
منطقة العلامة H 5 لأنها أقل منطقة تكلفة يمكن الوصول إليها من H 5 .
منطقة العلامة H 2 لأنها أقل منطقة تكلفة يمكن الوصول إليها من H 2 .
منطقة العلامة H 3 لأنها أقل منطقة تكلفة يمكن الوصول إليها من H 3 .
منطقة العلامة H 4 ثم حدد الحد الأدنى لمنطقة التكلفة التي يمكن الوصول إليها من H 4 إنه ح 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.
