Geekly articles weekly

اختصاصيو تكنولوجيا المعلومات يمشون على طرق غير ممهدة

بعد عقود من الركود ، تم العثور على اختصارات جديدة لمشكلة البائع المتجول.


الصورة

منذ وقت ليس ببعيد ، حطم فريق من الباحثين من جامعة ستانفورد وجامعة ماكجيل الرقم القياسي لعلوم الكمبيوتر لمدة 35 عامًا بكمية صغيرة لا يمكن تصورها - بأربعة مائة من تريليون تريليون من المئة في المئة. كان الاختراق - وهو مشكلة بائع في مشكلة كلاسيكيات علوم الكمبيوتر - صغيرًا جدًا بالنسبة لأي قيمة عملية ، لكنه تنفس حياة جديدة بحثًا عن حلول تقريبية محسنة.

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

من السهل صياغة مشكلة البائع ، ومن الناحية النظرية - من السهل حلها عن طريق التحقق من جميع المسارات المغلقة الممكنة للعثور على الأقصر. تكمن مشكلة نهج القوة الغاشمة في أنه عندما ينمو عدد المدن ، يبدأ العدد المقابل من المسارات بسرعة كبيرة في تجاوز قدرات أجهزة الكمبيوتر الأسرع. لعشر مدن ، هناك أكثر من 300000 طريق. في 15 مدينة ، يرتفع عددهم إلى 87 مليار نسمة.

خوارزمية كريستوفيدس


في عصر الكمبيوتر المبكر ، كان علماء الرياضيات يأملون أن يجد شخص ما نهجًا مناسبًا للمشكلة - خوارزمية تسمح بحلها في وقت معقول. ولكن على الرغم من أن المبرمجين حققوا تقدمًا في حالات محددة - تحديد أقصر مسار لـ 49 مدينة في الخمسينيات ، و 2392 مدينة في الثمانينيات ، و 85900 مدينة في عام 2006 - لم يقترح أحد خوارزمية تحل المشكلة بشكل فعال في الحالة العامة. وفقًا للعمل الرائع لعام 1972 ، من الممكن ألا توجد مثل هذه الخوارزمية على الإطلاق. أظهر عالم الكمبيوتر ريتشارد كارب من جامعة كاليفورنيا في بيركلي أن مشكلة البائع هي NP-Complete ، مما يعني عدم وجود خوارزمية فعالة (ما لم يثبت أي شخص أن P = NP - ولكن معظم العلماء يعتقدون أن هذا ليس كذلك) .

الصورة
أقصر طريق عبر 13509 مدينة في الولايات المتحدة التي يبلغ عدد سكانها أكثر من 500 (وفقًا لبيانات عام 1998)

بعد نشر Karp ، بدأ العديد من علماء الكمبيوتر في تطوير خوارزمية فعالة لإيجاد حلول تقريبية للمشكلة - المسارات المغلقة التي يزيد طولها قليلاً قليلاً عن الأقصر. وهنا كانوا أكثر حظًا - في عام 1976 ، قام نيكوس كريستوفيدس ، الأستاذ في إمبريال كوليدج لندن ، بتطوير خوارزمية تنتج مسارات مضمونة بألا تتجاوز أقصر مسار بأكثر من 50 ٪.

بعد إنشائها ، قرر العديد من العلماء أن هذه الخوارزمية ، التي هي بسيطة بما يكفي للطلاب للدراسة في ساعة واحدة ، ستصبح رابطًا وسيطًا ، وبعد ذلك سيتم العثور على حل حقيقي أكثر تعقيدًا وتقريبًا. ولكن بعد عقود ، لم تظهر مثل هذه الخوارزميات أبدًا.

قال سانجيف أرورا ، عالم في جامعة برينستون: "قضى جميع طلاب علوم الكمبيوتر تقريبًا أسابيع أو أشهر في محاولة تحسين خوارزمية كريستوفيدس".

أخيرًا ، في عام 2011 ، تجاوز فريق ستانفورد وماكجيل ضمان 50 ٪ لأنواع معينة من مهام البائع وأظهروا أن حلولهم ستتجاوز أقصر مسار بما لا يزيد عن 49.99999999999999999999999999999999999999999999999696٪.

منذ ذلك الحين ، ظهر عدد من الخوارزميات التقريبية المحسنة ، وذلك بفضل نظرة جديدة على المشكلة. على الرغم من أن هذه التقريبات تنطبق فقط على أنواع معينة من مهام البائع المتجول ، إلا أن نهجهم واعد جدًا ، وفقًا لمايكل جومانز ، اختصاصي تكنولوجيا المعلومات في معهد ماساتشوستس للتكنولوجيا.

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

أقصر شجرة


الصورة
الموناليزا كمسار بين 100.000 مدينة

لا تبدأ خوارزمية Christofides بالبحث عن أقصر مسار ، ولكن بالبحث عن الحد الأدنى من الشجرة الممتدة - مجموعة من الفروع التي تربط المدن بدون حلقات مغلقة. على عكس المسار الأقصر ، من السهل جدًا بناء شجرة الامتداد - تحتاج إلى البدء من خلال البحث عن أقصر مسار بين المدينتين ؛ سيكون هذا الفرع الأول. لإضافة ما يلي ، تحتاج إلى العثور على أقصر مسار بين المدينة الجديدة وواحدة من المدينتين السابقتين - وهكذا ، حتى يتم تغطية جميع المدن.

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

لكن المسار الناتج في أسوأ الحالات لم يعد أطول من أقصر مسار مرتين. من خلال إضافة فروع مختارة خصيصًا وتطبيق بعض الحيل ، أظهر Christofides كيفية قطع هذا المسار بحيث لا يتجاوز أقصره بنسبة تزيد عن 50 ٪.

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

لذا كان الهدف هو العثور على شجرة تحقق التوازن بين الطول والتحويل البسيط إلى الحل البديل. لا توجد خوارزميات فعالة للبحث عن شجرة مثالية (إذا كانت P = NP غير صحيحة) ، ولكن الخوارزمية التقريبية الناجحة تحتاج إلى العثور على ما يكفي فقط.

رحلة كسرية


تضمن الطريق إلى شجرة "جيدة إلى حد معقول" تقنية شائعة ، وإن كانت مضادة للحدس ، تعرف على الحلول الجزئية لمهام محددة. على سبيل المثال ، قد يشمل الحل الجزئي السفر في منتصف الطريق بين مينيابوليس وديترويت ، وفي منتصف الطريق بين كليفلاند وديترويت. من وجهة نظر عملية ، هذا المسار لا معنى له. ولكن يمكن وصفها رياضياً بدقة ، وعلى عكس مشكلة البائع المتجول الكلاسيكي ، يمكن حل مثل هذه النسخة الجزئية بكفاءة.

يمكن حل العديد من مشاكل التقريب في علوم الكمبيوتر عن طريق حساب الحلول للإصدار الجزئي للمشكلة ، ثم تقريب المشاركات بذكاء للحصول على حل تقريبي للمشكلة الأصلية. ولكن حتى وقت قريب ، لم يكن أحد قد اكتشف حتى الآن كيفية القيام بذلك في حالة مشكلة البائع المتجول.

في عام 2009 ، طور أمين صابري من جامعة ستانفورد وأراش أسدبور ، الذي كان آنذاك طالب دراسات عليا ، مخططًا تقريبًا مشتركًا يستخدم أرقامًا عشوائية لتحديد حل صحيح يحافظ على أكبر عدد ممكن من خصائص الحل الكسري. يعتقد صابري أن هذا النمط يذكرنا بـ "مطرقة ثقيلة بحثًا عن مسمار". وشتبه في أن مهمة البائع قد تكون المسمار الصحيح.

بعد بضعة أشهر ، أظهر صابر وأسبادور وغومانز وطالب خريج ستانفورد شايان غاران وألكسندر مادري ، الذين يعملون الآن في مدرسة لوزان البوليتكنيك الفيدرالية في سويسرا ، أن تقنية التقريب الجديدة يمكن أن توفر خوارزمية تقريبية جيدة لأحد الخيارات مهام البائع ، حالة "غير المتكافئة". بعد ذلك بعام ، استخدم صابري وجاران وموهيت سينغ من جامعة ماكجيل نفس النهج لتطوير خوارزمية تقريبية جديدة لمشكلة البائع المتجول المعتاد.

الصورة
كانت أكبر مشكلة مشكلة بالنسبة للبائع المتجول هو المسار بين 85900 مدينة ، محسوبة في عام 2006. يتطابق موقع "المدن" مع تصميم شريحة كمبيوتر محددة تم إنشاؤها في مختبر بيل ، والحل هو أقصر طريقة لقصها بالليزر

بعد الحصول على خريطة للمدن والطرق ، تبدأ الخوارزمية الجديدة بحساب الحل الجزئي الدقيق لمشكلة البائع المتجول. ثم يقوم بتقريب هذا الحل إلى شجرة ممتدة ، والتي من الناحية النظرية يجب أن تقترب من التوازن بين الطول والتحويل البسيط إلى الحل البديل. أخيرًا ، تتضمن الخوارزمية هذه الشجرة - وليس الحد الأدنى من الشجرة الممتدة - في شبكة Christofides.

يقول صابري إن الخوارزمية الجديدة كانت "فكرة يمكننا شرحها في غضون ساعتين ، لكن برهانها استغرق حوالي عام".

بعد تحليل طويل ، تمكن فريق ستانفورد / ماكجيل من تحسين خوارزمية كريستوفيدز بجزء صغير لفئة فرعية واسعة من مهام البائع ، "الرسم". بعد بضعة أشهر ، استخدمت فرق أخرى ، مستوحاة من النجاح ، مخططات التقريب الأخرى للحصول على خوارزميات للحالة الرسومية مع تقريب أفضل. الرقم القياسي الحالي هو 40 ٪ ، وهو أفضل بكثير من 50 ٪ من Christofides.

يقول أرورا إن الحالة الرسومية "تتضمن العديد من الصعوبات نفسها التي تمت مواجهتها في المشكلة العامة" ، مضيفًا أن المخططات التي تعمل في الحالة الرسومية يمكن أن تكون مفيدة أيضًا لمشكلة البائع المتجول العام.

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

Source: https://habr.com/ru/post/ar399873/

More articles:


All Articles