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

From Vigyanwiki
No edit summary
 
(No difference)

Latest revision as of 14:47, 11 September 2023

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

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

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

अप्रत्यक्ष समाधान और टी-जॉइन्स

इस प्रकार से अप्रत्यक्ष मार्ग निरीक्षण समस्या को टी-जॉइन की अवधारणा के आधार पर एक कलन विधि द्वारा बहुपद समय में हल किया जा सकता है।

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

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

संपूर्ण ग्राफ़ का निर्माण करना, और फिर उसमें मिलान ढूंढना, दोनों ही O(n3) कम्प्यूटेशनल चरणों में किया जा सकता है।।

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

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

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