हैमिल्टनियन पथ समस्या

From Vigyanwiki
This article is about यह निर्धारित करने की विशिष्ट समस्या कि किसी दिए गए ग्राफ़ में हैमिल्टनियन पथ या चक्र मौजूद है या नहीं. For सामान्य ग्राफ़ सिद्धांत अवधारणाएँ, see हैमिल्टनियन पथ.

ग्राफ सिद्धांत के गणित क्षेत्र में हैमिल्टनियन पथ समस्या और हैमिल्टनियन चक्र समस्या यह निर्धारित करती है कि हैमिल्टनियन पथ (अदिष्‍ट या दिष्ट ग्राफ में जो प्रत्येक शीर्ष पर बिल्कुल एक बार जाता है) या हैमिल्टनियन चक्र किसी दिए गए ग्राफ़ (चाहे दिष्ट ग्राफ हो या अदिष्‍ट ग्राफ) में सम्मिलित है। दोनों समस्याएँ एनपी-पूर्ण हैं।[1]

हैमिल्टनियन चक्र समस्या ट्रैवलिंग सेल्समैन समस्या का विशेष स्थिति है, जो दो शहरों के बीच की दूरी निर्धारित करके प्राप्त की जाती है यदि वे आसन्न और दो हैं अन्यथा, यह सत्यापित करते हुए कि यात्रा की गई कुल दूरी n के बराबर है (यदि हां, तो मार्ग है) हैमिल्टनियन परिपथ है; यदि कोई हैमिल्टनियन परिपथ नहीं है तो सबसे छोटा मार्ग लंबा होगा)।

पथ समस्या और चक्र समस्या के बीच कमी

हैमिल्टनियन पथ और हैमिल्टनियन चक्र अन्वेषण की समस्याएं इस प्रकार संबंधित हो सकती हैं:

  • एक दिशा में, G से प्राप्त ग्राफ़ H में हैमिल्टनियन चक्र समस्या ग्राफ़ G के लिए हैमिल्टनियन पथ समस्या से संबंधित हो सकती है, जिसमें नया सार्वभौमिक शीर्ष x जोड़कर, x को G के सभी शीर्षों से जोड़ा जा सकता है। इस प्रकार, हैमिल्टनियन पथ अन्वेषण संभव नहीं है हैमिल्टनियन चक्र अन्वेषण की तुलना में काफी धीमा होता है (सबसे खराब स्थिति में, शीर्षों की संख्या के एक फलन के रूप में)।
  • दूसरी दिशा में, ग्राफ़ G के लिए हैमिल्टनियन चक्र समस्या, ग्राफ़ H में हैमिल्टनियन पथ समस्या के समतुल्य है, जिसे क्रमशः G के शीर्ष v और v' से कनेक्टेड टर्मिनल (डिग्री-एक) शीर्ष s और t को जोड़कर प्राप्त किया गया है। v की क्लीव्ड प्रतिलिपि जो v' को v के समान निकटतम देता है। H में हैमिल्टनियन पथ शीर्षों से होकर गुजरता है से होकर गुजरता है G में चल रहे हैमिल्टनियन चक्र से मेल खाता है।[2]

एल्गोरिदम

शीर्षों के n! विभिन्न अनुक्रम जो किसी दिए गए n-शीर्ष ग्राफ़ में हैमिल्टनियन पथ हो सकते हैं (और एक पूर्ण ग्राफ़ में हैं), इसलिए मनमानीबल गवेक्षण एल्गोरिदम जो सभी संभावित अनुक्रमों का परीक्षण करता है वह बहुत धीमा होता है। दिष्ट ग्राफ़ पर हैमिल्टनियन चक्र को अन्वेषण के लिए प्रारंभिक सटीक एल्गोरिदम मार्टेलो का गणनात्मक एल्गोरिदम था।[3] फ़्रैंक रुबिन द्वारा गवेक्षण प्रक्रिया[4] ग्राफ़ के किनारों को तीन वर्गों में विभाजित करता है: वे जो पथ में होने चाहिए, वे जो पथ में नहीं हो सकते, और अनिर्णीत हैं। जैसे-जैसे गवेक्षण आगे बढ़ती है, निर्णय नियमों का समुच्चय अनिर्णीत किनारों को वर्गीकृत करता है, और यह निर्धारित करता है कि गवेक्षण को रोकना है या जारी रखना है। एल्गोरिदम ग्राफ़ को उन घटकों में विभाजित करता है जिन्हें अलग से हल किया जा सकता है। इसके अलावा, समय O(n2 2n) में समस्या को हल करने के लिए बेलमैन, हेल्ड और कार्प के गतिक क्रमादेशन एल्गोरिदम का उपयोग किया जा सकता है। इस विधि में, कोई यह निर्धारित करता है कि शीर्षों के प्रत्येक समुच्चय S और S में प्रत्येक शीर्ष v के लिए, क्या कोई ऐसा पथ है जो S में बिल्कुल शीर्षों को कवर करता है और v पर समाप्त होता है। S और v की प्रत्येक पसंद के लिए, एक पथ सम्मिलित है (S,v) यदि और केवल यदि v का कोई निकटतम w है, जैसे कि (S − v,w) के लिए पथ सम्मिलित है, जिसे गतिशील कार्यक्रम में पहले से ही गणना की गई जानकारी से देखा जा सकता है।[5][6]

एंड्रियास ब्योर्कलुंड ने हैमिल्टनियन चक्रों की संख्या की गणना करने की समस्या को कम करने के लिए समावेशन-बहिष्करण सिद्धांत का उपयोग करके चक्र कवर की गिनती की एक सरल गिनती समस्या को कम करने के लिए वैकल्पिक दृष्टिकोण प्रदान किया, जिसे कुछ मैट्रिक्स निर्धारकों की गणना करके हल किया जा सकता है। इस पद्धति का उपयोग करते हुए, उन्होंने दिखाया कि समय O(1.657n) में मोंटे कार्लो एल्गोरिथ्म द्वारा मनमाने ढंग से n-शीर्ष ग्राफ़ में हैमिल्टनियन चक्र समस्या को कैसे हल किया जाए); द्विदलीय ग्राफ के लिए इस एल्गोरिदम को समय o(1.415n) तक और बेहतर बनाया जा सकता है।[7]

अधिकतम डिग्री तीन के ग्राफ़ के लिए, सावधानीपूर्वक बैकट्रैकिंग गवेक्षण से समय O(1.251n) में हैमिल्टनियन चक्र (यदि कोई सम्मिलित है) पाया जा सकता है।[8]

सैट सॉल्वर का उपयोग करके हैमिल्टनियन पथ और चक्र पाए जा सकते हैं।

पारंपरिक कंप्यूटरों पर हैमिल्टनियन पथ और चक्र समस्याओं को हल करने की कठिनाई के कारण, कंप्यूटिंग के अपरंपरागत मॉडल में भी उनका अध्ययन किया गया है। उदाहरण के लिए, लियोनार्ड एडलमैन ने दिखाया कि हैमिल्टनियन पथ समस्या को डीएनए कंप्यूटिंग का उपयोग करके हल किया जा सकता है। रासायनिक प्रतिक्रियाओं में निहित समानता का फायदा उठाते हुए, ग्राफ़ के शीर्षों की संख्या में रैखिक कई रासायनिक प्रतिक्रिया चरणों का उपयोग करके समस्या को हल किया जा सकता है; हालाँकि, प्रतिक्रिया में भाग लेने के लिए डीएनए अणुओं की क्रमगुणित संख्या की आवश्यकता होती है।[9]

हैमिल्टनियन समस्या का प्रकाशिकी समाधान भी प्रस्तावित किया गया है।[10] समस्या का समाधान तैयार करने के लिए विचार यह है कि प्रकाशिकी केबल और बीम स्प्लिटर्स (किरणपुंज विपाटक) से बनी ग्राफ जैसी संरचना तैयार की जाए जो प्रकाश द्वारा पार की जाती है। इस दृष्टिकोण का अशक्त बिंदु ऊर्जा की आवश्यक मात्रा है जो नोड्स की संख्या में घातीय है।

सम्मिश्रता

हैमिल्टनियन चक्र या पथ अन्वेषण की समस्या एफएनपी (सम्मिश्रता) में है; अनुरूप निर्णय समस्या यह परीक्षण करना है कि हैमिल्टनियन चक्र या पथ सम्मिलित है या नहीं। दिष्ट और अदिष्‍ट हैमिल्टनियन चक्र समस्याएं कार्प की 21 एनपी-पूर्ण समस्याओं में से दो थीं। वे विशेष प्रकार के ग्राफ़ के लिए भी एनपी-पूर्ण रहते हैं, जैसे:

  • द्विदलीय ग्राफ,[11]
  • अधिकतम डिग्री तीन के अदिष्‍ट समतलीय ग्राफ,[12]
  • अंतःकोटि और आउटडिग्री के साथ अधिकतम दो दिष्ट समतलीय ग्राफ़,[13]
  • ब्रिजलेस ग्राफ अदिष्‍ट समतल 3-नियमित ग्राफ द्विदलीय ग्राफ,
  • 3-कनेक्टेड हुए 3-नियमित द्विदलीय ग्राफ़,[14]
  • वर्गाकार ग्रिड ग्राफ़ के उपग्राफ़,[15]
  • वर्ग ग्रिड ग्राफ़ के घन उपग्राफ़।[16]

हालाँकि, ग्राफ़ के कुछ विशेष वर्गों के लिए, समस्या को बहुपद समय में हल किया जा सकता है:

  • टुट्टे के कारण 4-कनेक्टेड समतलीय ग्राफ हमेशा हैमिल्टनियन होते हैं, और इन ग्राफ़ों में हैमिल्टनियन चक्र अन्वेषण का कम्प्यूटेशनल कार्य तथाकथित टुट्टे पथ की गणना करके रैखिक समय [17] में किया जा सकता है।
  • टुट्टे ने इस परिणाम को यह दिखाकर सिद्ध किया कि प्रत्येक 2-कनेक्टेड समतलीय ग्राफ में टुट्टे पथ होता है। बदले में टुट्टे पथों की गणना 2-कनेक्टेड समतलीय ग्राफ़ के लिए भी द्विघात समय में की जा सकती है,[18] जिसका उपयोग समतलीय ग्राफ़ के सामान्यीकरण में हैमिल्टनियन चक्र और लंबे चक्र को अन्वेषण के लिए किया जा सकता है।

इन सभी शर्तों को एक साथ रखने पर, यह खुला रहता है कि 3-कनेक्टेड 3-नियमित द्विदलीय समतल ग्राफ़ में हमेशा हैमिल्टनियन चक्र होना चाहिए, जिस स्थिति में उन ग्राफ़ों तक सीमित समस्या एनपी-पूर्ण नहीं हो सकती है; बार्नेट का अनुमान देखें.

ऐसे ग्राफ़ में जिनमें सभी शीर्षों की डिग्री विषम होती है, हैंडशेकिंग लेम्मा से संबंधित तर्क से पता चलता है कि किसी भी निश्चित किनारे के माध्यम से हैमिल्टनियन चक्रों की संख्या हमेशा सम संख्या होती है, इसलिए यदि हैमिल्टनियन चक्र दिया गया है, तो दूसरा भी सम्मिलित होना चाहिए।[19] हालाँकि, इस दूसरे चक्र का अन्वेषण कोई आसान कम्प्यूटेशनल कार्य नहीं लगता है। क्रिस्टोस पापादिमित्रियोउ ने इस तरह की समस्याओं को समाहित करने के लिए सम्मिश्रता वर्ग पीपीए (सम्मिश्रता) को परिभाषित किया है।[20]

संदर्भ

  1. ↑ Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1045-5 A1.3: GT37–39, pp. 199–200.
  2. ↑ Reduction from Hamiltonian cycle to Hamiltonian path
  3. ↑ Martello, Silvano (1983), "An Enumerative Algorithm for Finding Hamiltonian Circuits in a Directed Graph", ACM Transactions on Mathematical Software, 9 (1): 131–138, doi:10.1145/356022.356030, S2CID 11879800
  4. ↑ Rubin, Frank (1974), "A Search Procedure for Hamilton Paths and Circuits", Journal of the ACM, 21 (4): 576–80, doi:10.1145/321850.321854, S2CID 7132716
  5. ↑ Bellman, R. (1962), "Dynamic programming treatment of the travelling salesman problem", Journal of the ACM, 9: 61–63, doi:10.1145/321105.321111.
  6. ↑ Held, M.; Karp, R. M. (1962), "A dynamic programming approach to sequencing problems" (PDF), J. SIAM, 10 (1): 196–210, doi:10.1137/0110015, hdl:10338.dmlcz/103900.
  7. ↑ Björklund, Andreas (2010), "Determinant sums for undirected Hamiltonicity", Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10), pp. 173–182, arXiv:1008.0541, doi:10.1109/FOCS.2010.24, ISBN 978-1-4244-8525-3.
  8. ↑ Iwama, Kazuo; Nakashima, Takuya (2007), "An improved exact algorithm for cubic graph TSP", Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007), Lecture Notes in Computer Science, vol. 4598, pp. 108–117, CiteSeerX 10.1.1.219.1672, doi:10.1007/978-3-540-73545-8_13, ISBN 978-3-540-73544-1.
  9. ↑ Adleman, Leonard (November 1994), "Molecular computation of solutions to combinatorial problems", Science, 266 (5187): 1021–1024, Bibcode:1994Sci...266.1021A, CiteSeerX 10.1.1.54.2565, doi:10.1126/science.7973651, JSTOR 2885489, PMID 7973651.
  10. ↑ Mihai Oltean (2006). हैमिल्टनियन पथ समस्या को हल करने के लिए एक प्रकाश-आधारित उपकरण. Unconventional Computing. Springer LNCS 4135. pp. 217–227. arXiv:0708.1496. doi:10.1007/11839132_18.
  11. ↑ "प्रमाण है कि द्विदलीय ग्राफ़ में हैमिल्टन पथ का अस्तित्व एनपी-पूर्ण है". Computer Science Stack Exchange. Retrieved 2019-03-18.
  12. ↑ Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), "Some simplified NP-complete problems", Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi:10.1145/800119.803884, S2CID 207693360.
  13. ↑ Plesńik, J. (1979), "The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two" (PDF), Information Processing Letters, 8 (4): 199–201, doi:10.1016/0020-0190(79)90023-1.
  14. ↑ Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980–1981), "NP-completeness of the Hamiltonian cycle problem for bipartite graphs", Journal of Information Processing, 3 (2): 73–76, MR 0596313.
  15. ↑ Itai, Alon; Papadimitriou, Christos; Szwarcfiter, Jayme (1982), "Hamilton Paths in Grid Graphs", SIAM Journal on Computing, 4 (11): 676–686, CiteSeerX 10.1.1.383.1078, doi:10.1137/0211056.
  16. ↑ Buro, Michael (2000), "Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs" (PDF), Conference on Computers and Games, Lecture Notes in Computer Science, vol. 2063, pp. 250–261, CiteSeerX 10.1.1.40.9731, doi:10.1007/3-540-45579-5_17, ISBN 978-3-540-43080-3.
  17. ↑ Chiba, Norishige; Nishizeki, Takao (1989), "The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs", Journal of Algorithms, 10 (2): 187–211, doi:10.1016/0196-6774(89)90012-6
  18. ↑ Schmid, Andreas; Schmidt, Jens M. (2018), "Computing Tutte Paths", Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear.
  19. ↑ Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, pp. 259–268, doi:10.1016/S0167-5060(08)70511-9, ISBN 9780720408430, MR 0499124.
  20. ↑ Papadimitriou, Christos H. (1994), "On the complexity of the parity argument and other inefficient proofs of existence", Journal of Computer and System Sciences, 48 (3): 498–532, CiteSeerX 10.1.1.321.7008, doi:10.1016/S0022-0000(05)80063-7, MR 1279412.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=हैमिल्टनियन_पथ_समस्या&oldid=209426’