Search on the blog

2010年7月30日金曜日

部分和問題を切る!

DP(Dynamic Programming)の題材として、部分和問題を取り上げよう。

部分和問題はこんな感じ。

与えられた集合Aと整数Kに対して、
sum(A') = KとなるようなAの部分集合A'は存在するか?

※ここでsum(X)は集合Xの全要素の和である。

ちょっと、分かりにくいかもしれないので簡単な例題を。
A = {1, 3, 5, 12, 7}
K = 11
に対して、sum(A') = K となるようなAの部分集合A'は存在するか?
答えは、yes.
Aの部分集合A' = {1,3,7}の全要素の和は11だからである。

ということで、これをコーディングしてみよう。
普通に考えると、Aの部分集合を逐次抽出して行って、sum(A') == Kとなった時点で終了判定してループ抜ければいいのかなって感じだろう。。

しかし、Aの部分集合は全部で、2^|A|となってしまう。(|A|はAの要素数)
ということは、最悪計算量は、2^|A|である。これは、まずい。。。

とりあえず、ソースコードはこんな感じ。。


#define forf(i, n) for(int i=0; i<(int)(n); i++)

vector<int> subsetSum(vector<int> set, int K) {
vector<vector<int> > subset;
vector<int> phi;
subset.push_back(phi);

forf(i, set.size()) {
vector<vector<int> > newSubset;
forf (j, subset.size()) {
vector<int> subsetElm = subset[j];
subsetElm.push_back(set[i]);
int sum = 0;
forf (k, subsetElm.size())
sum += subsetElm[k];
if (sum == K)
return subsetElm;
newSubset.push_back(subsetElm);
}

forf(j, newSubset.size())
subset.push_back(newSubset[j]);
}

return vector<int> ();
}


さて、ここで気付いて欲しい。
上記のコードでは、sum(A') = KとなるA'をreturnしているが、もともとの問題は、sum(A') = KとなるA'が存在するかどうかだったのではないか。。
つまり、A'を出力しなくても、A'が存在するかどうかを出力すればいいのである。(このような問題を判定問題(または、決定問題)と呼びます。PとかNPとか言ってるやつは、実は判定問題に対するクラスの名称です。なので、決定問題じゃない問題に対してPとかNPとか言うのは間違いです。)

と、PとかNPはちょっと話が脱線してしまったが、

部分和問題は、条件を満たす部分集合の存在を問うているので
その部分集合を出力する必要はない。ということは‥部分集合を生成したり保持しなくてもいいんじゃないの??

この辺りにトリックが隠されてそうである。
この問題をDPでどのように多項式時間の解法に持ち込むか。
次回に続く・・・・・


0 件のコメント:

コメントを投稿