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

Question

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

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

Это делает четыре шага для 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))

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

Answer 1

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

• m число дочерних узлов
• k - количество симуляций ребенка

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

Ссылка:

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