1

我只是想检查一下我对 Russell 和 Norvig 给出的算法和计算的理解是否正确。

我使用传教士和食人族作为一个问题来测试时间和空间的复杂性。计算深度并不是什么大问题。我总是在深度 11 找到解决方案。我无法理解的是分支因素。

罗素和诺维格第 82 页说：

O(b^(d-1))“探索集中会有节点O(b^d)，边境会有节点……”

我的程序显示8502探索集中的14006节点和前沿节点。

d这是我的思考过程的方式：如果我根据 Russell 和 Norvig取节点数并取根，我应该得到分支因子是什么。现在我不知道我的想法是否正确。我刚想出来。

所以我取 10 个 (d-1) 的根8502并得到2.47（大约），我取 11 个 (d) 的根14006并得到2.39（大约）。所以我的结论是分支因子 b 大致为2.43。

我是完全达到目标还是完全错了？这是我现在正在做的事情之一。但很想知道我是对还是错。

4

1 回答 1

1

您基于探索集和前沿集对分支因子的估计基本上是正确的。对于小深度，分支因子的估计对于边界集比探索集更合理，因为探索集包括过去访问过的所有顶点，1 + b + ... + b^(d-1)而不仅仅是b^(d-1). 请注意，随着探索集的增长，您将拥有越来越多的已探索相邻顶点，因此b^d边界集的近似值将随着深度的增加而变得越来越差。在极端情况下，当您探索了所有顶点时，您将发现边界集不包含顶点，因此您将近似b^d为 0。但无论如何，您的估计程序看起来不错，并且在边界集和探索集之间给出了高度一致的结果。您可能应该单独使用边界集来估计分支因子。

于 2014-01-10T23:35:33.507 回答