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

مسألة البائع المتجول (بالإنجليزية: Travelling salesman problem) هي إحدى أهم المسائل في علم التعقيد الحسابي ونظرية المخططات، ونص المسألة هو : وصل تاجر إلى دولة فيها n مدينة ويريد البائع أن يزور كل مدينة في الدولة مرة واحدة فقط وبأقل وقت سفر بين المدن. بالرغم من بساطة عرض المسألة فقد تبين أن هذه المسألة هي أحد المسائل التي لا يُعرف لها خوارزمية تحلها بسرعة, أي أنه اذا كان هناك فقط 50 مدينة حينها يتطلب الأمر أكثر من ألف عام لايجاد الحل ! وقد وجدت هذه المسألة طريقها لنظرية التعقيد الحسابي حين أدرجها كارب في قائمته ال-21 لمسائل NP كاملة.

تاريخ

تم الإشارة للمسألة للمرة الأولى في ألمانيا عام 1832 في كتاب "البائع المتجول الناجح" وكان كارل منجر هو أول رياضياتي كتب عن المسألة حيث أنه أراد  حيث ان C هو مسطح بسيط في الفضاء المتري S وحسب التعريف هو :
عندما القيم العُلية(supremum) نأخذها على كل اختيار  على C حسب الترتيب الذي يضعه C, وما بينه منجر لحل هذه المسألة هو أننا نستطيع أن نفحص كل المجموعات الجزئية النهائية X ل-C اي  وعندها نأخذ القيمة الدنيا لكل الترتيبات X . لذا عرف لكل مجموعة جزئية X, لفضاء متري S  وهو طول المسار الأقصر الذي يمر من خلال , وقد برهن التالي :
كما حاول أن يبرهن أن 
ونجح ببرهنة ميرهنة أقوى :
عندما  هو الحد الأدنى للشجرة المتتدة في X .
نرى أأن  قريب جدا من مسألة البائع المتجول, وقد ذكر منجر هذه الصلة في عام 1930 في أحد محاضراته وحسب الوثائق في البداية سأل منجر اذا ما نستطيع أن نستبدل  بالحد الأدنى لشجرة ستاينير التي توصل X. وللمسألة الاقليدية تم ايجاد الحل في عام 1933 .
بين الأعوام 1930-1931 امضى منجر في هارفرد كمحاضر زائر وفي أحد محاضراته بيَّن نتاجه التي عرضناها واحد الاقتراحات كانت من هاسلر ويتني وبعدها بعام ذكر هاسلر مسألة العبور على ال48 ولاية .
وفي عام 1940 ظهرت مقالات تدرس مسألة البائع المتجول في سياق مُختلف , ميلجرام في عام 1940 درس مسألة المسار الأقصر خلال مجموعة من النقاط في الفضاء المتري وقد درس هذه المسألة على مسطح جوردان الأدنى والتي تُغطي اي مجموعة من النقاط في الفضاء المتري وليست بالضرورة مجموعة نهائية والتي حينها المسار الأقصر قد لا يكون موجودا . اما فيجيس في نفس العام درس المسألة في مربع الوحدة وقد توصل فيربولونسكي إلى ان طوله اقل من 
وقد اعطى ماهلانوبيس حدود دنيا للطول المتوقع ل-n نقاط عشوائية وقد اكمل هذا البحث جيسين عام 1942 .
وفي اخر الاربعينات وبداية الخمسينات ميلر فلود وقد كان في مؤسسة راند وهي مؤسسة بُحوث علمية حاول حلها بمساعدة علماء المؤسسة ولكن عبثا , وتم رصد جائزة لمن يساعد في حل المسألة(المسألة قد لا يوجد لها خوارزمية سريعة )
في عام 1954 اصدر فولكرسون وجونسون ودانتزيج مقال مهم في هذه المسألة وقد تطرقوا لخوارزميات لحل المسألة وقد اصبحت اساسية لاحقا في مسائل الاستمثال (combinatorial optimization )وقد استخدموا فيها المستويات القاطعة وبمساعدة البرمجة الخطية وطريقة السيمبلكس نجحوا في حل المسألة ل-49 ولاية . ولاحقا برهن كارب ان المسألة هي NP كاملة ومن حينها طور العلماء كثير من الطرق لحل المسألة بشكل مباشر مثل : البرمجة الخطية المختلطة وخوارزميات جينية ...

NP كاملة

لقد تبين ان مسألة البائع المتجول هي مسألة كاملة بالنسبة ل-NP , بحيث انه يوجد دالة تحويل او اختصار (reduction function) بين الحد الأدنى للدائرة الهاملتونية وهذه المسألة :
لنفرض انه معطى معنا مُدخل لمسألة الدائرة الهاملتونية(HC) نريد ان نبني اختصار بوقت حدودي والمُدخل لمسألة HC هو مُخطط  بحيث ان  نبني مُدخل لمسألة TSP بالشكل التالي : نبني مُخطط G , بحيث ان مجموعة الرؤوس هي V اما مجموعة الأضلاع هي  و  اذا  و- 
في سائر الأحوال , وحينها المخطط G يحوي دائرة هاملتونية اذا وفقط اذا قيمة مُدخل TSP هي n

خوارزميات دقيقة لحل المسألة

الحل المفهوم ضمنا وهو انتاج كل المسارات الدائرية ثم اختيار الأفضل هو حل غير قابل للتشغيل بسرعة إذ ان تعقيده  واذا كان فقط n=60 حينها سيكون هنالك احتمالات أكثر من ان نستطيع ان ننتجها(حدود الطاقة الحسابية للبشر على مر العصور هو  وهذا العدد اصغر بكثير من ) ولان الحل الجشع لا يمكن انتاجه بجودة عالية وسرعة ملائمة تم تطوير الكثير من الوسائل لحل المسألة وسنعدد بعضها :

خوارزميات تقريب

وهي خوارزميات لا تعطي جواب دقيق ولكنها تعطينا جواب لنفرض انه S ونفرض انه *S هو الحل الأمثل حينها : ,هو البعد عن الجواب الأمثل . للاسف لمسألة البائع المتجول لا يوجد خوارزميات تقريب سريعة الا اذا NP=P , وهذا لانه اذا كان هناك واحدا كهذا فهو حتما سوف يحل مسألة المسار الدائري الهاملتوني , والأسوأ من هذا انه حتى اذا  سينتج عن هذا ان NP=P !
بالرغم من هذا فان مسألة البائع المتجول مع خاصية متباينة المثلثات (او مسألة البائع المتجول المترية) يوجد لها خوارزميات تقرب الاجابة المثلى لذا سوف ننظر اولا لم لا يمكن تقريب TSP بشكل عام ثم نقرب TSP مع خاصية متباينة المثلثات :

صعوبة تقريب TSP

نظرية :  لكل دالة يمكن حسابها بوقت حدودي  , مسألة البائع المتجول لا يمكن تقريبها بمعامل  الا اذا NP=P .
برهان :  لنفرض من اجل التناقض ان هناك خوارزمية حدودية تقرب TSP بمعامل  سنسميه  سوف نُري انه يمكن استخدام  لكي نقرر مسألة المسار الدائري الهاملتوني ( حينها NP=P ) .
الفكرة المركزية هي اختصار مسألة المسار الهاملتوني الدائري لمسألة البائع المتجول اي انه باعطائنا G نريد بناء مخطط كامل مع اوزان 'G بحيث أنَّ:
1- اذا G يوجد فيه مسار دائري هاملتوني حينها في 'G وزن حل مسألة البائع المتجول الأمثل هو n .
2- اذا G لا يوجد فيه مسار دائري هاملتوني حينها في 'G وزن حل مسألة البائع المتجول الأمثل هو أكثر من 
لاحظ انه عندما نشعل الخوارزمية  على المخطط 'G على الخوارزمية ان تعطينا جوابا على الأكثر  في الحالة الاولى وفي الحالة الثانية جواب قيمته أكبر من  لذا يمكن تقرير مسألة المسار الدائري الهاملتوني .
والاختصار هو كالتالي : لكل ضلع من اضلاع G ضع وزن 1 , وكل الأضلاع ليست اضلاع ل-G وزنها هو  وهذا سوف يكون 'G .
يمكن ان نرى انه اذا في G يوجد مسار دائري هاملتوني حينها وزن TSP في 'G هو n , اما اذا G لم يحوِ مسار دائري هاملتوني فعليه استخدام ضلع واحدة على الاقل وزنها  لذا فان وزن TSP يكون أكثر من