Breadth First Searchによって生成されたノードの数に必要な情報が増えました

Question

私はAIを初めて使い、Peter Norvigの本を読んでいました。この質問はすでにWhat is the number of nodes generated by breadth-first search?です。 展開のために選択されたときに各ノードに目標テストを適用すると、ノード= 1 + b + b^2 + b^3 + ... + b^d +（b ^（d + 1）-b） しかし、私の目標状態が最後の深さにある葉ノードであればどうでしょうか？したがって、目標の後には全く深さがありません。次に、b ^（d + 1）をどのように評価することができるか。例：深さ3のツリーで、目標が深さ3にある場合、4番目のレベルがない場合、b ^（3 + 1）はどのように評価されますか？疑いを晴らしてください。前もって感謝します！あなたがリンクされ答えはそれが最悪の場合にをを生成されるノードの量であることを述べていること

Answer 1

注意。

生成されたは、それらのノードのすべてがテストされていないことを意味します。それらは単純に生成されて保存され、目標がまだ見つからない場合に最終的に目標と比較することができます。

最悪の場合には2つの重要な意味があります。幅優先検索を左から右へ、次に1つ下へ、次に左から右へ、次に下へなど、視覚化してみてください。最悪の場合、深度レベルdのどこにでも、目標は最後の（最も右の）ノードです。これは、その左側のすべてのノードが目標ノードと比較され、それらの後継ノードも生成されることを意味します。

さて、私はあなたがあなたのケースでがD下の深さのレベルではノードはありませんが、最悪の場合を言うの第二の意義は、我々は基本的に無限に多くがあると仮定しないということであると言ったことを知っています深さレベル。

は確かに、あなたのケースのためにその方程式は完全に正しいではありませんが、最悪の場合を持っていないので、これは単純です。あなたのケースでは、検索プロセスは実際に最後の（b ^（d + 1） - b）の節を生成する必要はありません。

あなたが使用される用語の最後の注意：あなたが尋ねたどのようB ^（D + 1）（例えば、B D以下の一切の深さレベルが存在しない場合を評価することができ^（3 + 1） = 3。この用語を数学的に評価するには問題はありません。深度レベル4がない場合でも、数学的にはb ^（3 + 1）と評価されます。それは正しいとは言えませんが、それでも問題はありませんが、それでも問題はないと評価しています。