تباين في مشكلة البائع المتجول - اختر روتينًا فرعيًا جيدًا من العديد من العقد بناءً على القيود

Question

إصدار TLDR: الأهم من ذلك هو أنه في مشكلة TSP ، بدلاً من العثور على أقصر دورة هاميلتون ، ما هي الطرق الجيدة للعثور على أفضل مسار (أفترض أن المسار الذي يزور معظم العقد) وهو طول X على الأكثر ، مع بداية ثابتة نقطة.

النسخة الكاملة:

أنا مهتم ببعض الأفكار لمشكلة تتضمن TSP. أولاً ، مثال على ذلك مشكلة TSP في العالم الحقيقي هي عندما يكون لديك مواقع جغرافية للزيارة وتحتاج إلى اتجاهات قيادة لطريق الأمثل (أو شبه مثالي) لزيارة الجميع ، إما مائدة مستديرة أو من A إلى Z. تنفيذ هذا في http://www.gebweb.net/optimap/ و JS TSP Solver متاح على http://code.google.com/p/google-maps-tsp-solver/.

الآن ضع في اعتبارك أن لديك N = 100 - 1000+ موقع. في هذه المرحلة ، لا يمكنك حساب المسار بأي قدر معقول من الوقت/الموارد ، ولكن حتى لو كان ذلك ممكنًا ، فهذا ليس مفيدًا لمعظم سيناريوهات العالم الواقعي. لنفترض أنك تختار نقطة انطلاق ثابتة وبناءً على ذلك ، من 1000+ المواقع التي تريد توليدها مثالية روتين الذي يناسب (صغير نسبيا) القيد القصوى (على سبيل المثال ، طريق يمكن تغطيته في يوم واحد أو أسبوع واحد). كيف يمكن حل هذا في الوقت الحقيقي بالقرب من الوقت الحقيقي؟ أفكاري Sofar:

1. قم ببناء مصفوفة المدة من نقطة البداية (هذه الخطوة ممكنة حتى في بضعة آلاف من النقاط) واختيار مجموعة فرعية صغيرة من النقاط الأقرب إلى نقطة البداية. من الناحية المثالية ، يجب أن تكون هذه المجموعة الفرعية كبيرة بما يكفي ، فإن زيارتها تمامًا هي بالتأكيد>القيد القصوى, ، ولكن صغيرة بما يكفي للمعالجة بسرعة ، على الأقل مع الخوارزميات الإرشادية.

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

أي روابط ، أو أفكار موضع تقدير ، وخاصة للنقطة 2.

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

Answer 1

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

Define a data structure Route {
  the route taken so far, 
  and can give the score (nodes visited)
  the distance traveled
  and the remaining nodes allowed
  the current location.
}

Define a Priority Queue of Routes which sorts on distance traveled.
Define a SortedSet of Routes which sorts on score called solutions.

Add a Route of Length 0, at the depot to the priority queue.
Loop until the head of the priority queue is greater than MAX
   Route r = take the head of the priority queue.
   for each potential remaining node n in r, 
     (in increasing order of distance from the current location)
      child = a new route of r with n appended
      if child distance < max, append to priority queue, otherwise break
   if no children were appended add r to solutions

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