"रंग क्रॉसिंग" की संख्या को कम करने के लिए वेरटेक्स-रंग/असाइनमेंट

Question

मुझे यकीन नहीं है कि यह वास्तव में एक "रंग" समस्या है जितना कि यह असाइनमेंट/रैखिक-प्रोग्रामिंग समस्या है। मेरे पास शून्य विशेषज्ञता है, इसलिए किसी भी नोब-नेस को क्षमा करें जो अनुसरण कर सकता है। लेकिन मुझे यह महसूस हो रहा है कि इस समस्या को लगभग निश्चित रूप से हल/जांच करनी चाहिए, मुझे http://en.wikipedia.org/wiki/Category:Graph_algorithms पर कई ग्राफ़ एल्गोरिदम देखने के बाद कुछ भी नहीं मिला। मैं कुछ दिशाओं को सही दिशा में प्राप्त करने की उम्मीद कर रहा था।

"समस्या को बयान" प्रभावी ढंग से करने पर निर्भर करता:

1. ग्राफ में कोने के दो प्रकार के होते हैं: रूटर और कोर।

2. कोर केवल राउटर से जुड़े हुए हैं। प्रत्येक कोर केवल एक सिंगल राउटर से जुड़ा होता है। और प्रत्येक में उपयोगकर्ता द्वारा इनपुट/परिभाषित "रंग" होता है। (मेरी विशिष्ट समस्या में रंग 4/5 संभावित रंगों में से एक तक सीमित है)। उनका रंग बदला नहीं जा सकता है, यह एक इनपुट पैरामीटर है। (कोर नीचे दी गई छवि में वर्ग हैं)

3. रूटर कोर के साथ-साथ अन्य राउटर से जुड़े हुए हैं। उनके पास असाइन किया गया "रंग" नहीं है। रंग को असाइन करना प्रोग्राम/एल्गोरिदम के उद्देश्य का हिस्सा है। (रूटर्स नीचे दी गई छवि में गोलाकार शिखर हैं।)

4. कार्यक्रम का उद्देश्य ग्राफ में प्रत्येक राउटर को रंग असाइन करना है जैसे कि विभिन्न रंगों के शिखर के बीच "क्रॉसिंग"/किनारों की संख्या कम हो जाती है ।

(एक वैकल्पिक दृश्य:। संक्षेप में आप एक ग्राफ जहां कुछ कोने रंगीन कर रहे हैं दी जाती है, दूसरों को नहीं उद्देश्य लोगों को है कि इस तरह नहीं कर रहे हैं रंग करने के लिए है कि अलग रंग के कोने के बीच किनारों की संख्या कम किया गया है।)

मैं एक इंटीजर-रैखिक कार्यक्रम के रूप में इसे (काफी खराब रूप से सुनिश्चित कर रहा हूं) बनाने में सक्षम था और एलपी-सॉलवे का उपयोग करके समाधान/दृष्टिकोण स्थापित कर पाया। मैं भी अपने ही एक ह्युरिस्टिक है। मुझे इसे हल करने के लिए "उचित"/ज्ञात/अन्य दृष्टिकोण जानना अच्छा लगेगा ?!

बहुत धन्यवाद!

Answer 1

रंग < = 5 और राउटर की संख्या < = 10 तो आप जानवर बल का उपयोग कर सकते हैं।

5^10 विकल्पों से बहुत कम हैं, खासकर यदि डिफ़ॉल्ट रूप से आप प्रत्येक राउटर को सबसे आम रंग रंगते हैं, और फिर केवल उनमें से कुछ का रंग बदलते हैं, जहां आवश्यक हो वहां बैकट्रैकिंग।

संपादित करें: इसके अलावा एक अच्छा हैमिल्टनियन पथ एल्गोरिदम भी है जो आप शायद अपनी आवश्यकताओं के अनुरूप हो सकते हैं बशर्ते 15 से कम राउटर हों। What is the dynamic programming algorithm for finding a Hamiltonian cycle in a graph?

Answer 2

चलो दो रंगों के साथ मामले पर ध्यान केंद्रित करके शुरू करते हैं। हम इसे एस-टीmin cut के उदाहरण में बदल सकते हैं। विचार यह है कि हम एक रों नोड और एक ग्राफ में एक टी नोड नामित किया है, और हम, या तो रों समूह या टी समूह में शेष नोड्स विभाजित ऐसी है कि का योग करना चाहते हैं कि दोनों समूहों के बीच किनारे के वजन को कम किया गया है।आपके संस्करण के लिए, हमारे पास एक मास्टर पीले नोड एस और मास्टर लाल नोड टी है, और हम प्रत्येक कोर और उनके संबंधित मास्टर रंग नोड के बीच आपके मूल ग्राफ में सभी किनारों की गिनती से अधिक वजन वाले उच्च भार वाले किनारे को रखते हैं, सभी मूल किनारों के साथ वजन 1 प्रत्येक के साथ बरकरार है। उच्च लागत वाले किनारों से यह सुनिश्चित होता है कि हम कभी भी किसी भी कोर को अवैध रूप से याद नहीं करेंगे क्योंकि सभी राउटर को स्थानांतरित करना सस्ता होगा। Max flow-Min cut theorem के माध्यम से standard max flow algorithms का उपयोग करके बहुपद समय में इस समस्या को हल किया जा सकता है। सबसे अच्छा विकल्प आपके किनारे और कशेरुक गणना पर निर्भर करता है।

एकाधिक रंगों के मामले में, आप "बहुआयामी कट" समस्या को हल करने की कोशिश कर रहे हैं। यह minimum k-cut समस्या से संबंधित है, लेकिन इस समस्या के लिए मानक संदर्भ पेपर The Complexity of Multiterminal Cuts है (जो के-अप्रत्यक्ष रूप से आलेख लिंक पर है)। स्पष्ट रूप से यदि ग्राफ प्लानर है, तो 2 से अधिक रंगों के लिए, समस्या अभी भी बहुपद समय में हल करने योग्य है; अन्यथा, यह NP-hard है, इसलिए आप अपने पूर्णांक प्रोग्रामिंग सॉल्वर का भी उपयोग कर सकते हैं क्योंकि यह एक और एनपी-हार्ड समस्या है।