我想计算一棵树的有效分支因子，以评估我在A*搜索中启发式的质量。

这篇文章提供了公式的非常好的解释：N+1=1+B∗+(B∗)^2+⋯+(B∗)^d，该公式在AI: A Modern Approach（由Stuart Russell和Peter Norvig撰写）书中介绍。其中，N是搜索的节点数，解决方案的深度是d，“b*是均匀树在深度d时必须具有的分支因子，以便包含N+1个节点”。

我对书中给出的例子感到非常困惑。他们说：

例如，如果A*在深度5处使用52个节点找到解决方案，那么有效分支因子是1.92。

他们是如何得出这个值的？如这里所解释的，该公式的近似值由B∗≈N^(1/d)给出。

使用书中例子的值，我得到2.20 = 52 ^ (1/5)，这与书中给出的解决方案值（顺便说一下，该值并未被称为近似值）相差甚远。

所以，我的疑问是他们是如何得出1.92这个值的？我错过了什么？

回答：

通过方程B∗ ≈ N^(1/d)对N+1 = 1+B∗+(B∗)^2+⋯+(B∗)^d的近似值仅在B∗较大时才准确。真实公式是((B∗)^(d+1) - 1) / (B∗ - 1) = N+1。当B∗不显著大于1时，近似值的误差可能非常大。

如果你在方程53 = ((B∗)^(d+1) - 1) / (B∗ - 1)中解B∗，例如使用牛顿法或其他数值求解器，真实值（精确到6位有效数字）是B∗ ≈ 1.916729，或在教科书中是B∗ ≈ 1.92。