Как найти разветвление заданного времени и глубины для итеративного углубления?

Question

Мой профессор задал следующий вопрос, и я действительно не знаю, как начать решать эту проблему. Любая помощь действительно приветствуется.

Пусть пространство дерева будет деревом с равномерным ветвлением b (каждый узел имеет ровно b дочерних элементов). Мы исследуем пространство с итеративным углублением, начиная с корня дерева. Программа находит первое решение на глубине 3 за 0,2 секунды, а следующее решение на глубине 5 за 10 секунд. Мы знаем, что третье решение находится на глубине 9. Приблизительно оцените, сколько времени мы можем ожидать от программы, чтобы найти третье решение.

Answer 1

Помните школьную математику и сумму геометрической прогрессии.

Дерево выглядит (пример для b = 3 детей)

         N
  N      N      N
N N N  N N N  N N N    

Количество узлов на K верхних уровнях равно (1 + b + b^2 + b^3... + b^(k-1))

S(k) = (b^k - 1) / (b - 1)

Мы можем видеть для k = 3 и k = 5

S(5) / S(3) = 10 / 0.2

(b^5 - 1) / (b^3 - 1) = 10 / 0.2 = 50

Приближение (пренебрегая -1 слагаемым для не столь малых степеней)

b^5 / b^3 = b^2 ~ 50

Чтобы найти результат для k = 9

b^9 / b^5 =  b^4 ~ 2500

Так что время 10*2500 = 25000 seconds ~ 7 hours