search - 幅優先探索と反復深化の違い

Question

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

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

    A
   / \
  B   C
 /   / \
D   E   F

Answer 1

私が理解していることから、反復的な深化はDFSを深さ1まで下げ、次にDFSを深さ2まで下げます...深さnまで、というようにレベルが見つからなくなるまで続けます

たとえば、ツリーが読み取られると思います

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

レベルごとに深さ制限のある個別の DFS を実行し、メモリを破棄していると思います。

Answer 2

アルゴリズムの私の理解では、IDDFS (反復深化深さ優先検索) は単純に複数回実行される深さ優先検索であり、各反復で検索されるノードのレベルを深めます。したがって、最大の深さの反復は完全な深さ優先検索であるため、メモリ要件は深さ優先検索と同じです。

したがって、与えられたツリーの例では、最初の反復はノード A を訪れ、2 番目の反復はノード A、B、および C を訪れ、3 番目の反復はツリーのすべてのノードを訪れます。

このように実装されている理由は、検索に時間の制約がある場合、完全なトラバーサルを行う前に制限時間に達した場合に、アルゴリズムが少なくとも「良いスコアリング」ノードが何であるかをある程度把握できるようにするためです。木。

これは幅優先検索とは異なります。これは、反復ごとに、幅優先検索とは異なり、深さ優先検索と同じようにノードがアクセスされるためです。通常、IDDFS アルゴリズムは、各反復で見つかった「最高のスコアリング」ノードを格納する可能性があります。

Answer 3

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

IDFS はいつでも、展開しているブランチのノードのみを保存する必要があります。C を展開する場合は、A と C のみを格納します (たとえば)。BFS は、検索している深さのすべてのノードを保存する必要があります。効果を確認するには、分岐係数が 2 ではなく 8 のツリーを使用します。深さ 3 まで検索するには、BFS に 64 個の大規模なノードを格納する必要があります。IDFS に必要なのは 3 つだけです。