एल्गोरिदम 'न्यूनतम स्पैनिंग पथ' ढूंढने के लिए?

Question

इस हास्य http://xkcd.com/173/

मैं जानता हूँ कि कई एल्गोरिदम एक भारित ग्राफ की न्यूनतम फैले पेड़ लगाने के लिए देखते हैं कि से प्रेरित होकर, लेकिन मैं किसी भी जो कम से कम स्पैनिंग 'पथ' पा सकते हैं खोजने के लिए संघर्ष कर रहा है।

हास्य के लिए, यदि हम प्रत्येक जोड़े संबंधों के आधार पर हर किनारे को भारित करते हैं, तो सामाजिक रूप से इष्टतम व्यवस्था न्यूनतम अवधि 'पथ' होगी, यानी एक पथ जो सभी शिखरों को फैलाता है। क्या कोई मदद कर सकता है?

Answer 1

एक इष्टतम हैमिल्टनियन पथ ढूंढना (जिसे इष्टतम पथ कवर के रूप में भी जाना जाता है) एक मुश्किल समस्या है। (यह निर्धारित करना कि कोई हैमिल्टनियन पथ मौजूद है एनपी-पूर्ण समस्या है।) This scholarly article अन्य चीजों के साथ, इष्टतम पथ कवर एल्गोरिदम चर्चा करता है। आप अन्य संसाधनों को खोजने के लिए इन शर्तों के लिए वेब खोज सकते हैं। मुझे किसी भी आसानी से उपलब्ध कोड के बारे में पता नहीं है।

संयोग से, this question (जो मूल रूप से आपके डुप्लिकेट है) स्पष्ट रूप से बताता है कि ट्रैवलिंग सेल्समैन समस्या क्यों शुरू करने की जगह नहीं है।