मैं पाइथन में स्विस टूर्नामेंट सिस्टम पर काम कर रहा हूं और मैं एक इष्टतम जोड़ी एल्गोरिदम को समझने की कोशिश कर रहा हूं।
मेरी सबसे बड़ी समस्या यह है कि प्रत्येक एल्गोरिदम मैं कुछ अनुक्रमों में उत्पादित त्रुटि के साथ आया था, जहां आखिरी जोड़ी को चुनने के लिए पहले से ही एक-दूसरे को खेला गया है, यह तय करना कि युग्मन अमान्य है।स्विस टूर्नामेंट - जोड़ी एल्गोरिदम
जिस स्विस सिस्टम पर मैं काम कर रहा हूं वह सरल है: यहां तक कि खिलाड़ी, प्रत्येक दौर में हर कोई खेलता है और जोड़ी जीतने की निकटता के आधार पर किया जाता है (इसलिए मजबूत खिलाड़ी मजबूत खिलाड़ियों के खिलाफ खेलते हैं, और कमज़ोर के खिलाफ कमजोर होते हैं)।
कोई अलविदा, केवल जीत/हार (कोई ड्रॉ नहीं), विरोधी एक दूसरे को दो बार नहीं खेल सकते हैं।
वर्तमान एल्गोरिथ्म मैं इस प्रकार काम करता है क्या किया:
- क्रम रैंकिंग से एक खिलाड़ियों की सूची का उत्पादन (कम से कम करने के लिए जीत में सर्वाधिक जीत हासिल)
- पिक खिलाड़ी, सबसे जीत के साथ खिलाड़ी से शुरू
- मैच उसे निकटतम रैंकिंग खिलाड़ी के साथ। अगर वे पहले से ही खेला जाता है, ऐसे ही किसी के साथ उसे मेल खाते हैं जब तक कोई मिलान पाया जाता
को सूची से बाहर जोड़ी पॉप और वापस उदाहरण के लिए:
रैंकिंग 2 के बाद दौर:
1. P1: [P2 win, P3 win] 2 wins
2. P5: [P6 win, P2 win] 2 wins
3. P3: [P4 win, P1 lost] 1 win, 1 loss
4. P4: [P6 win, P3 lost] 1 win, 1 loss
5. P2: [P1 lost, P5 lost] 2 losses
6. P6: [P5 lost, P4 lost] 2 losses
पहला चयन पी 1 होगा और पहला मैच पी 5 होगा। सूची में से बाहर लेना (पी 1, पी 5)।
1. P3: [P4 win, P1 lost] 1 win, 1 loss
2. P4: [P6 win, P3 lost] 1 win, 1 loss
3. P2: [P1 lost, P5 lost] 2 losses
4. P6: [P5 lost, P4 lost] 2 losses
पहला चयन पी 3 होगा, पहले ही पी 4 खेला जाएगा, इसलिए मैच पी 2 होगा। सूची में से बाहर लेना (पी 3, पी 2)।
इस क्रम मैं एक जोड़ी है कि एक दूसरे को और जोड़ी के खिलाफ खेले साथ खत्म में अमान्य है:
1. P4: [P6 win, P3 lost] 1 win, 1 loss
2. P6: [P5 lost, P4 lost] 2 losses
प्रश्न: क्या कोई एल्गोरिथ्म एक इष्टतम जोड़ी मॉड्यूल की गारंटी देता है कि जब तक बना रही है यकीन है कि मैं नहीं मिलता है एक दूसरे को खेलने वाले दो खिलाड़ियों के साथ अंत में 'अटक गया'?
इसे वजन के किनारों के साथ न्यूनतम लागत वाली अधिकतम मिलान समस्या के रूप में मॉडलिंग किया जा सकता है। जीत (ए) - जीत (बी) | प्रत्येक जोड़ी {ए, बी} टीमों के लिए जो अभी तक एक-दूसरे के खिलाफ नहीं खेले हैं। यह सुनिश्चित नहीं है कि इसे कैसे हल किया जाए। –
वास्तव में, एक [बहुपद समय समाधान] (http://mpc.zib.de/index.php/MPC/article/viewFile/11/4) –
@NiklasB प्रतीत होता है। सामान्य मिलान हमें एक दौर में फंसने से रोकता है, लेकिन मुझे लगता है कि वैध राउंड चुनना संभव है जो सामान्य मिलान वाले डी-नियमित ग्राफ को छोड़ दें। –