A Statistically Rigorous, Held–Karp- and LKH-Validated Empirical Evaluation of a Classical 2-opt + Or-opt Local Search Pipeline for the Euclidean Traveling Salesman Problem
تقدم هذه الورقة تقييماً تجريبياً دقيقاً إحصائياً، ومتحققاً منه عبر خوارزميتي Held–Karp وLKH، لسلسلة عمليات تتكون من أقرب جار (nearest-neighbor)، و2-opt، وOr-opt لمسألة البائع المتجول في الفضاء الإقليدي (Euclidean TSP)، مما يثبت تحسنها الكبير مقارنة بـ 2-opt وحدها وقربها المستمر من حدود الأمثلية المعتمدة عبر نماذج اصطناعية وواقعية.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
إن إيجاد أقصر مسار ممكن يزور مجموعة من المواقع مرة واحدة بالضبط ويعود إلى نقطة البداية هو مشكلة حيرت علماء الرياضيات واللوجستيين لعقود من الزمن. تُعرف هذه المشكلة باسم "مسألة البائع المتجول"، وهي ليست مجرد لغز تجريدي؛ بل هي أساس لتحديات واقعية مثل تسليم الطرود، وحفر الثقوب في لوحات الدوائر المطبوعة، وتسلسل الحمض النووي. ولأن عدد المسارات الممكنة ينمو بشكل انفجاري مع إضافة المزيد من المدن، فإن إيجاد المسار المثالي الوح ideally غالباً ما يكون مستحيلاً من الناحية الحسابية في وقت معقول. بدلاً من ذلك، يعتمد الخبراء على طرق "البحث المحلي". وهذه استراتيجيات عملية تبدأ بمسار تقريبي وتجري تحسينات صغيرة وتدريجية، عبر تبديل الوصلات أو نقل أجز Det de المسار لمعرفة ما إذا كان إجمالي المسافة سيتقلص. وبينما تُعد هذه الطرق أدوات قياسية، إلا أنها غالباً ما تُعامل كـ "صناديق سوداء": نحن نعرف أنها تعمل، لكننا نادراً ما نقيس بدقة مدى اقترابها من الأفضل نظرياً، أو مدى تفوق طريقة على أخرى، ببرهان إحصائي صارم.
لقد جلبت دراسة حديثة أجراها محمد فتاحي وحمزة براتي هذا المستوى من الدقة إلى مزيج كلاسيكي من تقنيات البحث المحلي هذه. لم يبتكر الباحثون طريقة جديدة لحل المشكلة، بل أخذوا مسار عمل (pipeline) معروفاً — يبدأ بنهج "الجار الأقرب" البسيط لبناء مسودة أولية، ثم يحسنها باستخدام خطوتين محددتين للتحسين تُسميان "2-opt" و"Or-opt" — وأخضعوه لتدقيق إحصائي صارم. كان هدفهم هو قياس مدى تحسن الطريقة المركبة مقارنة باستخدام خطوة التحسين الأولى فقط، وتحديد مدى اقتراب المسارات النهائية من الحد الرياضي الأقصى للكمال. وللقيام بذلك، قاموا بإنشاء آلاف خرائط المدن العشوائية واختبروا الطريقة أيضاً على أربع خرائط مدن شهيرة وحقيقية حيث تُعرف الإجابة المثالية مسبقاً.
أجرى الباحثون تجاربهم على مجموعات مدن تتراوح بين 50 إلى 500 موقع. ولكل حجم، قاموا بتشغيل العملية ثلاثين مرة لضمان أن النتائج لم تكن مجرد ضربة حظ. وقارنوا بين طريقة قياسية، تستخدم فقط خطوة التحسين الأولى، وبين مسار العمل الهجين الخاص بهم الذي يضيف خطوة التحسين الثانية. كانت النتائج واضحة ومتسقة: مسار العمل الهجين، الذي يضيف طبقة إضافية من التحسين، أنتج مسارات أقصر في كل حالة. وفي المتوسط، أدت هذه الخطوة الإضافية إلى تحسين طول المسار بنسبة تتراوح بين 2.09% و3.48% اعتماداً على حجم المشكلة. وقد أكد التحليل الإحصائي أن هذه التحسينات لم تكن تقلبات عشوائية؛ إذ كان الفرق كبيراً بما يكفي لاعتباره مكسباً حقيقياً. علاوة على ذلك، حسب الباحثون "حداً أدنى" (lower bound)، وهو أرضية رياضية تمثل أقصر مسافة يمكن أن يحققها أي مسار نظرياً لتلك الخريطة المحددة. ووجدوا أن المسارات التي أنتجتها طريقتهم الهجينة كانت أطول بنسبة تترافي بين 4.9% و5.6% فقط من هذا الحد الأدنى النظري، وهي فجوة تتوافق مع ما يتوقعه الخبراء منذ زمن طويل من هذا النوع من الخوارزميات.
ولضمان صمود نتائجهم في العالم الحقيقي، اختبر الفريق طريقتهم على أربع خرائط تاريخية محددة لمدن مثل برلين وغيرها ذات الحلول المثالية المعروفة. وفي هذه الاختبارات، قارنوا نتائجهم مع برنامج حل متطور للغاية يُعرف باسم LKH، والذي يُعتبر المعيار الذهبي لإيجاد مسارات شبه مثالية. نجح برنامج LKH في إيجاد المسارات المثلى المعروفة لجميع الخرائط الأربع. ولم تطابق طريقة العمل الهجينة التي استخدمها الباحثون ذلك الكمال، لكنها اقتربت منه بشكل ملحوظ، حيث تراوحت المسارات النهائية بين 0% و5.78% أطول من المسار الأفضل المعروف. وقد أكد هذا أن التحسينات التي شوهدت في الخرائط الاصطناعية العشوائية تُرجمت مباشرة إلى سيناريوهات العالم الحقيقي. كما اختبرت الدراسة فكرة أكثر تعقيداً: استخدام بيانات رياضية من الحد الأدنى النظري لتوجيه ترتيب عمليات التحسين. وقد فشلت هذه المحاولة في إنتاج أي نتائج أفضل، وهي نتيجة أبلغها المؤلفون بشفافية لتوفير وقت الباحثين الآخرين من إضاعة الجهد في نفس الطريق المسدود.
تكمن أهمية هذا العمل ليس في خوارزمية جديدة، بل في وضوح قياسها. فمن خلال الجمع بين حد رياضي محسوب ذاتياً وبين برنامج حل يعتبر معياراً ذهبياً واختبار إحصائي صارم، قدم المؤلفون صورة نهائية لما يمكن أن تحققه الطريقة الكلاسيكية غير القائمة على التعلم. لقد أظهروا أنه بينما هذه التقنيات ليست مثالية، إلا أنها قوية للغاية، وتظل ثابتة باستمرار ضمن هامش ضيق من الإجابة الأفضل الممكنة. وتعمل هذه الدراسة كمرجع موثق وصلب، يثبت أن الطرق الكلاسيكية، حتى بدون تعقيد تعلم الآلة الحديث، تظل أدوات قوية، وقابلة للتنبؤ، وفعالة للغاية لحل بعض أكثر تحديات التوجيه تعقيداً في العالم.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.