バックトレース

概要

終了状態から逆再生しながら何かを調べるアルゴリズム。
終了となる状況が限られていたり、最後の状態が指定されているときに役立つことがある。

また、動的計画法の経路復元にも用いる。

例えば、以下のような問題を考える。

ホワイトボードあり、最初は1と書いてある。
以下の2種類の操作を自由に行える。
- 書いてある数をその3倍より1小さい数に書き換える
- 書いてある数をその3倍より1大きい数に書き換える
ホワイトボードに書いてある数を200にできるか？
できるなら、その方法は？

この程度の数なら全パターン試しても間に合うが、ゴールとなる数値が大きいと TLE する。
そこで、終了状態に指定があることに目をつけて、ゴールからの逆算を考える。

最後に $200$ になるわけだが、そのでき方は実は $67 \times 3 - 1 = 200$ しかない。
なぜなら、$199$ は $3$ の倍数ではないから。

ではその $67$ はというと、そのでき方は実は $22 \times 3 + 1 = 67$ しかない。
なぜなら、$68$ は $3$ の倍数ではないから。

同様に繰り返していくと、$200 \leftarrow 67 \leftarrow 22 \leftarrow 7 \leftarrow 2 \leftarrow 1$ という列ができる。

これを $1$ 側から見ることで、答えは次のようにわかる。

可能である
方法は、1 →（小）→ 2 →（大）→ 7 →（大）→ 22 →（大）→ 67 →（小）→ 200

このように、

場合には、逆再生してバックトレースで解くとうまくいくことがある。

動的計画法では、答えの値だけでなく、「どの選び方をすればその答えになるか」を求めたいことがある。
その場合、最終状態から「どの状態から来たか」を逆向きにたどることで、具体例を復元できる。
最長共通部分列や最長増加部分列を求めるのにも用いる。

特になし。