反復深化A*

反復深化A*（IDA* ）は、重み付きグラフにおいて、指定された開始ノードと目標ノード群の任意のメンバーとの間の最短経路を見つけることができるグラフ探索および経路探索アルゴリズムです。これは、A*探索アルゴリズムからヒューリスティック関数を使用して目標に到達するまでの残りのコストを保守的に推定するというアイデアを取り入れた、反復深化深さ優先探索の変種です。深さ優先探索アルゴリズムであるため、メモリ使用量はA*よりも少なくなりますが、通常の反復深化探索とは異なり、最も有望なノードの探索に集中するため、探索ツリーのどこでも同じ深さまで探索することはありません。A*とは異なり、IDA*は動的計画法を利用しないため、同じノードを何度も探索することになります。

標準的な反復深化深さ優先探索では、各反復のカットオフとして探索深度を使用しますが、IDA* ではより情報量の多い${\displaystyle f(n)=g(n)+h(n)}$、 どこ${\displaystyle g(n)}$ルートからノードへの移動コスト${\displaystyle n}$そして${\displaystyle h(n)}$これは、からの移動にかかる費用に関する問題固有のヒューリスティックな推定値です。${\displaystyle n}$目標に向かって。

このアルゴリズムは、1985年にリチャード・E・コルフによって初めて記述された。 ^{[ 1 ]}

反復深化A*は次のように動作します。各反復で深さ優先探索を実行し、総コストが一定値を超えたら分岐を切り捨てます。${\displaystyle f(n)=g(n)+h(n)}$与えられたしきい値を超えます。このしきい値は、初期状態でのコストの推定値から始まり、アルゴリズムの各反復ごとに増加します。各反復において、次の反復で使用されるしきい値は、現在のしきい値を超えたすべての値の最小コストです。^{[ 1 ]}

A*アルゴリズムと同様に、ヒューリスティックアルゴリズムも最適性（最短経路）を保証するために特定の特性を備えている必要があります。詳細は下記の「特性」を参照してください。

path現在の検索パス（スタックのように機能）node現在のノード（現在のパスの最後のノード）g現在のノードに到達するまでのコストf最も安いパス（ルート..ノード..ゴール）の推定コストh ( node ) 最も安いパス（ノード..ゴール）の推定コストcost ( node , succ ) ステップコスト関数is_goal ( node ) ゴールテストsuccessors ( node ) ノード展開関数、g + h(node) の順にノードを展開ida_star ( root ) NOT_FOUND を返すか、最適なパスとそのコストのペアを返す手続きida_star ( root ) bound := h ( root ) path := [ root ] loop t := search ( path , 0, bound ) if t = FOUND then return (path, bound) if t = ∞ then return NOT_FOUND bound := t end loop end procedurefunction search ( path , g , bound ) node := path .last f := g + h ( node ) if f > bound then return f if is_goal ( node ) then return FOUND min := ∞ for succ in successors ( node ) do if succ not in path then path .push( succ ) t := search ( path , g + cost ( node , succ ), bound ) if t = FOUND then return FOUND if t < min then min := t path .pop() end if end for return min end function

A*と同様に、IDA*は、ヒューリスティック関数hが許容可能であれば、問題グラフ内の指定された開始ノードから任意の目標ノードへの最短経路を見つけることが保証されます^{[ 1 ]。}

${\displaystyle h(n)\leq h^{*}(n)}$

すべてのノードnに対して、h *はnから最も近い目標までの最短経路の真のコスト（「完全なヒューリスティック」）である。^{[ 2 ]}

IDA* は、メモリ制約のある問題に有効です。A* 探索では、未探索ノードの大きなキューが保持され、メモリがすぐにいっぱいになる可能性があります。対照的に、IDA* は現在のパス上のノード以外を記憶しないため、構築する解の長さに比例するだけのメモリ量しか必要としません。その時間計算量は、ヒューリスティックなコスト推定hが一貫しているという仮定の下でKorf らによって分析されています。

${\displaystyle h(n)\leq \mathrm {cost} (n,n')+h(n')}$

すべてのノードnとnのすべての隣接ノードn'について、指数関数的な問題に対する総当たりツリー検索と比較すると、IDA* は検索深度は（定数倍）小さくなるが、分岐係数は小さくならないと結論付けている。^{[ 3 ]}

再帰的最良優先探索は、A*探索のメモリ制約版であり、ノードの再生成回数が少ないため、実際にはIDA*よりも高速になる可能性がある。^{[ 2 ]： 282-289}

IDA*はA*に比べてメモリ効率が良いとよく評価されるが、特定の条件下では最悪の場合の時間計算量が著しく悪化する可能性がある。

IDA* の応用例としては、計画などの問題が挙げられます。^{[ 8 ]}ルービックキューブを解くことは、IDA* で解決できる計画問題の一例です。^{[ 9 ]}