Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming
تقترح هذه الورقة خوارزميات ترشيح جديدة ضمن البرمجة المنطقية المقيدة تستفيد من المعلومات الهندسية من الإحداثيات الإقليدية لتحقيق انتشار قيود أقوى وتحسين الأداء الحسابي لمسألة البائع المتجول الإقليدية ومتغيراتها، مثل مسألة البائع المتجول المعممة.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تخيل أنك سائق توصيل ولديك خريطة مليئة بالنقاط التي يجب التوقف عندها. تريد زيارة كل نقطة بالضبط مرة واحدة والعودة إلى منزلك، لكنك تريد أيضاً حرق أقل كمية ممكنة من الوقود. هذه هي "مسألة البائع المتجول" الكلاسيكية، وهي لغز أذهل علماء الرياضيات وعلوم الحاسوب لعقود. الأمر لا يقتصر فقط على شاحنات التوصيل؛ بل يتعلق بكل شيء، من توجيه المركبات الذكية إلى تنظيم البيانات على رقاقة الكمبيوتر. الجزء الصعب هو أنه مع إضافة المزيد من التوقفات، ينفجر عدد المسارات الممكنة بسرعة كبيرة لدرجة أن حتى أسرع أجهزة الكمبيوتر في العالم يمكن أن تضيع في المتاهة.
لحل هذا، غالبًا ما تستخدم أجهزة الكمبيوتر طريقة تسمى "البرمجة بالقيود" (Constraint Programming). فكر في هذا الأمر كأنه محقق ذكي للغاية، لا يقوم بمجرد تخمين المسارات عشوائيًا، بل يضع مجموعة من القواعد (القيود) لاستبعاد الخيارات المستحيلة أو السخيفة فورًا. على سبيل المثال: "لا يمكنك زيارة نفس المدينة مرتين" أو "لا يمكنك القيادة في دائرة تتخطى بقية الرحلة". عادةً، عندما يتضمن الأمر مسافات على خريطة مسطحة (ما يسميه العلماء الحالة الإقليدية)، يعامل الكمبيوتر الخريطة كمجرد قائمة من الأرقام، متجاهلاً حقيقة أن التوقفات مرسومة في الواقع على ورقة بخطوط وزوايا مستقيمة. إنه يشبه محاولة التنقل في مدينة من خلال النظر فقط إلى قائمة بأسماء الشوارع، دون النظر أبدًا إلى الخريطة نفسها.
يسأل هذا البحث سؤالاً بسيطًا ولكنه قوي: ماذا لو توقفنا عن تجاهل الخريطة؟ قرر المؤلفان، أليساندرو بيرتانون وماركو غافانيلي، بناء مجموعة جديدة من "القواعد" لمحقق الكمبيوتر الخاص بهم تفهم الهندسة بالفعل. لقد أنشأا خوارزميات خاصة تدرك أنه في المسار المثالي والأقصر، لا ينبغي للطرق أن تتقاطع مثل حرف "X" في السماء، وأن الحافة الخارجية لمجموعة من النقاط يجب زيارتها بترتيب دائري منظم. من خلال تعليم الكمبيوتر "رؤية" شكل المشكلة، وجدا طريقة لقص ملايين التخمينات السيئة بشكل أسرع بكثير من ذي قبل. كما أظهرا أن هذه الحيل الهندسية تعمل حتى عندما تصبح المشكلة أكثر تعقيدًا، مثل عندما يتعين عليك زيارة مجموعة من المدن ولكن تحتاج فقط إلى التوقف في واحدة منها.
الاكتشاف الجوهري للورقة البحثية
الاكتشاف الرئيسي لهذا العمل هو أنه باستخدام الخصائص الهندسية المحددة لمسألة البائع المتجول (TSP) - وتحديدًا حقيقة أن المسار الأقصر على مستوٍ مسطح لا يتقاطع مع نفسه ويتبع الحافة الخارجية لشكل ما بترتيب معين - يمكن لأجهزة الكمبيوتر حل ألغاز التوجيه هذه بشكل أسرع بكثير. قام المؤلفان بتنفيذ هذه القواعد الجديدة في لغة برمجة تسمى "البرمجة المنطقية بالقيود" (CLP).
لقزا اختبار "الترشيح الهندسي" الجديد الخاص بهما مقابل أفضل الطرق الموجودة. كانت النتائج مذهلة: بالنسبة للخرائط العشوائية التي تحتوي على ما يصل إلى 100 نقطة، قلل نهجهما الجديد الوقت المستغرق للعثور على الحل الأمثل بنسبة 70% في المتوسط. ومن حيث "خطوات التفكير" للكمبيوتر (عقد البحث)، فقد قلصا العمل بنسبة تتراوح بين 59% إلى 75%، اعتمادًا على الاستراتيجية المستخدمة. وهذا يعني أن الكمبيوتر لم يكتفِ بالتفكير بشكل أسرع في كل خطوة فحسب، بل كان عليه التفكير في عدد أقل بكثير من الخطوات للوصقة إلى الإجابة.
ما الذي استبعدوه وكيف فعلوا ذلك
تجادل الورقة صراحة ضد النهج القياسي الذي يعامل مسائل TSP الإقليدية (حيث المسافات خطوط مستقيمة على مستوٍ) تمامًا مثل مسائل TSP العامة. الطريقة الشائعة هي حساب المسافة بين كل زوج من النقاط، وإنشاء جدول ضخم من الأرقام، ثم تطبيق قواعد عامة. يوضح المؤلفان أن هذا النهج "الأعمى" يتجاهل معلومات قيمة موجودة بالفعل: وهي إحداثيات النقاط. كما يوضحان أن تجاهل الهندسة يؤدي إلى مساحة بحث أكبر وحلول أبطأ.
كما يوضحان أيضًا ما لا يمثله منهجهما. فهما لا يدعيان حل مسألة TSP بشكل كامل أو إنشاء حل سحري يعمل لكل نوع من أنواع مشاكل التوجيه. على سبيل المثال، يشيران إلى أن قاعدة "عدم التقاطع" الخاصة بهما لا تنطبق على المشكلات التي يجب أن تتقاطع فيها الطرق، مثل شبكات المدن في العالم الحقيقي ذات الشوارع ذات الاتجاه الواحد أو الجسور، أو في المشكلات التي تتطلب نوافذ زمنية صارمة حيث قد يكون تغيير المسار ضروريًا. عملهما مخصص لـ "حالات إقليدية كاملة" حيث تكون النقاط على مستوٍ مسطح والتقاطعات يمكن تجنبها.
سحر "عدم التقاطع" و"الغلاف المحدب"
لجعل الكمبيوتر أكثر ذكاءً، قدم المؤلفان مفهومين هندسيين رئيسيين:
قاعدة عدم التقاطع: تخيل أنك ترسم حلقة باستخدام خيط يربط بين نقاط على طاولة. إذا تقاطع خيطك مع نفسه، يمكنك دائمًا شد الخيط بإحكام لجعل الحلقة أقصر وبدون تقاطعات. أثبت المؤلفان رياضياً أن المسار الأمثل (الأقصر) لن يحتوي أبدًا على خطوط متقاطعة. لقد بنيا "مرشحًا" خاصًا داخل برنامج الكمبيوتر يحذف فورًا أي خيار مسار قد يسبب تقاطعًا. هذا يشبه حارسًا عند ملهى ليلي يطرد فورًا أي شخص يحاول الدخول من الباب الخاطئ، مما يوفر على الحارس عناء فحص هويته لاحقًا.
ترتيب الغلاف المحدب: تخيل شد شريط مطاطي حول مجموعة من المسامير على لوحة. الشكل الذي يشكله الشريط المطاطي يسمى "الغلاف المحدب" (Convex Hull). أظهر المؤلفان أنه في أقصر مسار، يجب زيارة المسامير الموجودة على الحافة الخارجية لهذا الشريط المطاطي بترتيب معين (مع عقارب الساعة أو عكس اتجاه عقارب الساعة). لقد وضعا قواعد تجبر الكمبيوتر على احترام هذا الترتيد، مما يمنعه من إضاعة الوقت في فحص المسارات التي تتردد ذهابًا وإيابًا عبر الحافة.
توسيع السحر ليشمل مشكلات المجموعات
تتناول الورقة أيضًا نسخة أصعب من المشكلة تسمى "مسألة البائع المتجول المعممة" (GTSP). في هذه النسخة، بدلًا من زيارة كل مدينة بمفردها، يتعين عليك زيارة مجموعة من "العناقيد" (المجموعات)، ولكنك تحتاج فقط إلى التوقف في مدينة واحدة في كل مجموعة. هذا يشبه سائق التوصيل الذي يتعين عليه تسليم طرود في ثلاثة أحياء مختلفة، ولكنه يحتاج فقط إلى زيارة منزل واحد في كل حي.
أظهر المؤلفان أن قواعدهما الهندسية يمكن تكييفها لهذه المشكلة الأصعب أيضًا. فقد حددا "الجيران" بناءً على هندسة العناقيد وطبقا نفس منطق عدم التقاطع والترتيب. في اختباراتهما على مشكلات المجموعات هذه، قلل نهجهما الهندسي الجديد متوسط وقت الحل بنسبة تصل إلى 76% للخرائط المتجمعة و67% للخرائط الشبيهة بالشبكة.
الخلاصة
يؤكد المؤلفان بحذر أنه على الرغم من أن منهجهما يعد تحسنًا كبيرًا مقارنة بتقنيات البرمجة بالقيود السابقة، إلا أنه ليس بعد بسرعة الحلول المتخصصة الأكثر قوة في العالم (مثل Concorde) لمسألة TSP الأساسية. ومع ذلك، فإن تلك الحلول الفائقة غالبًا لا تستطيع التعامل مع النسخ "المعممة" الأكثر تعقيدًا التي نجح المؤلفان في معالجتها.
تخلص الورقة إلى أنه بمجرد الانتباه لشكل المشكلة - باستخدام حقيقة أن الخطوط لا تتقاطع وأن الحواف تتبع منحنى - يمكن لأجهزة الكمبيوتر تقليم الإجابات السيئة بكفاءة أكبر بكثير. هذا لا يسرع عملية الحساب فحسب، بل يغير طبيعة البحث، مما يسمح لأجهزة الكمبيوتر بحل مشكلات توجيه أكبر وأكثر تعقيدًا كانت في السابق صعبة الحل ضمن وقت معقول. ويقترح المؤلفان أن هذا النهج الهندسي يمكن أن يلهم تحسينات مماثلة في مشكلات التوجيد الأخرى، طالما أن الطرق لا تضطر للتقاطع بطرق لا يمكن تجنبها.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.