طول الجولة
أقصر ما وُجد
الخطوات
الجولات الممكنة
  • الجولة
  • أقصر ما وُجد
  • البداية

الطريقة الطول الزيادة عن الأقصر الخطوات
- - -
- - -
- - -
- - -
- - -

مزيد عن مسألة البائع المتجول

مسألة البائع المتجول

على بائع متجول أن يزور كل مدينة مرة واحدة ثم يعود إلى بيته. فبأي ترتيب تكون الرحلة أقصر؟ السؤال سهل الطرح، لكن مع ازدياد عدد المدن يصبح الجواب عنه بتجربة كل ترتيب أمرًا ميؤوسًا منه: 30 مدينة وحدها تسمح بنحو 4.4 × 10³⁰ جولة. انثر المدن على خريطة أو انقر لتضعها بنفسك، ثم شاهد قواعد تقريبية سريعة وتحسينات بارعة وطريقة دقيقة واحدة تبني جولاتها خطوة بخطوة، وانظر إلى أي حد تقترب الطرق السريعة. اختر طريقة توزيع المدن وعددها، ثم اختر طريقة حل واضغط «حلّ» لتشاهدها تبني جولة مغلقة خطوة بخطوة، أو «خطوة» للتقدم حركة واحدة في كل مرة. انقر على الخريطة لإضافة مدينة، أو انقر على مدينة لحذفها. يشغّل «قارن الكل» كل الطرق على المدن نفسها ويبيّن مدى ابتعاد كل منها عن أقصر جولة وُجدت. المدينة الحمراء هي نقطة بداية الرحلة.

كيف يعمل

  1. اختر توزيعًا وعدد المدن، أو انقر على الخريطة لتضع مدنك بنفسك، وانقر على مدينة لحذفها.
  2. اختر طريقة واضغط «حلّ» لتشاهدها خطوة بخطوة، أو «خطوة» للتقدم حركة واحدة في كل مرة.
  3. اضغط «قارن الكل» لتشغيل كل الطرق على المدن نفسها، واقرأ كم تزيد كل جولة على أقصر جولة وُجدت.

لماذا هي صعبة

إذا كان عدد المدن n فهناك (n − 1)! / 2 جولة مختلفة، لأنه لا يهم من أين تبدأ ولا في أي اتجاه تدور. وهذا يعني 12 جولة لـ 5 مدن، و181,440 لـ 10، ونحو 6 × 10¹⁶ لـ 20. لا تُعرف طريقة تجد أقصر رحلة لكل خريطة في زمن لا ينمو إلا كقوة لـ n؛ فالمسألة NP-صعبة. وأفضل طريقة دقيقة في هذا التطبيق، وهي البرمجة الديناميكية لهيلد–كارب من عام 1962، لا تزال تحتاج إلى نحو n² · 2ⁿ خطوة، لذا تقتصر هنا على 12 مدينة.

جولات جيدة بسرعة

عمليًا، يمكن إيجاد جولات قريبة جدًا من الأقصر بسرعة. يتجه أقرب جار دائمًا إلى أقرب مدينة لم تُزر بعد، وينتهي عادةً بجولة تزيد بنحو 25% على أفضل جولة. أما الإدراج الأرخص فيُنمّي حلقة ويضيف إليها المدينة التي تمدّها بأقل قدر. ويأخذ 2-opt أي جولة ويواصل استبدال حافتين بحافتين أقصر، فيزيل بذلك كل تقاطع ويقترب عادةً إلى حدود 5% تقريبًا. ويُجري التلدين المحاكى حركات 2-opt عشوائية، وما دام «ساخنًا» يقبل بعض الحركات التي تطيل الجولة، فيستطيع أن يخرج من الطرق المسدودة قبل أن يستقر.

الأسئلة المتداولة

هل توجد صيغة لأقصر طريق؟

لا. أقصر جولة تعتمد على المواقع الدقيقة لكل المدن، ولا تُعرف طريقة تجدها لكل خريطة دون جهد ينمو أُسّيًا في أسوأ الحالات. ومع ذلك، تستطيع حلّالات دقيقة متخصصة مثل كونكورد (Concorde) أن تثبت الجولات المثلى لبضع مئات أو آلاف من المدن بالجمع بين البرمجة الخطية والتقليم البارع، وأكبر حالة حُلّت حلًا دقيقًا حتى الآن فيها 85,900 نقطة.

لماذا يزيل 2-opt كل تقاطع؟

إذا تقاطعت حافتان في جولة، فإن المدن الأربع التي تصل بينها تشكّل رباعيًا قطراه هاتان الحافتان. واستبدالهما بضلعين متقابلين من أضلاع الرباعي يكون دائمًا أقصر بحسب متباينة المثلث، ويعكس اتجاه جزء الجولة الواقع بينهما. ويواصل 2-opt إجراء هذه المبادلات حتى لا تفيد أي منها، لذا لا تتقاطع جولته النهائية مع نفسها أبدًا.

ما درجة الحرارة في التلدين المحاكى؟

إنها تتحكم في مدى استعداد الطريقة لقبول حركة تطيل الجولة. فالحركة التي تزيد الطول بمقدار d تُقبل باحتمال e^(−d/T). عند درجة حرارة T مرتفعة يُقبل كل شيء تقريبًا، مما يتيح للجولة الإفلات من ترتيب رديء؛ ومع انخفاض T تصبح الطريقة جشعة وتستقر. والاسم مأخوذ من تبريد المعدن ببطء لكي تجد ذراته ترتيبًا منخفض الطاقة.

لماذا تقتصر الطريقة الدقيقة على 12 مدينة؟

تخزّن خوارزمية هيلد–كارب أقصر مسار لكل مجموعة جزئية من المدن ولكل مدينة أخيرة ممكنة، أي نحو n · 2ⁿ عددًا، وتملأ كلًّا منها بـ n مقارنة. لـ 12 مدينة يعني ذلك بضع مئات الآلاف من الخطوات؛ ولـ 25 مدينة سيبلغ المليارات. ومع ذلك تبقى أسرع بكثير من تجربة كل الجولات البالغ عددها (n − 1)! / 2: فلـ 12 مدينة سيكون عددها قرابة 20 مليونًا.

هل يُرسل أي شيء إلى خادم؟

لا. المدن والطرق الخمس كلها تعمل في متصفحك. والمدن التي تضعها بالنقر تبقى في التخزين المحلي لهذا المتصفح.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

الانتقال إلى المحرر