लोगों को सबसे संतुष्टि के लिए टीमों में विभाजित करें

Question

बस एक जिज्ञासा प्रश्न। याद रखें जब कक्षा समूह में प्रोफेसर लोगों को एक निश्चित संख्या (n) के समूहों में विभाजित करेगा?

मेरी प्रोफेसरों में से कुछ n लोग एक साथ काम करना चाहता है और n लोगों की एक सूची ले जाएगा एक-एक छात्र से साथ काम नहीं करना चाहता है, और फिर जादुई n के समूहों जहां छात्रों के साथ मिलान किया जाएगा बाहर बारी वे लोग जो पसंद करते हैं और उन लोगों के साथ काम करने से बचते हैं जिन्हें वे पसंद नहीं करते हैं।

मेरे लिए यह एल्गोरिदम एक नापसैक समस्या की तरह बहुत कुछ लगता है, लेकिन मैंने सोचा कि मैं इस तरह की समस्या के बारे में आपके दृष्टिकोण के बारे में पूछूंगा।

EDIT: an ACM article मिला मेरे प्रश्न की तरह कुछ वर्णन करता है। देजा वी के लिए दूसरा पैराग्राफ पढ़ें।

Answer 1

मेरे लिए यह clique समस्या की तरह कुछ लगता है।

तरह से मैं समस्या देखते हैं, मैं की स्थापना की थी निम्नलिखित graph:

• कोने छात्रों होगा
• दो छात्रों को एक बढ़त से जुड़ा होगा अगर इन निम्नलिखित बातें दोनों पकड़:
  1. कम से कम दो छात्रों में से एक दूसरे के साथ काम करना चाहता है।
  2. दो में से कोई भी छात्र दूसरे के साथ काम नहीं करना चाहता।

यह तो आकार n का क्लिक्स में ग्राफ विभाजन की बात है।

(छात्रों की संख्या मान लिया जाये कि एन से विभाज्य है) यदि यह संभव नहीं था, मैं शायद किनारों पर्ची पर पहले बाधा जाने चाहते हैं, और जब तक उनमें से कोई भी स्पष्ट रूप से कहा गया है कि दो लोगों के बीच किनारों है वे दूसरे के साथ काम नहीं करना चाहते हैं।

इस कुशलता से हल करने के लिए एक दृष्टिकोण के रूप में, मुझे कोई जानकारी नहीं है, लेकिन उम्मीद है कि आपको समस्या में कुछ अंतर्दृष्टि के करीब आना चाहिए।

Answer 2

यह समस्या क्रूर-मजबूर हो सकती है, इसलिए मेरा दृष्टिकोण बलपूर्वक बलपूर्वक होगा, फिर मुझे बेहतर विचार मिलने पर इसे ठीक करें।

Answer 3

आप एक क्लस्टरिंग समस्या के रूप में बहुत आसानी से इस मॉडल सकता है और तुम भी वास्तव में एक अंतरिक्ष परिभाषित करने की जरूरत नहीं है, आप वास्तव में सिर्फ दूरी निर्धारित कर सकते हैं:

दो लोगों को बहुत करीब बनाओ अगर वे दोनों काम करना चाहते हैं साथ में। अगर उनमें से एक दूसरे के साथ काम करना चाहता है तो बंद करें। मध्यम दूरी अगर केवल उदासीनता है। दूर अगर कोई अन्य के साथ काम नहीं करना चाहता है।

तब आप क्लस्टर ढूंढ सकते हैं, याय। फिर बड़े पैमाने पर बड़े आकार के किसी भी समूह को विभाजित करें, विश्वास के साथ कि क्लस्टर में लोग सभी एक साथ काम कर रहे होंगे।

Answer 4

कुछ एल्गोरिदम आप उपयोग कर सकते हैं। एक महान उदाहरण तथाकथित "स्थिर विवाह समस्या" है, जिसका एक आदर्श समाधान है।आप यहाँ इसके बारे में अधिक पढ़ सकते हैं:

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

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

लेकिन आपने एक टीम के लिए पूछा (जिसे मैं प्रति टीम 2 लोगों में अनुवाद करता हूं)। इस मामले में आप सभी को सबसे खराब मैच में सबसे अच्छा भरने दे सकते हैं और फिर