幅の最初の検索と反復深化の違い

Question

私はBFSとDFSを理解していますが、私の人生では、反復的な深化とBFSの違いを理解することはできません。どうやら反復的な深化はDFSと同じメモリ使用法を持っていますが、BFSのように拡大し続けるので、これがどのように可能であるかを見ることができません。誰かが明確にすることができれば、それは素晴らしいことです。

必要に応じて作業するツリー：

    A
   / \
  B   C
 /   / \
D   E   F

Answer 1

私が理解していることから、反復深化からDFSを深さ1まで下げて、DFSを2の深さまで下げます。

たとえば、木は読まれると思います

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

各レベルの深さ制限を備えた別のDFSを実行し、メモリを捨てると思います。

Answer 2

アルゴリズムの理解から、IDDFS（反復的な深さの深さfirst検索）は、単に複数回実行される深度first検索であり、各反復で検索されたノードのレベルを深めます。したがって、最大の深さ反復は完全な深度検索であるため、メモリ要件は深度最初の検索と同じです。

したがって、あなたが与えたツリーの例では、最初の反復はノードAにアクセスし、2番目の反復はノードA、B、およびCにアクセスし、3回目の反復はツリーのすべてのノードにアクセスします。

このように実装される理由は、検索に時間制約がある場合、アルゴリズムは少なくとも「良いスコアリング」ノードが何であるかについての考えを持つことです。木。

これは、各反復で、ノードが幅広い最初の検索のようではなく、深さ最初の検索のように訪問されるため、幅広い検索とは異なります。通常、IDDFSアルゴリズムは、おそらく各反復から見つかった「最高のスコアリング」ノードを保存します。

Answer 3

メモリの使用量は、任意の時点で保存するノードの最大数です。訪問されたノードの数ではありません。

いつでもIDFSは、拡張しているブランチにノードのみを保存する必要があります。C（EGで）を拡張している場合はAとCの範囲です。 BFSは、検索している深さのすべてのノードを保存する必要があります。効果を確認するには、2ではなく分岐ファクター8のツリーを取得します。3の深さを検索するには、BFSが大規模な64ノードを保存する必要があります。 IDFSには3つだけが必要です。

Answer 4

反復型の検索の各反復では、制限があり、DFSアプローチを使用してグラフを通過しますが、各反復の各ステップについては、ルートから深さまでパス内のノードのみを追跡する必要があります。 。それが記憶の節約です。

たとえば、下の写真の最後の行を見てください。 BFSを使用した場合、すべてのノードを深さ2まで追跡する必要がありました。しかし、DFSを使用しているため、いくつかのノードがすでに訪問されているため、すべてのノードをメモリに保つ必要はありません。それらを必要とするか、まだ訪問していないので、後で追加します。ルート（灰色のパス）へのパスを保持するだけです。

写真はピーター・ノーヴィヒとスチュアート・ラッセルによる人工知能の本からのものです