एल्गोरिदम तीन

Question

के समूहों में पसंदीदा भागीदारों से मेल खाने के लिए इस समस्या को हल करने के लिए एक अच्छा एल्गोरिदम क्या है?

मेरे पास तीन समूह हैं - समूह ए, समूह बी, और समूह सी। प्रत्येक समूह में समान संख्या में लोग हैं। उनमें से प्रत्येक के पास अन्य समूहों में लोगों की एक सूची है जो वे काम करने के इच्छुक हैं। मैं इन सभी लोगों को 3 के समूहों में समूहित करना चाहता हूं (ए से एक, बी से एक, और सी से एक) जैसे कि समूह में हर कोई अपने समूह के अन्य लोगों के साथ काम करना चाहता है।

मैं इन समूहों को तेजी से कैसे ढूंढ सकता हूं? अगर सभी को खुश करने का कोई तरीका नहीं है, तो एल्गोरिदम को पहले कई समूहों को तीन लोगों के साथ काम करना चाहिए जो एक-दूसरे के साथ काम करना चाहते हैं, और फिर अन्य समूहों में बहुत से लोगों को खुश कर दें।

एक अंतिम बिंदु: लोग इस बात पर सहमत हैं कि वे किसके साथ काम करना चाहते हैं (यदि व्यक्ति एक्स व्यक्ति के साथ काम करना चाहता है, तो y भी x के साथ काम करना चाहता है)। यदि आप अपने एल्गोरिदम के चलने वाले समय का बड़ा-ओ भी दे सकते हैं, तो यह बहुत अच्छा होगा!

Answer 1

यह स्थिर विवाह समस्या की तरह है, लेकिन दो के बजाय 3 पार्टियों के साथ।

पूर्व समस्या (द्वि-अंशबद्ध ग्राफ मिलान) के लिए कुशल समाधानों पर नज़र डालें और उन्हें अपनी आवश्यकताओं के अनुसार अनुकूलित करें।

http://en.wikipedia.org/wiki/Stable_marriage_problem

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

सर्वोत्कृष्ट समाधान k-partite को मिलान खोजने के लिए एनपी कठिन है:

http://books.google.com/books?id=wqs31L1MF4IC&pg=PA309&lpg=PA309&dq=k-partite+matching&source=bl&ots=kgBuvi7ym_&sig=j3Y-nyo51y8qp0-HwToyUlkao4A&hl=de&sa=X&oi=book_result&resnum=1&ct=result:

http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps

k-partite मिलान समस्या के लिए एक गैर इष्टतम समाधान के लिए इस पत्र देखें

मुझे यकीन है कि आप Google पर अपने आप को अन्य लोगों को ढूंढ सकते हैं जिन्हें आप खोजना चाहते हैं। मुझे नहीं पता कि एक कुशल एल्गोरिदम है जो के = 3 के लिए इष्टतम समाधान दे रहा है।

Answer 2

यह स्थिर विवाह समस्या के विस्तार से अलग है, क्योंकि जब मैं ओपी के प्रश्न को समझता हूं, तो प्रत्येक समूह के लोगों के पास आदेश की सूची नहीं होती है कि वे सबसे कम से कम किसके साथ काम करना चाहते हैं; यह एक द्विआधारी संबंध है (तैयार/इच्छुक नहीं)।

इसे एक पूर्णांक प्रोग्रामिंग समस्या के रूप में तैयार किया जा सकता है जिसे बहुत जल्दी हल किया जा सकता है। मैं नीचे की समस्या का गणितीय फॉर्मूलेशन देता हूं; आप डेटा को संसाधित करने के लिए glpk या AMPL/CPLEX जैसे पैकेज का उपयोग कर सकते हैं।

निम्नलिखित मैट्रिक्स को परिभाषित करें:

M1 = |A| x |B| मैट्रिक्स, जहां

M1(a,b) = 1 अगर एक (ए के दिए गए सदस्य) ख के साथ काम करने को तैयार है (बी के सदस्य दी गयी है), और अन्यथा 0

M2 = |A| x |C| मैट्रिक्स, जहां M2(a,c) = 1 अगर एक (ए के दिए गए सदस्य) ग के साथ काम करने को तैयार है (दिए गए सी के सदस्य), और 0 अन्यथा

M2 = |B| x |C| मैट्रिक्स, क

: पहले

M3(b,c) = 1 यदि ख (बी के सदस्य दी गयी है) ग (सी के दिए गए सदस्य) के साथ काम करने को तैयार है, और 0 अन्यथा

अब एक नया मैट्रिक्स हम अपने अधिकतम के लिए इस्तेमाल करेगा परिभाषित X = |A| x |B| x |C| मैट्रिक्स, जहां

X(a,b,c) = 1 यदि हम एक, बी, और सी एक साथ काम करते हैं।

अब, हमारा उद्देश्य समारोह को परिभाषित: रख दिया जाता है

// है कि कोई भी सुनिश्चित करने के लिए:

// समूहों

की संख्या को अधिकतम अधिकतम निम्नलिखित की कमी के Sum[(all a, all b, all c) X(a,b,c)]

विषय दो समूहों में

सभी के मानों के लिए: Sum[(all j, k) X(a, j, k)] <= 1

ख के सभी मानों के लिए: Sum[(all i, k) X(i, b, k)] <= 1

ग के सभी मानों के लिए: Sum[(all i, j) X(i, j, c)] <= 1

// यह सुनिश्चित करना कि सभी समूहों संगत व्यक्तियों

सब एक, ख, ग के लिए से बने होते हैं: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3

Answer 3

आरंभ करने के लिए, आप किसी भी तथ्य को खत्म कर सकते हैं जहां दोनों पक्षों के पास तीसरे समूह में किसके साथ काम करेगा, इस सूची को अलग कर सकते हैं। फिर एक क्रूर बल शुरू करें, गहराई की पहली खोज, हमेशा कम से कम लोकप्रिय से सबसे लोकप्रिय चुनना।

वैकल्पिक रूप से, उपरोक्त उन्मूलन के बराबर, सभी संभावित तीनों की सूची बनाएं और इसके बजाय कार्य करें।

Answer 4

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

Answer 5

मैं एक समान समस्या में भाग गया और सिर्फ एक स्क्रिप्ट लिखी जो इसे बलपूर्वक बल देता है ...http://grouper.owoga.com/

मेरे शुरुआती विचार थे: एक बड़े समूह के लिए जो बलपूर्वक बल के लिए बहुत बड़ा था, कुछ प्रकार के अनुवांशिक एल्गोरिदम? एन यादृच्छिक स्वैप एम बार बनाओ। कुछ 'खुशी' समारोह द्वारा प्रत्येक नई व्यवस्था को स्कोर करें। सबसे अच्छा कुछ, नस्ल, दोहराना ले लो।

छोटे समूहों के लिए मैंने कुछ समूहों पर लूपिंग करके बेहतर परिणाम प्राप्त कर लिया, 'सर्वश्रेष्ठ' स्वैप (जिसने उच्चतम समग्र 'खुशी' लाभ अर्जित किया) को ढूंढकर, फिर दोहराया।