Mixed Chinese postman problem
मिश्रित चीनी डाकिया समस्या (एम. सी. पी. पी. या एम. सी. पी.) शीर्षों वी के एक समूह के साथ एक ग्राफ के सबसे छोटे पारगमन की खोज है, सकारात्मक तर्कसंगत भार के साथ दिशाहीन किनारों ई का एक समूह, और सकारात्मक तर्कसंगत भार के साथ निर्देशित चाप ए का एक समूह जो प्रत्येक किनारे या चाप को कम से कम एक बार न्यूनतम लागत पर कवर करता है। पापदिमित्रिउ द्वारा समस्या को एन. पी.-पूर्ण साबित किया गया है। मिश्रित चीनी डाकिया समस्या अक्सर बर्फ की जुताई जैसी चाप मार्ग समस्याओं में उत्पन्न होती है, जहां कुछ सड़कें दोनों दिशाओं में पार करने के लिए बहुत संकीर्ण होती हैं जबकि अन्य सड़कें द्विदिश होती हैं और दोनों दिशाओं में जुताई की जा सकती हैं। यह सत्यापित करना आसान है कि क्या एक मिश्रित ग्राफ में किसी भी आकार का डाकिया दौरा है या नहीं, यह सत्यापित करके कि क्या ग्राफ दृढ़ता से जुड़ा हुआ है। समस्या एन. पी. कठिन है यदि हम डाकिये के दौरे को प्रत्येक चाप को ठीक एक बार पार करने के लिए प्रतिबंधित करते हैं या यदि हम इसे प्रत्येक किनारे को ठीक एक बार पार करने के लिए प्रतिबंधित करते हैं, जैसा कि जरागोजा मार्टिनेज द्वारा साबित किया गया है। गणितीय परिभाषा गणितीय परिभाषा हैः इनपुटः प्रत्येक किनारे के लिए लागत और अधिकतम लागत के साथ एक दृढ़ता से जुड़ा हुआ, मिश्रित ग्राफ। प्रश्नः क्या कोई (निर्देशित) दौरा है जो कम से कम एक बार में हर किनारे और हर चाप को पार करता है और इसमें अधिक से अधिक लागत आती है? कम्प्यूटेशनल जटिलता मिश्रित चीनी डाकिया समस्या को हल करने में मुख्य कठिनाई (दिशाहीन) किनारों के लिए अभिविन्यास चुनने में निहित है जब हमें अपने दौरे के लिए एक तंग बजट दिया जाता है और हम प्रत्येक किनारे को केवल एक बार पार कर सकते हैं। फिर हमें किनारों को उन्मुख करना होगा और कुछ और चाप जोड़ना होगा ताकि एक निर्देशित यूलरियन ग्राफ प्राप्त किया जा सके, यानी प्रत्येक शीर्ष को संतुलित किया जा सके। यदि एक शीर्ष पर कई किनारे होते हैं, तो प्रत्येक किनारे का सही अभिविन्यास निर्धारित करना आसान काम नहीं है। गणितशास्त्री पापाडिमित्रिउ ने अधिक प्रतिबंधों के साथ इस समस्या का विश्लेषण किया; "मिश्रित चीनी पोस्टमैन एन. पी.-पूर्ण है, भले ही इनपुट ग्राफ समतल हो, प्रत्येक शीर्ष में अधिकतम तीन डिग्री होती है, और प्रत्येक किनारे और चाप की लागत एक होती है।" यूलरियन ग्राफ यह जाँचने की प्रक्रिया कि क्या एक मिश्रित ग्राफ यूलरियन है, मिश्रित चीनी डाकिया समस्या को हल करने के लिए एक एल्गोरिथ्म बनाने के लिए महत्वपूर्ण है। एक मिश्रित ग्राफ जी की डिग्री एक यूलरियन चक्र होने के लिए सम होनी चाहिए, लेकिन यह पर्याप्त नहीं है। अनुमान यह तथ्य कि मिश्रित चीनी डाकिया एन. पी.-कठोर है, ने बहुपद समय एल्गोरिदम की खोज को प्रेरित किया है जो उचित सीमा तक इष्टतम समाधान तक पहुँचते हैं। फ्रेडरिकसन ने 3/2 के कारक के साथ एक विधि विकसित की जिसे समतलीय ग्राफ पर लागू किया जा सकता है, और राघवचारी और वीरासामी ने एक ऐसी विधि की खोज की जिसे समतलीय होने की आवश्यकता नहीं है। हालांकि, बहुपद समय में सिर कलम करने की लागत नहीं मिल सकती है, सड़कों तक पहुंचने के लिए एक बर्फ के हल में लगने वाले समय में यह हल करेगा या सड़कों पर पहुंचने के लिए एक सड़क सफाई करने वाला यह झाड़ू लगाएगा। औपचारिक परिभाषा एक शीर्ष समूह के साथ एक मजबूत रूप से जुड़े मिश्रित ग्राफ, और किनारे सेट, एक चाप सेट और प्रत्येक के लिए एक गैर-नकारात्मक लागत को देखते हुए, एम. सी. पी. पी. में कम से कम एक बार प्रत्येक लिंक से गुजरने के लिए एक न्यूनतम लागत वाला दौरा खोजना शामिल है। दिए गए,,, और में बिल्कुल एक अंतिम बिंदु के साथ किनारों के समूह को दर्शाता है। एक शीर्ष को देखते हुए, (इंडेग्री) प्रवेश करने वाले चापों की संख्या को दर्शाता है, (आउट डिग्री) छोड़ने वाले चापों की संख्या है, और (डिग्री) के साथ जुड़ने वाले लिंक की संख्या है। इस पर ध्यान दें। एक मिश्रित ग्राफ को कहा जाता है, भले ही इसके सभी शीर्षों में सम डिग्री हो, इसे सममित कहा जाता है यदि प्रत्येक शीर्ष के लिए, और इसे संतुलित कहा जाता है यदि, शीर्षों के किसी भी उपसमुच्चय को देखते हुए, से निर्देशित चापों की संख्या, और से निर्देशित चापों की संख्या के बीच का अंतर, और से जुड़ने वाले दिशाहीन किनारों की संख्या से अधिक नहीं है। यह एक सर्वविदित तथ्य है कि एक मिश्रित ग्राफ यूलरियन है यदि और केवल तभी जब वह सम और संतुलित हो। ध्यान दें कि यदि सम और सममित है, तो G भी संतुलित (और यूलरियन) है। इसके अलावा, यदि सम है, तो बहुपद समय में ठीक से हल किया जा सकता है। यहाँ तक कि एम. सी. पी. पी. एल्गोरिदम एक सम और दृढ़ता से जुड़े मिश्रित ग्राफ को देखते हुए, समान लागतों के साथ किनारों को यादृच्छिक रूप से एक दिशा निर्धारित करके प्राप्त चापों का सेट होने दें। निर्देशित ग्राफ में प्रत्येक शीर्ष i के लिए गणना करें। के साथ एक शीर्ष को आपूर्ति मांग के साथ एक स्रोत (सिंक) के रूप में माना जाएगा। ध्यान दें कि एक सम ग्राफ के रूप में, सभी आपूर्ति और मांग सम संख्याएँ हैं (शून्य को एक सम संख्या माना जाता है)। मान लीजिए कि उन संबंधित किनारों की लागत के साथ और उनके विपरीत दिशा में चापों का समूह है, और शून्य लागत पर समानांतर चापों का समूह है। सभी शीर्षों की मांगों को पूरा करने के लिए, ग्राफ में न्यूनतम लागत प्रवाह समस्या को हल करें, जिसमें प्रत्येक चाप में अनंत क्षमता होती है और प्रत्येक चाप में क्षमता 2 होती है। इष्टतम प्रवाह होने दें। इन में प्रत्येक चाप के लिएः यदि, तो संबंधित किनारे को एक से दूसरे की ओर उन्मुख करें (चरण 1 में संबंधित किनारे को दी गई दिशा, "गलत" थी); यदि, तो जी में संबंधित किनारे को एक से दूसरे की ओर उन्मुख करें (इस मामले में, चरण 1 में अभिविन्यास "सही" था)। ध्यान दें कि मामला असंभव है, क्योंकि चापों के माध्यम से सभी प्रवाह मान सम संख्याएँ हैं। प्रत्येक चाप की प्रतियों को जोड़कर वृद्धि करें। परिणामी ग्राफ सम और सममित है। ह्यूरिस्टिक एल्गोरिदम जब मिश्रित ग्राफ सम नहीं होता है और सभी नोड्स में सम डिग्री नहीं होती है, तो ग्राफ को सम ग्राफ में बदला जा सकता है। माना कि यह एक मिश्रित ग्राफ है जो दृढ़ता से जुड़ा हुआ है। चाप दिशाओं को नजरअंदाज करके विषम डिग्री नोड्स का पता लगाएं और न्यूनतम लागत वाला मिलान प्राप्त करें। एक सम ग्राफ उत्पन्न करने के लिए न्यूनतम लागत मिलान से किनारों के साथ ग्राफ को बढ़ाएं। ग्राफ सम है लेकिन सममित नहीं है और एक यूलरियन मिश्रित ग्राफ सम और सममित है। एक सममित ग्राफ प्राप्त करने के लिए न्यूनतम लागत प्रवाह समस्या को हल करें जो सम नहीं हो सकता है। अंतिम चरण में सममित ग्राफ को समान बनाना शामिल है। विषम डिग्री नोड्स को लेबल करें। चाप सेट में रेखाओं और किनारे सेट में रेखाओं के बीच वैकल्पिक चक्रों का पता लगाएं जो अंदर के बिंदुओं पर शुरू और समाप्त होते हैं। अंदर के चापों को दिशाहीन किनारों के रूप में माना जाना चाहिए, न कि निर्देशित चाप के रूप में। आनुवंशिक एल्गोरिथ्म हुआ जियांग एट द्वारा प्रकाशित एक पेपर। अल ने एक आबादी पर काम करके मिश्रित चीनी डाकिया समस्या को हल करने के लिए एक आनुवंशिक एल्गोरिथ्म तैयार किया। एम. सी. पी. पी. के लिए अन्य सन्निकटन एल्गोरिदम की तुलना में एल्गोरिदम ने अच्छा प्रदर्शन किया। कैपेसिटेड आर्क रूटिंग समस्या भी देखें संदर्भ ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं