खिलाड़ी की पसंद के आधार पर टीम को असाइन करने के लिए एल्गोरिदम

Question

मुझे यहां बहुत ही समान प्रश्न मिले लेकिन मुझे कोई समाधान नहीं मिला जो मेरे लिए काम करेगा। तो यहां समस्या है:

मेरे पास 4 टीमें और एक विशाल (4 से अधिक) खिलाड़ियों की संख्या है। प्रत्येक खिलाड़ी को अपनी पसंद के हिसाब, उदाहरण के द्वारा टीमों में शुमार है:

1. टीम बी
2. टीम डी
3. टीम ए
4. टीम सी

अंत मैं चाहता हूँ में सम संख्या है करने के लिए प्रत्येक टीम में खिलाड़ियों के लेकिन उनके विकल्पों से भारित।

यह एक हंगेरियन एल्गोरिदम है, नौकरियों की तुलना में अधिक पुरुषों के साथ। क्या कोई मुझे इसके लिए एल्गोरिदम खोजने में मदद कर सकता है? मैं लंबे समय से खोज कर रहा हूं।

Answer 1

आप इसे 1-0 पूर्णांक प्रोग्रामिंग समस्या के प्रकार के रूप में प्रस्तुत कर सकते हैं।

x_N टीम असाइनमेंट का वर्णन करने वाले वेक्टर बनने दें: व्यक्ति मैं टीम वाई पर हूं यदि x_Y (i) = 1, और यदि वे टीम वाई पर नहीं हैं तो x_Y (i) = 0. | x_Y | = एन, जहां एन खिलाड़ियों की संख्या है।

इसके अलावा, p_Y टीम वाई के लिए प्लेयर की वरीयता वेटिंग होने दें, ताकि p_Y (i) = 4 अगर खिलाड़ी मैं वास्तव में टीम वाई पर होना चाहता हूं, और p_Y (i) = 1 अगर वे नहीं चाहते हैं टीम वाई

पर हो (आप भारित वरीयताओं 1 और 4 को जो भी हो, उसे प्रतिस्थापित कर सकते हैं, वे केवल एक उदाहरण हैं)।

एक एल्गोरिद्म जो हल करती है तुम्हारी समस्या क्या करना चाहिए निम्नलिखित:

अधिकतम: x_A * p_A + x_B * p_B + x_C * p_C + x_D * p_D

के अधीन रहते हुए: x_A + x_B + x_C + x_D = 1 (एन के साथ वेक्टर)

और x_Y (i) {0, 1} में {ए, बी, सी, डी} में सभी वाई के लिए, मैं {1, ..., एन}

में

आप जो अधिकतम कर रहे हैं वह वास्तव में असाइनमेंट और वरीयता मैट्रिस के मैट्रिक्स उत्पाद का पता लगाने वाला है, जो एक सेमेडिफिन पूर्णांक प्रोग्रामिंग अल है gorithm। मुझे पूरा यकीन है कि एनपी-हार्ड है।

इसे हल करने के लिए एक ह्युरिस्टिक को यादृच्छिक रूप से टीमों के बराबर संख्या में खिलाड़ियों को असाइन करना है। फिर, यदि आप उद्देश्य कार्य में वृद्धि करते हैं तो आप टीमों के बीच "व्यापार" की एक श्रृंखला बना सकते हैं। बेहतर अभी तक, आप बहुपद समय में पता लगा सकते हैं कि व्यापार किसी दिए गए असाइनमेंट पर सबसे अच्छा है। यह आपको इष्टतम असाइनमेंट नहीं देगा, लेकिन मुझे लगता है कि यह आपको बहुत करीब ले जाएगा।

इस विधि, वैसे, hill climbing पर एक भिन्नता है। असल में, इनमें से किसी भी अन्य heuristic methods में इस समस्या के संदर्भ में एक समान एनालॉग होगा।

Answer 2

अंकन:

प्लेयर सरणी: p[1], ..., p[n]

टीम सरणी: T[1], T[2], T[3], T[4]

इच्छा मैट्रिक्स: w[i,j]; आयाम = nx4; w[i,j] = टीम Tj में pi की इच्छा। यहां धारणा है कि w[i,1] + w[i,2] + w[i,3] + w[i,4] = 1 सभी i के लिए।

सदस्यता मैट्रिक्स: x[i,j], आयाम = nx4; x[i,j]=1 या 0 निर्भर करता है कि piTj में है या नहीं।

संतुष्टि सरणी: s[1], ..., s[n]; s[i] := w[i,1] * x[i,1] + ... + w[i,4] * x[i,4]।

संतुष्टि: s := (s[1] + ... + s[n])/n।

ऑपरेशन:

मान लें निम्नलिखित:

1. x[k,q] = 1 (p[k]T[q] में अंतर्गत आता है)
2. x[k,r] = 0 (p[k]T[r]
3. x[h,r] = 1 में नहीं है (p[h]में अंतर्गत आता है)
4. x[h,q] = 0 (p[h]T[q]

आपरेशन swap([k,q][h,r]) इंटरचेंज खिलाड़ियों p[k] और p[h] टीमों T[q] और T[r] के बीच में नहीं है। यह है:

1. x[k,q] := 0, x[k,r] := 1।
2. x[h,r] := 0, x[h,q] := 1।
3. s[k] := s[k] - w[k,q] + w[k,r], s[h] = s[h] - w[h,r] + w[h,q]।
4. s := (s * n - w[k,q] - w[h,r] + w[h,r] + w[k,q])/n।

अब आप संतुष्टि s को अधिकतम करने के लिए सिम्युलेटेड एनीलिंग का उपयोग करने के लिए तैयार हैं।किसी भी विन्यास (के रूप में वे दिखाई देंगे टीमों के लिए खिलाड़ियों आवंटित)

साथ

1. प्रारंभ एक तापमान की स्थापना

2. दो जोड़े [k,q] और [h,r] पर उठाओ: यहाँ एल्गोरिथ्म के एक संक्षिप्त वर्णन है यादृच्छिक

3. swap आपरेशन की कोशिश करो। अगर संतुष्टि s बढ़ जाती है, तो स्वैप स्वीकार करें। यदि ऐसा नहीं होता है, तो इसे केवल कुछ संभावना के साथ स्वीकार करें, अन्यथा स्वैप को अस्वीकार करें (विवरण के लिए सिम्युलेटेड एनीलिंग एल्गोरिदम देखें)

4. कई बार चरण 3 और 4 दोहराएं।

5. तापमान में कमी और 3.

टिप्पणी के लिए वापस जाओ:

खिलाड़ियों रेंज 1, ..., 4 में वरीयताओं (या किसी अन्य,) हर खिलाड़ी के लिए विभाजन उन संख्याओं द्वारा है उनमें से प्रत्येक की इच्छा वेक्टर प्राप्त करने के लिए उनकी राशि बाधा w[i,1] + ... + w[i,4] = 1 को संतुष्ट करती है।

दो जोड़े [h,q] और [k,r] के यादृच्छिक चयन swap ऑपरेशन की मान्यताओं को पूरा करना होगा। तो, यह मूल रूप से तो दो खिलाड़ियों के प्रत्येक टीम में एक यादृच्छिक (q और r) पर दो टीमों और चुनने में होते हैं।

swap संचालन में चरण 3 और 4 रकम और उत्पादों की संख्या को कम करने के लिए आवश्यक हैं, इसलिए स्वैप परीक्षण तेजी से हैं।

एक swap सिर्फ swap फिर से वही जोड़े अस्वीकार करने के लिए,।