指定された深さ制限なしの反復深化

Question

検索手法の反復深化に関する質問があります。私の質問は、特定の深さ制限なしで通常の深さ優先検索と反復深化の違いは何ですか？だから私は目標ノードを持つツリーを持っていますが、私の反復深化検索では指定された制限はありません。これは通常の深さ優先検索を行うのと同じトラバーサルシーケンスを出力しますか？

Answer 1

目標は深度レベル3（ルートは深度= 0）であり、ツリーの「左」側にあるわけではありません（深度 - 最初の検索（DFS））。

通常のDFSでは、ツリーを「上に」「右に」移動し、最終的に深みで目標を見つけることに慣れて、4,5,6などの深さレベルで多くの時間を費やすことがあります3.反復深化では、深度= 3の目標がある場合、深度= 4のノードを見るのに時間を費やすことはありません。これは、反復深化が最初に深度制限が1のDFSを実行してから、深さ制限2、最後に深度制限3のDFS（目標を見つけて検索を終了します）。

この例の状況では、幅優先検索（BrFS）は深度4で時間を無駄にすることはなく、以前に既に行われていた作業を再実行しないためにおそらく少し速くなることに注意してください。しかし、それはもっと多くのメモリを取るだろう。

反復的深化のもう一つの利点は、それが無限に長い経路にこだまれないということです。今ほとんどの実用的な状況では、とにかく無限に長い経路はありませんが、間違いなく可能です。 DFSは、このような無限の経路で立ち往生する可能性があります。

最後に、反復型ディープニングは、処理時間の不足により終了時により有用な結果を提供できる点でDFSと比較して利点があります。これは、ゲームプレイのための検索アルゴリズム（チェスエンジンを考える）において特に重要です。あなたの状況にゴール・ノードがあることを明示しているので、これはあなたにとって重要ではないと思っていますが、興味があれば教えてください。