time-complexity - 如何在给定时间和深度的情况下找到分支以进行迭代深化？

Question

我的教授提出了以下问题，我真的不知道如何开始解决这个问题。任何帮助都非常受欢迎。

让树的空间是一棵具有统一分支 b 的树（每个节点正好有 b 个子节点）。我们正在通过迭代深化探索空间，从树的根开始。程序在 0.2 秒内找到深度为 3 的第一个解，并在 10 秒内找到深度为 5 的下一个解。我们知道第三个解决方案在深度 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