我只是想检查一下我对Russell和Norvig中给出的算法和计算的理解是否正确 .
我使用传教士和食人族作为测试时间和空间复杂性的问题 . 计算深度并不是什么大不了的事 . 我总是在深度11处找到解决方案 . 我无法解决的问题是分支因素 .
Russell和Norvig第82页说：
“探索集合中将有O（b ^（d-1）个）节点，边界中有O（b ^ d）个节点......”
我的程序在探索的集合中显示了 8502 个节点，在边界中显示了 14006 个节点 .
这是我的思维过程的方式：如果我根据Russell和Norvig获取节点的数量并采用 d 根，我应该得到分支因子 . 现在我不知道我在想什么是正确的 . 我想出来了 .
所以我取 8502 的第10个（d-1）根并得到 2.47 （大约），我取 14006 的第11个（d）根并得到 2.39 （大约） . 所以我的结论是分支因子b大致为 2.43 .
我是否完全达到了标记，还是我完全错了？这是我现在正在展开的那些事情之一 . 但是我很想知道我是错还是对 .
1 回答
您根据探索集和边界集估计分支因子基本上是正确的 . 对于小深度，分支因子的估计对于边界集比对于探索集更合理，因为探索集包括过去访问的所有顶点，更像是
1 + b + ... + b^(d-1)而不仅仅是b^(d-1). 请注意，随着探索集的增长，您将拥有越来越多的已经探索过的邻居顶点，因此边界集的近似值随着深度的增加而变得越来越不好 . 在极端情况下，当您探索了所有顶点时，您将得到边界集不包含顶点，因此您将近似b^d为0.但无论如何，您的估计程序看起来很好并且在边界集和探索之间给出高度一致的结果组 . 您应该单独使用前沿集来给出分支因子的估计值 .