M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

Memorandum

プログラミングに関する覚え書や四方山話です。
[ Home ]
2012年 1月

2012 年 1月

1月7日

●部分和問題 (4)

部分和問題の続きです。今までのプログラムは総和 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 の要素を増やすとメモリを大量に消費する場合があります。興味のある方は集合の要素数を増やすなど、いろいろなデータで試してみてください。


1月3日

●部分和問題 (3)

部分和問題の続きです。今回は「動的計画法」で部分和問題を解いてみましょう。動的計画法を簡単に説明すると、問題を小さな部分問題に分割し、その部分問題を順番に解いていき、その解を使って大きな問題の解を求める方法です。部分和問題の場合、総和が N となる部分集合があるか判定するだけでよければ、動的計画法で解くことが可能です。

部分和問題の場合、要素をひとつずつ追加しながら、総和 N となる部分集合があるか判定します。簡単な例を示しましょう。次の図を見てください。

        xs = {2, 3, 5, 8}, N = 10

                0 1 2 3 4 5 6 7 8 9 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

             0 1 2 3 4 5 6 7 8 9 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 が大きくなると、どうしても時間がかかるようになります。そこで、次回は配列を使わずにプログラムを作ってみましょう。


Copyright (C) 2012 Makoto Hiroi
All rights reserved.

[ Home ]