حل مشكلة بائع السفر في روبي (أكثر من 50 موقعًا)

Question

أنا أعمل في شركة توصيل. نقوم حاليًا بحل أكثر من 50 مواقعًا بواسطة "اليد".

لقد كنت أفكر في استخدام Google Maps API لحل هذه المشكلة ، لكنني قرأت أن هناك قدرًا 24 نقطة.

نستخدم حاليًا Rails في الخادم الخاص بنا ، لذا أفكر في استخدام برنامج نصي Ruby الذي سيحصل على إحداثيات أكثر من 50 موقعًا وإخراج حل معقول.

ما هي الخوارزمية التي ستستخدمها للتعامل مع هذه المشكلة؟

هل روبي لغة برمجة جيدة لحل هذا النوع من المشاكل؟

هل تعرف أي نص روبي موجود؟

Answer 1

قد يكون هذا ما تبحث عنه:

تحذير:

يتم وضع علامة على هذا الموقع بواسطة Firefox كموقع للهجوم - لكنني لا يبدو أنني كذلك. في الواقع لقد استخدمته من قبل بدون مشكلة

تحقق من تاريخ المراجعة لعنوان URL

يبدو أن Rubyquiz قد انخفض (لقد تم أسفل قليلاً) ولكن لا يزال بإمكانك التحقق من آلة Wayback و Archive.org لمعرفة تلك الصفحة:http://web.archive.org/web/20100105132957/http://rubyquiz.com/quiz142.html

Answer 2

حتى مع وجود حل DP المذكور في إجابة أخرى ، سيتطلب ذلك عمليات O (10^15). لذلك سيتعين عليك النظر في الحلول التقريبية ، والتي ربما تكون مقبولة بالنظر إلى أنك تقوم بها حاليًا باليد. ينظر الى http://en.wikipedia.org/wiki/travelling_salesman_problem#heuristic_and_approixation_algorithms

Answer 3

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

إليك LIB PY مع جولة bitonic و هنا آخر
دعني أذهب للبحث عن روبي. أواجه مشكلة في العثور على أكثر من مجرد RGL, التي لديها مشاكل الكفاءة ....

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

Answer 4

أحد الحلول المحسّنة هو استخدام البرمجة الديناميكية ولكن لا يزال مكلفًا للغاية O (2 ** n) ، وهو أمر غير ممكن للغاية ، إلا إذا كنت تستخدم بعض المجموعات وتوزيع الحوسبة ، فلن يكون الخادم المفرد أو الخادم المفرد مفيدًا جدًا لك.

أوصيك بالتوصل إلى معايير جشع بدلاً من استخدام DP أو قوة الغاشمة التي سيكون من الأسهل تنفيذها.

بمجرد انتهاء البرنامج ، يمكنك القيام ببعض المذكرات ، وتخزين النتائج في مكان ما للبحث اللاحق ، والتي يمكن أن توفر لك أيضًا بعض الدورات.

فيما يتعلق بالرمز ، تحتاج إلى تنفيذ القمم ، الحواف التي لها أوزان.

IE: فئة Vertex التي لها حواف مع الأوزان ، العودية. من فئة الرسم البياني الذي من شأنه ملء البيانات.

Answer 5

لقد عملت على استخدام خوارزميات Meta-Heurestic مثل ANT Colony Optimazation لحل مشاكل TSP لمشكلة Bays29 (29-City) ، وقد أعطتني بالقرب من الحلول المثلى في وقت قصير جدًا. يمكنك استخدام نفس الشيء.

لقد كتبته في Java رغم ذلك ، سأربطه هنا على أي حال ، لأنني أعمل حاليًا على منفذ إلى Ruby: Java: https://github.com/mohammedri/ant_colony_java_tspروبي: https://github.com/mohammedri/aco-ruby (غير مكتمل) هذه هي مجموعة البيانات التي تحلها لـ: https://github.com/jorik041/osmsharp/blob/master/core/osmsharp.tools/benchmark/tsplib/problems/tsp/bays29.tsp

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

Answer 6

إذا كنت تريد تكلفة الحل التي تنتجها الخوارزمية في غضون 3/2 من الأمثل ، فأنت تريد خوارزمية Christofides. لا يتمتع ACO و GA بتكلفة مضمونة.