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

🚚 البائع الذي لا ينام أبدًا

على بائع متجول أن يزور 50 مدينة، كل واحدة مرة واحدة بالضبط، ثم يعود إلى نقطة الانطلاق. السؤال : بأي ترتيب يزورها لكي يقلّص المسافة الإجمالية المقطوعة إلى أدنى حد ؟

بالنسبة إلى 5 مدن، الأمر سهل : هناك 4!/2 = 12 مسارًا ممكنًا، نجربها كلها، ونختار الأقصر. بالنسبة إلى 10 مدن : 9!/2 = 181 440 مسارًا. لا يزال قابلًا للمعالجة من طرف حاسوب.

بالنسبة إلى 50 مدينة : 49!/2 ≈ 3 × $1 0^{62}$ مسارًا ممكنًا. عدد أكبر من عدد الذرات في درب التبانة. لا يستطيع أي حاسوب، حتى باستعمال جميع حواسيب الكوكب، إحصاءها في زمن معقول.

🎛️ العب بالمسألة

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

🎛️ TSP تفاعلي

انقر على اللوحة لإضافة مدينة. قارن الجشعة مع البحث المحلي.

المدن

المسافة الإجمالية

—

📐 التعقيد الخوارزمي

القوة الغاشمة : O((n−1)!/2) — تنفجر بسرعة (50 مدينة = 3· $1 0^{62}$ مسارًا)
البرمجة الديناميكية : O( $n^{2}$ · $2^{n}$ ) — أفضل، لكنها محدودة بـ ~25 مدينة عمليًا
الجشعة (أقرب جار) : O( $n^{2}$ ) — سريعة جدًا، لكنها قد تعطي نتيجة أطول من المثلى بنسبة تصل إلى 25%
2-opt (البحث المحلي) : O( $n^{3}$ ) لكل تكرار — حل وسط جيد
الخوارزميات الحديثة (LKH، Concorde) : يمكنها حل حالات تضم عدة آلاف من المدن في بضع ساعات

💰 P في مقابل NP : المسألة بمليون دولار

ينتمي بائع متجول إلى عائلة من المسائل تسمى NP-تامة. الخاصية المشتركة :

التحقق من أن حلًا معطى صحيح هو أمر سريع (زمن متعدد الحدود)
إيجاد حل أمثل يبدو أنه يتطلب زمنًا أسيًا

السؤال الجوهري : هل توجد خوارزمية متعددة الحدود لحل المسائل NP-تامة ؟ بالترميز النظري : P = NP ؟

🚀 الاستدلالات (heuristiques) الحديثة

حتى بدون حل دقيق، لدينا تقنيات لـالاقتراب من المثلى :

التلدين المحاكى : مستوحى من تبريد المعادن. يقبل أحيانًا حلولًا أقل جودة للهروب من المثليات المحلية.
الخوارزميات الجينية : تحاكي التطور البيولوجي. تهجين وطفرة «الجولات».
مستعمرات النمل : تحاكي إيداع الفيرومونات من طرف نملات افتراضية.
التفريع والتقييد (Branch and bound) : تقلّم شجرة الإمكانيات بذكاء.

🌍 تطبيقات واقعية

مسألة بائع متجول ليست مجرد أحجية نظرية. بأشكال متنوعة، نجدها في كل مكان :

اللوجستيك : جولات أمازون، البريد، موصِّلو Uber Eats
الصناعة : تحسين سلاسل الإنتاج، تثقيب الدارات المطبوعة
الروبوتيك : تخطيط مسارات الروبوتات المكنسة، طائرات المراقبة المسيّرة
البيولوجيا : تسلسل الحمض النووي (مسألة تجميع الأجزاء)
الفلك : ترتيب رصد أهداف تلسكوب

🎓 الرابط مع المقرر

مسألة بائع متجول ليست في مقرر البكالوريا علوم رياضية، لكن المفاهيم في المتناول :

التعداد (مفهوم أطلس «التعداد») : (n−1)!/2 مسارًا ممكنًا لـ n مدينة
المتتاليات العاملية : نمو أسرع من الأسي
المبيانات (الخطوط) : المدن هي الرؤوس، والطرق هي الحواف المثقّلة
الأمثلة (l'optimisation) : البحث عن قيمة دنيا لدالة (المسافة الإجمالية) على مجموعة منتهية لكن ضخمة

🧠 تأمل أخير

تعلمنا مسألة بائع متجول أمرًا مهمًا : بعض المسائل الرياضية تقاوم القوة الغاشمة. يمكن أن تمتلك حواسيب عملاقة فائقة القوة، وذكاءات اصطناعية هائلة — وتبقى أسئلة حيث يسحق فيها التعقيد التوافقي كل شيء.

إنها أيضًا مقدمة رائعة للتفكير المعلوماتي الحديث : بدلًا من البحث عن الحل المثالي، نبحث عن حلول وسط ذكية. نتيجة جيدة + زمن معقول > نتيجة مثالية + زمن لانهائي.

🎯

تحقّق من فهمك

٣ أسئلة قصيرة للتأكد من مكتسباتك. يمكنك إعادة المحاولة.

← أطلس المفاهيم يُثرى الأطلس كل أسبوع