شرح مسألة البائع المتجول
أعطِ بائعًا متجولًا قائمة بالمدن واطلب منه أقصر رحلة تزور كلًّا منها مرة واحدة وتعود إلى البيت. يستطيع أي شخص أن يتحقق من طريق مقترح، ويستطيع أي شخص أن يحسّن طريقًا سيئًا بالنظر، ومع ذلك لا يعرف أحد طريقة سريعة تجد الأفضل دائمًا. لقد أصبحت مسألة البائع المتجول المثال المعياري للمسائل الصعبة، والطرق التي ابتُكرت لمعالجتها تُستخدم اليوم لتخطيط عمليات التوصيل وثقب لوحات الدوائر وتجميع الجينومات.
المسألة
تزور الجولة كل مدينة مرة واحدة بالضبط وتنتهي حيث بدأت؛ وطولها مجموع المسافات على طول الطريق. والمطلوب إيجاد أقصر جولة. في النسخة المعروضة هنا المسافات خطوط مستقيمة على خريطة، لذا لا يكون الذهاب من A إلى C أطول أبدًا من المرور عبر B: هذه هي مسألة البائع المتجول المترية. ناقش عالم الرياضيات كارل منغر (Karl Menger) هذا اللغز نحو عام 1930، وشاع الاسم في العقود التالية حين تناول رياضيو مؤسسة راند (RAND Corporation) المسألة.
انفجار عدد الطرق
ثبّت مدينة البداية. هناك n − 1 خيارًا للمدينة التالية، وn − 2 للتي بعدها، وهكذا، ويمكن قطع كل جولة في اتجاهين، فيكون عدد الجولات (n − 1)! / 2. لـ 10 مدن يبلغ ذلك 181,440، وهو أمر سهل على الحاسوب. ولـ 20 مدينة يبلغ نحو 6 × 10¹⁶، ولـ 70 مدينة يتجاوز عدد الذرات في الكون المرئي. ولا تفيد الحواسيب الأسرع كثيرًا: فكل مدينة إضافية تضاعف العمل نحو n مرة.
NP-صعبة
في عام 1972 بيّن ريتشارد كارب (Richard Karp) أن السؤال عمّا إذا كان لمخطط جولة تمر بكل رأس، أي دورة هاملتونية، ينتمي إلى عائلة من المسائل NP-التامة التي تتساوى كلها في الصعوبة. ومسألة البائع المتجول تتضمن هذا السؤال، لذا فهي NP-صعبة. ولو وُجدت طريقة سريعة لحلها لأعطت طرقًا سريعة لآلاف المسائل الأخرى في الجدولة واللوجستيات والتشفير. وما إذا كانت مثل هذه الطريقة موجودة هو سؤال P مقابل NP، أحد مسائل جائزة الألفية.
طريقة دقيقة: هيلد–كارب
في عام 1962 استخدم مايكل هيلد (Michael Held) وريتشارد كارب البرمجة الديناميكية، وكذلك فعل ريتشارد بيلمان (Richard Bellman) بشكل مستقل. لكل مجموعة S من المدن ولكل مدينة j في S، احسب أقصر مسار يبدأ من مدينة الانطلاق ويزور مدن S بالضبط وينتهي عند j. كل قيمة تُستنتج من قيم S من دون j، فيُملأ الجدول من المجموعات الصغيرة إلى الكبيرة، وتظهر أقصر جولة في النهاية. تحتاج الطريقة إلى نحو n² · 2ⁿ خطوة بدلًا من n!، وهو الفرق بين دقائق وعمر الكون عند 30 مدينة، لكنها مع ذلك تنمو أُسّيًا.
قواعد بناء سريعة
ينتقل أقرب جار دائمًا إلى أقرب مدينة لم تُزر بعد. إنه بسيط وسريع، لكنه يميل إلى ترك بضع مدن معزولة لا بد من جمعها في النهاية بالتفافات طويلة، لذا تكون جولاته عادةً أطول من الأفضل بنحو 25%. أما طرق الإدراج فتحافظ بدلًا من ذلك على حلقة مغلقة وتضيف المدن المتبقية واحدة تلو الأخرى حيث تكون كلفتها أقل. وفي عام 1976 وجد نيكوس كريستوفيدس (Nicos Christofides) طريقة بناء مضمونًا ألا تتجاوز 1.5 ضعف الأمثل على أي خريطة مترية، وهو حدّ صمد دون أن يُتجاوز تقريبًا لأكثر من أربعين عامًا.
تحسين الجولة: 2-opt
يبدأ البحث المحلي من أي جولة ويواصل إجراء تغييرات صغيرة تقصّرها. الحركة الكلاسيكية 2-opt تزيل حافتين وتعيد وصل القطعتين بالطريقة الأخرى، مما يعكس اتجاه الجزء الواقع بينهما. وكلما تقاطعت حافتان، تفك هذه الحركة تقاطعهما وتوفّر في الطول، لذا فإن الجولة التي لا يستطيع 2-opt تحسينها لا تتقاطع مع نفسها أبدًا. وعلى الخرائط العشوائية تزيد جولات 2-opt عادةً بنحو 5% على الأمثل. والحركات الأقوى التي تبادل ثلاث حواف، أو طريقة العمق المتغير التي وضعها لين وكيرنيغان عام 1973، تقترب أكثر.
التلدين المحاكى
قد يعلق البحث المحلي في جولة تزيدها كل حركة منفردة سوءًا، مع أن هناك جولة أفضل بكثير. والتلدين المحاكى، الذي طبّقه على هذه المسألة سكوت كيركباتريك (Scott Kirkpatrick) ودانيال جيلات (Daniel Gelatt) وماريو فيكي (Mario Vecchi) عام 1983، يستعير فكرته من علم المعادن: فهو يقبل الحركة الأسوأ باحتمال يتوقف على درجة حرارة تكون مرتفعة في البداية ثم تُخفَّض ببطء. في البداية تتجول الجولة بحرية؛ وفي النهاية لا تُقبل إلا التحسينات. ومع تبريد بطيء بما يكفي يجد جولات جيدة جدًا بموثوقية.
استكشفها بنفسك
افتح عرض البائع المتجول لتضع ما يصل إلى 200 مدينة عشوائيًا، أو على دائرة، أو في عناقيد، أو على شبكة، أو حيثما تنقر. شاهد أقرب جار يترك آخر مدنه معزولة، وانظر إلى 2-opt وهو يفك كل تقاطع، وتابع درجة حرارة التلدين المحاكى وهي تنخفض، ودع هيلد–كارب يثبت أقصر جولة لما يصل إلى 12 مدينة. ويشغّل «قارن الكل» كل الطرق على الخريطة نفسها ويبيّن كم تزيد كل جولة على أقصر جولة وُجدت.
الأسئلة المتداولة
أين تُستخدم مسألة البائع المتجول؟
حيثما يجب على شيء ما أن يزور أماكن كثيرة بترتيب فعّال: مسارات التوصيل والجمع، ومسار المثقب أو الليزر فوق لوحة دوائر، والترتيب الذي يرصد به تلسكوب النجوم، وترتيب انتقاء الطلبات في مستودع، ومع مسافات من نوع آخر، ترتيب الأجزاء عند تجميع تسلسل DNA.
ما أكبر مسألة حُلّت حلًا دقيقًا على الإطلاق؟
في عام 1954 أثبت جورج دانتزيغ (George Dantzig) وراي فولكرسون (Ray Fulkerson) وسيلمر جونسون (Selmer Johnson) أقصر جولة عبر 49 مدينة في الولايات المتحدة. وفي عام 2006 أثبت حلّال كونكورد (Concorde) الذي طوّره ديفيد أبلغيت (David Applegate) وروبرت بيكسبي (Robert Bixby) وفاشيك خفاتال (Vašek Chvátal) وويليام كوك (William Cook) الجولة المثلى عبر 85,900 نقطة مأخوذة من تصميم شريحة، بعد سنوات من وقت الحاسوب.
هل تخلو أقصر جولة دائمًا من التقاطعات؟
نعم، على خريطة مستوية بمسافات الخطوط المستقيمة. فلو تقاطعت حافتان، لأدى استبدالهما بضلعين من الرباعي الذي تشكلانه إلى تقصير الجولة، لذا لا يمكن لجولة متقاطعة أن تكون الأقصر.
هل تعطي الطرق الاستدلالية الجولة نفسها في كل مرة؟
أقرب جار والإدراج الأرخص و2-opt كما تُستخدم هنا طرق حتمية: فهي تعطي الجولة نفسها على المدن نفسها. أما التلدين المحاكى فيبدأ من جولة عشوائية ويُجري حركات عشوائية، لذا قد ينتهي تشغيلان بجولتين مختلفتين، تكونان عادةً بطولين متقاربين جدًا.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
افتح عرض البائع المتجول