مسألة البائع المتجول
مسألة البائع المتجول هي إحدى أهم المسائل في علم التعقيد الحسابي ونظرية المخططات، ونص المسألة هو : وصل تاجر إلى دولة فيها n مدينة ويريد البائع أن يزور كل مدينة في الدولة مرة واحدة فقط وبأقل وقت سفر بين المدن. بالرغم من بساطة عرض المسألة فقد تبين أن هذه المسألة هي أحد المسائل التي لا يُعرف لها خوارزمية تحلها بسرعة, أي أنه اذا كان هناك فقط 50 مدينة حينها يتطلب الأمر أكثر من ألف عام لايجاد الحل ! وقد وجدت هذه المسألة طريقها لنظرية التعقيد الحسابي حين أدرجها كارب في قائمته ال-21 لمسائل NP كاملة.
تم الإشارة للمسألة للمرة الأولى في ألمانيا عام 1832 في كتاب "البائع المتجول الناجح" وكان كارل منجر هو أول رياضياتي كتب عن المسألة حيث أنه أراد formula_1 حيث ان C هو مسطح بسيط في الفضاء المتري S وحسب التعريف هو :
عندما القيم العُلية(supremum) نأخذها على كل اختيار formula_2 على C حسب "الترتيب" الذي يضعه C, وما بينه منجر لحل هذه المسألة هو أننا نستطيع أن نفحص كل المجموعات الجزئية النهائية X ل-C اي formula_3 وعندها نأخذ القيمة الدنيا لكل الترتيبات X . لذا عرف لكل مجموعة جزئية X, لفضاء متري S formula_4 وهو طول المسار الأقصر الذي يمر من خلال , وقد برهن التالي :
كما حاول أن يبرهن أن formula_5
ونجح ببرهنة ميرهنة أقوى :
عندما formula_6 هو الحد الأدنى للشجرة المتتدة في X .
نرى أأن formula_7 قريب جدا من مسألة البائع المتجول, وقد ذكر منجر هذه الصلة في عام 1930 في أحد محاضراته وحسب الوثائق في البداية سأل منجر اذا ما نستطيع أن نستبدل formula_6 بالحد الأدنى لشجرة ستاينير التي توصل X. وللمسألة الاقليدية تم ايجاد الحل في عام 1933 .
بين الأعوام 1930-1931 امضى منجر في هارفرد كمحاضر زائر وفي أحد محاضراته بيَّن نتاجه التي عرضناها واحد الاقتراحات كانت من هاسلر ويتني وبعدها بعام ذكر هاسلر مسألة العبور على ال48 ولاية .
وفي عام 1940 ظهرت مقالات تدرس مسألة البائع المتجول في سياق مُختلف , ميلجرام في عام 1940 درس مسألة المسار الأقصر خلال مجموعة من النقاط في الفضاء المتري وقد درس هذه المسألة على مسطح جوردان الأدنى والتي تُغطي اي مجموعة من النقاط في الفضاء المتري وليست بالضرورة مجموعة نهائية والتي حينها المسار الأقصر قد لا يكون موجودا . اما فيجيس في نفس العام درس المسألة في مربع الوحدة وقد توصل فيربولونسكي إلى ان طوله اقل من formula_9
وقد اعطى ماهلانوبيس حدود دنيا للطول المتوقع ل-n نقاط عشوائية وقد اكمل هذا البحث جيسين عام 1942 .
وفي اخر الاربعينات وبداية الخمسينات ميلر فلود وقد كان في مؤسسة راند وهي مؤسسة بُحوث علمية حاول حلها بمساعدة علماء المؤسسة ولكن عبثا , وتم رصد جائزة لمن يساعد في حل المسألة(المسألة قد لا يوجد لها خوارزمية سريعة )
في عام 1954 اصدر فولكرسون وجونسون ودانتزيج مقال مهم في هذه المسألة وقد تطرقوا لخوارزميات لحل المسألة وقد اصبحت اساسية لاحقا في مسائل الاستمثال (combinatorial optimization )وقد استخدموا فيها المستويات القاطعة وبمساعدة البرمجة الخطية وطريقة السيمبلكس نجحوا في حل المسألة ل-49 ولاية . ولاحقا برهن كارب ان المسألة هي NP كاملة ومن حينها طور العلماء كثير من الطرق لحل المسألة بشكل مباشر مثل : البرمجة الخطية المختلطة وخوارزميات جينية ...
ليكن formula_10 مخطوطا حيث تمثل V مجموعة الرؤوس (vertices) و-A مجموعة الأضلاع (edges). ولتكن formula_11 مصفوفة الأوزان أو الأطوال أي أنه formula_12 هو الوزن الذي على الضلع الذي بين i و- j أو طول الضلع. ومسألة البائع المتجول حينها تسأل اذا ما هناك دائرة تعبر في كل رأس مرة واحدة فقط حيث أن وزن الدائرة اقل ما يمكن ؟
ملاحظات :
وهذه الخاصية تتبين في مسألة البائع المتجول الاقليدية اي عندما تكون الرؤوس نقاط في formula_16 والاطوال بين الرؤوس اي اطوال الأضلاع هو البعد الاقليدي اي انه اذا formula_17 حينها طول الضلع formula_18 هو formula_19
لقد تبين ان مسألة البائع المتجول هي مسألة كاملة بالنسبة ل-NP , بحيث انه يوجد دالة تحويل او اختصار (reduction function) بين الحد الأدنى للدائرة الهاملتونية وهذه المسألة :
لنفرض انه معطى معنا مُدخل لمسألة الدائرة الهاملتونية(HC) نريد ان نبني اختصار بوقت حدودي والمُدخل لمسألة HC هو مُخطط formula_10 بحيث ان formula_21 نبني مُدخل لمسألة TSP بالشكل التالي : نبني مُخطط G , بحيث ان مجموعة الرؤوس هي V اما مجموعة الأضلاع هي formula_22 و formula_23 اذا formula_24 و- formula_25
في سائر الأحوال , وحينها المخطط G يحوي دائرة هاملتونية اذا وفقط اذا قيمة مُدخل TSP هي n
الحل المفهوم ضمنا وهو انتاج كل المسارات الدائرية ثم اختيار الأفضل هو حل غير قابل للتشغيل بسرعة إذ ان تعقيده formula_29 واذا كان فقط n=60 حينها سيكون هنالك احتمالات أكثر من ان نستطيع ان ننتجها(حدود الطاقة الحسابية للبشر على مر العصور هو formula_30 وهذا العدد اصغر بكثير من formula_31) ولان الحل الجشع لا يمكن انتاجه بجودة عالية وسرعة ملائمة تم تطوير الكثير من الوسائل لحل المسألة وسنعدد بعضها :
طور فلكرسون وجونسون ودانتزيج هذه الطريقة وهي : لكل ضلع في المخطط نخصص متغير formula_32 وهو 1 اذا وفقط اذا الضلع من ضمن الحل الأفضل للمسألة وقد كان تعريف مسألة البرمجة الخطية كالتالي :
توضيحات :
لحل هذه المسألة الخطية يمكن استخدام اي وسيلة لحل المسائل الخطية على الاعداد الكاملة ولكن هذه الخوارزمية لا يمكن ان تحله بوقت حدودي إذ انه يوجد formula_39 متغيرات و-formula_40 قيود درجة (1+2) و formula_41 قيود على طول المسارات (3) لذا فانه لا يمكن حلها بشكل مباشر ما يحتم علينا استخدام طرق اخرى .
لتخفيف كمية القيود كانت هناك حاجة لتغيير هذه البرمجة الخطية واستبدالها بمسألة خطية اخرى مع كمية قيود اقل وقد كان هذا وسميت البرمجة الخطية MTZ على أسماء كاتبيها . وكان الحل باضافة متغيرات اضافية :توضيح :
ملاحظات :
يمكن استخدام هذه الوسيلة لحل مسألة البائع المتجول (TSP) . في مجال البرمجة الرياضياتية يمكن النظر إلى هذه الوسيلة من الجهة التالية: اولا تخفيف بعض القيود ثم اخذ الناتج وحله بطريقة سريعة وجيدة . حينها جودة وسيلة فرق تسد تكون من كمية الحد الأقصى لكل مجموعة قيود نقصيها . اما بالنسبة لمسألة TSP بداية يمكن تخفيف قيود 3 وارجاء باقي القيود والتي تشكل معا مسألة التلائم(assignment problem) والتي يمكن حلها بشكل دقيق بوقت formula_47 لذا فان القيمة السفلى لمسألة البائع المتجول هي مسألة التلائم سوف نستخدم هذه المسألة لنركب خوارزمية بطريقة فرق تسد :
سوف نستخدم الامور التالية :
الخوارزمية :
الخطوة 1 : (الابتداء) حصِّل على قيمة اولية ل-formula_48 بمعنى ان نستخدم طريقة الحدس المهني (Heuristic) توصلنا للحل , ابدأ في الرأس 1 من شجرة البحث و:formula_55 واحصل على formula_56 بحل المسألة AP , اذا formula_57 توقف: الحدس المهني يعطي الحل الأمثل . واذا حل AP لا يحوي مسارات جزئية دائرية توقف لانه يعطي الحل الأمثل . خلاف هذا : ضع 1 في طابور
الخطوة 2 : (اختيار الرأس (vertex)) اذا الطابور فارغ , توقف . خلاف هذا اختر رأس (vertex) من الطابور .
الخطوة 3 : (تقسيم المسألة الجزئية) الحل الموجود في الرأس h هو حل غير جائز ويجب ازالته بتقسيم المسألة الحالية لمسائل متجاورة formula_58 التي تتميز بالمجموعتين formula_59 و- formula_60 . وحتى نُنتج هذه التقسيمات , فليكن مسار دائري جزئي يحيث انه على الاقل s اضلاع لا تحويها formula_61 لنفرض ان هذه الأضلاع هي : formula_62 حسب الترتيب التي تظهر في المسار الجزئي وحينها انتج s مسائل جزئية عندما :
نفذ الخطوات 4 حتى 6 لكل r=1...,s
الخطوة 4 : احسب حد اسفل formula_63 ل-formula_64 عن طريق تخفيض عامود وسطر من مصفوفة الأوزان واذا formula_65 اكمل للخطوة 5 خلاف هذا اعد الخطوة 4 عندما r=r+1 .
الخطوة 5 : حل المسألة الجزئية التي في formula_66 واذا formula_67 عد إلى 4 عندما r=r+1 .
الخطوة 6 : افحص اذا ما الحل الحالي يحوي على مسائل جزئية اذا كان كذلك ضع formula_58 في الطابور خلاف هذا : formula_69 احفظ المسار واذا formula_70 اذهب إلى 2 .
وهي خوارزميات لا تعطي جواب دقيق ولكنها تعطينا جواب لنفرض انه S ونفرض انه *S هو الحل الأمثل حينها : formula_71,هو البعد عن الجواب الأمثل . للاسف لمسألة البائع المتجول لا يوجد خوارزميات تقريب سريعة الا اذا NP=P , وهذا لانه اذا كان هناك واحدا كهذا فهو حتما سوف يحل مسألة المسار الدائري الهاملتوني , والأسوأ من هذا انه حتى اذا formula_72 سينتج عن هذا ان NP=P !
بالرغم من هذا فان مسألة البائع المتجول مع خاصية متباينة المثلثات (او مسألة البائع المتجول المترية) يوجد لها خوارزميات تقرب الاجابة المثلى لذا سوف ننظر اولا لم لا يمكن تقريب TSP بشكل عام ثم نقرب TSP مع خاصية متباينة المثلثات :
نظرية : لكل دالة يمكن حسابها بوقت حدودي formula_73 , مسألة البائع المتجول لا يمكن تقريبها بمعامل formula_73 الا اذا NP=P .
برهان : لنفرض من اجل التناقض ان هناك خوارزمية حدودية تقرب TSP بمعامل formula_73 سنسميه formula_76 سوف نُري انه يمكن استخدام formula_76 لكي نقرر مسألة المسار الدائري الهاملتوني ( حينها NP=P ) .
الفكرة المركزية هي اختصار مسألة المسار الهاملتوني الدائري لمسألة البائع المتجول اي انه باعطائنا G نريد بناء مخطط كامل مع اوزان 'G بحيث أنَّ:
1- اذا G يوجد فيه مسار دائري هاملتوني حينها في 'G وزن حل مسألة البائع المتجول الأمثل هو n .
2- اذا G لا يوجد فيه مسار دائري هاملتوني حينها في 'G وزن حل مسألة البائع المتجول الأمثل هو أكثر من formula_78
لاحظ انه عندما نشعل الخوارزمية formula_76 على المخطط 'G على الخوارزمية ان تعطينا جوابا على الأكثر formula_78 في الحالة الاولى وفي الحالة الثانية جواب قيمته أكبر من formula_78 لذا يمكن تقرير مسألة المسار الدائري الهاملتوني .
والاختصار هو كالتالي : لكل ضلع من اضلاع G ضع وزن 1 , وكل الأضلاع ليست اضلاع ل-G وزنها هو formula_78 وهذا سوف يكون 'G .
يمكن ان نرى انه اذا في G يوجد مسار دائري هاملتوني حينها وزن TSP في 'G هو n , اما اذا G لم يحوِ مسار دائري هاملتوني فعليه استخدام ضلع واحدة على الاقل وزنها formula_78 لذا فان وزن TSP يكون أكثر من formula_78
الخوارزمية :يمكن البرهنة بأن معامل هذه الخوارزمية هو 2 . يمكن تحسين هذه النتيجة ل-formula_87 باستخدام مسألة التلائم في المخططات والخوارزمية الناتجة تكون جدا مشابهة للموصفة اعلاه.