我不确定这个问题是否应该放在 stackoverflow 或 cs.stackexchange.com 上,所以如果我应该移动它,请告诉我。
我试图找到蒙特卡洛树搜索(MCTS)的时间复杂度。谷歌搜索没有帮助,所以我想看看我自己计算了多远。
它为n
迭代或在时间用完之前执行四个步骤。所以我们会有
O(n*(选择+扩展+模拟+反向传播))
扩展只是将一个子节点添加到当前选定的节点。假设您没有使用单链表或类似的东西来存储树的孩子,这可能会在恒定时间内发生,所以我们可以排除它:
O(n*(选择+模拟+反向传播))
给定分支因子b
和t
树中的节点总数,我假设选择阶段在 O(b*log b t) 中运行,因为树的深度是 log b t,并且在每个深度,我们去超过b个孩子。
所以我们的时间复杂度变成
O(n*(b*log b t+模拟+反向传播))
反向传播所花费的时间也与树的深度成正比,因此变为:
O(n*(b*log b t+模拟+b*log b t))
但现在我不确定如何将模拟阶段添加到此。