🚚 البائع الذي لا ينام أبدًا
على بائع متجول أن يزور 50 مدينة، كل واحدة مرة واحدة بالضبط، ثم يعود إلى نقطة الانطلاق. السؤال : بأي ترتيب يزورها لكي يقلّص المسافة الإجمالية المقطوعة إلى أدنى حد ؟
بالنسبة إلى 5 مدن، الأمر سهل : هناك 4!/2 = 12 مسارًا ممكنًا، نجربها كلها، ونختار الأقصر. بالنسبة إلى 10 مدن : 9!/2 = 181 440 مسارًا. لا يزال قابلًا للمعالجة من طرف حاسوب.
بالنسبة إلى 50 مدينة : 49!/2 ≈ 3 × 10⁶² مسارًا ممكنًا. عدد أكبر من عدد الذرات في درب التبانة. لا يستطيع أي حاسوب، حتى باستعمال جميع حواسيب الكوكب، إحصاءها في زمن معقول.
🎛️ العب بالمسألة
انقر لإضافة مدن. قارن الخوارزمية الجشعة (سريعة لكن دون المثلى) مع تحسين حقيقي بالبحث المحلي (بطيء لكن أفضل).
🎛️ TSP تفاعلي
انقر على اللوحة لإضافة مدينة. قارن الجشعة مع البحث المحلي.
المدن
0
المسافة الإجمالية
—
📐 التعقيد الخوارزمي
- القوة الغاشمة : O((n−1)!/2) — تنفجر بسرعة (50 مدينة = 3·10⁶² مسارًا)
- البرمجة الديناميكية : O(n² · 2ⁿ) — أفضل، لكنها محدودة بـ ~25 مدينة عمليًا
- الجشعة (أقرب جار) : O(n²) — سريعة جدًا، لكنها قد تعطي نتيجة أطول من المثلى بنسبة تصل إلى 25%
- 2-opt (البحث المحلي) : O(n³) لكل تكرار — حل وسط جيد
- الخوارزميات الحديثة (LKH، Concorde) : يمكنها حل حالات تضم عدة آلاف من المدن في بضع ساعات
💰 P في مقابل NP : المسألة بمليون دولار
ينتمي بائع متجول إلى عائلة من المسائل تسمى NP-تامة. الخاصية المشتركة :
- التحقق من أن حلًا معطى صحيح هو أمر سريع (زمن متعدد الحدود)
- إيجاد حل أمثل يبدو أنه يتطلب زمنًا أسيًا
السؤال الجوهري : هل توجد خوارزمية متعددة الحدود لحل المسائل NP-تامة ؟ بالترميز النظري : P = NP ؟
🚀 الاستدلالات (heuristiques) الحديثة
حتى بدون حل دقيق، لدينا تقنيات لـالاقتراب من المثلى :
- التلدين المحاكى : مستوحى من تبريد المعادن. يقبل أحيانًا حلولًا أقل جودة للهروب من المثليات المحلية.
- الخوارزميات الجينية : تحاكي التطور البيولوجي. تهجين وطفرة «الجولات».
- مستعمرات النمل : تحاكي إيداع الفيرومونات من طرف نملات افتراضية.
- التفريع والتقييد (Branch and bound) : تقلّم شجرة الإمكانيات بذكاء.
🌍 تطبيقات واقعية
مسألة بائع متجول ليست مجرد أحجية نظرية. بأشكال متنوعة، نجدها في كل مكان :
- اللوجستيك : جولات أمازون، البريد، موصِّلو Uber Eats
- الصناعة : تحسين سلاسل الإنتاج، تثقيب الدارات المطبوعة
- الروبوتيك : تخطيط مسارات الروبوتات المكنسة، طائرات المراقبة المسيّرة
- البيولوجيا : تسلسل الحمض النووي (مسألة تجميع الأجزاء)
- الفلك : ترتيب رصد أهداف تلسكوب
🎓 الرابط مع المقرر
مسألة بائع متجول ليست في مقرر البكالوريا علوم رياضية، لكن المفاهيم في المتناول :
- التعداد (مفهوم أطلس «التعداد») : (n−1)!/2 مسارًا ممكنًا لـ n مدينة
- المتتاليات العاملية : نمو أسرع من الأسي
- المبيانات (الخطوط) : المدن هي الرؤوس، والطرق هي الحواف المثقّلة
- الأمثلة (l'optimisation) : البحث عن قيمة دنيا لدالة (المسافة الإجمالية) على مجموعة منتهية لكن ضخمة
🧠 تأمل أخير
تعلمنا مسألة بائع متجول أمرًا مهمًا : بعض المسائل الرياضية تقاوم القوة الغاشمة. يمكن أن تمتلك حواسيب عملاقة فائقة القوة، وذكاءات اصطناعية هائلة — وتبقى أسئلة حيث يسحق فيها التعقيد التوافقي كل شيء.
إنها أيضًا مقدمة رائعة للتفكير المعلوماتي الحديث : بدلًا من البحث عن الحل المثالي، نبحث عن حلول وسط ذكية. نتيجة جيدة + زمن معقول > نتيجة مثالية + زمن لانهائي.