خوارزمية لتوليد حلول TSP بشكل عشوائي

Question

تتطلب الأساليب الأكثر شيوعًا لحل مشكلة TSP (وخاصةً كيرنغان - الإرشادية) للعمل على جولة تم إنشاؤها عشوائيًا وتحسين الحل بدءًا من ذلك. ومع ذلك ، فإن الطريقة الوحيدة التي توصلت بها إلى القيام بذلك هي توليد تقليب عشوائي للرؤوس والتحقق مما إذا كان حلًا أم لا.

بالنسبة للحالات الكبيرة للمشكلة (على سبيل المثال 1000 رؤوس) ، يمكن أن تستغرق هذه العملية بعض الوقت. هل هناك طريقة ذكية أخرى لتوليد جولة عشوائية لمشكلة TSP بشكل أسرع؟ لاحظ أنني أبحث عن جولة ، بغض النظر عن التكلفة ، وليس الحل الأمثل.

شكرا مقدما

Answer 1

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

Answer 2

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

Answer 3

تريد استخدام منحنى ملء الفضاء.