كيف تجد دورة تحتوي على مجموعة من العقد في رسم بياني؟

Question

بالنظر إلى رسم بياني غير موجه G = (V ، E) ومجموعة من العقد P. أحتاج إلى العثور على دورة (وليس أقصر دورة الطول) التي تحتوي على هذه العقد؟ كيف أجد هذه الدورة؟

Answer 1

يحتوي على دورة Hamiltonian (لـ P = V) ، وبالتالي فإن مشكلة القرار (مجرد معرفة ما إذا كان هناك شيء من هذا القبيل) مكتملة NP. لذلك لا توجد خوارزمية فعالة ما لم P = NP.

Answer 2

من المحتمل أن أبدأ في تصميم الخوارزمية عن طريق اختيار العقدة الأولى في P (دعنا نسميها P [0]) ، ثم تشغيل بحث للعمق الأول من P [0] ، يتم الوصول إلى أي وقت في أي وقت P [0]. يجب عليك تخزين المسار الذي تم نقله لإعادة الوصول إلى P [0] (أو على الأقل ما إذا كانت العقد الأخرى من P قد تم الوصول إليها) حتى تعرف أن أي دورة تجدها تحتوي على جميع العقد في وقت التشغيل P. كما هو الحال بالنسبة للبحث في العمق الأول ، والذي أعتقد أنه O (V + E).

قد يأتي شخص ما بحل أفضل ، وقد يتم تطبيق بعض الاستدلال على المساعدة ، ولكن يجب أن تبدأ ذلك. (على سبيل المثال ، قد تستنتج أنك يجب أن تبدأ في عقدة P مع أقل عدد من الحواف بدلاً من البدء في P [0].)

يحرر:

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

مزيد من التحرير:

لا تهتم بتحرير الأخير - لن ينجح إلا إذا كان من الممكن التأكد من أنه لا توجد عقدة في P على طريق مختلف بين p [0] والوصول إلى العقدة التي لا يمكن الوصول إليها بطريقة أخرى ، ولن نتمكن من ذلك اعلم ذلك بالتأكيد دون القيام بأكمل DFS.

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