検索手法の反復深化について質問があります。私の質問は、通常の深さ優先検索と指定された深さ制限のない反復的深化の違いは何ですか? したがって、目標ノードを持つツリーがありますが、反復的な深化検索に指定された制限はありません。これは、通常の深さ優先検索を行った場合と同じトラバーサル シーケンスを出力しますか?
質問する
475 次
1 に答える
1
目標が深さレベル 3 にあり (ルートは深さ = 0)、ツリーの「左側」(深さ優先検索 ( DFS)))。
通常の DFS では、深さレベル 4、5、6 などでの検索に多くの時間を費やしてから、ツリーの「上」、「右」に戻り、最終的に深さ 3 でゴールを見つけることがあります。深化、深さ = 3 に目標がある場合、深さ = 4 のノードを見て時間を無駄にすることはありません。これは、反復深化が最初に深さ制限 1 の DFS を実行し、次に深さ制限 2 の DFS を実行するためです。 、そして最後に深さ制限が 3 の DFS (ゴールを見つけて検索を終了します)。
この例の状況では、幅優先探索 (BrFS) も深さ 4 で時間を無駄にしないことに注意してください。また、以前に既に行われた作業をやり直さないため、おそらく少し速くなるでしょう。ただし、より多くのメモリが必要になります。
Iterative Deepening のもう 1 つの利点は、無限に長いパスで行き詰まらないことです。現在、ほとんどの実際の状況では、無限に長いパスはとにかくありそうにありませんが、それは間違いなく可能です. DFS は、このような無限のパスでスタックする可能性があります。
最後に、Iterative Deepening には、DFS と比較して、処理時間が不足したために終了するときに、より有用な結果を提供できるという利点があります。これは、ゲームをプレイするための検索アルゴリズムで特に重要です (チェス エンジンを考えてみてください)。状況にゴール ノードがあることを明示的に指定したため、これは関係ないと思いますが、興味がある場合はお知らせください。この利点についての説明も書くことができます。
于 2016-08-29T08:21:19.170 に答える