深さ優先探索によって生成されたノードの総数はいくらですか

Question

と仮定します。 'd'は木の有限深度です。 'b'は分岐因子です。 'g'は最も浅いゴールノードです。

私が知っているところから、最悪のケースは、ゴールノードがツリーの最後の右下ノードにあるときです。 したがって、生成されたノードの総数はO（bg）です。 しかし、私のインストラクターは、最悪のケースは、ゴールノードに根ざしたサブツリーを除いてすべてのツリーを探索しているので間違っていると私に言った。 彼はO（bd） - O（b（g-d））について何か言及しました.... 私は完全にはわかりません。

私は本当に彼が何を意味するかは分からないので、誰かが正しい答えを教えてくれますか？

Answer 1

ツリーを描画し、探索されたノードをマークし、そこに含まれるノードの数を数えることをお勧めします。

幅広い最初の検索を使用する場合は、ブランチごとに深さがgに達しただけなので、推論は正しいです（O(b**g)ノードが合計で探索されます）。

深さの最初の検索を使用すると、ゴール（O(b**d - b**(d-g))ノードが探索されたもの）以外のツリーのすべての部分の深度に達するので、インストラクターの推論は正しいです。

目標は、緑色の円です。

青いノードが探索されます。

赤いノードは探索されません。

調査した数を数えるには、ツリー内の合計を数え、赤い数字を取り除きます。深IツリーO(b**d)内のノードの総数を求めている= 1 = G

分岐係数= B = 3

注で

深さ= 2 = D

ゴール。厳密に言えば、合計はb**d + b**(d-1) + b**(d-2) + ... + 1ですが、これはO(b**d)です。