चायनीस पोस्टमैन प्रोब्लेम

From Vigyanwiki
Revision as of 16:58, 4 July 2023 by alpha>Akanksha

ग्राफ सिद्धांत में, गणित और कंप्यूटर विज्ञान की शाखा, गुआन की मार्ग समस्या, चीनी डाकिया समस्या, डाकिया यात्रा या मार्ग निरीक्षण समस्या सबसे छोटा बंद पथ या सर्किट ढूंढना है जो कम से कम एक बार (जुड़े) अप्रत्यक्ष ग्राफ के हर किनारे पर जाता है . जब ग्राफ़ में एक यूलेरियन सर्किट (एक बंद वॉक जो हर किनारे को एक बार कवर करता है) होता है, तो वह सर्किट एक इष्टतम समाधान होता है। अन्यथा, अनुकूलन समस्या डुप्लिकेट करने के लिए ग्राफ किनारों की सबसे छोटी संख्या (या न्यूनतम संभव कुल वजन के साथ किनारों का सबसेट) ढूंढना है ताकि परिणामी मल्टीग्राफ में एक यूलेरियन सर्किट हो।[1] इसे बहुपद समय में हल किया जा सकता है।[2]

इस समस्या का अध्ययन मूल रूप से 1960 में चीनी गणितज्ञ मुझे मैं कहानी जीयू मामले|क्वान मेई-को द्वारा किया गया था, जिनके चीनी पेपर का 1962 में अंग्रेजी में अनुवाद किया गया था।[3] मूल नाम चाइनीज़ पोस्टमैन प्रॉब्लम उनके सम्मान में गढ़ा गया था; विभिन्न स्रोत इस सिक्के के निर्माण का श्रेय एलन जे. गोल्डमैन या जैक एडमंड्स को देते हैं, जो दोनों एनआईएसटी|यू.एस. में थे। उस समय राष्ट्रीय मानक ब्यूरो।[4][5]

एक सामान्यीकरण समान रूप से कई शीर्षों के किसी भी सेट टी को चुनना है, जिन्हें ग्राफ़ में एक किनारे सेट से जोड़ा जाना है, जिसके विषम-डिग्री कोने बिल्कुल टी के हैं। ऐसे सेट को टी-जॉइन कहा जाता है। यह समस्या, 'टी-जॉइन समस्या', बहुपद समय में भी उसी दृष्टिकोण से हल की जा सकती है जो डाकिया समस्या को हल करती है।

अप्रत्यक्ष समाधान और टी-जोड़

अप्रत्यक्ष मार्ग निरीक्षण समस्या को टी-जॉइन की अवधारणा के आधार पर एक कलन विधि द्वारा बहुपद समय में हल किया जा सकता है। मान लीजिए T एक ग्राफ़ में शीर्षों का एक समूह है। एक एज सेट J को T'-जॉइन' कहा जाता है यदि J में विषम संख्या में आपतित किनारों वाले शीर्षों का संग्रह बिल्कुल सेट T है। एक T-जॉइन तब मौजूद होता है जब ग्राफ़ के प्रत्येक कनेक्टेड घटक में सम संख्या होती है टी में शीर्ष। टी'-जॉइन समस्या' किनारों की न्यूनतम संभावित संख्या या न्यूनतम संभव कुल वजन के साथ टी-जॉइन ढूंढना है।

किसी भी टी के लिए, एक सबसे छोटा टी-जॉइन (जब यह मौजूद होता है) आवश्यक रूप से शामिल होता है वे पथ जो जोड़े में T के शीर्षों से जुड़ते हैं। पथ ऐसे होंगे कि उन सभी की कुल लंबाई या कुल भार यथासंभव कम हो। एक इष्टतम समाधान में, इनमें से कोई भी दो पथ किसी भी किनारे को साझा नहीं करेंगे, लेकिन उनके शीर्ष साझा हो सकते हैं। दिए गए इनपुट ग्राफ़ में सबसे छोटे पथ का प्रतिनिधित्व करने वाले किनारों के साथ, टी के शीर्ष पर एक पूर्ण ग्राफ़ बनाकर और फिर इस पूर्ण ग्राफ़ में एक मिलान (ग्राफ़ सिद्धांत) ढूंढकर न्यूनतम टी-ज्वाइन प्राप्त किया जा सकता है। इस मिलान के किनारे मूल ग्राफ़ में पथों का प्रतिनिधित्व करते हैं, जिनका मिलन वांछित टी-जॉइन बनाता है। पूर्ण ग्राफ़ का निर्माण करना और फिर उसमें मिलान ढूंढना, दोनों O(n) में किया जा सकता है3) कम्प्यूटेशनल चरण।

मार्ग निरीक्षण समस्या के लिए, टी को सभी विषम-डिग्री शीर्षों के सेट के रूप में चुना जाना चाहिए। समस्या की धारणाओं से, पूरा ग्राफ़ जुड़ा हुआ है (अन्यथा कोई दौरा मौजूद नहीं है), और हाथ मिलाना लेम्मा द्वारा इसमें विषम शीर्षों की संख्या सम है, इसलिए एक टी-जॉइन हमेशा मौजूद रहता है। टी-जॉइन के किनारों को दोगुना करने से दिया गया ग्राफ़ एक यूलेरियन मल्टीग्राफ (एक कनेक्टेड ग्राफ़ जिसमें प्रत्येक शीर्ष पर सम डिग्री होती है) बन जाता है, जिससे यह पता चलता है कि इसमें एक यूलर टावर है, एक टूर जो मल्टीग्राफ के प्रत्येक किनारे पर जाता है बिल्कुल एक बार. यह दौरा मार्ग निरीक्षण समस्या का इष्टतम समाधान होगा।[6][2]


निर्देशित समाधान

निर्देशित ग्राफ़ पर, समान सामान्य विचार लागू होते हैं, लेकिन विभिन्न तकनीकों का उपयोग किया जाना चाहिए। यदि निर्देशित ग्राफ यूलेरियन है, तो किसी को केवल यूलर चक्र खोजने की आवश्यकता है। यदि ऐसा नहीं है, तो किसी को टी-जॉइन ढूंढना होगा, जिसमें इस मामले में आउट-डिग्री (ग्राफ सिद्धांत) से अधिक इन-डिग्री (ग्राफ सिद्धांत) वाले शीर्षों से आउट-डिग्री (ग्राफ सिद्धांत) वाले शीर्षों से पथ ढूंढना शामिल है। ) उनके इन-डिग्री (ग्राफ़ सिद्धांत) से अधिक, जैसे कि वे प्रत्येक शीर्ष की इन-डिग्री को उसके आउट-डिग्री के बराबर बना देंगे। इसे न्यूनतम-लागत प्रवाह समस्या के एक उदाहरण के रूप में हल किया जा सकता है जिसमें अतिरिक्त डिग्री की प्रत्येक इकाई के लिए आपूर्ति की एक इकाई होती है, और अतिरिक्त आउट-डिग्री की प्रत्येक इकाई के लिए मांग की एक इकाई होती है। इस प्रकार यह O(|V|) में हल करने योग्य है2|ई|) समय. कोई समाधान तभी मौजूद होता है जब दिया गया ग्राफ़ मजबूती से जुड़ा हो।[2][7]

अनुप्रयोग

चीनी पोस्टमैन समस्या में विभिन्न संयोजनात्मक समस्याओं को कम कर दिया गया है, जिसमें एक समतलीय ग्राफ में अधिकतम कटौती खोजना भी शामिल है और एक अप्रत्यक्ष ग्राफ़ में न्यूनतम-माध्य लंबाई सर्किट।[8]

वेरिएंट

चीनी डाकिया समस्या के कुछ प्रकारों का अध्ययन किया गया है और उन्हें एनपी-पूर्ण दिखाया गया है।[9]

  • हवादार डाकिया समस्या मार्ग निरीक्षण समस्या का एक प्रकार है जिसमें इनपुट एक अप्रत्यक्ष ग्राफ है, लेकिन जहां प्रत्येक किनारे को दूसरी दिशा में पार करने की तुलना में एक दिशा में पार करने के लिए एक अलग लागत हो सकती है। निर्देशित और अप्रत्यक्ष ग्राफ़ के समाधान के विपरीत, यह एनपी-पूर्ण है।[10][11]
  • मिश्रित चीनी डाकिया समस्या: इस समस्या के लिए, कुछ किनारों को निर्देशित किया जा सकता है और इसलिए केवल एक दिशा से ही जाया जा सकता है। जब समस्या के लिए डिग्राफ (या मल्टीडिग्राफ) के न्यूनतम ट्रैवर्सल की आवश्यकता होती है तो इसे न्यूयॉर्क स्ट्रीट स्वीपर समस्या के रूप में जाना जाता है।[12]
  • के-चीनी डाकिया समस्या: एक निर्दिष्ट स्थान से शुरू होने वाले सभी के चक्रों को ढूंढें, जैसे कि प्रत्येक किनारे को कम से कम एक चक्र द्वारा पार किया जाता है। लक्ष्य सबसे महंगी साइकिल की लागत को कम करना है।
  • ग्रामीण डाकिया समस्या: कुछ अनावश्यक किनारों से समस्या का समाधान करें।[11]

यह भी देखें

संदर्भ

  1. ↑ Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 640–642, ISBN 9781420099829
  2. ↑ 2.0 2.1 2.2 Edmonds, J.; Johnson, E.L. (1973), "Matching Euler tours and the Chinese postman problem" (PDF), Mathematical Programming, 5: 88–124, doi:10.1007/bf01580113, S2CID 15249924
  3. ↑ Kwan, Mei-ko (1960), "Graphic programming using odd or even points", Acta Mathematica Sinica (in 中文), 10: 263–266, MR 0162630. Translated in Chinese Mathematics 1: 273–277, 1962.
  4. ↑ Pieterse, Vreda; Black, Paul E., eds. (September 2, 2014), "Chinese postman problem", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, retrieved 2016-04-26
  5. ↑ Grötschel, Martin; Yuan, Ya-xiang (2012), "Euler, Mei-Ko Kwan, Königsberg, and a Chinese postman" (PDF), Optimization stories: 21st International Symposium on Mathematical Programming, Berlin, August 19–24, 2012, Documenta Mathematica, Extra: 43–50, MR 2991468.
  6. ↑ Lawler, E.L. (1976), Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston
  7. ↑ Eiselt, H. A.; Gendeaeu, Michel; Laporte, Gilbert (1995), "Arc Routing Problems, Part 1: The Chinese Postman Problem", Operations Research, 43 (2): 231–242, doi:10.1287/opre.43.2.231
  8. ↑ A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Volume A, Springer. (2002).
  9. ↑ Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G, A compendium of NP optimization problems, KTH NADA, Stockholm, retrieved 2008-10-22
  10. ↑ Guan, Meigu (1984), "On the windy postman problem", Discrete Applied Mathematics, 9 (1): 41–46, doi:10.1016/0166-218X(84)90089-1, MR 0754427.
  11. ↑ 11.0 11.1 Lenstra, J.K.; Rinnooy Kan, A.H.G. (1981), "Complexity of vehicle routing and scheduling problems" (PDF), Networks, 11 (2): 221–227, doi:10.1002/net.3230110211
  12. ↑ Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 642–645, ISBN 9781420099829


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=चायनीस_पोस्टमैन_प्रोब्लेम&oldid=210825’