動的計画法

動的計画法は、最適な部分構造と重複する部分問題を持つ問題を解決するためのアルゴリズム設計パラダイムであり、各部分問題を一度だけ解き、その結果を再利用のために保存することで、指数関数的な再計算を多項式時間計算に変換します。

Definition

動的計画法は、最適化問題または数え上げ問題を、重複する部分問題の観点から再帰的にその値を定義し、各異なる部分問題を正確に一度だけ計算し、その結果をキャッシュして再計算せずに再利用できるようにすることで解決する手法です。

Scope

このトピックでは、動的計画法が適用可能であるための2つの特徴 — 最適な部分構造と重複する部分問題 — および2つの実装スタイル、トップダウンのメモ化とボトムアップのテーブル化について説明します。最長共通部分列、編集距離、ナップサック問題、行列連鎖乗算、最短経路動的計画法などの典型的な問題、ならびに状態空間設計、時間と空間のトレードオフの分析が含まれます。グラフアルゴリズムで扱われるグラフ固有の最短経路法は、同じ根底にある原理を共有していますが、ここでは除外します。

Core questions

• 問題は、最適な部分解から最適な解を構築できるような最適な部分構造を持っていますか？
• 各部分問題が多項式回数だけ再帰するように、部分問題の集合（状態空間）はどのように定義されますか？
• 解はメモ化を用いたトップダウンで実装すべきですか、それともテーブル化を用いたボトムアップで実装すべきですか？
• その値だけでなく、実際の最適な解を復元するためにテーブルをどのように再構築できますか？
• 各ステップでテーブルの一部のみが必要な場合、どのように空間を削減できますか？

Key concepts

• 最適な部分構造
• 重複する部分問題
• 最適性の原理
• メモ化
• テーブル化
• 状態空間と漸化式
• 最長共通部分列
• 編集距離
• ナップサック問題

Key theories

最適性の原理

ベルマンの最適性の原理は、最適な方策は、初期状態と決定が何であれ、残りの決定が結果の状態に対する最適な方策を構成するという特性を持つと述べています。これは動的計画法の漸化式の形式的な基礎となります。

メモ化とテーブル化

動的計画法は、再帰的な定式化にキャッシュを追加することでトップダウンで（メモ化）、または依存関係の順序でテーブルを埋めることでボトムアップで（テーブル化）実現できます。どちらも各部分問題を一度だけ計算しますが、評価順序と空間挙動が異なります。

Clinical relevance

動的計画法は実用において広く普及しています。計算生物学における配列アラインメント（Needleman-Wunsch、Smith-Waterman）、スペルチェックやバージョン管理の差分における編集距離、音声認識や通信におけるビタビアルゴリズム、オペレーションズリサーチ、金融、強化学習における動的計画法などがあります。

History

リチャード・ベルマンは1950年代にRAND研究所で動的計画法を開発しました。その名称は、研究スポンサーに受け入れられやすいように一部選ばれました。最適性の原理とベルマン方程式は、オペレーションズリサーチ、制御理論、コンピュータサイエンス全体で基礎となり、この手法は後にアルゴリズムの教科書で中心的なアルゴリズムパラダイムとして体系化されました。

Key figures

• Richard Bellman
• Thomas H. Cormen
• Jon Kleinberg
• Éva Tardos

Seminal works

• bellman1957
• cormen2009

Frequently asked questions

分割統治法と動的計画法の違いは何ですか？

どちらも問題を部分問題に分解しますが、分割統治法の部分問題は独立しており一度だけ解決されるのに対し、動的計画法の部分問題は重複しており、素朴な再帰では何度も再計算されることになります。動的計画法は、その再計算を避けるために部分問題の解をキャッシュします。

動的計画法が適用できないのはどのような場合ですか？

動的計画法は、最適な部分構造と多項式サイズの異なる部分問題の集合を必要とします。問題に最適な部分構造がない場合、または自然な状態空間が指数関数的であり圧縮できない場合、動的計画法は不正確であるか、もはや効率的ではありません。