iterative deepeningについて読み続けていますが、 depth-first searchとの違いがわかりません。
深さ優先探索がますます深く進んでいることがわかりました。
反復的な深化では、レベルの値を確立します。そのレベルに解決策がない場合は、その値を増やして、ゼロ (ルート) からやり直します。
これは深さ優先探索と同じではないでしょうか?
つまり、解決策が見つかるまで、どんどん増やしていきます。私はこれを同じものと見ています！ゼロからやり直すと、以前と同じブランチにたどり着くので、同じブランチにたどり着きます。
深さ優先探索では、グラフのあるノードから開始し、まだ到達していない新しいノードを見つけることができる間 (または解が見つかるまで)、グラフをどんどん深く探索します。DFS が動きを使い果たすたびに、別の選択を行うことができる最新のポイントに戻り、そこから探索します。グラフが非常に大きく、ソリューションが 1 つしかない場合、これは深刻な問題になる可能性があります。これは、各ノードを調べた後にソリューションを見つけるためだけに、1 つの DFS パスに沿ってグラフ全体を探索することになる可能性があるためです。さらに悪いことに、グラフが無限の場合 (たとえば、グラフがすべての数値で構成されている場合など)、検索が終了しない可能性があります。さらに、探しているノードが見つかったら、
この問題に対する 1 つの潜在的な解決方法は、DFS がたどる 1 つのパスの深さを制限することです。たとえば、DFS 検索を実行しても、5 を超える長さのパスを取得した場合は検索を停止します。これにより、開始ノードから 5 を超える距離にあるノードを決して探索しないことが保証されます。つまり、探索しないことを意味します。または (グラフが非常に密でない限り) グラフ全体を検索しません。ただし、これは、必ずしもグラフ全体を探索するとは限らないため、探しているノードが見つからない可能性があることを意味します。
反復的な深化の背後にある考え方は、この 2 番目のアプローチを使用することですが、各レベルで深さを増やし続けることです。つまり、問題のノードが見つかるまで、長さ 1 のすべてのパス、次に長さ 2 のすべてのパス、長さ 3 のすべてのパスを使用して探索を試みることができます。これは、各パスの長さが各ステップである程度の長さで制限されるため、無限の行き止まりのパスに沿って探索することは決してないことを意味します。また、深さ d でノードが見つからなかったが、深さ d + 1 でノードが見つかった場合、長さ d のパスは存在できないため、宛先ノードへの可能な最短パスを見つけることも意味します (またはしたがって、長さ d + 1 のパスは確かに最適です。
これが DFS と異なる理由は、終了せずにグラフの周りを非常に長く迂回するパスをたどるケースに決して遭遇しないためです。パスの長さには常に上限があるため、不要な分岐を探索することはありません。
これが BFS と異なる理由は、BFS ではすべてのフリンジ ノードを一度にメモリに保持する必要があるためです。これにはメモリ O(b d ) が必要です。ここで、b は分岐係数です。これを、反復深化による O(d) メモリ使用量と比較します (現在のパスの d ノードごとに状態を保持するため)。もちろん、BFS が同じパスを複数回探索することは決してありませんが、反復的な深化は深さの制限を増加させるため、任意のパスを複数回探索する可能性があります。ただし、漸近的には、2 つの実行時間は同じです。BFS は、距離 dにあるすべての O(b d ) ノードを考慮した後、O(b d ) ステップで終了します。反復的な深化では、レベルごとにO(b d ) の時間を使用します。これは、全体で O(b d ) になりますが、より高い定数係数を使用します。
要するに：
お役に立てれば！
これについては、ウィキペディアにまともなページがあります。
あなたが見逃したと思う基本的な考え方は、反復的な深化は主にヒューリスティックであるということです。解決策がルートの近くで見つかる可能性が高い場合、反復的な深化は比較的高速に解決策を見つけますが、単純な深さ優先検索は「間違った」決定を下し、実りのない深い分岐に多くの時間を費やす可能性があります。
(これは、検索ツリーが無限になる可能性がある場合に特に重要です。この場合、 BFS または反復的な深化は、答えが存在する場合、いつか必ず答えを見つけることができますが、DFS は永遠にスタックする可能性があるため、同等性はさらに低くなります)