結論
IDA* (Iterative Deepening A*) は A* の派生アルゴリズムで、メモリ消費を抑えながら最短経路を探すことを目的にしています。A* は展開候補のノード集合 (オープン集合) をメモリに抱え込むため、状態空間が大きい問題ではメモリが爆発する弱点があります。IDA* はオープン集合を持たず、深さ優先探索を $f$ 値のしきい値を徐々に引き上げながら繰り返すことで、同じ最適性保証をそのままに、メモリを一定量に抑えます。
こんな人向けの記事
- アルゴリズムの仕組みをざっくり知りたい方
- A* を実装したら、メモリ不足で大きな問題が解けなかった方
- 反復深化 (iterative deepening) の考え方を具体例で理解したい方
- パズルソルバーで IDA* がいつ選ばれるかを知りたい方
基本概念: しきい値付き DFS の反復
IDA* の処理は次の手順で進みます。
- しきい値 $T$ を初期値 (スタートノードの $h(n)$ が一般的) に設定する
- スタートから深さ優先探索を開始する。ただし $f(n) = g(n) + h(n)$ が $T$ を超えたノードは展開しない
- ゴールに到達できれば終了。届かない場合は、展開を打ち切った最小の $f$ 値を新しい $T$ として、同じ手順を繰り返す
ポイントは (2) の「$T$ を超えたら打ち切る」という枝刈りです。探索の深さがしきい値で抑えられ、同時に深さ優先探索はスタックフレームしか使わないため、メモリ消費は一定量に収まります。A* がオープン集合に 107 個のノードを抱えて GB 級メモリを食うような場面でも、IDA* なら数 MB の再帰スタックで同じ探索を回せます。
トレードオフは同じノードを複数の反復で何度も展開する点です。$T$ が少しずつ上がるたびに浅い部分の探索が再実行されるため、単純には指数関数的に展開数が増えます。時間と引き換えにメモリを節約するアルゴリズム、とイメージしてください。
てくてくピクミンでの使い方と工程
本記事の解析では、Python で実装した A* ソルバーで 68 ステージ中 66 ステージを解きました。しかし残る Stage 28 (30 × 11 マス、最短 53 手) と Stage 57 (22 × 9 マス、最短 52 手) は、オープン集合が数千万ノードに膨らんでメモリ上限に達し、打ち切りになりました。ここで IDA* の出番です。
- Python 版ターン処理の C 移植 — 盤面のタイル更新、同方向移動、ハザード判定などを配列演算に落とし込み、1 状態あたりの計算コストを Python 比で 2 桁以上削減しました。
- A* と同じ 許容的 ヒューリスティック — 宝物マス起点の多源 BFS 距離をそのまま使用。白ピクミンの 2 マス移動を $\lceil d/2 \rceil$ で補正する調整も揃えました。
- IDA* のしきい値反復ループ — 再帰 DFS を $f$ 値のしきい値で打ち切り、到達しなければ次の最小 $f$ に切り替えて再実行、という素朴な形で実装。メモリは一定、時間は秒単位ではなく分 〜 時間単位を許容する前提です。
結果は以下の通りでした。
- Stage 28: 約 4,520 万状態 / 11 分 で 53 手の最短解を確定 (VBA 作者による解析解 61 手から -8 手の短縮)
- Stage 57: 約 30 億状態 / 1 時間 45 分 で 52 手の最短解を確定 (VBA 解 53 手から -1 手の短縮)
Python A* では手が届かなかった大規模ステージが、IDA* の「メモリ定数 × 時間延長」というトレードオフで解けることを実証できました。
まとめ
IDA* は A* のメモリ問題を、反復深化 DFS という地味だが強力な手法で解決します。$f = g + h$ を最小化する原理は A* と共通で、許容的 なヒューリスティックさえ用意できれば最適解が保証されます。てくてくピクミンの Stage 28 / Stage 57 のように、状態空間が数千万 〜 数十億を超える問題で A* が打ち切られた場合の、現実的な次の一手として覚えておく価値があります。
全ステージの解析結果と実装の詳細は、本編記事「てくてくピクミン全 68 ステージの最短解 — A* 探索の実装とヒューリスティック設計」でまとめています。
コメント