部分和

\(\textsc{SubsetSum}\) というもっと複雑な問題を考えましょう。正の整数の集合 \(X\) とターゲットとなる整数 \(T\) が与えられたときに、和が \(T\) となる \(X\) の部分集合を求める問題です。

条件を満たす部分集合が複数存在しても構わないことに注意してください。例えば \(X = \lbrace 8,6,7\) \(,5,3,10,\) \(9 \rbrace\) で \(T = 15\) のとき、答えは \(\textsc{True}\) であり、和が 15 になる部分集合は \(\lbrace 8, 7 \rbrace\), \(\lbrace 7,5,3 \rbrace\), \(\lbrace 6, 9 \rbrace\) の三つです。一方 \(X = \lbrace 11, 6, 5, 1, 7, 13, 12 \rbrace\) で \(T = 15\) のとき、答えは \(\textsc{False}\) です。

自明なケースが二つあります。一つは \(T = 0\) のときで、この場合すぐに \(\textsc{True}\) を答えることができます。なぜなら空集合は任意の集合 \(X\) の部分集合であり、要素の和が \(0\) だからです¹。もう一つは "\(T < 0\)" または "\(T \neq 0\) かつ \(X\) が空集合" のときで、この場合は答えが \(\textsc{False}\) であるとすぐに分かります。

一般の場合について、\(x \in X\) を任意に取ってきたとします (\(X\) が空の場合は既に処理しました)。 和が \(T\) となる \(X\) の部分集合が存在するのは、次の条件どちらかが真のときです:

• \(x\) を含む \(X\) の部分集合であって和が \(T\) になるものが存在する。
• \(x\) を含まない \(X\) の部分集合であって和が \(T\) になるものが存在する。

最初の場合では、\(X \backslash \lbrace x \rbrace\) の部分集合であって和が \(T - x\) であるものが存在します。二つ目の場合では、\(X \backslash \lbrace x \rbrace\) の部分集合であって和が \(T\) であるものが存在します。したがって、\(\textsc{SubsetSum}(X, T)\) という問題を \(\textsc{SubsetSum}(X \backslash \lbrace x \rbrace, T - x)\) と \(\textsc{SubsetSum}(X \backslash \lbrace x \rbrace, T)\) というより単純なインスタンスに帰着させることができます。この考え方によるアルゴリズムを以下に示します:

正しさ

このアルゴリズムの正しさの証明は帰納法の簡単な練習問題としてちょうどいいでしょう:

\(T = 0\) のとき、空集合の和が \(T\) と等しくなるので、\(\textsc{True}\) が正しい答えです。 \(T\) が負または \(X\) が空のとき、和が \(T\) となる \(X\) の部分集合は存在しないので、\(\textsc{False}\) が正しい答えです。そうでなければ、和が \(T\) となる \(X\) の部分集合は \(x\) を含むか含まないかのどちらかであり、どちらの場合も再帰の妖精によって正しくチェックされます。証明終わり。

解析

このアルゴリズムを解析するには、実装の詳細を正確に決める必要があります。まず入力の集合 \(X\) は配列 \(X[1..n]\) と表されているとします。

アルゴリズムの再帰の部分で、任意の要素 \(x \in X\) を選ぶ操作があります。残りの要素 \(X \backslash \lbrace x \rbrace\) がなるべく簡単に表記できてかつ簡単に計算できるような \(x\) を選んで再帰呼び出しのオーバーヘッドを抑えることが望ましいので、ここでは配列の最後の要素 \(X[n]\) を \(x\) として選ぶことにします。こうすれば部分集合 \(X \backslash \lbrace x \rbrace\) は \(X[1..n-1]\) と表記できます。

また再帰呼び出しにおいて部分配列の完全なコピーを渡すのは ――配列のコピーは \(\Theta(n)\) 時間の処理なために―― 時間がかかりすぎるので、代わりに配列への参照 (あるいは開始アドレス) とその長さだけを再帰呼び出しに渡すようにします (\(X\) をグローバル変数にして、再帰呼び出しで \(X\) への参照を渡さないようにもできます)。

実装をこのように選べば、このアルゴリズムの実行時間 \(T(n)\) は再帰方程式 \(T(n) \leq T(n - 1) + O(1)\) を満たし、その解は \(T(n) = O(2^{n})\) です。求めるには再帰木を使うか、「あ、この再帰方程式って Hanoi の塔で解いたじゃん」を使います。最悪ケース ――例えば \(T\) が \(X\) の全ての要素の和よりも大きい場合―― では再帰木が高さ \(n\) の完全二分木となり、このアルゴリズムは \(2^{n}\) 個ある \(X\) の部分集合を全て調べます。

変種

ここまで説明してきたアルゴリズムを少しだけ変更すれば、\(\textsc{SubsetSum}\) 問題の変種を解くことができます。例えば次に示すのは、和が \(T\) となる \(X\) の部分集合が存在するなら実際に構築してそれを返し、存在しないならエラー値 \(\textsc{None}\) を返すアルゴリズムです。このアルゴリズムで使われている再帰的な戦略はこれまでの判定問題に対するものと全く同じであり、実行時間は \(O(2^{n})\) です。実行時間の解析は新しい要素の追加が \(O(1)\) 時間で行えるデータ構造 (例えば単純連結リスト) を仮定すると簡単に行えますが、仮に新しい要素の追加に \(O(n)\) 時間がかかるデータ構造 (例えばソート済み配列) を使ったとしても実行時間は \(O(2^{n})\) で変わりません。

\(\textsc{SubsetSum}\) 問題の他の変種としては、和がある値になる部分集合の数を数える問題や和がある値になる部分集合の中で何らかの基準に沿って一番良いものを選ぶ問題などがあります。

バックトラッキングを使って解けるたいていの問題には、この「同じ再帰的な戦略がその問題のたくさんの変種に対して使える」という特徴があります。例えば一つ前の節で紹介したあるゲームの状態が良いか悪いかを求める問題では、見つかった良い手を返したり、全ての良い手を含む配列を返すようにアルゴリズムを改変するのは簡単です。

このことから、バックトラッキングを使ったアルゴリズムを設計するときには、問題の変種の中で可能な限り一番単純なものを考えるべきだということが言えます。複雑な情報やデータ構造ではなくて、一つの値や真偽値を求める問題が最初に考えるものとして適しているでしょう。

1. 他のどの値になると言うのです？^[return]