एल्गोरिदम सर्वोत्तम टीम और गठन निर्धारित करने के लिए?

Question

मैं उपयुक्त एल्गोरिदम की तलाश में हूं जो मैं स्पोर्ट्स टीम मैनेजमेंट सिम्युलेटर (जैसे हॉकी या सॉकर) में उपयोग कर सकता हूं। सिम्युलेटर की कुछ विशेषताएं:

• टीम विभिन्न संरचनाओं (जैसे सॉकर के 4-4-2) के साथ खेल सकती है।
• टीम के प्रत्येक खिलाड़ी के पास संख्यात्मक रेटिंग है कि वे गठन में प्रत्येक स्थिति के लिए कितने अच्छे हैं।
• वहाँ अलग क्षमताओं के दस्ते खिलाड़ियों का एक पूल जहां से टीम

क्या एल्गोरिदम प्रोग्राम के रूप से और कुशलता से सबसे मजबूत टीमों और संरचनाओं निर्धारित करने के लिए इस्तेमाल किया जा सकता चयनित किया जा सकता है?

Answer 1

हम ग्राफ और विभिन्न संरचनाओं की संख्या देख अपनी समस्या मॉडल हैं छोटा है, समस्या maximum weighted bipartite matching, जो Hungarian Algorithm से व्याख्या करने योग्य है, ....

लेकिन यह कैसे द्विपक्षीय ग्राफ के साथ समस्या यह मॉडल करने के लिए? खिलाड़ियों के एक पूल और उनके लिए 11 पद बनाने के लिए खिलाड़ियों को एक हिस्से के रूप में सेट करें, और अन्य भाग (जैसे सॉकर में) के रूप में सेट करें, सभी खिलाड़ियों को सभी पदों से कनेक्ट करें, और स्थिति में संबंधित खिलाड़ी रेटिंग के रूप में इसी किनारे के वजन को सेट करें ।

अब आपको यह करना चाहिए कि इस पूरे द्विपक्षीय ग्राफ में maximum (weighted) matching खोजें। (कोड विकी लिंक में उपलब्ध हैं)।

मुझे लगता है कि हमारे पास सीमित संख्या में गठन है, प्रत्येक गठन के लिए हम संबंधित मिलान ग्राफ पा सकते हैं, और फिर अधिकतम मिलान, आखिरकार सभी संभावित संरचनाओं (सभी ग्राफों में) पर अधिकतम मूल्य लेते हैं।

Answer 2

आपकी समस्या पर लागू किए जा सकने वाले सिमुलेशन हेरिस्टिक को लालची एल्गोरिदम है, जिसका स्पष्टीकरण http://en.wikipedia.org/wiki/Greedy_algorithm पर पाया जा सकता है।

एक और समाधान दो डमी नोड्स (प्रारंभ और अंत) बनाने और ऑर्डर करने वाले ग्राफ के रूप में खिलाड़ियों के पूल पर विचार करना है (पहले गोलकीपर, फिर दाएं पंख डिफेंडर और इसी तरह) आता है। किनारों पर विचार के तहत खिलाड़ियों की रेटिंग शामिल होगी। इस दृश्य में, आपके पास एक परिदृश्य होगा जहां आप ए * एल्गोरिदम लागू कर सकते हैं, जिसका विवरण आपको http://en.wikipedia.org/wiki/A*_search_algorithm पर मिलेगा (केवल याद रखें कि अधिकतमकरण समस्या केवल व्यस्त कार्य का एक छोटाकरण है)।

Answer 3

आप Genetic Algorithms या Hill Climbing जैसे अनुकूलन के लिए मौजूदा एआई उपकरण का उपयोग करके एक मानवीय दृष्टिकोण का प्रयास कर सकते हैं।
मैं हिल चढ़ाई पर अधिक जानकारी दूंगा, क्योंकि यह मेरा पसंदीदा है।

आपकी समस्या का प्रतिनिधित्व करते हैं के रूप में राज्यों का ग्राफ़ बनानेG = (V,E) ऐसी है कि V = {all possible states } और E = {(u,v) | swapping one player you can move from u to v }।
इसके अलावा, u:V->R एक गठन के लिए उपयोगिता फ़ंक्शन बनें।
जब से हम ग्राफ उत्पन्न करने के लिए नहीं करना चाहते, next:V->2^V एक समारोह हो ऐसी है कि next(v) = {all possible formation that you can get by changing one player }

पहाड़ी चढ़ाई के विचार एक यादृच्छिक गठन से शुरू करने के लिए है, और लालच से सबसे अच्छा परिवर्तन संभव बनाने के लिए, जब आप कर रहे हैं अटक गया - एक नए यादृच्छिक गठन से एल्गोरिदम को पुनरारंभ करें।

1. best<- -INFINITY 
2. while there is more time 
3. choose a random matching 
4. NEXT <- next(s) 
5. if max{ u(v) | for each v in NEXT} < u(s): //s is a local maximum 
    5.1. if u(s) > best: best <- u(s) //if s is better then the previous result - store it. 
    5.2. go to 2. //restart the hill climbing from a different random point. 
6. else: 
    6.1. s <- max { NEXT } 
    6.2. goto 4. 
7. return best //when out of time, return the best solution found so far. 

ध्यान दें कि पहाड़ी चढ़ाई (पहाड़ी यादृच्छिक पुनरारंभ साथ चढ़ाई) की इस बदलाव एक any time algorithm है - जिसका अर्थ है जब अधिक समय दिया जाता है यह बेहतर हो जाएगा, और जब अनंत समय दिया जाता है - यह वैश्विक अधिकतम founds ।