Какова временная сложность поиска дерева Монте-Карло?

Question

Я не уверен, должен ли этот вопрос идти в stackoverflow или cs.stackexchange.com, поэтому, пожалуйста, дайте мне знать, если я его переведу.

Я пытаюсь найти временную сложность поиска по дереву Монте-Карло (MCTS). Googling не помогает, поэтому я пытаюсь понять, как далеко я сам рассчитываю.

Он выполняет четыре шага для n итераций или до истечения времени. Таким образом, мы будем иметь

O (N * (выбор + расширение + моделирование + обратное распространение))

Расширение просто добавляет ребенок к выбранному узлу. Предполагая, что вы не используете односвязан список или что-то подобное для хранения дерева детей, это может произойти в постоянное время, так что мы можем исключить его:

O (N * (выбор + моделирование + обратное распространение))

Учитывая коэффициент ветвления b и t общего числа узлов в дереве, я предполагая, что фазовый выбор трассы в O (б ​​* войти _б т), потому что глубина дерева журнал _b t, и на каждой глубине мы переходим через b детей.

Таким образом, наша временная сложность становится

О (п * (б * войти _б T + моделирование + обратное распространение))

обратного распространение занимает время, пропорциональное глубине дерева как хорошо, так что становится:

О (п * (б * войти _б T + моделирование + Ь * войти _b t))

Но теперь я не уверен, как добавить фазу моделирования к этому.

Answer 1

После того, как мы выбрали узел для расширения, мы разберем узел в виде m случайных детей, а не одного ребенка. Кроме того, вместо , имитирующего дочернее состояние только один раз, мы имитируем каждое дочернее состояние k раз.

• м это число детей узла
• К является количество моделирования ребенка

выполнения алгоритма можно просто вычислить как O (МКИ/C) где m и k такие же, как и раньше, и I - число итераций , а C - количество доступных сердечников.

Ссылка:

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