IDDFSの空間複雑度

Question

私はの反復深化深さ最初の検索の空間複雑さと苦労しています。グラフの最後のノードである最悪のケースでは、グラフ全体を作成する必要があるので、あなたのスペースはです（b ^m）ここで、bは分岐要因です最大深度はmです。しかし、それはO（bm）と言われています。誰かがなぜ私に説明してくれますか？前もって感謝します！

Answer 1

グラフ全体を一度に作成したり訪れたりすることはできますが、同時にすべてのグラフを保持する必要はありません。任意の時点で、メモリ内に保持する必要があるのは、現在の場所までのパスで、これはmをbmで与えます。私は、パスの各ノードの子を保持する形式、または同等の情報がbの要素であると仮定します。実際には、https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_searchのウィキペディアのエントリーは

と言っています。IDDFSの時間複雑さはO（bd）{\ displaystyle O（b^d）} O（b^d）であり、その空間複雑度はO \ displaystyle O（d）} O（d）ここで、b {\ displaystyle b} bは分岐因子であり、d {\ displaystyle d} dは最も浅い目標の深さである[2]