अधिकतम भारित द्विपक्षीय मिलान, बाधा: प्रत्येक ग्राफ का ऑर्डरिंग

Question

मान लें कि मेरे पास दो सेट हैं: (n_1, n_2, ...) और (m_1, m_2, ...) और मिलान मिलान फ़ंक्शन मिलान (एन, विपरीत सेट में

• प्रत्येक तत्व होना आवश्यक अधिकतम 1 मिलान किया तत्व: मीटर) है कि 0 से 1. करने के लिए एक मान देता है मैं दो सेट के बीच मानचित्रण ऐसी है कि निम्नलिखित की कमी पूरी की जाती हैं खोजना चाहते हैं।
• बेजोड़ तत्वों कीमत पर एक डमी तत्व के साथ रखा जाएगा 1
• मैच समारोह जब सभी तत्वों के लिए लागू की राशि अधिक से अधिक
• मैं मुसीबत यह औपचारिक रूप से व्यक्त कर रहा हूँ है, लेकिन यदि आप प्रत्येक सेट समानांतर खड़े एक दूसरे को अपने मूल क्रम के साथ और मिलान तत्वों के बीच एक रेखा खींचा, लाइनों में से कोई भी पार नहीं होगा। E.x. [n_1 < -> m_2, n_2 < -> m_3] एक मान्य मैपिंग है लेकिन [n_1 < -> m_2, n_2 < -> m_1] नहीं है।

(मेरा मानना ​​है कि पहले तीन मानक भारित द्विपक्षीय मिलान की कमी कर रहे हैं, लेकिन मैं उन्हें निर्दिष्ट मामले में मैं भारित द्विपक्षीय मिलान गलत समझा)

यह घातीय समय में एक संपूर्ण खोज के साथ क्या करना अपेक्षाकृत सीधे आगे है (सेट के आकार के संबंध में), लेकिन मैं एक बहुपद समय की उम्मीद कर रहा हूं (आदर्श ओ ((| एन | * | एम |)^3) या बेहतर) समाधान मौजूद है।

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

Answer 1

इस समस्या का अध्ययन "अधिकतम वजन गैर-क्रॉसिंग मिलान" नाम से किया गया है। एक साधारण वर्गबद्ध समय गतिशील कार्यक्रम है। चलो एम (ए, बी) एक इष्टतम मिलान का मूल्य n पर हो , ..., n _एक और मीटर , ..., मीटर _ख। हम पुनरावृत्ति

एम है (0, ख) = बी
एम (एक, 0) = -एक
एम (ए, बी) = अधिकतम {M (एक - 1, बी - 1) + मैच (ए, बी), एम (ए -1, बी) - 1, एम (ए, बी -1) - 1}।

Argmaxes को वापस ढूंढकर, आप इसके मूल्य से इष्टतम समाधान पुनर्प्राप्त कर सकते हैं।

यदि मिलान -1 से अधिक प्रविष्टियों की श्रेणीबद्ध संख्या से काफी कम है, तो एक एल्गोरिदम है जो उपयोगी प्रविष्टियों की संख्या में समय रैखिक रूप से चलता है (Khoo and Cong, A Fast Multilayer General Area Router for MCM Designs)।