algorithm - 深さ優先反復深化検索と深さ優先検索

Question

コーディングに関する質問はありませんが、検索アルゴリズムについては、これで問題ないと思います。課題では、次の質問を解決する必要があります。

「dfid が dfs よりもはるかに悪い状態空間を記述してください。たとえば、O(n²) と O(n) のように。」dfid は深さ優先反復深化検索であり、dfs 通常の深さ優先検索です。この問題を解決する方法がわかりません。最悪の場合の実行時間は、ツリー内の両方の検索で O(b^d) のようなものであることはわかっていますが、実際に良い例を見つけるのは難しいと思います。

分岐が少ないほど dfid ランタイムが悪化するため、分岐が 2 つだけのツリーについて考えました。

誰かがこれで私を助けることができますか?

Answer 1

状態空間がリンクされたリストのようなもの (つまり、ノードごとに 1 つの子のみ) であり、目標状態が葉である場合、説明したとおりの状況になります。

DFS では、リーフに到達するまで各子に沿って進みます。ノードがある場合n、実行時間は O(n) です。

IDS では、最初の反復ではルートの子のみにアクセスします。2 回目の反復では、ルートの子とその子にアクセスします (深さ = 2、2 つのノードにアクセス)。3 回目の反復では、深さ 3 に進み、3 つのノードにアクセスします。したがって、訪問の総数は 1 + 2 + .... + n = O(n^2) です。