View source for मिक्सड चायनिज पोस्टमैन प्रॉब्‌लम्‌

{{Short description|Problem in mathematics}}
'''मिश्रित चीनी डाकिया समस्या (एमसीपीपी या एमसीपी)''' एक ग्राफ के सबसे छोटे ट्रैवर्सल की खोज है जिसमें शीर्ष वी का एक सेट, सकारात्मक तर्कसंगत वजन के साथ अप्रत्यक्ष किनारों ई का एक सेट और सकारात्मक तर्कसंगत वजन के साथ निर्देशित आर्क ए का एक सेट है। इस प्रकार न्यूनतम लागत पर प्रत्येक किनारे या चाप को कम से कम एक बार कवर करता है।<ref>{{Cite journal |last=Minieka |first=Edward |date=July 1979 |title=मिश्रित नेटवर्क के लिए चीनी डाकिया समस्या|url=http://dx.doi.org/10.1287/mnsc.25.7.643 |journal=Management Science |volume=25 |issue=7 |pages=643–648 |doi=10.1287/mnsc.25.7.643 |issn=0025-1909}}</ref> इस प्रकार [[क्रिस्टोस पापादिमित्रियोउ]] द्वारा समस्या को एनपी-पूर्ण सिद्ध किया गया है।<ref>{{Cite journal |last=Papadimitriou |first=Christos H. |date=July 1976 |title=एज ट्रैवर्सिंग की जटिलता पर|journal=Journal of the ACM |volume=23 |issue=3 |pages=544–554 |doi=10.1145/321958.321974 |s2cid=8625996 |issn=0004-5411|doi-access=free }}</ref> इस प्रकार मिश्रित चीनी डाकिया समस्या अधिकांशतः बर्फ की जुताई जैसी अधिकांशतः [[आर्क रूटिंग समस्या]] में उत्पन्न होती है जहां कुछ सड़कें दोनों दिशाओं में पार करने के लिए बहुत संकीर्ण होती हैं जबकि अन्य सड़कें द्विदिशात्मक होती हैं और दोनों दिशाओं में जुताई की जा सकती हैं। इस प्रकार यह जांचना आसान है कि मिश्रित ग्राफ़ में किसी भी आकार का डाकिया दौरा है या नहीं, यह सत्यापित करके कि ग्राफ़ दृढ़ता से जुड़ा हुआ है या नहीं। इस प्रकार समस्या एनपी कठिन है यदि हम डाकिया दौरे को प्रत्येक चाप को ठीक एक बार पार करने के लिए प्रतिबंधित करते हैं या यदि हम इसे प्रत्येक किनारे को ठीक एक बार पार करने के लिए प्रतिबंधित करते हैं, जैसा कि ज़रागोज़ा मार्टिनेज ने सिद्ध करना  किया है।<ref>{{Cite journal |last=Zaragoza Martinez |first=Francisco |date=September 2006 |title=आर्क्स पर प्रतिबंधों के साथ मिश्रित डाकिया समस्या की जटिलता|url=http://dx.doi.org/10.1109/iceee.2006.251877 |journal=2006 3rd International Conference on Electrical and Electronics Engineering |pages=1–4 |publisher=IEEE |doi=10.1109/iceee.2006.251877|isbn=1-4244-0402-9 }}</ref><ref>{{Cite journal |last=Zaragoza Martinez |first=Francisco |date=2006 |title=किनारों पर प्रतिबंध के साथ मिश्रित डाकिया समस्या की जटिलता|url=http://dx.doi.org/10.1109/enc.2006.9 |journal=2006 Seventh Mexican International Conference on Computer Science |pages=3–10 |publisher=IEEE |doi=10.1109/enc.2006.9|isbn=0-7695-2666-7 |s2cid=17176905 }}</ref>
== गणितीय परिभाषा ==
'''गणितीय परिभाषा''' है:

इनपुट: एक दृढ़ता से जुड़ा हुआ, मिश्रित ग्राफ़ <math>G=(V,E,A)</math> लागत के साथ <math>c(e)\geq0</math> हर किनारे के लिए <math>e \subset E \cup A</math> और अधिकतम लागत <math>c_{max}</math>.

प्रश्न: क्या कोई (निर्देशित) दौरा है जो हर किनारे को पार करता है <math>E</math> और हर चाप में <math>A</math> कम से कम एक बार और अधिक से अधिक लागत आई है <math>c_{max}</math>?<ref>{{Cite journal |last1=Edmonds |first1=Jack |last2=Johnson |first2=Ellis L. |date=December 1973 |title=मिलान, यूलर पर्यटन और चीनी डाकिया|url=http://dx.doi.org/10.1007/bf01580113 |journal=Mathematical Programming |volume=5 |issue=1 |pages=88–124 |doi=10.1007/bf01580113 |s2cid=15249924 |issn=0025-5610}}</ref>
== अभिकलनात्मक जटिलता ==
मिश्रित चीनी डाकिया समस्या को हल करने में मुख्य कठिनाई (अप्रत्यक्ष) किनारों के लिए अभिविन्यास चुनने में है, जब हमें अपने दौरे के लिए एक तंग बजट दिया जाता है और हम केवल एक बार प्रत्येक किनारे को पार करने का जोखिम उठा सकते हैं। इस प्रकार फिर हमें किनारों को उन्मुख करना होगा और एक निर्देशित यूलेरियन ग्राफ प्राप्त करने के लिए, अर्थात प्रत्येक शीर्ष को संतुलित बनाने के लिए कुछ और चाप जोड़ना होगा। इस प्रकार यदि एक शीर्ष पर कई किनारे आपतित हैं, तो प्रत्येक किनारे का सही अभिविन्यास निर्धारित करना आसान काम नहीं है।<ref>{{Cite book |last=Corberán |first=Ángel |title=''Arc Routing: Problems, Methods, and Applications'' |year=2015 |isbn=978-1-61197-366-2}}</ref> इस प्रकार गणितज्ञ पापादिमित्रीउ ने अधिक प्रतिबंधों के साथ इस समस्या का विश्लेषण किया; '''"मिश्रित चीनी पोस्टमैन एनपी-पूर्ण है, यदि  इनपुट ग्राफ समतल हो, प्रत्येक शीर्ष पर अधिकतम तीन डिग्री होती है, और प्रत्येक किनारे और चाप की लागत एक होती है।"'''<ref>{{Cite journal |last=Papadimitriou |first=Christos H. |date=July 1976 |title=एज ट्रैवर्सिंग की जटिलता पर|journal=Journal of the ACM |volume=23 |issue=3 |pages=544–554 |doi=10.1145/321958.321974 |s2cid=8625996 |issn=0004-5411|doi-access=free }}</ref>
== यूलेरियन ग्राफ ==
मिश्रित चीनी पोस्टमैन समस्या को हल करने के लिए एक एल्गोरिदम बनाने के लिए यह जांचने की प्रक्रिया महत्वपूर्ण है कि मिश्रित '''ग्राफ़ यूलेरियन''' है या नहीं। इस प्रकार एक यूलेरियन चक्र के लिए मिश्रित ग्राफ़ जी की डिग्री सम होनी चाहिए, किन्तु यह पर्याप्त नहीं है।<ref>{{Cite book |last=Randolph. |first=Ford, Lester |url=http://worldcat.org/oclc/954124517 |title=नेटवर्क में प्रवाह|date=2016 |publisher=Princeton University Press |isbn=978-1-4008-7518-4 |oclc=954124517}}</ref>
==अनुमान ==
यह तथ्य कि मिश्रित चीनी पोस्टमैन एनपी-हार्ड है, ने बहुपद समय एल्गोरिदम की खोज को जन्म दिया है जो उचित सीमा तक इष्टतम समाधान तक पहुंचता है। इस प्रकार फ्रेडरिकसन ने 3/2 के कारक के साथ एक विधि विकसित की जिसे समतलीय ग्राफ़ पर लागू किया जा सकता है<ref>{{Cite journal |last=Frederickson |first=Greg N. |date=July 1979 |title=कुछ डाकिया समस्याओं के लिए सन्निकटन एल्गोरिदम|url=http://dx.doi.org/10.1145/322139.322150 |journal=Journal of the ACM |volume=26 |issue=3 |pages=538–554 |doi=10.1145/322139.322150 |s2cid=16149998 |issn=0004-5411}}</ref> और राघवाचारी और वीरासामी ने एक ऐसी विधि ढूंढी जिसका समतलीय होना आवश्यक नहीं है।<ref>{{Cite journal |last1=Raghavachari |first1=Balaji |last2=Veerasamy |first2=Jeyakesavan |date=January 1999 |title=A 3/2-Approximation Algorithm for the Mixed Postman Problem |url=http://dx.doi.org/10.1137/s0895480197331454 |journal=SIAM Journal on Discrete Mathematics |volume=12 |issue=4 |pages=425–433 |doi=10.1137/s0895480197331454 |issn=0895-4801}}</ref> यद्यपि, बहुपद समय डेडहेडिंग की लागत का पता नहीं लगा सकता है, सड़कों तक पहुँचने के लिए बर्फ हटाने वाले हल से या सड़कों तक पहुँचने के लिए सड़क साफ़ करने वाले को लगने वाले समय की आवश्यकता होती है।<ref>{{Cite journal |last=Zaragoza Martinez |first=Francisco |date=2006 |title=किनारों पर प्रतिबंध के साथ मिश्रित डाकिया समस्या की जटिलता|url=http://dx.doi.org/10.1109/enc.2006.9 |journal=2006 Seventh Mexican International Conference on Computer Science |pages=3–10 |publisher=IEEE |doi=10.1109/enc.2006.9|isbn=0-7695-2666-7 |s2cid=17176905 }}</ref><ref>{{Cite journal |last=Zaragoza Martinez |first=Francisco |date=September 2006 |title=आर्क्स पर प्रतिबंधों के साथ मिश्रित डाकिया समस्या की जटिलता|url=http://dx.doi.org/10.1109/iceee.2006.251877 |journal=2006 3rd International Conference on Electrical and Electronics Engineering |pages=1–4 |publisher=IEEE |doi=10.1109/iceee.2006.251877|isbn=1-4244-0402-9 }}</ref>
== औपचारिक परिभाषा ==
एक दृढ़ता से जुड़ा हुआ मिश्रित ग्राफ़ दिया गया है <math>G=(V,E,A)</math> एक शीर्ष सेट के साथ <math>V</math>, और किनारा सेट <math>E</math>, एक चाप सेट <math>A</math> और एक गैर-नकारात्मक लागत <math>c_e</math> प्रत्येक के लिए <math>e \in E \cup A</math>, एमसीपीपी में प्रत्येक लिंक से गुजरते हुए न्यूनतम लागत वाला दौरा ढूंढना सम्मिलित है <math>e\in E \cup A</math> कम से कम एक बार।

दिया गया <math>S\subset V</math>, <math>\delta^+(S)=\{(i,j)\in A:i\in S, j \in V \backslash S \}</math>, <math>\delta^-(S)=\{ (i,j)\in A:i\in V\backslash S, j \in S \}</math>, <math>\delta(S)</math> बिल्कुल एक समापन बिंदु वाले किनारों के सेट को दर्शाता है <math>S</math>, और <math>\delta^\star=\delta(S)\cup \delta^+(S) \cup \delta^-</math>. एक शीर्ष दिया गया  <math display="inline">i</math>, <math>d_i^-</math>(डिग्री) अंकित किए गए चापों की संख्या को दर्शाता है <math>i</math>, <math>d_i^+</math>(आउटडिग्री) निकलने वाले चापों की संख्या है <math display="inline">i</math>, और <math>d_i</math> (डिग्री) लिंक की संख्या है जिसके साथ घटना घटी है <math>i</math>.<ref>{{Cite book |last=Corberán |first=Ángel |title=''Arc Routing: Problems, Methods, and Applications'' |year=2015 |isbn=978-1-61197-366-2}}</ref> ध्यान दें कि <math>d_i=|\delta^\star(\{{i}\})|</math>. एक मिश्रित ग्राफ <math>G=(V,E,A)</math> इसे सममित कहा जाता है यदि  इसके सभी शीर्षों की डिग्री सम हो, इसे सममित कहा जाता है यदि <math>d_i^-=d_i^+</math> प्रत्येक शीर्ष के लिए <math display="inline">i</math>, और यदि कोई उपसमुच्चय दिया जाए तो इसे संतुलित कहा जाता है <math>S</math> शीर्षों से, निर्देशित चापों की संख्या के बीच का अंतर <math>S</math> को <math>V\backslash S</math>, <math>|\delta^+(S)|</math>, और से निर्देशित चापों की संख्या <math>V\backslash S</math> को <math>S</math>, <math>|\delta^-(S)|</math>, जुड़ने वाले अप्रत्यक्ष किनारों की संख्या से अधिक नहीं है <math>S</math> और <math>V \backslash S</math>, <math>|\delta (S)|</math>.

यह सर्वविदित तथ्य है कि मिश्रित ग्राफ <math>G</math> यूलेरियन है यदि और केवल यदि <math>G</math> सम और संतुलित है.<ref>{{Cite book |last=Ford |first=L.R. |title=नेटवर्क में प्रवाह|publisher=Princeton University Press |year=1962 |location=Princeton, N.J.}}</ref> ध्यान दें कि यदि <math>G</math> सम और सममित है, तो G भी संतुलित है (और ऑयलेरियन)। इस प्रकार इसके अतिरिक्त, यदि <math>G</math> सम है, द <math>MCPP</math> बहुपद समय में बिल्कुल हल किया जा सकता है।<ref>{{Cite journal |last1=Edmonds |first1=Jack |last2=Johnson |first2=Ellis L. |date=December 1973 |title=मिलान, यूलर पर्यटन और चीनी डाकिया|url=http://dx.doi.org/10.1007/bf01580113 |journal=Mathematical Programming |volume=5 |issue=1 |pages=88–124 |doi=10.1007/bf01580113 |s2cid=15249924 |issn=0025-5610}}</ref>

== सम एमसीपीपी एल्गोरिथम ==
# एक सम और दृढ़ता से जुड़ा हुआ मिश्रित ग्राफ़ दिया गया है <math>G=(V,E,A)</math>, होने देना <math>A_i</math> किनारों को बेतरतीब ढंग से एक दिशा निर्दिष्ट करके प्राप्त चापों का सेट बनें <math>E</math> और समान लागत के साथ. गणना करना <math>s_i=d_j^--d_i^+</math> निर्देशित ग्राफ़ में प्रत्येक शीर्ष i के लिए <math>(V, A\cup A_1)</math>. एक शिखर <math display="inline"> i</math> साथ <math>s_i>0(s_i<0)</math> आपूर्ति मांग के साथ एक स्रोत (सिंक) के रूप में माना जाएगा <math>s_i(-s_i)</math>. ध्यान दें कि जैसे <math>G</math> एक सम ग्राफ है, सभी आपूर्तियाँ और माँगें सम संख्याएँ हैं (शून्य को एक सम संख्या माना जाता है)।
# होने देना <math>A_2</math> चापों का समूह उनके विपरीत दिशा में हो <math>A_1</math> और उन संगत किनारों की लागत के साथ, और चलो <math>A_3</math> के समानांतर चापों का समुच्चय हो <math>A_2</math> शून्य लागत पर.
#मांगों को पूरा करना <math>s_i</math> सभी शीर्षों में से, ग्राफ़ में न्यूनतम लागत प्रवाह समस्या को हल करें <math>(V, A\cup A_1\cup A_2\cup A_3)</math>, जिसमें प्रत्येक चाप सम्मिलित है <math>A\cup A_1\cup A_2</math> इसमें अनंत क्षमता है और प्रत्येक चाप अंदर है <math>A_3</math> क्षमता है 2. चलो <math>x_{ij}</math> इष्टतम प्रवाह हो.
# प्रत्येक चाप के लिए <math>(i,j)</math> में <math>A_3</math> करो: यदि <math>x_{ij}=2</math>, फिर संबंधित किनारे को अंदर की ओर उन्मुख करें <math>G</math> से <math>i</math> को <math>j</math> (दिशा, से <math>j</math> को <math>i</math>, चरण 1 में संबंधित किनारे को सौंपा गया गलत था); यदि <math>x_{ij}=0</math>, फिर संबंधित किनारे को जी से उन्मुख करें <math>j</math> को <math>i</math> (इस स्थितियोंमें, चरण 1 में अभिविन्यास सही था)। स्थितियोंपर ध्यान दें <math>x_{ij}=1</math> असंभव है, क्योंकि सभी प्रवाह मान चाप के माध्यम से अंदर आते हैं <math>A_3</math> सम संख्याएँ हैं.
# संवर्द्धन <math>G</math> जोड़कर <math>x_{ij}</math> प्रत्येक आर्क की प्रतिलिपियाँ <math>A \cup A_1 \cup A_2</math>. परिणामी ग्राफ़ सम और सममित है।

== अनुमानी एल्गोरिदम ==
जब मिश्रित ग्राफ़ सम नहीं होता है और सभी नोड्स में सम डिग्री नहीं होती है, इस प्रकार तो ग्राफ़ को सम ग्राफ़ में बदला जा सकता है।

* होने देना <math>\mathrm{G=\{V,E,A\}}</math> एक मिश्रित ग्राफ बनें जो [[मजबूती से जुड़ा हुआ घटक|'''दृढ़ता से जुड़ा''']] हो। इस प्रकार आर्क दिशाओं को अनदेखा करके विषम डिग्री नोड्स ढूंढें और न्यूनतम-लागत मिलान प्राप्त करें। एक सम ग्राफ़ उत्पन्न करने के लिए न्यूनतम लागत मिलान से किनारों के साथ ग्राफ़ को संवर्धित करें <math>\mathrm{G'=\{V',E',A'\}}</math>.
* ग्राफ सम है किन्तु सममित नहीं है और यूलेरियन मिश्रित ग्राफ सम और सममित है। इस प्रकार न्यूनतम लागत प्रवाह समस्या का समाधान करें <math>G'</math> एक सममित ग्राफ प्राप्त करने के लिए जो सम नहीं हो सकता हैं <math>G''</math>.
* अंतिम चरण में सममित ग्राफ बनाना सम्मिलित है <math>G''</math> यहां तक की। विषम डिग्री नोड्स को लेबल करें <math>V_O</math>. ऐसे चक्र खोजें जो चाप सेट में रेखाओं के बीच वैकल्पिक हों <math>A'' \backslash A</math> और किनारे में रेखाएँ सेट हैं <math>E''</math> जो बिंदुओं पर प्रारंभ और समाप्त होता है <math>V_O</math>. में चाप <math>A''\backslash A</math> इसे अप्रत्यक्ष किनारों के रूप में माना जाना चाहिए, निर्देशित चाप के रूप में नहीं हैं।

=== आनुवंशिक एल्गोरिथ्म ===
हुआ जियांग एट द्वारा प्रकाशित एक पेपर एवं अल ने आबादी पर ऑपरेशन करके मिश्रित चीनी डाकिया समस्या को हल करने के लिए एक '''आनुवंशिक एल्गोरिदम''' तैयार किया हैं। इस प्रकार एमसीपीपी के लिए अन्य सन्निकटन एल्गोरिदम की तुलना में एल्गोरिदम ने अच्छा प्रदर्शन किया हैं।<ref>{{Citation |last1=Jiang |first1=Hua |title=Genetic Algorithm for Mixed Chinese Postman Problem |date=2010 |url=http://link.springer.com/10.1007/978-3-642-16493-4_20 |work=Advances in Computation and Intelligence |volume=6382 |pages=193–199 |editor-last=Cai |editor-first=Zhihua |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/978-3-642-16493-4_20 |isbn=978-3-642-16492-7 |access-date=2022-10-25 |last2=Kang |first2=Lishan |last3=Zhang |first3=Shuqi |last4=Zhu |first4=Fei |editor2-last=Hu |editor2-first=Chengyu |editor3-last=Kang |editor3-first=Zhuo |editor4-last=Liu |editor4-first=Yong}}</ref>
== यह भी देखें ==

* [[कैपेसिटेटेड आर्क रूटिंग समस्या]]

== संदर्भ ==
{{Reflist}}

[[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:ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]]