部分和問題

前章で触れた部分和問題とは、正の整数の配列 \(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} \]

おなじみのボイラープレートを使えば、この再帰方程式を動的計画法のアルゴリズムに変形できます。

完成したアルゴリズムを示します:

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


  1. ええ、速すぎる最適化に関する自分のルールを破っています。[return]

  2. 部分和問題は NP 困難ですが、この実行時間の上限をもって P = NP と結論することはできません。 \(T\) を入力サイズの多項式関数で抑えることができないためです。[return]

  3. 1967 年、Donald Michie はメモ関数を提案した研究の覚書 (!) でこう書いています: 「必要ない関数の値を記録するのは空間の無駄使いであり、同じ値をもう一度計算するのは時間の無駄使いである」 しかし実際には、必要のない関数の値を記録することは時間の無駄でもあります![return]



Amazon.co.jp アソシエイト (広告)
Audible の無料体験を始めよう
amazon music unlimited で音楽聞き放題
The Art of Computer Programming Volume 1 Fundamental Algorithms
プログラミングコンテストチャレンジブック [第2版]
世界標準MIT教科書 Python言語によるプログラミングイントロダクション
アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書