مسار غير دورة إلى جميع العقد

Question

هل هناك خوارزمية أو مجموعة من الخوارزميات التي تتيح لك العثور على أقصر مسافة قريبة من عقدة البداية التعسفية بحيث يتم زيارة كل عقدة في وزن غير موجه؟ إنه ليس بائعًا مسافرًا تمامًا ، لأنني لا أهتم إذا تمت زيارة العقدة أكثر من مرة. (لا يهم حتى إذا عادت إلى البداية-يمكن أن ينتهي المشي في بعض العقدة البعيدة طالما كانت آخرها اللازم لزيارة جميع العقد.) إنها ليست شجرة تمتد على الأقل ، لأنه قد يكون ذلك هو الذهاب-> b-> c-> a-> d هو أقصر (غير متكبر) لزيارة A و B و C و D. يقول حدسي أن هذا ليس ' T مشكلة NP تمامًا ، لأنها لا تحتوي على قيود تجعل مشاكل NP صعبة للغاية. يمكنني ، بالطبع ، أن أكون مخطئا تماما.

Answer 1

من مقال ويكيبيديا عن مشكلة بائع السفر:

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

Answer 2

لست متأكدًا من ماهية الآداب لإضافة إجابة إلى سؤال مع إجابة مقبولة بالفعل.

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

يمكن تقليل مشكلة مسار Hamiltonian إلى هذا:

لنفترض أن لدينا خوارزمية زمنية متعددة الحدود لحل مشكلتنا المتمثلة في إيجاد المشي على الأقل وزنًا يزور جميع القمم.

بالنظر إلى رسم بياني نحتاج إليه إلى تحديد مسار هاميلتون موجود أم لا ، فإننا فقط نطعمه كما هو ، إلى خوارزمية المشكلة في متناول اليد ، وضع أوزان الحافة = 1. إذا كانت الخوارزمية تُرجع قيمة> n-1 ، ثم هناك ليس مسار هاميلتون في الرسم البياني الأصلي ، وإلا

لذلك هذه المشكلة هي np-hard.