2012-09-17 36 views
0

我有一个对象Tournament有匹配的列表,每个人都有的概率存储在Map<Player, Float>该PLAYER1或player2胜。
我重复获取元件ii + 1创建使用他们的获奖者一个新的比赛的比赛名单上。优胜者是这样选择的:如果p1(或p2)以高于某个阈值的概率获胜,我选择它,否则我必须分支并评估两个案例(案例1:p1胜 - 案例2:p2胜)。
我的目标是创建所有可能的场景并评估所有可能的锦标赛获胜者。
我能做到这一点没有分支(只是递归评估所有比赛的赢家,直到只有最后一场比赛),但是如果我想所有的情况我真的不知道该怎么做。
任何想法?我应该使用哪种数据结构?是否有可能做类似C fork的事情并使用它?评估所有比赛场景

回答

0

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

1

是否有可能做一些像C叉子和使用它?

您可以使用ExecutorService来提交任意数量的任务。假设它们是CPU绑定的,你可能需要使用一个固定的线程池,其大小为Runtime.getRuntime.availableProcessors()

0

你可能正在寻找某种树型浏览算法。您可以使用breadth-first-searchdepth-first-search。使用递归基本上使用后者,但要小心,Java堆空间不够用,而且最终必须由您自己实现。

BFS和DFS都非常相似,当涉及到使用的数据结构它们的区别。 BFS使用队列,由JSE的LinkedList实现,而DFS使用堆栈,由Stack类实现。