确定最佳团队和队形的算法？

Question

我正在寻找合适的算法，我可以使用在运动队管理模拟器(如曲棍球或足球)。模拟器的一些特性：

• 这支球队可以使用不同的阵型(例如足球的4-4-2).
• 队里的每一个球员都有一个数字等级来衡量他们在队里的每一个位置都有多好。
• 有一群能力各异的队员可以从中挑选出球队。

什么样的算法可以用来以编程和有效的方式确定最强的团队和阵型？

Answer 1

如果我们用图来模拟你的问题，并且注意到不同形状的数目很小，那么问题就是最大加权二部匹配，它可以被匈牙利算法解决，.

为了用二部图建模问题，把球员放在一边，位置放在另一部分(例如在足球中)，形成一个球员池和他们的11个位置，将所有球员连接到所有位置，并将相应的边缘权重设置为相应的位置上的球员等级。

现在你要做的就是在这个完全的二分图中找到一个最大(加权)匹配。(代码可在wiki链接中获得)。

我假设我们有有限的构形，对于每个构形，我们可以找到相应的匹配图，以及它的最大权重匹配，最后取所有可能的构形的最大值(在所有的图中)。

Answer 2

您可以尝试一种启发式的方法，使用现有的人工智能工具进行优化，例如遗传算法或爬山。

我会给出更多关于爬山的细节，因为这是我最喜欢的。

将您的问题表示为状态图 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.

注意，爬山的这种变化(随机重新开始爬山)是一个任意时间算法 --这意味着当给出更多的时间和无限的时间时，它会变得更好--它创建了全局最大值。

Answer 3

可以应用于您的问题的简单启发式是贪婪算法，它的解释可以在算法中找到。

另一个解决方案是创建两个虚拟节点(开始和结束)，并将玩家池看作一个有序图(首先是守门员，然后是右翼后卫，等等)。边缘将包括球员对正在考虑的位置的评级。在这个场景中，您将有一个场景，您可以应用A*算法，您将在算法上找到该算法的描述(请记住，最大化问题只是反函数的最小化)。