मेरे पास अपेक्षाकृत छोटे (40-80 नोड्स) क्यूबिक (3-नियमित) प्लानर ग्राफ हैं, और मुझे उनकी हैमिल्टनिसिटी तय करनी है। मैं तथ्य यह है कि इस कार्य को एनपी पूरा हो गया है के बारे में पता कर रहा हूँ, लेकिन मैं asymptotically घातीय समय एल्गोरिदम कि फिर भी ग्राफ आकार मैं में दिलचस्पी के लिए बहुत तेजी से कर रहे हैं के लिए आशा है किक्यूबिक प्लानर ग्राफ में हैमिल्टनियन चक्र ढूंढना
40 नोड्स संभव लगता है। आप शामिल करने के लिए 40 में से 60 किनारों का चयन कर रहे हैं।
चलिए गहराई से पहली खोज करने का प्रयास करें।
प्रारंभ करने के लिए, एक वर्टेक्स वी चुनें। आपको अपने 3 घटना किनारों में से एक को बाहर करने की आवश्यकता होगी। एक समय में इन 3 संभावनाओं को आजमाएं। जब आप बाहर निकलने के लिए किनारे का चयन करते हैं, तो आप 4 किनारों को शामिल करने के लिए मजबूर कर रहे हैं। इसके बाद, हम "इस्तेमाल" के बाहर के किनारे के शिखर पर कॉल करेंगे।
यदि आप इस प्रक्रिया को 10 बार दोहरा सकते हैं, तो आप केवल 40^किनारों को चुन सकते थे, केवल 3^10 (5 9 4 9 4) संभावनाओं को खोजते थे। बेशक, पर्याप्त किनारों को निर्धारित करने के बाद आप "पृथक" शीर्षकों से बाहर चले जाएंगे।
लेकिन, अब हमारे पास एल्गोरिदम का विचार है। प्रत्येक चरण में, सबसे कम "प्रयुक्त" पड़ोसियों के साथ एक कशेरुक चुनने का प्रयास करें। असल में, 2 प्रयुक्त पड़ोसियों के साथ एक कशेरुक चुनना सबसे अच्छा है, क्योंकि इस्तेमाल किए गए किनारे को मजबूर किया जाता है। मुझे यकीन नहीं है कि 1 या 0 इस्तेमाल किए गए पड़ोसियों के साथ एक कशेरुक चुनना अगली सबसे अच्छी है। दोनों तरीकों का प्रयास करें! (और 3 इस्तेमाल पड़ोसियों ने एक असफल खोज इंगित की है)
जब हम किनारों को चुनते हैं, तो जांचें कि वे एक चक्र बनाते हैं या नहीं।
क्या आपके पास कुछ नमूना ग्राफ हैं? मैं एक सरल कार्यान्वयन का प्रयास कर सकता हूं।
:। "रुबिन (1974) का वर्णन करता है एक कुशल खोज प्रक्रिया जो कटौती का उपयोग करके ग्राफ में कुछ या सभी हैमिल्टन पथ और सर्किट पा सकती है जो बैकट्रैकिंग और अनुमान को कम करती है। "
कागज बिक्री के लिए यहां है: http://portal.acm.org/citation.cfm?id=321850.321854