部分和問題の続きです。今までのプログラムは総和 N に対応する配列を用意しました。N が大きくなると、配列から True を検索する処理に時間がかかるようになります。そこで、配列の代わりに Python の「セット (集合 : set) 」を使って部分集合の総和を管理することにします。プログラムは次のようになります。
リスト : 部分和問題 (1)
def subset_sum3(n, xs):
a = set([0])
for x in xs:
b = []
for y in a:
if x + y <= n: b.append(x + y)
a.update(b)
return n in a
最初に部分集合の総和を管理するセット a を {0} に初期化します。セット a から要素を取り出している間、セット a は更新できないので、新しく追加する総和の値を配列 b にセットしておきます。a の要素をすべてチェックしてから a.update(b) で新しい総和を a に追加します。このとき、重複要素のチェックが行われるので、同じ値が複数追加されることはありません。
それでは実行結果を示します。
リスト : テストプログラム
nums = [ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946]
def test():
for x in [16,17,18,19,20]:
xs = nums[0:x]
s = time.clock()
print subset_sum3(sum(xs) - 1, xs)
print time.clock() - s
True 0.00423713069678 True 0.00662542306355 True 0.0107932712118 True 0.0173049926736 True 0.0302532863814 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.7
前回よりも速くなりましたが、それでも分岐限定法には及びません。そこで、分岐限定法と同様の枝刈りを行うことにします。次のリストを見てください。
リスト : 部分和問題 (2)
def subset_sum31(n, xs):
a = set([0])
r = sum(xs)
for x in xs:
b = []
r -= x
for y in a:
if x + y <= n and x + y + r >= n: b.append(x + y)
a.update(b)
return n in a
残りの要素の総和を変数 r で管理します。x + y + r が n 未満であれば、総和 x + y は n にならないのは明白です。x + y を集合 a を追加する必要はありません。
実行結果は次のようになりました。
True 0.000512076255502 True 0.000274895273003 True 0.00027992384507 True 0.000292215910123 True 0.000306184165865 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.7
分岐限定法と同等以上の実行速度になりました。
もうひとつ、簡単なテストを行ってみましょう。次のリストを見てください。
リスト : 簡単なテスト (2)
nums1 = [93057, 89728, 88489, 84353, 83190, 73846, 63272, 63121, 62842, 60169,
54123, 51409, 46751, 39788, 35209, 30222, 29706, 24978, 14548, 10283]
def test1():
for x in [16,17,18,19,20]:
xs = nums1[0:x]
s = time.clock()
subset_sum1(sum(xs)/2, xs)
print time.clock() - s
s = time.clock()
print subset_sum31(sum(xs)/2, xs)
print time.clock() - s
print "-----"
nums1 の整数値は乱数で生成して、それを降順に並べたものです。分岐限定法 (subset_sum1) と動的計画法 (subset_sum31) で実行時間を計測したところ、結果は次のようになりました。
0.0354595346615 False 0.0105437981643 ----- [93057, 89728, 88489, 73846, 63272, 46751, 39788, 29706] 0.0649498749143 True 0.0182512023176 ----- 0.113215227075 False 0.0312559277785 ----- [89728, 84353, 83190, 63272, 62842, 46751, 39788, 30222, 29706, 14548] [89728, 88489, 63272, 63121, 62842, 46751, 39788, 35209, 30222, 24978] 0.172173837736 True 0.0539378608175 ----- [88489, 84353, 83190, 62842, 60169, 54123, 51409, 29706, 24978, 10283] [89728, 63272, 63121, 62842, 60169, 54123, 46751, 39788, 30222, 24978, 14548] [93057, 88489, 84353, 83190, 73846, 51409, 35209, 29706, 10283] [93057, 89728, 73846, 63272, 63121, 46751, 39788, 35209, 30222, 14548] 0.254507206922 True 0.0768189811834 ----- 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.7
分岐限定法よりも動的計画法の方が速くなりました。ただし、今回のプログラム (subset_sum31) は集合 xs の要素を増やすとメモリを大量に消費する場合があります。興味のある方は集合の要素数を増やすなど、いろいろなデータで試してみてください。
部分和問題の続きです。今回は「動的計画法」で部分和問題を解いてみましょう。動的計画法を簡単に説明すると、問題を小さな部分問題に分割し、その部分問題を順番に解いていき、その解を使って大きな問題の解を求める方法です。部分和問題の場合、総和が N となる部分集合があるか判定するだけでよければ、動的計画法で解くことが可能です。
部分和問題の場合、要素をひとつずつ追加しながら、総和 N となる部分集合があるか判定します。簡単な例を示しましょう。次の図を見てください。
xs = {2, 3, 5, 8}, N = 10
０ １ ２ ３ ４ ５ ６ ７ ８ ９ 10
-------------------------------------------------
0: {} ○ × × × × × × × × × ×
1: {2} ○ × ○ × × × × × × × ×
2: {2, 3} ○ × ○ ○ × ○ × × × × ×
3: {2, 3, 5} ○ × ○ ○ × ○ × ○ ○ × ○
4: {2, 3, 5, 8} ○ × ○ ○ × ○ × ○ ○ × ○
上図は xs = {2, 3, 5, 8} で N = 10 の部分集合があるか判定する場合です。最初に N + 1 の配列 Ai を用意します。空集合の総和は 0 なので A0[0] に○をセットします。次に、要素 2 を追加します。部分集合は { } と {2} になります。A1[0] と A1[2] に○をセットします。その次に要素 3 を追加します。追加される部分集合は {3} と {2, 3} になるので、A2[0], A2[2], A2[3] と A2[5] に○をセットします。
つまり、i 番目の要素 x を追加する場合、Ai-1 で○が付いている位置を y とすると、Ai[y] と Ai[x + y] に○をセットすればいいわけです。添字 y は部分集合の総和を表しています。Ai[y] に○をセットすることは、その部分集合に x を加えないことを意味し、Ai[x + y] に○をセットすることは、その部分集合に x を追加することを意味するわけです。
次に 5 を追加します。A2 の○の位置は 0, 2, 3, 5 なので、これに 5 を足した 5, 7, 8, 10 の位置に○をセットします。最後に 8 を追加します。A3 の○の位置は 0, 2, 3, 5, 7, 8, 10 なので、これに 8 を足した 8, 10 の位置に○をセットします。A4[10] の値が○になので、部分和が 10 となる部分集合があることがわかります。
もうひとつ簡単な例を示しましょう。今度は総和が 14 となる部分集合があるか判定します。
xs = {2,3,5,8}, N = 14
０ １ ２ ３ ４ ５ ６ ７ ８ ９ 10 11 12 13 14
----------------------------------------------------------
0: {} ○ × × × × × × × × × × × × × ×
1: {2} ○ × ○ × × × × × × × × × × × ×
2: {2,3} ○ × ○ ○ × ○ × × × × × × × × ×
3: {2,3,5} ○ × ○ ○ × ○ × ○ ○ × ○ × × × ×
4: {2,3,5,8} ○ × ○ ○ × ○ × ○ ○ × ○ ○ × ○ ×
3 番目で○の位置は 0, 2, 3, 5, 7, 8, 10 です。次は 8 を追加しますが、総和 14 より大きい値は不要なので、8, 10, 11, 13 の位置に○を追加します。14 の位置は×なので、総和が 14 となる部分集合は無いことがわかります。
プログラムは次のようになります。
リスト : 部分和問題 (動的計画法)
def subset_sum2(n, xs):
a = [False] * (n + 1)
a[0] = True
for x in xs:
for i in xrange(n - x, -1, -1):
if a[i]: a[x + i] = True
return False
○を True で、×を False で表します。配列をひとつで済ますため、配列の後ろから True の位置を検索していることに注意してください。また、検索の開始位置を n - x とすることで、True をセットするときの範囲チェックを省略しています。今回のプログラムでは xs の要素をすべてチェックしていますが、x + i が n と等しくなったら return で True を返してもかまいません。あとは特に難しいところはないと思います。
それでは実際に試してみましょう。テストプログラムを示します。
リスト : テストプログラム
nums = [ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946]
def test():
for x in [16,17,18,19,20]:
xs = nums[0:x]
s = time.clock()
print subset_sum2(sum(xs) - 1, xs)
print time.clock() - s
実行結果は次のようになりました。
True 0.00835553121975 True 0.01373219222 True 0.0233462632821 True 0.0395391034335 True 0.0669884021573 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.7
ナイーブな方法よりも高速になりましたが、分岐限定法にはかないませんでした。集合の要素数を M, 総和を N とすると、今回のプログラムの実行速度は N * M に比例します。たとえば、N の値を (xs[-1] - 1) とすると、実行結果は次のようになります。
True 0.00331829883407 True 0.00521742288475 True 0.00883408366147 True 0.0148563574421 True 0.0251914698656 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.7
N が小さくなったので、実行時間も速くなりました。このように、動的計画法では N が大きくなると、どうしても時間がかかるようになります。そこで、次回は配列を使わずにプログラムを作ってみましょう。