تباين من شاي التي تزور مدن متعددة

Question

أنا أتطلع إلى مناقشة الفرع والحل المنصوص عليه في TSP مع زيارات متعددة. (هذه مدينة تحتاج إلى زيارة على الأقل مرة واحدة، بدلا من مرة واحدة فقط)

يحرر:

إزالة الشك لأنه لم يكن ذا صلة كما أشار جيتس. الآن السؤال هو أكثر وضوحا.

Answer 1

ببساطة زيادة الرسم البياني عن طريق إضافة، لكل زوج من العقد A و B، حافة تمثل أقصر طريق من A إلى B. خوارزمية فلويد وارشال يتيح لك القيام بذلك في O (n ^ 3)، وهو أسرع بكثير من أي خوارزمية TSP. بمجرد القيام بذلك، استخدم فرع TSP القياسي وتقنية ملزمة. هذا الموقع لديه بعض المعلومات من كتاب Applegate, ، والتي تناقش الفرع ونزام tsp وفقا ل Wikipedia TSP Entry..

Answer 2

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

يحتاج الفرع والخوارزمية المرتبطة إلى الجمع بين خوارزمية لإعادة بناء مسارات التكلفة الأقل تكلفة بالنظر إلى إخراج خوارزمية Floyd-Warshall. الفرع والخوارزمية المرتبطة هو الحلقة الخارجية، وتحدد العقد غير المتفجرة. ثم تستخدم خوارزمية إعادة إعمار مسار الأقل تكلفة لإضافة الحواف والعقد في الدورة إلى الدورة. يجب وضع علامة على العقد كما تمت زيارتها من خلال خوارزمية إعادة إعمار مسار الأقل تكلفة، وليس فقط من قبل الفرع وجزء.