java - 评估所有锦标赛场景

Question

我有一个Tournament包含匹配列表的对象，每个对象都有 player1 或 player2 获胜的概率，存储在Map<Player, Float>.
我在比赛列表中进行迭代，i并i + 1使用他们的获胜者创建一个新的比赛。获胜者是这样选择的：如果 p1（或 p2）以高于某个阈值的概率获胜，我选择它，否则我必须分支并评估两种情况（情况 1：p1 获胜 - 情况 2：p2 获胜）。
我的目标是创建所有可能的场景并评估所有可能的锦标赛获胜者。
我可以在没有分支的情况下做到这一点（只需递归评估所有比赛获胜者，直到只有最后一场比赛），但如果我想要所有场景，我真的不知道该怎么做。
有任何想法吗？我应该使用哪种数据结构？是否可以做类似 C 的事情fork并使用它？

Answer 1

是否可以做类似 C fork 的事情并使用它？

您可以使用 ExecutorService 提交任意数量的任务。假设它们受 CPU 限制，您可能希望使用固定线程池，其大小为Runtime.getRuntime.availableProcessors()

Answer 2

您可能正在寻找某种树浏览算法。您可以使用广度优先搜索或深度优先搜索。使用递归基本上是使用后者，但要注意，Java 堆空间不够用是很常见的，最终您将不得不自己实现它。

BFS 和 DFS 非常相似，它们在使用数据结构时有所不同。BFS 使用队列，由 JSE 实现LinkedList，而 DFS 使用栈，由Stack类实现。

Answer 3

最后我用蒙特卡洛方法解决了。我多次参加比赛（10k），每次模拟都会根据他的概率选择每场比赛的获胜者。由于我运行了很多次，我确信我会遇到所有可能的情况（我一步一步地保存它们，以及预测的锦标赛获胜者）。它被证明是快速有效的，不需要额外的数据结构（只需一组保存所有场景和一张地图来保存锦标赛获胜者的概率）。