ナップサック問題からビタビ復号法まで：動的計画法の本質を理解する

はじめに

情報工学演習において、ナップサック問題およびビタビ復号法を実装した。本記事では、

を通して、動的計画法の本質について整理する。

最大化問題：

$$
\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}
$$

ここで

各商品について「入れる／入れない」を全探索する。

計算量は

$$
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)$ はハミング距離。

これは「最短路問題」と同型であり、
動的計画法の応用例である。

ナップサック問題からビタビ復号法までを通して、
動的計画法の考え方が分野横断的に応用できることを実感した。

今後はメモリ最適化や他の近似アルゴリズムとの比較も行っていきたい。