我想計算一棵樹的有效分支因子，以評估我在 A* 搜索中的啟發式演算法的質量。
這里的帖子很好地解釋了這個公式：N 1=1 B? (B?)^2 ? (B?)^d，在AI: A Modern Approach (by Stuart Russell and彼得·諾維格）書。其中，N 是搜索的節點數，解深度為 d，“b* 是深度為 d 的均勻樹必須具有的分支因子，以包含 N 1 個節點”
我真的對書中給出的例子感到困惑。他們說：
例如，如果 A* 使用 52 個節點在深度 5 處找到解，則有效分支因子為 1.92。
他們是如何得出這個值的？正如這里所解釋的，這個公式的近似值由 B?≈N^(1/d) 給出。
使用該公式和書中示例中的值，我得到 2.20 = 52 ^ (1/5)，這與書中作為解決方案提出的值有點遠（順便說一句，這并不是一個近似值）。
所以，我的問題是他們是如何得出 1.92 的值的？我錯過了什么？
uj5u.com熱心網友回復：
N 1 = 1 B? (B?)^2 ? (B?)^d方程的近似值B? ≈ N^(1/d)僅對 的較大值是準確的B?。真正的公式是((B?)^(d 1) - 1) / (B? - 1) = N 1。當B?不顯著大于1時，近似誤差可能非常高。
如果您B?在方程中求解53 = ((B?)^(d 1) - 1) / (B? - 1)，例如使用牛頓法或其他數值求解器，則真實值（至 6 sf）為B? ≈ 1.916729，或B? ≈ 1.92在教科書中。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446430.html
上一篇：在對矩陣進行O(n^2)操作時將矩陣減半的時間復雜度是多少？
下一篇：查找附近重復和偽造的影像