باستخدام Sale Salidman Solver لتحديد مسار هاميلتون

Question

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

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

الآن سيحصل أي رسم بياني كامل على مسار هاميلتون في ذلك، وبالتالي يجب توسيع نطاق إغراء TSP إلى أي رسم بياني. يمكن القيام بذلك عن طريق تحديد الحواف إلى بعض القيمة اللانهاية إذا لم يكن هناك مسار بين مدينتين، وإعادة المسار الأول الذي هو مسار هاميلتون صالح.

هل هذه هي الطريقة الصحيحة للتعامل معها؟ أو يجب علي استخدام مزيج مختلف لمسار هاميلتون؟ قلقي الرئيسي هو ما إذا كان نهجا قابلا للتطبيق لأنني أستطيع أن أكون متأكدا إلى حد ما أن تعمل TSP الأمثل (لأنك تبدأ بحلول وتحسينها) ولكن ليس إذا كان قرارا مسار هاميلتون ستجد أي مسار في عدد ثابت من الأجيال.

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

Answer 1

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

Answer 2

كلاهما مشاكل كاملة NP، لذلك بحكم التعريف، يمكنك تحويل المدخلات واستخدام نفس الخوارزمية ؛-)

لكن الفكرة الأساسية يجب أن تعمل. بالطبع قد تحتاج إلى تغيير جيل مسارات جديدة ومعايير النجاح.

تحرير: BTW: هناك اقتراح لخوارزمية عشوائية:http://en.wikipedia.org/wiki/hamilton_path_problem.