मिक्सड चायनिज पोस्टमैन प्रॉब्‌लम्‌: Difference between revisions

Revision as of 23:59, 4 July 2023

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

गणितीय परिभाषा

गणितीय परिभाषा है:

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

प्रश्न: क्या कोई (निर्देशित) दौरा है जो हर किनारे को पार करता है $E$ और हर चाप में $A$ कम से कम एक बार और अधिक से अधिक लागत आई है $c_{max}$ ?^[5]

कम्प्यूटेशनल जटिलता

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

यूलेरियन ग्राफ

मिश्रित चीनी पोस्टमैन समस्या को हल करने के लिए एक एल्गोरिदम बनाने के लिए यह जांचने की प्रक्रिया महत्वपूर्ण है कि मिश्रित ग्राफ़ यूलेरियन है या नहीं। यूलेरियन चक्र के लिए मिश्रित ग्राफ़ G की डिग्री सम होनी चाहिए, किन्तु यह पर्याप्त नहीं है।^[8]

अनुमान

यह तथ्य कि मिश्रित चीनी पोस्टमैन एनपी-हार्ड है, ने बहुपद समय एल्गोरिदम की खोज को जन्म दिया है जो उचित सीमा तक इष्टतम समाधान तक पहुंचता है। फ्रेडरिकसन ने 3/2 के कारक के साथ एक विधि विकसित की जिसे समतलीय ग्राफ़ पर लागू किया जा सकता है^[9] और राघवाचारी और वीरासामी ने एक ऐसी विधि ढूंढी जिसका समतल होना आवश्यक नहीं है।^[10] यद्यपि, बहुपद समय डेडहेडिंग की लागत का पता नहीं लगा सकता है, बर्फ हटाने वाले हल को उन सड़कों तक पहुँचने में लगने वाला समय लगता है जिन सड़कों पर वह हल चलाएगा या एक सड़क साफ़ करने वाले को उन सड़कों तक पहुँचने में समय लगेगा जहाँ वह साफ़ करेगा।^[11]^[12]

औपचारिक परिभाषा

एक दृढ़ता से जुड़ा हुआ मिश्रित ग्राफ़ दिया गया है $G=(V,E,A)$ एक शीर्ष सेट के साथ $V$ , और किनारा सेट $E$ , एक चाप सेट $A$ और एक गैर-नकारात्मक लागत $c_{e}$ प्रत्येक के लिए $e\in E\cup A$ , एमसीपीपी में प्रत्येक लिंक से गुजरते हुए न्यूनतम लागत वाला दौरा ढूंढना सम्मिलित है $e\in E\cup A$ कम से कम एक बार।

दिया गया $S\subset V$ , $\delta ^{+}(S)=\{(i,j)\in A:i\in S,j\in V\backslash S\}$ , $\delta ^{-}(S)=\{(i,j)\in A:i\in V\backslash S,j\in S\}$ , $\delta (S)$ बिल्कुल एक समापन बिंदु वाले किनारों के सेट को दर्शाता है $S$ , और $\delta ^{\star }=\delta (S)\cup \delta ^{+}(S)\cup \delta ^{-}$ . एक शीर्ष दिया गया ${\textstyle i}$ , $d_{i}^{-}$ (डिग्री) अंकित किए गए चापों की संख्या को दर्शाता है $i$ , $d_{i}^{+}$ (आउटडिग्री) निकलने वाले चापों की संख्या है ${\textstyle i}$ , और $d_{i}$ (डिग्री) लिंक की संख्या है जिसके साथ घटना घटी है $i$ .^[13] ध्यान दें कि $d_{i}=|\delta ^{\star }(\{{i}\})|$ . एक मिश्रित ग्राफ $G=(V,E,A)$ इसे सममित कहा जाता है यदि इसके सभी शीर्षों की डिग्री सम हो, इसे सममित कहा जाता है यदि $d_{i}^{-}=d_{i}^{+}$ प्रत्येक शीर्ष के लिए ${\textstyle i}$ , और यदि कोई उपसमुच्चय दिया जाए तो इसे संतुलित कहा जाता है $S$ शीर्षों से, निर्देशित चापों की संख्या के बीच का अंतर $S$ को $V\backslash S$ , $|\delta ^{+}(S)|$ , और से निर्देशित चापों की संख्या $V\backslash S$ को $S$ , $|\delta ^{-}(S)|$ , जुड़ने वाले अप्रत्यक्ष किनारों की संख्या से अधिक नहीं है $S$ और $V\backslash S$ , $|\delta (S)|$ .

यह सर्वविदित तथ्य है कि मिश्रित ग्राफ $G$ यूलेरियन है यदि और केवल यदि $G$ सम और संतुलित है.^[14] ध्यान दें कि यदि $G$ सम और सममित है, तो G भी संतुलित है (और ऑयलेरियन)। इसके अतिरिक्त, यदि $G$ सम है, द $MCPP$ बहुपद समय में बिल्कुल हल किया जा सकता है।^[15]

सम एमसीपीपी एल्गोरिथम

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

अनुमानी एल्गोरिदम

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

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

आनुवंशिक एल्गोरिथ्म

हुआ जियांग एट द्वारा प्रकाशित एक पेपर। अल ने आबादी पर ऑपरेशन करके मिश्रित चीनी डाकिया समस्या को हल करने के लिए एक आनुवंशिक एल्गोरिदम तैयार किया। एमसीपीपी के लिए अन्य सन्निकटन एल्गोरिदम की तुलना में एल्गोरिदम ने अच्छा प्रदर्शन किया।^[16]

यह भी देखें

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

संदर्भ

↑ Minieka, Edward (July 1979). "मिश्रित नेटवर्क के लिए चीनी डाकिया समस्या". Management Science. 25 (7): 643–648. doi:10.1287/mnsc.25.7.643. ISSN 0025-1909.
↑ Papadimitriou, Christos H. (July 1976). "एज ट्रैवर्सिंग की जटिलता पर". Journal of the ACM. 23 (3): 544–554. doi:10.1145/321958.321974. ISSN 0004-5411. S2CID 8625996.
↑ Zaragoza Martinez, Francisco (September 2006). "आर्क्स पर प्रतिबंधों के साथ मिश्रित डाकिया समस्या की जटिलता". 2006 3rd International Conference on Electrical and Electronics Engineering. IEEE: 1–4. doi:10.1109/iceee.2006.251877. ISBN 1-4244-0402-9.
↑ Zaragoza Martinez, Francisco (2006). "किनारों पर प्रतिबंध के साथ मिश्रित डाकिया समस्या की जटिलता". 2006 Seventh Mexican International Conference on Computer Science. IEEE: 3–10. doi:10.1109/enc.2006.9. ISBN 0-7695-2666-7. S2CID 17176905.
↑ Edmonds, Jack; Johnson, Ellis L. (December 1973). "मिलान, यूलर पर्यटन और चीनी डाकिया". Mathematical Programming. 5 (1): 88–124. doi:10.1007/bf01580113. ISSN 0025-5610. S2CID 15249924.
↑ Corberán, Ángel (2015). Arc Routing: Problems, Methods, and Applications. ISBN 978-1-61197-366-2.
↑ Papadimitriou, Christos H. (July 1976). "एज ट्रैवर्सिंग की जटिलता पर". Journal of the ACM. 23 (3): 544–554. doi:10.1145/321958.321974. ISSN 0004-5411. S2CID 8625996.
↑ Randolph., Ford, Lester (2016). नेटवर्क में प्रवाह. Princeton University Press. ISBN 978-1-4008-7518-4. OCLC 954124517.{{cite book}}: CS1 maint: multiple names: authors list (link)
↑ Frederickson, Greg N. (July 1979). "कुछ डाकिया समस्याओं के लिए सन्निकटन एल्गोरिदम". Journal of the ACM. 26 (3): 538–554. doi:10.1145/322139.322150. ISSN 0004-5411. S2CID 16149998.
↑ Raghavachari, Balaji; Veerasamy, Jeyakesavan (January 1999). "A 3/2-Approximation Algorithm for the Mixed Postman Problem". SIAM Journal on Discrete Mathematics. 12 (4): 425–433. doi:10.1137/s0895480197331454. ISSN 0895-4801.
↑ Zaragoza Martinez, Francisco (2006). "किनारों पर प्रतिबंध के साथ मिश्रित डाकिया समस्या की जटिलता". 2006 Seventh Mexican International Conference on Computer Science. IEEE: 3–10. doi:10.1109/enc.2006.9. ISBN 0-7695-2666-7. S2CID 17176905.
↑ Zaragoza Martinez, Francisco (September 2006). "आर्क्स पर प्रतिबंधों के साथ मिश्रित डाकिया समस्या की जटिलता". 2006 3rd International Conference on Electrical and Electronics Engineering. IEEE: 1–4. doi:10.1109/iceee.2006.251877. ISBN 1-4244-0402-9.
↑ Corberán, Ángel (2015). Arc Routing: Problems, Methods, and Applications. ISBN 978-1-61197-366-2.
↑ Ford, L.R. (1962). नेटवर्क में प्रवाह. Princeton, N.J.: Princeton University Press.
↑ Edmonds, Jack; Johnson, Ellis L. (December 1973). "मिलान, यूलर पर्यटन और चीनी डाकिया". Mathematical Programming. 5 (1): 88–124. doi:10.1007/bf01580113. ISSN 0025-5610. S2CID 15249924.
↑ Jiang, Hua; Kang, Lishan; Zhang, Shuqi; Zhu, Fei (2010), Cai, Zhihua; Hu, Chengyu; Kang, Zhuo; Liu, Yong (eds.), "Genetic Algorithm for Mixed Chinese Postman Problem", Advances in Computation and Intelligence, Berlin, Heidelberg: Springer Berlin Heidelberg, vol. 6382, pp. 193–199, doi:10.1007/978-3-642-16493-4_20, ISBN 978-3-642-16492-7, retrieved 2022-10-25

[1] Minieka, Edward (July 1979). "मिश्रित नेटवर्क के लिए चीनी डाकिया समस्या". Management Science. 25 (7): 643–648. doi:10.1287/mnsc.25.7.643. ISSN 0025-1909.

[2] Papadimitriou, Christos H. (July 1976). "एज ट्रैवर्सिंग की जटिलता पर". Journal of the ACM. 23 (3): 544–554. doi:10.1145/321958.321974. ISSN 0004-5411. S2CID 8625996.

[3] Zaragoza Martinez, Francisco (September 2006). "आर्क्स पर प्रतिबंधों के साथ मिश्रित डाकिया समस्या की जटिलता". 2006 3rd International Conference on Electrical and Electronics Engineering. IEEE: 1–4. doi:10.1109/iceee.2006.251877. ISBN 1-4244-0402-9.

[4] Zaragoza Martinez, Francisco (2006). "किनारों पर प्रतिबंध के साथ मिश्रित डाकिया समस्या की जटिलता". 2006 Seventh Mexican International Conference on Computer Science. IEEE: 3–10. doi:10.1109/enc.2006.9. ISBN 0-7695-2666-7. S2CID 17176905.

[5] Edmonds, Jack; Johnson, Ellis L. (December 1973). "मिलान, यूलर पर्यटन और चीनी डाकिया". Mathematical Programming. 5 (1): 88–124. doi:10.1007/bf01580113. ISSN 0025-5610. S2CID 15249924.

[6] Corberán, Ángel (2015). Arc Routing: Problems, Methods, and Applications. ISBN 978-1-61197-366-2.

[7] Papadimitriou, Christos H. (July 1976). "एज ट्रैवर्सिंग की जटिलता पर". Journal of the ACM. 23 (3): 544–554. doi:10.1145/321958.321974. ISSN 0004-5411. S2CID 8625996.

[8] Randolph., Ford, Lester (2016). नेटवर्क में प्रवाह. Princeton University Press. ISBN 978-1-4008-7518-4. OCLC 954124517.{{cite book}}: CS1 maint: multiple names: authors list (link)

[9] Frederickson, Greg N. (July 1979). "कुछ डाकिया समस्याओं के लिए सन्निकटन एल्गोरिदम". Journal of the ACM. 26 (3): 538–554. doi:10.1145/322139.322150. ISSN 0004-5411. S2CID 16149998.

[10] Raghavachari, Balaji; Veerasamy, Jeyakesavan (January 1999). "A 3/2-Approximation Algorithm for the Mixed Postman Problem". SIAM Journal on Discrete Mathematics. 12 (4): 425–433. doi:10.1137/s0895480197331454. ISSN 0895-4801.

[11] Zaragoza Martinez, Francisco (2006). "किनारों पर प्रतिबंध के साथ मिश्रित डाकिया समस्या की जटिलता". 2006 Seventh Mexican International Conference on Computer Science. IEEE: 3–10. doi:10.1109/enc.2006.9. ISBN 0-7695-2666-7. S2CID 17176905.

[12] Zaragoza Martinez, Francisco (September 2006). "आर्क्स पर प्रतिबंधों के साथ मिश्रित डाकिया समस्या की जटिलता". 2006 3rd International Conference on Electrical and Electronics Engineering. IEEE: 1–4. doi:10.1109/iceee.2006.251877. ISBN 1-4244-0402-9.

[13] Corberán, Ángel (2015). Arc Routing: Problems, Methods, and Applications. ISBN 978-1-61197-366-2.

[14] Ford, L.R. (1962). नेटवर्क में प्रवाह. Princeton, N.J.: Princeton University Press.

[15] Edmonds, Jack; Johnson, Ellis L. (December 1973). "मिलान, यूलर पर्यटन और चीनी डाकिया". Mathematical Programming. 5 (1): 88–124. doi:10.1007/bf01580113. ISSN 0025-5610. S2CID 15249924.

[16] Jiang, Hua; Kang, Lishan; Zhang, Shuqi; Zhu, Fei (2010), Cai, Zhihua; Hu, Chengyu; Kang, Zhuo; Liu, Yong (eds.), "Genetic Algorithm for Mixed Chinese Postman Problem", Advances in Computation and Intelligence, Berlin, Heidelberg: Springer Berlin Heidelberg, vol. 6382, pp. 193–199, doi:10.1007/978-3-642-16493-4_20, ISBN 978-3-642-16492-7, retrieved 2022-10-25

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

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

Anonymous

Search

मिक्सड चायनिज पोस्टमैन प्रॉब्‌लम्‌: Difference between revisions

Namespaces

More

Page actions

Revision as of 23:59, 4 July 2023

Contents

गणितीय परिभाषा

कम्प्यूटेशनल जटिलता

यूलेरियन ग्राफ

अनुमान

औपचारिक परिभाषा

अनुमानी एल्गोरिदम

आनुवंशिक एल्गोरिथ्म

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

मिक्सड चायनिज पोस्टमैन प्रॉब्‌लम्‌: Difference between revisions

Revision as of 23:59, 4 July 2023

गणितीय परिभाषा

कम्प्यूटेशनल जटिलता

यूलेरियन ग्राफ

अनुमान

औपचारिक परिभाषा

अनुमानी एल्गोरिदम

आनुवंशिक एल्गोरिथ्म

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories