ナップサック問題からビタビ復号法まで：動的計画法の本質を理解する
はじめに
情報工学演習において、ナップサック問題およびビタビ復号法を実装した。本記事では、
- 全列挙法
- 動的計画法
- グリーディ法
- ビタビ復号法
を通して、動的計画法の本質について整理する。
ナップサック問題
数理定式化
最大化問題：
$$
\max \sum_{i=1}^{n} p_i x_i
$$
制約条件：
$$
\sum_{i=1}^{n} c_i x_i \le C, \quad x_i \in {0,1}
$$
ここで
- $p_i$：価値
- $c_i$：重さ
- $x_i$：選択変数
全列挙法
各商品について「入れる／入れない」を全探索する。
計算量は
$$
O(2^n)
$$
であり、商品数が増えると現実的に計算不能となる。
動的計画法
状態定義
$$
S(i,c) = 商品1からiまでを用いた容量cでの最大価値
$$
初期条件
$$
S(0,c) = 0
$$
漸化式
$$
S(i,c) =
\begin{cases}
S(i-1,c) & (c_i > c) \
\max{S(i-1,c), S(i-1,c-c_i)+p_i} & (c_i \le c)
\end{cases}
$$
計算量は
$$
O(nC)
$$
指数時間から擬多項式時間へと改善される。
グリーディ近似解法
価値密度を定義する。
$$
r_i = \frac{p_i}{c_i}
$$
降順に並べ、容量を超えるまで詰め込む。
計算量は
$$
O(n \log n)
$$
高速だが最適解を保証しない。
ビタビ復号法
畳み込み符号の復号を動的計画法として実装した。
更新式は
$$
S[k][j] = \min_i \left( S[k-1][i] + d(i,j) \right)
$$
ここで $d(i,j)$ はハミング距離。
これは「最短路問題」と同型であり、
動的計画法の応用例である。
学んだこと
- 計算量はアルゴリズム設計の本質である
- 最適部分構造を見抜くことが重要
- 動的計画法は最短路問題と密接に関係している
- 理論と実装を結びつけることで理解が深まる
おわりに
ナップサック問題からビタビ復号法までを通して、
動的計画法の考え方が分野横断的に応用できることを実感した。
今後はメモリ最適化や他の近似アルゴリズムとの比較も行っていきたい。