確定最佳團隊和形成的算法？

Question

我正在尋找可用於運動隊管理模擬器（例如曲棍球或足球）的合適算法。模擬器的一些特點：

• 團隊可以用不同的地層玩（如足球的4-4-2）。
• 團隊中的每個球員對陣型中每個位置的得分都有數字評分。
• 有一種不同的能力隊內球員池從哪個球隊可以選擇

什麼算法可以用來編程和有效地確定最強的球隊和陣型？

Answer 1

如果我們模型的圖形和注意到，許多不同的地層你的問題是小，問題是maximum weighted bipartite matching，這是Hungarian Algorithm可解，....

但如何將問題與二分圖模型？將球員設置爲一個部分，並將其定位爲另一部分（例如足球），形成球員和他們的11個位置，將所有球員連接到所有位置，並將相應的邊緣權重設置爲相應的球員等級。

現在你應該做的就是在這個完整的二分圖中找到maximum (weighted) matching。 （代碼可以在wiki鏈接中找到）。我認爲我們有有限數量的陣型，對於每個陣列我們都可以找到相應的匹配圖，然後進行最大匹配，最後在所有可能隊形中（在所有圖中）取最大值。

Answer 2

可應用於您的問題的簡單啓發式是貪婪算法，其解釋可在http://en.wikipedia.org/wiki/Greedy_algorithm找到。

另一種解決方案是創建兩個虛擬節點（開始和結束），並將您的玩家池視爲有序圖形（先來守門員，然後是右翼防禦者，等等）。邊緣將由玩家對所考慮位置的評分組成。在這個場景中，你將會有一個應用A *算法的場景，你可以在http://en.wikipedia.org/wiki/A*_search_algorithm找到它的描述（只記得最大化問題只是最小化反函數）。

Answer 3

您可以嘗試使用現有AI工具進行優化的啓發式方法，例如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 - 這意味着當有更多的時間它會變得更好，而當被賦予無限的時間 - 它開創了全球最大。