動的計画法の最適解復元
概要¶
動的計画法（DP）では最適値（例: 最短手数・最大価値）を求めるだけでなく、最適解そのもの（例: 具体的な経路・選んだ品物）を復元することができる。
最適値を求める解説は多いが、最適解を復元する方法はあまり詳しく解説されていない。
最適解を復元する 2 つの方法¶
方法 1: 素朴なやり方¶
ゴールから逆順に「1 つ前の状態になりうるもの」を探索して辿る方法。
例: 迷路の最短路で手数 16 のゴールから「15 → 14 → … → 0 」と逆に辿る。
欠点: 各ノードの近傍の探索範囲が広い場合に時間がかかる。最悪オーダーレベルで計算量が悪化することもある。
方法 2: 汎用的な方法（推奨）¶
DP テーブルの更新時に、どのノードから伝播して来たかを同時にメモしておく方法。
テーブル更新時に処理を 1 行追加するだけで実現できる。
ゴールから prev 配列を辿ることで最適解を復元できる。
利点: 近傍探索が不要なため、方法 1 の欠点を解消できる。
方法の使い分け¶
| 状況 | 推奨方法 |
|---|---|
| 近傍探索が軽い場合 | どちらでも可（方法 1 は実装が楽） |
| 近傍探索コストが高い場合 | 方法 2 |
具体例¶
- BFSによる経路復元 - 迷路の最短路（BFS + prev 配列）
- ナップサック問題の最適解復元 - ナップサック DP での選択品物の復元
また、最長増加部分列(LIS)の長さの求め方 は「長さのみ」を求めるアルゴリズムだが、この方法を応用することで具体的な LIS も復元できる。
応用: 辞書順最小な解の復元¶
一般に最適解は複数存在することが多い。そのうち辞書順最小のものを求めたい場合、ゴール側からスタートに向けて DP の更新を行うことで実現できる。
- 通常: スタート → ゴール方向に DP を計算 → ゴールから
prevを逆辿り - 辞書順最小: ゴール → スタート方向に DP を計算 → スタートから順に辿る
スタートからゴール方向へ辿ることで、辞書順が最小となる経路を自然に選べる。
応用: 最適解の数え上げ¶
DP の更新部分をほんの少し修正することで、最適解の 個数 も同時に数え上げることができる。 詳細は「最短経路の個数も一緒に数え上げる最短経路アルゴリズム」などを参照。