0

我不确定这个问题是否应该放在 stackoverflow 或 cs.stackexchange.com 上,所以如果我应该移动它,请告诉我。

我试图找到蒙特卡洛树搜索(MCTS)的时间复杂度。谷歌搜索没有帮助,所以我想看看我自己计算了多远。

它为n迭代或在时间用完之前执行四个步骤。所以我们会有

O(n*(选择+扩展+模拟+反向传播))

扩展只是将一个子节点添加到当前选定的节点。假设您没有使用单链表或类似的东西来存储树的孩子,这可能会在恒定时间内发生,所以我们可以排除它:

O(n*(选择+模拟+反向传播))

给定分支因子bt树中的节点总数,我假设选择阶段在 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))

但现在我不确定如何将模拟阶段添加到此。

4

1 回答 1

0

在我们选择了要扩展的节点后,我们将该节点扩展为 m 个随机子节点,而不是单个子节点。此外,我们不是只模拟一次子状态,而是模拟每个子状态 k 次。

  • m 是节点的子节点数
  • k 是孩子的模拟次数

算法的运行时间可以简单地计算为 O(mkI/C) ,其中 m 和 k 与以前相同,I 是迭代次数,C 是可用内核数。

参考:

http://stanford.edu/~rezab/dao/projects/montecarlo_search_tree_report.pdf

于 2016-01-11T15:22:19.197 回答