समूह सौंपना

Question

मुझे एक समस्या है जहां मैं सेट करने के लिए चर असाइन करने के लिए हूं। प्रत्येक सेट में चर की एक सीमा होती है जिसे इसे सौंपा जा सकता है और प्रत्येक चर को कुल सेट के कुछ सबसेट को सौंपा जा सकता है।

उदाहरण:

• aसेट में हो सकता है AयाB
• b सेट में हो सकता है B
• cसेट में हो सकता है AयाB
• d सेट में हो सकता है A

इस प्रकार, हम कर सकते हैं A: a, d; B: b, cया A: c, d; B: a,b(सेट के भीतर चर का क्रम कोई फर्क नहीं पड़ता) / /

बेशक, ऐसे समय होंगे जब सभी चर को निर्दिष्ट करना असंभव है, ऐसे समय जब हमारे पास कई विकल्प हैं, और केवल 1 विकल्प के साथ समय है।

मुझे लगता है कि इस समस्या का एक सरल संस्करण है, लेकिन मैं इस पर अपनी उंगली नहीं रख सकता। कोई भी संकेतक प्रशंसनीय होंगे।

Answer 1

अधिकतम प्रवाह का उपयोग कर कुशलता से हल करने योग्य। एक स्रोत से प्रत्येक चर के लिए एक इकाई क्षमता चाप के साथ एक प्रवाह नेटवर्क तैयार करें, प्रत्येक चर से प्रत्येक के लिए एक इकाई क्षमता चाप, जिसमें यह हो सकता है, और प्रत्येक सेट से एक आर्क सेट की क्षमता के बराबर क्षमता के सिंक के लिए। । उदाहरण के लिए,

ARCS

tail head capacity
------------------
s    a    1
s    b    1
s    c    1
s    d    1
a    A    1
a    B    1
b    B    1
c    A    1
c    B    1
d    A    1
A    t    2
B    t    2

अपने पसंदीदा अधिकतम प्रवाह एल्गोरिथ्म का उपयोग करें जो एक अभिन्न प्रवाह का उत्पादन करता है और असाइनमेंट को निकालता है जिसके अनुसार चर सेट करने के लिए चर प्रवाह होता है।

Answer 2

यह समस्या एनपी-पूर्ण है जिसका अर्थ है कि इसके लिए कोई बहुपद समय समाधान नहीं है। आपको इस मामले में बैकट्रैकिंग का उपयोग करना होगा।

इन लिंक पर एक नजर:

https://www.geeksforgeeks.org/vertex-cover-problem-set-1-introduction-approximate-algorithm-2/ https://www.geeksforgeeks.org/set-cover-problem-set-1-greedy-approximate-algorithm/