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

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

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

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

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

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

अभिकलनात्मक जटिलता

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

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

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

अनुमान

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

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

एक दृढ़ता से जुड़ा हुआ मिश्रित ग्राफ़ दिया गया है $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$. ध्यान दें कि $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$ सम और संतुलित है. ध्यान दें कि यदि $G$ सम और सममित है, तो G भी संतुलित है (और ऑयलेरियन)। इस प्रकार इसके अतिरिक्त, यदि $G$ सम है, द $MCPP$ बहुपद समय में बिल्कुल हल किया जा सकता है।

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

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

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

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

यह भी देखें

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