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

بدايةً، مسألة البائع المُتجوِّل هي إحدى أهم المسائل في علم التعقيد الحسابي ونظرية المخططات، ونص المسألة هو: وصل تاجر إلى دولة فيها n مدينة ويريد البائع أن يزور كل مدينة في الدولة مرة واحدة فقط وبأقل وقت سفر بين المدن. بالرغم من بساطة عرض المسألة فقد تبين أن هذه المسألة هي إحدى المسائل التي لا يُعرف لها خوارزمية تحلها بسرعة، أي أنه إذا كان هناك فقط 50 مدينة حينها يتطلب الأمر أكثر من ألف عام لايجاد الحل ! وقد وجدت هذه المسألة طريقها لنظرية التعقيد الحسابي حين أدرجها كارب في قائمته ال-21 لمسائل NP كاملة. وفيما يلي تفاصيل أوسع عن ذلك.
: Subject to
توضيح:
من جانب آخر، لحل هذه المسألة الخطية يمكن استخدام أي وسيلة لحل المسائل الخطية على الاعداد الكاملة ولكن هذه الخوارزمية لا يمكن ان تحله بوقت حدودي إذ انه يوجد متغيرات و- قيود درجة (1+2) و قيود على طول المسارات (3) لذا فانه لا يمكن حلها بشكل مباشر ما يحتم علينا استخدام طرق أخرى.
: أفضل قيمة ل TSP وجدناها حتى اللحظة.
التفريع والتحديد(Branch and Bound)
كذلك، لتخفيف كمية القيود كانت هناك حاجة لتغيير هذه البرمجة الخطية واستبدالها بمسألة خطية أخرى مع كمية قيود اقل وقد كان هذا وسميت البرمجة الخطية MTZ على أسماء كاتبيها. وكان الحل باضافة متغيرات اضافية:
القيد الثاني يضمن ان كل معرف بشكل واحد ووحيد لكل حل ممكن.
ومن ناحية أخرى، يمكن استخدام هذه الوسيلة لحل مسألة البائع المتجول (TSP). في مجال البرمجة الرياضياتية يمكن النظر إلى هذه الوسيلة من الجهة التالية: اولا تخفيف بعض القيود ثم أخذ الناتج وحله بطريقة سريعة وجيدة. حينها جودة وسيلة فرق تسد تكون من كمية الحد الأقصى لكل مجموعة قيود نقصيها. اما بالنسبة لمسألة TSP بداية يمكن تخفيف قيود 3 وارجاء باقي القيود والتي تشكل معا مسألة التلائم (assignment problem) والتي يمكن حلها بشكل دقيق بوقت لذا فان القيمة السفلى لمسألة البائع المتجول هي مسألة التلائم سوف نستعمل هذه المسألة لنركب خوارزمية بطريقة فرق تسد:
سوف نستعمل الأمور التالية:
ملاحظات:
يمكن تقوية MTZ باضافة: بدل القيد الأول.
ومن جهة أخرى، : قيمة دالة الهدف لمسألة التلائم (AP) في الرأس h في شجرة البحث،
علاوةً على ذلك، من الواضح ان دالة الهدف هي مقياس لوزن الدائرة التي نريد ايجادها، وذلك لان كل يمكن ان يكون 1 أو 0 , أي ان ضلع يمكن ان تكون بالحل وبالتالي نضيف وزنها (وحينها ) أو يمكن الا يكون بالحل ثم بالتالي أي انه لن نحسب وزن الضلع.
كذلك، اما القيد 3 فهو يدعى «إلغاء المسارات الدائرية القصيرة» أي مسارات دائرية بطول اقل من n , وذلك لانه إذا كان هناك مسار دائري أقصر من n على مجموعة جزئية S من الرؤوس حينها سيحوي هذا المسار الدائري على اضلاع، وحينها القيد 3 لن يتحقق لذا لا يمكن ان نجد حلا أقصر من المرغوب به، وانتبه كذلك ان مسار دائري بطول 1 لا يمكن ان يكون حلا وذلك حسب قيود 1+2 (وبالتالي كذلك ل-n-1) لذا فانه مسموح وضع القيد:
وفي هذا السياق، تبين ان البرمجة الخطية MTZ اضعف من البرمجة الأولى لانه تم برهنة انه في بعض الحالات القيمة التي يمكن ان ينتجها MTZ تكون اقل منها في البرمجة الأولى.
في هذا الإطار، اما القيد الأخير فهو لبيان ان كل ضلع يمكن ان تكون بالحل الأمثل أو لا: إذا كان الضلع في الحل حينها يكون قيمة المتغير 1 وخلاف ذلك 0 .
وفي هذا السياق، القيد الأول منهما لضمان انه لا يوجد مسار دائري جزئي على المجموعات الجزئية: لذا فانه لا يوجد مسارات دائرية جزئية طولها اقل من n
في هذا الإطار، القيود (Constraints) في السطر 1+2 هي تحدد ان كل رأس (vertex) نستعمله مرة واحدة في الحل أي ان لكل رأس درجة الخروج ودرجة الدخول اليه على الأكثر 1 .
يمكن استبدال قيد 3 بالقيد التالي:
توضيحات:
NP كاملة
وفي السياق ذاته، لنفرض انه معطى معنا مُدخل لمسألة الدائرة الهاملتونية (HC) نريد ان نبني اختصار بوقت حدودي والمُدخل لمسألة HC هو مُخطط بحيث ان نبني مُدخل لمسألة TSP بالشكل التالي: نبني مُخطط G , بحيث ان مجموعة الرؤوس هي V اما مجموعة الأضلاع هي و إذا و-
ومن ناحية أخرى، في سائر الأحوال، وحينها المخطط G يحوي دائرة هاملتونية إذا وفقط إذا قيمة مُدخل TSP هي n
وفي هذا السياق، لقد تبين ان مسألة البائع المتجول هي مسألة كاملة بالنسبة ل-NP , بحيث انه يوجد دالة تحويل أو اختصار (reduction function) بين الحد الأدنى للدائرة الهاملتونية وهذه المسألة:
تسمى الدائرة التي نريدها دائرة هاملتونية
وفي السياق ذاته، في بعض المسائل سيتعين علينا أن نميز بين مصفوفة أطوال متناظرة أي: وبين مصفوفة غير متناظرة
خاصية غير الزامية للمصفوفة هي خاصية متباينة المثلث وهي:
علاوةً على ذلك، وهذه الخاصية تتبين في مسألة البائع المتجول الاقليدية أي عندما تكون الرؤوس نقاط في والاطوال بين الرؤوس أي اطوال الأضلاع هو البعد الاقليدي أي انه إذا حينها طول الضلع هو
كما حاول أن يبرهن أن
ومن ناحية أخرى، في عام 1954 اصدر فولكرسون وجونسون ودانتزيج مقال مهم في هذه المسألة وقد تطرقوا لخوارزميات لحل المسألة وقد أصبحت أساسية لاحقا في مسائل الاستمثال (combinatorial optimization)وقد استعملوا فيها المستويات القاطعة وبمساعدة البرمجة الخطية وطريقة السيمبلكس نجحوا في حل المسألة ل-49 ولاية. ولاحقا برهن كارب ان المسألة هي NP كاملة ومن حينها طور العلماء كثير من الطرق لحل المسألة بشكل مباشر مثل: البرمجة الخطية المختلطة وخوارزميات جينية...
وفي هذا الصدد، نرى أأن قريب جدا من مسألة البائع المتجول، وقد ذكر منجر هذه الصلة في سنة 1930 في أحد محاضراته وحسب الوثائق في البداية سأل منجر إذا ما نستطيع أن نستبدل بالحد الأدنى لشجرة ستاينير التي توصل X. وللمسألة الاقليدية تم إيجاد الحل في سنة 1933 .
ونجح ببرهنة مبرهنة أقوى:
علاوةً على ذلك، وفي عام 1940 ظهرت مقالات تدرس مسألة البائع المتجول في سياق مُختلف، ميلجرام في عام 1940 درس مسألة المسار الأقصر خلال مجموعة من النقاط في الفضاء المتري وقد درس هذه المسألة على مسطح جوردان الأدنى والتي تُغطي أي مجموعة من النقاط في الفضاء المتري وليست بالضرورة مجموعة نهائية والتي حينها المسار الأقصر قد لا يكون موجودا. اما فيجيس في نفس العام درس المسألة في مربع الوحدة وقد توصل فيربولونسكي إلى ان طوله اقل من
علاوةً على ذلك، وفي اخر الاربعينات وبداية الخمسينات ميلر فلود وقد كان في مؤسسة راند وهي مؤسسة بُحوث علمية حاول حلها بمساعدة علماء المؤسسة ولكن عبثا، وتم رصد جائزة لمن يساعد في حل المسألة (المسألة قد لا يوجد لها خوارزمية سريعة)
ومن ناحية أخرى، بين الأعوام 1930-1931 أمضى منجر في هارفرد كمحاضر زائر وفي أحد محاضراته بيَّن نتاجه التي عرضناها واحد الاقتراحات كانت من هاسلر ويتني وبعدها بعام ذكر هاسلر مسألة العبور على ال48 ولاية.
علاوةً على ذلك، وقد اعطى ماهلانوبيس حدود دنيا للطول المتوقع ل-n نقاط عشوائية وقد أكمل هذا البحث جيسين عام 1942 .
عندما هو الحد الأدنى للشجرة المتتدة في X .
صعوبة تقريب TSP
إضافةً إلى ذلك، برهان: لنفرض من اجل التناقض ان هناك خوارزمية حدودية تقرب TSP بمعامل سنسميه سوف نُري انه يمكن استخدام لكي نقرر مسألة المسار الدائري الهاملتوني (حينها NP=P).
ومن ناحية أخرى، لاحظ انه عندما نشعل الخوارزمية على المخطط 'G على الخوارزمية ان تعطينا جوابا على الأكثر في الحالة الأولى وفي الحالة الثانية جواب قيمته أكبر من لذا يمكن تقرير مسألة المسار الدائري الهاملتوني.
علاوةً على ذلك، 2- إذا G لا يوجد فيه مسار دائري هاملتوني حينها في 'G وزن حل مسألة البائع المتجول الأمثل هو أكثر من
من جهة ثانية، الفكرة المركزية هي اختصار مسألة المسار الهاملتوني الدائري لمسألة البائع المتجول أي انه باعطائنا G نريد بناء مخطط كامل مع اوزان 'G بحيث أنَّ:
وفي هذا الصدد، 1- إذا G يوجد فيه مسار دائري هاملتوني حينها في 'G وزن حل مسألة البائع المتجول الأمثل هو n .
إضافةً إلى ذلك، يمكن ان نرى انه إذا في G يوجد مسار دائري هاملتوني حينها وزن TSP في 'G هو n , اما إذا G لم يحوِ مسار دائري هاملتوني فعليه استخدام ضلع واحدة على الاقل وزنها لذا فان وزن TSP يكون أكثر من
من جانب آخر، والاختصار هو كالتالي: لكل ضلع من اضلاع G ضع وزن 1 , وكل الأضلاع ليست اضلاع ل-G وزنها هو وهذا سوف يكون 'G .
وفي السياق ذاته، نظرية: لكل دالة يمكن حسابها بوقت حدودي , مسألة البائع المتجول لا يمكن تقريبها بمعامل الا إذا NP=P .
نفذ الخطوات 4 حتى 6 لكل r=1,...,s
إضافةً إلى ذلك، الخطوة 4 : احسب حد أسفل ل- عن طريق تخفيض عامود وسطر من مصفوفة الأوزان وإذا أكمل للخطوة 5 خلاف هذا اعد الخطوة 4 عندما r=r+1 .
من جانب آخر، الخطوة 5 : حل المسألة الجزئية التي في وإذا عد إلى 4 عندما r=r+1 .
في هذا الإطار، الخطوة 6 : افحص إذا ما الحل الحالي يحوي على مسائل جزئية إذا كان كذلك ضع في الطابور خلاف هذا: احفظ المسار وإذا اذهب إلى 2 .
: قيمة سُفلى ل-
- مجموعة الأضلاع ضمن الحل في الرأس h من شجرة البحث
- مجموعة الأضلاع التي ليست ضمن الحل في الرأس h من شجرة البحث
- الخوارزمية:
ومن ناحية أخرى، الخطوة 3 : (تقسيم المسألة الجزئية) الحل الموجود في الرأس h هو حل غير جائز ويجب ازالته بتقسيم المسألة الحالية لمسائل متجاورة التي تتميز بالمجموعتين و- . وحتى نُنتج هذه التقسيمات، فليكن مسار دائري جزئي يحيث انه على الاقل s اضلاع لا تحويها لنفرض ان هذه الأضلاع هي: حسب الترتيب التي تظهر في المسار الجزئي وحينها انتج s مسائل جزئية عندما:
وعلى صعيد آخر، الخطوة 1 : (الابتداء) حصِّل على قيمة اولية ل- بمعنى ان نستعمل طريقة الحدس المهني (Heuristic) توصلنا للحل، ابدأ في الرأس 1 من شجرة البحث و: واحصل على بحل المسألة AP , إذا توقف: الحدس المهني يعطي الحل الأمثل. وإذا حل AP لا يحوي مسارات جزئية دائرية توقف لانه يعطي الحل الأمثل. خلاف هذا: ضع 1 في طابور
كذلك، الخطوة 2 : (اختيار الرأس (vertex)) إذا الطابور فارغ، توقف. خلاف هذا اختر رأس (vertex) من الطابور.
تعريف
وفي هذا الصدد، ليكن مخطوطا حيث تمثل V مجموعة الرؤوس (vertices) و-A مجموعة الأضلاع (edges). ولتكن مصفوفة الأوزان أو الأطوال أي أنه هو الوزن الذي على الضلع الذي بين i و- j أو طول الضلع. ومسألة البائع المتجول حينها تسأل إذا ما هناك دائرة تعبر في كل رأس مرة واحدة فقط حيث أن وزن الدائرة اقل ما يمكن؟
ملاحظات:
خوارزميات تقريب
في هذا الإطار، بالرغم من هذا فان مسألة البائع المتجول مع خاصية متباينة المثلثات (أو مسألة البائع المتجول المترية) يوجد لها خوارزميات تقرب الإجابة المثلى لذا سوف ننظر اولا لم لا يمكن تقريب TSP عمومًا ثم نقرب TSP مع خاصية متباينة المثلثات:
إضافةً إلى ذلك، وهي خوارزميات لا تعطي جواب دقيق ولكنها تعطينا جواب لنفرض انه S ونفرض انه *S هو الحل الأمثل حينها: , هو البعد عن الجواب الأمثل. للاسف لمسألة البائع المتجول لا يوجد خوارزميات تقريب سريعة الا إذا NP=P , وهذا لانه إذا كان هناك واحدا كهذا فهو حتما سوف يحل مسألة المسار الدائري الهاملتوني، والأسوأ من هذا انه حتى إذا سينتج عن هذا ان NP=P !
البرمجة الخطية
: Minimize
ومن جهة أخرى، طور فلكرسون وجونسون ودانتزيج هذه الطريقة وهي: لكل ضلع في المخطط نخصص متغير وهو 1 إذا وفقط إذا الضلع من ضمن الحل الأفضل للمسألة وقد كان تعريف مسألة البرمجة الخطية كالتالي:
تاريخ
وعلى صعيد آخر، تم الإشارة للمسألة للمرة الأولى في ألمانيا عام 1832 في كتاب «البائع المتجول الناجح» وكان كارل منجر هو أول رياضياتي كتب عن المسألة حيث أنه أراد حيث ان C هو مسطح بسيط في الفضاء المتري S وحسب التعريف هو:
وفي هذا الصدد، عندما القيم العُلية (supremum) نأخذها على كل اختيار على C حسب الترتيب الذي يضعه C, وما بينه منجر لحل هذه المسألة هو أننا نستطيع أن نفحص كل المجموعات الجزئية النهائية X ل-C أي وعندها نأخذ القيمة الدنيا لكل الترتيبات X . لذا عرف لكل مجموعة جزئية X, لفضاء متري S وهو طول المسار الأقصر الذي يمر من خلال، وقد برهن التالي:
مسائل TSP سهلة
وفي هذا السياق، إذا كان المخطط، G , شجرة أو مسار أو دائرة أو نجمة حينها كذلك يمكن حل المسألة بسهولة
إذا كانت مصفوفة الأطوال مصفوفة مثلثة عُلوية أي
وعلى صعيد آخر، نعرف مصفوفة C ان تكون صغيرة إذا: حينها إذا كانت مصفوفة الأطوال صغيرة يمكن حل المسألة بوقت
تقريب مسألة البائع المتجول المترية
- الخوارزمية:
- جد الشجرة الممتدة ذات الحد الأدنى (MST) ولنسمها T .
- ضاعف كل ضلع في T واحصل على مخطط اويلراني.
خوارزميات دقيقة لحل المسألة
وفي هذا الصدد، الحل المفهوم ضمنا وهو إنتاج كل المسارات الدائرية ثم اختيار الأفضل هو حل غير قابل للتشغيل بسرعة إذ ان تعقيده وإذا كان فقط n=60 حينها سيكون هنالك احتمالات أكثر من ان نستطيع ان ننتجها (حدود الطاقة الحسابية للبشر على مر العصور هو وهذا العدد اصغر بكثير من ) ولان الحل الجشع لا يمكن انتاجه بجودة عالية وسرعة ملائمة تم تطوير الكثير من الوسائل لحل المسألة وسنعدد بعضها:
جد مسار اويلراني
إضافةً إلى ذلك، اخرج المسار الذي رؤوس G حسب ترتيب ظهورها في . فلنسم المسائر الدائري الناتج C .
وفي السياق ذاته، يمكن البرهنة بأن معامل هذه الخوارزمية هو 2 . يمكن تحسين هذه النتيجة ل- باستخدام مسألة التلائم في المخططات والخوارزمية الناتجة تكون جدا مشابهة للموصفة اعلاه.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟