部分和問題
前章で触れた部分和問題とは、正の整数の配列 \(X[1..n]\) と整数 \(T\) を受け取って \(X\) の部分集合で和が \(T\) となるものがあるかどうかを答える問題です。前章ではこの問題に対する再帰的なアルゴリズムを次の真偽値関数 \(SS(i,t)\) を使って定式化しました。この式では入力 \(X[1..n]\) と \(T\) が固定されています: \[ SS(i, t) = \textsc{True} \Leftrightarrow X[i..n] \text{ の部分集合で和が }t \text{ になるものが存在する} \] 計算すべきは \(SS(1,T)\) です。この関数は次の再帰方程式を満たしました: \[ SS(i, t) = \begin{cases} \textsc{True} & \text{if } t = 0 \\ \textsc{False} & \text{if } t < 0 \text{ or } i > n \\ SS(i + 1, t) \lor SS(i + 1, t - X[i]) & \text{それ以外} \end{cases} \]
おなじみのボイラープレートを使えば、この再帰方程式を動的計画法のアルゴリズムに変形できます。
-
小問題: 再帰的な小問題は添え字 \(0 \leq i \leq n+1\) と整数 \(t \leq T\) で特定できる。ここで \(t < 0\) のときの答えは自明だから、メモを取らないようにする1。あるいは再帰方程式を書き換えて、\(t\) が負にならないようにすることもできる。 \[ SS(i, t) = \begin{cases} \textsc{True} & \text{if } t = 0 \\ \textsc{False} & \text{if } t < 0 \text{ or } i > n \\ SS(i + 1, t) & \text{if } t < X[i] \\ SS(i + 1, t) \lor SS(i + 1, t - X[i]) & \text{それ以外} \end{cases} \]
-
メモ化のためのデータ構造: 二次元配列 \(S[1..n+1, 0..T]\) に再帰方程式の値を格納できる。ここで \(S[i, t]\) が \(SS(i ,t)\) を表す。
-
評価順序: \(S[i,t]\) は最大で二つの要素に依存し、どちらも \(SS[i+1, \cdot]\) という形をしている。したがって、外側のループで行を下から上に、内側のループで列を適当な順番で考えていけば、詰まることなく配列を埋めることができる。
-
空間と時間: メモ化のためのデータ構造は空間を \(O(nT)\) だけ使う。\(S[i+1, t]\) と \(S[t+1, t - X[i]]\) が既知のとき \(S[i,t]\) は定数時間で計算できるので、アルゴリズム全体の実行時間は \(\pmb{O(nT)}\) となる。
完成したアルゴリズムを示します:
procedure \(\texttt{FastSubsetSum}\)(\(X[1..n], T\))
\(S[n+1, 0] \leftarrow \textsc{True}\)
for \(t \leftarrow 1\) to \(T\) do
\(S[n+1, t] \leftarrow \textsc{False}\)
for \(i \leftarrow n\) downto \(1\) do
\(S[i,0] = \textsc{True}\)
for \(t \leftarrow 1\) to \(X[i] - 1\) do
⟨⟨\(t < 0\) を除外する⟩⟩
\(S[i,t] \leftarrow S[i+1, t]\)
for \(t \leftarrow X[i]\) to \(T\) do
\(S[i, t] \leftarrow S[i+1,t] \lor S[i+1, t-X[i]]\)
return \(S[1,T]\)
バックトラッキングを使った再帰的なアルゴリズムの実行時間は \(O(2^{n})\) だったので、最悪計算時間が \(O(nT)\) というのは \(T\) が小さい場合には非常に大きな高速化です2。しかしもし目標の値 \(T\) が \(2^{n}\) よりもはるかに大きい場合、この for ループを使ったアルゴリズムは再帰的なアルゴリズムが考えない小問題を考えることになり、ナイーブな再帰的アルゴリズムよりも遅くなります。動的計画法は常に実行時間を改善するわけではありません3！