応用情報の科目B問3では、漸化式や DP (動的計画法) を擬似言語で読み解く問題が出ます。設計戦略 (DP・分割統治・貪欲) の名前と特徴を押さえましょう。
鳴海 理央
動的計画法 は、部分問題の解を保存して全体を組み立てる手法です。
フィボナッチ・最短経路・ナップザック問題などで定番。
砂原 ニコ
DP の何がうれしいの?
緒方 ナオミ 先生
メモ化 で同じ計算を繰り返さないため、指数時間が多項式時間に化けるの。
フィボナッチを再帰で素朴に書くと O(2^n) なのが、DP なら O(n) になる、という劇的な高速化。
鳴海 理央
分割統治法 は、問題を半分ずつに分けて解いて統合。
マージソート・クイックソート・FFT などが代表例。
貪欲法 は、各ステップで局所最適を選ぶ手法で、コイン両替や Dijkstra の経路選択で使います。
藤咲 まりあ
貪欲法って…なんだか欲張りな感じですねぇ。
緒方 ナオミ 先生
ふふっ、そうなのよ。
ただし常に最適解を出せるわけではないの。
たとえばコイン両替で日本の硬貨は貪欲で最適だけど、特殊な額面だと最適にならないこともある。
最適解を保証したいときは DP に切り替える、という判断ができれば一人前ね。
確認クイズ
動的計画法を適用する典型的な前提として、最も適切なものはどれか。
- 問題が完全に独立した部分問題に分割でき、依存関係がない
- 部分問題の解が重複して何度も必要になり、それを記憶することで計算量を削減できる
- 各ステップで局所最適を選べば必ず全体最適が得られる
- 問題が線形時間で解けることが事前に分かっている
こたえを見る
正解: 2. 部分問題の解が重複して何度も必要になり、それを記憶することで計算量を削減できる
DP は『部分問題の重複』が前提。重複がなければ単純な再帰や分割統治で十分です。重複した解を記憶 (メモ化) することで、指数時間→多項式時間の高速化を実現します。
