algorithm - 确定最佳团队和阵型的算法？

Question

我正在寻找可以在运动队管理模拟器（例如曲棍球或足球）中使用的合适算法。模拟器的一些特点：

• 球队可以使用不同的阵型（例如足球的 4-4-2）。
• 球队中的每个球员都有一个数字评分，表示他们在阵型中每个位置的表现如何。
• 有一群能力各异的小队球员，可以从中选择球队

哪些算法可用于以编程方式有效地确定最强的球队和阵型？

Answer 1

如果我们通过图形对您的问题进行建模并注意到不同编队的数量很少，则问题是最大加权二分匹配，这可以通过匈牙利算法解决，...。

用二分图对问题进行建模，将球员放在一个部分，将位置放在另一部分（例如足球），形成一个球员池和 11 个位置，将所有球员连接到所有位置，并设置相应的边权重作为该位置的相应球员评分。

现在你要做的就是在这个完整的二分图中找到一个最大（加权）匹配。（代码可在 wiki 链接中找到）。

我假设我们有有限数量的编队，对于每个编队我们可以找到相应的匹配图，并且它的最大权重匹配，最终在所有可能的编队（在所有图中）取最大值。

Answer 2

您可以尝试使用现有 AI 工具进行优化的启发式方法，例如遗传算法或爬山。
我会提供更多关于爬山的细节，因为它是我最喜欢的。

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

可以应用于您的问题的简单启发式算法是贪心算法，其解释可以在http://en.wikipedia.org/wiki/Greedy_algorithm找到。

另一种解决方案是创建两个虚拟节点（开始和结束）并将您的球员池视为有序图（首先是守门员，然后是右翼后卫，依此类推）。边缘将包括玩家对所考虑位置的评分。在这个场景中，您将有一个可以应用 A* 算法的场景，您可以在http://en.wikipedia.org/wiki/A*_search_algorithm找到其描述（请记住，最大化问题只是最小化的反函数）。