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

Latest revision as of 14:47, 11 September 2023

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

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

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

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

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

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

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

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

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

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

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

अनुप्रयोग

अतः चीनी पोस्टमैन समस्या में विभिन्न संयोजनात्मक समस्याओं को कम कर दिया गया है, जिसमें एक समतलीय ग्राफ में अधिकतम कटौती खोजना भी सम्मिलित किया गया है

और एक अप्रत्यक्ष ग्राफ़ में न्यूनतम-माध्य लंबाई परिपथ ढूंढना सम्मिलित किया गया है।।^[8]

वेरिएंट

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

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

यह भी देखें

ट्रैवलिंग सेल्समैन की समस्या
आर्क रूटिंग
मिश्रित चीनी डाकिया समस्या

संदर्भ

↑ Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 640–642, ISBN 9781420099829
↑ ^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
↑ 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.
↑ 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
↑ 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.
↑ Lawler, E.L. (1976), Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston
↑ 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
↑ A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Volume A, Springer. (2002).
↑ Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G, A compendium of NP optimization problems, KTH NADA, Stockholm, retrieved 2008-10-22
↑ 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.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
↑ Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 642–645, ISBN 9781420099829

बाहरी संबंध

Weisstein, Eric W., "Chinese Postman Problem", MathWorld
Media related to चायनीस पोस्टमैन प्रोब्लेम at Wikimedia Commons

[1] Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 640–642, ISBN 9781420099829

[EdmondsJohnson-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.

[Complexity-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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 1: / Line 1: @@
 {{Short description|Finding shortest walks through all graph edges}}
-[[ग्राफ सिद्धांत]] में, गणित और [[कंप्यूटर विज्ञान]] की  शाखा, गुआन की मार्ग समस्या, चीनी डाकिया समस्या, डाकिया यात्रा या मार्ग निरीक्षण समस्या सबसे छोटा बंद पथ या सर्किट ढूंढना है जो कम से कम एक बार (जुड़े) [[अप्रत्यक्ष ग्राफ]] के हर किनारे पर जाता है . जब ग्राफ़ में एक [[यूलेरियन सर्किट]] (एक बंद वॉक जो हर किनारे को एक बार कवर करता है) होता है, तो वह सर्किट एक इष्टतम समाधान होता है। अन्यथा, अनुकूलन समस्या डुप्लिकेट करने के लिए ग्राफ किनारों की सबसे छोटी संख्या (या न्यूनतम संभव कुल वजन के साथ किनारों का सबसेट) ढूंढना है ताकि परिणामी [[मल्टीग्राफ]] में एक यूलेरियन सर्किट हो।<ref>{{citation|first1=Fred S.|last1=Roberts|first2=Barry|last2=Tesman|title=Applied Combinatorics|edition=2nd|year=2009|publisher=CRC Press|isbn=9781420099829|pages=640–642}}</ref> इसे बहुपद समय में हल किया जा सकता है।<ref name = "EdmondsJohnson" />
+[[ग्राफ सिद्धांत]] में, गणित और [[कंप्यूटर विज्ञान]] की शाखा, '''गुआन''' की '''मार्ग समस्या''', चीनी डाकिया समस्या, डाकिया यात्रा या मार्ग निरीक्षण समस्या सबसे छोटा बंद पथ या परिपथ ढूंढना है जो कम से कम एक बार (जुड़े) [[अप्रत्यक्ष ग्राफ]] के किनारे पर जाता है . इस प्रकार से जब ग्राफ़ में एक [[यूलेरियन सर्किट|यूलेरियन]] परिपथ (एक बंद रास्ता जो हर किनारे को एक बार कवर करता है) होता है, तो वह परिपथ एक इष्टतम समाधान होता है। अन्यथा, अनुकूलन समस्या डुप्लिकेट करने के लिए ग्राफ किनारों की सबसे छोटी संख्या (या न्यूनतम संभव कुल वजन के साथ किनारों का उपसमूह) ढूंढना है जिससे परिणामी [[मल्टीग्राफ]] में एक यूलेरियन परिपथ होता है।<ref>{{citation|first1=Fred S.|last1=Roberts|first2=Barry|last2=Tesman|title=Applied Combinatorics|edition=2nd|year=2009|publisher=CRC Press|isbn=9781420099829|pages=640–642}}</ref> इस प्रकार से इसे बहुपद समय में हल किया जा सकता है।<ref name = "EdmondsJohnson" />
-इस समस्या का अध्ययन मूल रूप से 1960 में चीनी गणितज्ञ [[मुझे मैं कहानी जीयू मामले]]|क्वान मेई-को द्वारा किया गया था, जिनके चीनी पेपर का 1962 में अंग्रेजी में अनुवाद किया गया था।<ref>{{citation
+इस समस्या का अध्ययन मूल रूप से 1960 में चीनी गणितज्ञ क्वान मेई-को द्वारा किया गया था, जिनके चीनी पेपर का 1962 में अंग्रेजी में अनुवाद किया गया था।<ref>{{citation
   | last = Kwan | first = Mei-ko | author-link = Meigu Guan
   | journal = [[Acta Mathematica Sinica]]
@@ Line 10: / Line 10: @@
   | title = Graphic programming using odd or even points
   | volume = 10
-  | year = 1960}}. Translated in ''Chinese Mathematics'' '''1''': 273–277, 1962.</ref> मूल नाम चाइनीज़ पोस्टमैन प्रॉब्लम उनके सम्मान में गढ़ा गया था; विभिन्न स्रोत इस सिक्के के निर्माण का श्रेय एलन जे. गोल्डमैन या [[जैक एडमंड्स]] को देते हैं, जो दोनों एनआईएसटी|यू.एस. में थे। उस समय राष्ट्रीय मानक ब्यूरो।<ref>{{citation|contribution=Chinese postman problem|title=Dictionary of Algorithms and Data Structures|editor1-first=Vreda|editor1-last=Pieterse|editor2-first=Paul E.|editor2-last=Black|date=September 2, 2014|access-date=2016-04-26|contribution-url=https://xlinux.nist.gov/dads/HTML/chinesePostman.html|publisher=[[National Institute of Standards and Technology]]}}</ref><ref>{{citation
+  | year = 1960}}. Translated in ''Chinese Mathematics'' '''1''': 273–277, 1962.</ref> और मूल नाम चाइनीज़ पोस्टमैन प्रॉब्लम उनके सम्मान किया गया था; विभिन्न स्रोत इस सिक्के के निर्माण का श्रेय एलन जे. गोल्डमैन या [[जैक एडमंड्स]] को देते हैं, जोकी उस समय अमेरिकी राष्ट्रीय मानक ब्यूरो में थे।।<ref>{{citation|contribution=Chinese postman problem|title=Dictionary of Algorithms and Data Structures|editor1-first=Vreda|editor1-last=Pieterse|editor2-first=Paul E.|editor2-last=Black|date=September 2, 2014|access-date=2016-04-26|contribution-url=https://xlinux.nist.gov/dads/HTML/chinesePostman.html|publisher=[[National Institute of Standards and Technology]]}}</ref><ref>{{citation
   | last1 = Grötschel | first1 = Martin | author1-link = Martin Grötschel
   | last2 = Yuan | first2 = Ya-xiang
@@ Line 22: / Line 22: @@
   | year = 2012}}.</ref>
-एक सामान्यीकरण समान रूप से कई शीर्षों के किसी भी सेट टी को चुनना है, जिन्हें ग्राफ़ में एक किनारे सेट से जोड़ा जाना है, जिसके विषम-डिग्री कोने बिल्कुल टी के हैं। ऐसे सेट को टी-जॉइन कहा जाता है। यह समस्या, 'टी-जॉइन समस्या', बहुपद समय में भी उसी दृष्टिकोण से हल की जा सकती है जो डाकिया समस्या को हल करती है।
+इस प्रकार से एक सामान्यीकरण समान रूप से कई शीर्षों के किसी भी समुच्चय टी को चुना जाता है, जिन्हें ग्राफ़ में एक किनारे समुच्चय से जोड़ा जाता है, जिसके विषम-डिग्री कोने बिल्कुल टी के होते हैं। ऐसे समुच्चय को टी-जॉइन कहा जाता है। यह समस्या, 'टी-जॉइन समस्या', बहुपद समय में भी उसी दृष्टिकोण से हल की जा सकती है जोकी डाकिया समस्या को हल करती है।
-==अप्रत्यक्ष समाधान और टी-जोड़==
+==अप्रत्यक्ष समाधान और टी-जॉइन्स==
-अप्रत्यक्ष मार्ग निरीक्षण समस्या को टी-जॉइन की अवधारणा के आधार पर एक [[कलन विधि]] द्वारा बहुपद समय में हल किया जा सकता है।
+इस प्रकार से अप्रत्यक्ष मार्ग निरीक्षण समस्या को टी-जॉइन की अवधारणा के आधार पर एक [[कलन विधि]] द्वारा बहुपद समय में हल किया जा सकता है।
-मान लीजिए T एक ग्राफ़ में शीर्षों का एक समूह है। एक एज सेट J को T'-जॉइन' कहा जाता है यदि J में विषम संख्या में आपतित किनारों वाले शीर्षों का संग्रह बिल्कुल सेट T है। एक T-जॉइन तब मौजूद होता है जब ग्राफ़ के प्रत्येक कनेक्टेड घटक में सम संख्या होती है टी में शीर्ष। टी'-जॉइन समस्या' किनारों की न्यूनतम संभावित संख्या या न्यूनतम संभव कुल वजन के साथ टी-जॉइन ढूंढना है।
+और मान लीजिए ''टी'' एक ग्राफ़ में शीर्षों का एक समूह होता है। एक एज समुच्चय जे को टी '-जॉइन' कहा जाता है यदि जे में विषम संख्या में आपतित किनारों वाले शीर्षों का संग्रह बिल्कुल समुच्चय ''टी'' है। एक टी -जॉइन तब उपस्तिथि होता है जब ग्राफ़ के प्रत्येक कनेक्टेड घटक में सम संख्या होती है टी में शीर्ष। टी'-जॉइन समस्या' किनारों की न्यूनतम संभावित संख्या या न्यूनतम संभव कुल वजन के साथ टी-जॉइन ढूंढना होता है।
-किसी भी टी के लिए, एक सबसे छोटा टी-जॉइन (जब यह मौजूद होता है) आवश्यक रूप से शामिल होता है <math>\tfrac{1}{2}|T|</math> वे पथ जो जोड़े में T के शीर्षों से जुड़ते हैं। पथ ऐसे होंगे कि उन सभी की कुल लंबाई या कुल भार यथासंभव कम हो। एक इष्टतम समाधान में, इनमें से कोई भी दो पथ किसी भी किनारे को साझा नहीं करेंगे, लेकिन उनके शीर्ष साझा हो सकते हैं। दिए गए इनपुट ग्राफ़ में सबसे छोटे पथ का प्रतिनिधित्व करने वाले किनारों के साथ, टी के शीर्ष पर एक पूर्ण ग्राफ़ बनाकर और फिर इस पूर्ण ग्राफ़ में एक मिलान (ग्राफ़ सिद्धांत) ढूंढकर न्यूनतम टी-ज्वाइन प्राप्त किया जा सकता है। इस मिलान के किनारे मूल ग्राफ़ में पथों का प्रतिनिधित्व करते हैं, जिनका मिलन वांछित टी-जॉइन बनाता है।
+किन्तु किसी भी टी के लिए, एक सबसे छोटा टी-जॉइन (जब यह उपस्तिथि होता है) आवश्यक रूप से <math>\tfrac{1}{2}|T|</math> सम्मिलित होता है वे पथ जो जोड़े में टी के शीर्षों से जुड़ते हैं। किन्तु पथ ऐसे होंगे कि उन सभी की कुल लंबाई या कुल भार यथासंभव कम हो। एक इष्टतम समाधान में, इनमें से कोई भी दो पथ किसी भी किनारे को साझा नहीं करेंगे, जिससे उनके शीर्ष साझा हो सकते हैं। दिए गए इनपुट ग्राफ़ में सबसे छोटे पथ का प्रतिनिधित्व करने वाले किनारों के साथ, टी के शीर्ष पर एक पूर्ण ग्राफ़ बनाकर और फिर इस पूर्ण ग्राफ़ में एक मिलान (ग्राफ़ सिद्धांत) ढूंढकर न्यूनतम टी-ज्वाइन प्राप्त किया जा सकता है। इस मिलान के किनारे मूल ग्राफ़ में पथों का प्रतिनिधित्व करते हैं, जिनका मिलन वांछित टी-जॉइन बनाता है।
-पूर्ण ग्राफ़ का निर्माण करना और फिर उसमें मिलान ढूंढना, दोनों O(n) में किया जा सकता है<sup>3</sup>) कम्प्यूटेशनल चरण।
-मार्ग निरीक्षण समस्या के लिए, टी को सभी विषम-डिग्री शीर्षों के सेट के रूप में चुना जाना चाहिए। समस्या की धारणाओं से, पूरा ग्राफ़ जुड़ा हुआ है (अन्यथा कोई दौरा मौजूद नहीं है), और [[ हाथ मिलाना लेम्मा |हाथ मिलाना लेम्मा]] द्वारा इसमें विषम शीर्षों की संख्या सम है, इसलिए एक टी-जॉइन हमेशा मौजूद रहता है। टी-जॉइन के किनारों को दोगुना करने से दिया गया ग्राफ़ एक यूलेरियन मल्टीग्राफ (एक कनेक्टेड ग्राफ़ जिसमें प्रत्येक शीर्ष पर सम डिग्री होती है) बन जाता है, जिससे यह पता चलता है कि इसमें एक [[यूलर टावर]] है, एक टूर जो मल्टीग्राफ के प्रत्येक किनारे पर जाता है बिल्कुल एक बार. यह दौरा मार्ग निरीक्षण समस्या का इष्टतम समाधान होगा।<ref>{{citation|first=E.L.|last=Lawler|title=Combinatorial Optimization: Networks and Matroids|publisher=Holt, Rinehart and Winston|year=1976}}</ref><ref name = "EdmondsJohnson">{{citation|first1=J.|last1=Edmonds|first2=E.L.|last2=Johnson|title=Matching Euler tours and the Chinese postman problem|journal=Mathematical Programming|volume=5|year=1973|pages=88–124|doi=10.1007/bf01580113|s2cid=15249924|url=http://www.eecs.umich.edu/%7Epettie/matching/Edmonds-Johnson-chinese-postman.pdf}}</ref>
+संपूर्ण ग्राफ़ का निर्माण करना, और फिर उसमें मिलान ढूंढना, दोनों ही O(''n''<sup>3</sup>) कम्प्यूटेशनल चरणों में किया जा सकता है।।
+अतः मार्ग निरीक्षण समस्या के लिए, टी को सभी विषम-डिग्री शीर्षों के समुच्चय के रूप में चुना जाना चाहिए। समस्या की धारणाओं से, पूरा ग्राफ़ जुड़ा हुआ है (अन्यथा कोई दौरा उपस्तिथि नहीं है), और [[ हाथ मिलाना लेम्मा |हाथ मिलाना लेम्मा]] द्वारा इसमें विषम शीर्षों की संख्या सम होती है, इसलिए एक टी-जॉइन सदैव उपस्तिथि रहता है। इस प्रकार से टी-जॉइन के किनारों को दोगुना करने से दिया गया ग्राफ़ एक यूलेरियन मल्टीग्राफ (एक कनेक्टेड ग्राफ़ जिसमें प्रत्येक शीर्ष पर सम डिग्री होती है) बन जाता है, जिससे यह पता चलता है कि इसमें एक [[यूलर टावर]] है, एक टूर जो मल्टीग्राफ के प्रत्येक किनारे पर जाता है इसके अतिरिक्त यह दौरा मार्ग निरीक्षण समस्या का इष्टतम समाधान होता है ।<ref>{{citation|first=E.L.|last=Lawler|title=Combinatorial Optimization: Networks and Matroids|publisher=Holt, Rinehart and Winston|year=1976}}</ref><ref name="EdmondsJohnson">{{citation|first1=J.|last1=Edmonds|first2=E.L.|last2=Johnson|title=Matching Euler tours and the Chinese postman problem|journal=Mathematical Programming|volume=5|year=1973|pages=88–124|doi=10.1007/bf01580113|s2cid=15249924|url=http://www.eecs.umich.edu/%7Epettie/matching/Edmonds-Johnson-chinese-postman.pdf}}</ref>
 ==निर्देशित समाधान==
-निर्देशित ग्राफ़ पर, समान सामान्य विचार लागू होते हैं, लेकिन विभिन्न तकनीकों का उपयोग किया जाना चाहिए। यदि निर्देशित ग्राफ यूलेरियन है, तो किसी को केवल यूलर चक्र खोजने की आवश्यकता है। यदि ऐसा नहीं है, तो किसी को टी-जॉइन ढूंढना होगा, जिसमें इस मामले में आउट-[[डिग्री (ग्राफ सिद्धांत)]] से अधिक इन-डिग्री (ग्राफ सिद्धांत) वाले शीर्षों से आउट-डिग्री (ग्राफ सिद्धांत) वाले शीर्षों से पथ ढूंढना शामिल है। ) उनके इन-डिग्री (ग्राफ़ सिद्धांत) से अधिक, जैसे कि वे प्रत्येक शीर्ष की इन-डिग्री को उसके आउट-डिग्री के बराबर बना देंगे। इसे न्यूनतम-लागत प्रवाह समस्या के एक उदाहरण के रूप में हल किया जा सकता है जिसमें अतिरिक्त डिग्री की प्रत्येक इकाई के लिए आपूर्ति की एक इकाई होती है, और अतिरिक्त आउट-डिग्री की प्रत्येक इकाई के लिए मांग की एक इकाई होती है। इस प्रकार यह O(|V|) में हल करने योग्य है<sup>2</sup>|ई|) समय. कोई समाधान तभी मौजूद होता है जब दिया गया ग्राफ़ मजबूती से जुड़ा हो।<ref name = "EdmondsJohnson" /><ref>{{citation |last1 = Eiselt | first1 = H. A. | last2 = Gendeaeu | first2 = Michel | last3 = Laporte | first3 = Gilbert | title = Arc Routing Problems, Part 1: The Chinese Postman Problem | journal = [[Operations Research (journal)|Operations Research]] | year = 1995 | volume = 43 | issue = 2 | pages = 231–242 | doi=10.1287/opre.43.2.231| doi-access = free }}</ref>
+निर्देशित ग्राफ़ पर, समान सामान्य विचार प्रस्तुत किये जाते हैं, जिससे विभिन्न विधियों का उपयोग किया जाना चाहिए। यदि निर्देशित ग्राफ यूलेरियन है, तो किसी को केवल यूलर चक्र खोजने की आवश्यकता होती है। यदि ऐसा नहीं होता है, तो किसी को टी-जॉइन ढूंढना होगा, जिसमें इस विषय में आउट-[[डिग्री (ग्राफ सिद्धांत)]] से अधिक इन-डिग्री (ग्राफ सिद्धांत) वाले शीर्षों से आउट-डिग्री (ग्राफ सिद्धांत) वाले शीर्षों से पथ ढूंढना सम्मिलित है। ) उनके इन-डिग्री (ग्राफ़ सिद्धांत) से अधिक, जैसे कि वे प्रत्येक शीर्ष की इन-डिग्री को उसके आउट-डिग्री के समान बना देते है । इसे न्यूनतम-व्यय प्रवाह समस्या के एक उदाहरण के रूप में हल किया जा सकता है जिसमें अतिरिक्त डिग्री की प्रत्येक इकाई के लिए आपूर्ति की एक इकाई होती है, और अतिरिक्त आउट-डिग्री की प्रत्येक इकाई के लिए मांग की एक इकाई होती है। इस प्रकार यह O(|''V''|<sup>2</sup>|''E''|) में हल करने योग्य होती है इसके अतिरिक्त कोई समाधान तभी उपस्तिथि होता है जब दिया गया ग्राफ़ कठोरता से जुड़ा होता है ।<ref name = "EdmondsJohnson" /><ref>{{citation |last1 = Eiselt | first1 = H. A. | last2 = Gendeaeu | first2 = Michel | last3 = Laporte | first3 = Gilbert | title = Arc Routing Problems, Part 1: The Chinese Postman Problem | journal = [[Operations Research (journal)|Operations Research]] | year = 1995 | volume = 43 | issue = 2 | pages = 231–242 | doi=10.1287/opre.43.2.231| doi-access = free }}</ref>
 ==अनुप्रयोग==
-चीनी पोस्टमैन समस्या में विभिन्न संयोजनात्मक समस्याओं को कम कर दिया गया है, जिसमें एक समतलीय ग्राफ में अधिकतम कटौती खोजना भी शामिल है
+अतः चीनी पोस्टमैन समस्या में विभिन्न संयोजनात्मक समस्याओं को कम कर दिया गया है, जिसमें एक समतलीय ग्राफ में अधिकतम कटौती खोजना भी सम्मिलित किया गया है
-और एक अप्रत्यक्ष ग्राफ़ में न्यूनतम-माध्य लंबाई सर्किट।<ref>A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Volume A, Springer. (2002).</ref>
+और एक अप्रत्यक्ष ग्राफ़ में न्यूनतम-माध्य लंबाई परिपथ ढूंढना सम्मिलित किया गया है।।<ref>A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Volume A, Springer. (2002).</ref>
 ==वेरिएंट==
-चीनी डाकिया समस्या के कुछ प्रकारों का अध्ययन किया गया है और उन्हें एनपी-पूर्ण दिखाया गया है।<ref>{{citation
+इस प्रकार से चीनी डाकिया समस्या के कुछ प्रकारों का अध्ययन किया गया है और उन्हें एनपी-पूर्ण दिखाया गया है।<ref>{{citation
   | last = Crescenzi
   | first = P.
@@ Line 48: / Line 49: @@
   | access-date = 2008-10-22
 }}</ref>
-*हवादार डाकिया समस्या मार्ग निरीक्षण समस्या का एक प्रकार है जिसमें इनपुट एक अप्रत्यक्ष ग्राफ है, लेकिन जहां प्रत्येक किनारे को दूसरी दिशा में पार करने की तुलना में एक दिशा में पार करने के लिए एक अलग लागत हो सकती है। निर्देशित और अप्रत्यक्ष ग्राफ़ के समाधान के विपरीत, यह एनपी-पूर्ण है।<ref>{{citation
+*विंडी डाकिया समस्या मार्ग निरीक्षण समस्या का एक प्रकार है जिसमें इनपुट एक अप्रत्यक्ष ग्राफ है, जिससे जहां प्रत्येक किनारे को दूसरी दिशा में पार करने की तुलना में एक दिशा में पार करने के लिए एक अलग निवेश हो सकती है। निर्देशित और अप्रत्यक्ष ग्राफ़ के समाधान के विपरीत, यह एनपी-पूर्ण होते है।<ref>{{citation
   | last = Guan | first = Meigu | author-link = Meigu Guan
   | doi = 10.1016/0166-218X(84)90089-1
@@ Line 60: / Line 61: @@
   }}.</ref><ref name = "Complexity">{{citation|first1=J.K.|last1=Lenstra|first2=A.H.G.|last2=Rinnooy Kan|title=Complexity of vehicle routing and scheduling problems|journal=Networks|volume=11|issue=2|year=1981|pages=221–227|doi=10.1002/net.3230110211|url=http://ageconsearch.umn.edu/record/272191/files/erasmus119.pdf}}</ref>
 * [[मिश्रित चीनी डाकिया समस्या]]: इस समस्या के लिए, कुछ किनारों को निर्देशित किया जा सकता है और इसलिए केवल एक दिशा से ही जाया जा सकता है। जब समस्या के लिए डिग्राफ (या मल्टीडिग्राफ) के न्यूनतम ट्रैवर्सल की आवश्यकता होती है तो इसे न्यूयॉर्क स्ट्रीट स्वीपर समस्या के रूप में जाना जाता है।<ref>{{citation|first1=Fred S.|last1=Roberts|first2=Barry|last2=Tesman|title=Applied Combinatorics|edition=2nd|year=2009|publisher=CRC Press|isbn=9781420099829|pages=642–645}}</ref>
-* के-चीनी डाकिया समस्या: एक निर्दिष्ट स्थान से शुरू होने वाले सभी के चक्रों को ढूंढें, जैसे कि प्रत्येक किनारे को कम से कम एक चक्र द्वारा पार किया जाता है। लक्ष्य सबसे महंगी साइकिल की लागत को कम करना है।
+* के-चीनी डाकिया समस्या: एक निर्दिष्ट स्थान से प्रारंभ होने वाले सभी के चक्रों को ढूंढें, जैसे कि प्रत्येक किनारे को कम से कम एक चक्र द्वारा पार किया जाता है। और लक्ष्य सबसे बहुमूल्य साइकिल की निवेश को कम करना है।
-* ग्रामीण डाकिया समस्या: कुछ अनावश्यक किनारों से समस्या का समाधान करें।<ref name = "Complexity" />
+* "ग्रामीण डाकिया समस्या": कुछ ऐसे किनारों से समस्या का समाधान करें जिनकी आवश्यकता नहीं है।<ref name = "Complexity" />
 ==यह भी देखें==
 *[[ट्रैवलिंग सेल्समैन की समस्या]]
@@ Line 69: / Line 70: @@
 ==संदर्भ==
 {{Reflist|30em}}
 ==बाहरी संबंध==
 *{{mathworld|urlname=ChinesePostmanProblem|title=Chinese Postman Problem|mode=cs2}}
 *{{commons category-inline}}
-[[Category: एनपी-पूर्ण समस्याएँ]] [[Category: ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]]
-[[Category: Machine Translated Page]]
+[[Category:CS1]]
+[[Category:CS1 中文-language sources (zh)]]
 [[Category:Created On 25/06/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:एनपी-पूर्ण समस्याएँ]]
+[[Category:ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 14:47, 11 September 2023

Contents

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

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

अनुप्रयोग

वेरिएंट

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 14:47, 11 September 2023

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

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

अनुप्रयोग

वेरिएंट

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories