このリンクから反復的深化を研究しています。私の主な関心事はOverheadです。そのリンクはそれを言う
分岐係数が高いほど、繰り返し展開される状態のオーバーヘッドが低くなります
この声明についての説明はなく、そのリンクには説得力のある議論もありません。このステートメントの背後にある理由を探しています。なぜなら、分岐係数が増加するにつれてオーバーヘッドが増加するはずであり、それはノードが増加していないことを意味し、オーバーヘッドがどのように減少しているのか?
今まで、合理的で役立つものは何も見つかりませんでした。誰かが私の概念を修正するのを手伝ってくれるなら、私はあなたに感謝します.
あなたの質問への答えは、ステートメントの上の式にあります
(d)b + (d-1)b^{2} + \cdots + 3b^{d-2} + 2b^{d-1} + b^{d}
BFS を実行するためのコスト (比較する必要があるもの) は、次のとおりです。
b + b^{2} + \cdots + b^{d-2} + b^{d-1} + b^{d}
したがって、オーバーヘッドは
(d-1)b + (d-2)b^{2} + \cdots + 2b^{d-2} + 1b^{d-1}
明らかに、これは分岐要因の影響を大きく受けています。特に最終学期を見ると1b^{d-1}