प्राथमिकता आधारित समूह

Question

के लिए एल्गोरिदम मैं लोगों को वरीयताओं से कक्षाओं में वर्गीकृत करने का एक तरीका समझने के लिए देख रहा हूं।

उदाहरण के लिए, 100 छात्रों कि प्रत्येक पाँच वर्गों में से एक आवंटित करने के लिए जा रहे हैं देखते हैं:

• विज्ञान - 40 सीटों
• मठ - 15 सीटों
• इतिहास - 15 सीटों
• कंप्यूटर्स - 20 सीटें
• लेखन - 10 सीटें

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

मैं निम्न विधि द्वारा यह आ के बारे में सोचा है:

1. समूह उनकी पहली पसंद वर्ग
2. देखें द्वारा सभी छात्रों को जो कक्षाएं भी कई छात्रों है और जो करने के लिए बहुत कुछ
3. चेक राशि देखें कि ओवरबुक बुक किए गए वर्गों में से किसी भी छात्र के पास दूसरी पसंद कक्षाएं हैं जो
4. उन छात्रों को तदनुसार
5. दो विकल्प विकल्प के साथ 2-4 दोहराएं

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

Answer 1

अपने विवरण से, यह बहुत ज्यादा Stable Marriage Problem

के रूपांतरों विकी लिंक की जाँच करें और आप आंधी-Shapley एल्गोरिथ्म, जो एक अच्छा है का एक विवरण देखेंगे में से एक की तरह लगता है उपाय।