خوارزمية البحث المحلية، ارتباك كامل

Question

في (أ) و(ب)، بافتراض وجود عامل تحويل ثنائي التبادل، قم بتوصيل الحلول A وB، وهي جولات TSP في تمثيل المسار، بجيرانها المحتملين بين الجولات C وD وE وF وG

(a) A: 1 2 3 4 5 6 7

C: 1 3 5 7 2 4 6
D: 1 2 5 4 3 6 7
E: 2 3 1 7 5 4 6
F: 4 1 7 5 3 2 6
G: 1 2 3 7 6 5 4

(b) B: 1 3 2 7 5 4 6

C: 1 3 5 7 2 4 6
D: 1 2 5 4 3 6 7
E: 2 3 1 7 5 4 6
F: 4 1 7 5 3 2 6
G: 1 2 3 7 6 5 4

ليس لدي أي فكرة عما يطلب مني هذا القيام به.

Answer 1

تعريفات (يُستدل عليه من نص المشكلة، ربما ناقشت هذا الأمر في الفصل أيضًا)
جولة TSP في تمثيل المسار:
تسلسل مرتب للأرقام من 1 إلى 7، يتم ذكر كل رقم مرة واحدة فقط.
يمثل كل رقم المدينة التي زارها مندوب المبيعات المتجول.
على سبيل المثال د: 1 2 5 4 3 6 7, ، يشير إلى أن مندوب المبيعات يبدأ في المدينة 1، ويذهب إلى المدينة 2،
ثم المدينة 5 ...وينتهي في المدينة 7.
ربما يكون من المفيد في هذه المرحلة تقديم مفهوم "التوقف" وتسميته به أحرف صغيرة الحروف، وtrhu ز.(لا توجد علاقة على الإطلاق بالأحرف الكبيرة المستخدمة لتحديد المسارات المختلفة في المشكلة).
في المسار D، المحطة هي المدينة 1، والمحطة c هي المدينة 5 وما إلى ذلك.

عامل تحويل 2-التبادل
عملية تعمل على تحويل مسار TSP عن طريق استبدال مدينتين بالضبط (أو بشكل أكثر دقة، عن طريق تبديل المدينة لمحطتين من المحطات).
وبالتالي يمكن فهم عملية التحويل ثنائية التبادل على أنها عملية تأخذ ثلاث وسائط:المسار X، ومؤشرا التوقف m,n، وإرجاع المسار X' حيث تم تبديل المدن عند m وn.
إذا أسمينا هذه العملية Swp()، فيمكننا الكتابة

   Swp(A, c, e) = 1 2 5 4 3 6 7

المهمة (مهمتك هل تقبلها ;-))
ربط الحلول A وB، وهي جولات TSP في تمثيل المسار، بجيرانها المحتملين بين الجولات C وD وE وF وG
أعتقد أن الشرط هو التحديد بين C وD وE F وG (الحالة الكبيرة أي.المسارات) وهي مسارات "مجاورة" لـ A (أو B)، أي.أي منها يمكن اشتقاقه من A (أو من B) بعملية Swp() واحدة (وربما لتوفير معلمات العملية المذكورة).

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