11

整数の 2 つのセット (正と負の両方) を取り、それぞれの中で同じ合計を持つサブセットを見つけることができるアルゴリズムを探しています。

この問題は、サブセットの和の問題と似ていますが、両側でサブセットを探している点が異なります。

次に例を示します。

リスト A {4、5、9、10、1}

リスト B {21, 7, -4, 180}

したがって、ここでの唯一の一致は次のとおりです: {10, 1, 4, 9} <=> {21, 7, -4}

この種の問題に対する既存のアルゴリズムがあるかどうかは誰にもわかりませんか?

これまでのところ、私が持っている唯一の解決策は、すべての組み合わせを試す力ずくのアプローチですが、指数時間で実行され、時間がかかりすぎないように考慮する要素の数に厳しい制限を課す必要がありました。

私が考えることができる他の唯一の解決策は、両方のリストで階乗を実行し、そこで等値を探すことですが、それでもあまり効率的ではなく、リストが大きくなるにつれて指数関数的に長くかかります.

4

4 に答える 4

9

部分和問題と同様に、この問題は弱いNP 完全であるため、時間多項式 (M) で実行される解があります。ここで、M は問題インスタンスに現れるすべての数値の合計です。動的計画法でそれを実現できます。セットごとに、2 次元のバイナリ テーブルに入力することで、考えられるすべての合計を生成できます。ここで、(k,m) で "true" とは、セットの最初の k 個の要素からいくつかの要素を選択することで、サブセットの合計 m が得られることを意味します。

繰り返し入力します-(k-1,m)が「true」に設定されている場合、(k,m)を「true」に設定します(明らかに、k-1要素からmを取得できる場合、kから取得できますk 番目の要素を選択しない場合)、または (k-1,md) が "true" に設定されている場合、d はセット内の k 番目の要素の値です (k 番目の要素を選択する場合)。

テーブルに入力すると、最後の列 (セット全体を表す列) にすべての可能な合計が表示されます。両方のセットに対してこれを行い、共通の合計を見つけます。テーブルを埋めるために使用したプロセスを逆にすることで、ソリューションを表す実際のサブセットをバックトラックできます。

于 2009-01-14T17:02:23.500 に答える
9

他の人が言ったことは真実です：

  1. この問題は NP 完全です。簡単な削減は、通常のサブセットサムです。これは、A の部分集合が B の部分集合 (両方が空ではない) になるのは、A の部分集合 (-B) の合計がゼロになる場合のみであることに注意することで示すことができます。

  2. この問題は、関連する数値のサイズが多項式であるという点で、弱く NP 完全であるだけですが、対数では指数関数的であると推測されます。これは、モニカ「NP-complete」が示唆するよりも問題が簡単であることを意味します。

  3. 動的計画法を使用する必要があります。

では、私はこの議論に何を貢献しているのでしょうか? さて、コード（Perlで）：

@a = qw(4 5 9 10 1);
@b = qw(21 7 -4 180);
%a = sums( @a );
%b = sums( @b );
for $m ( keys %a ) {
    next unless exists $b{$m};
    next if $m == 0 and (@{$a{0}} == 0 or @{$b{0}} == 0);
    print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n";
}

sub sums {
    my( @a ) = @_;
    my( $a, %a, %b );
    %a = ( 0 => [] );
    while( @a ) {
        %b = %a;
        $a = shift @a;
        for my $m ( keys %a ) {
            $b{$m+$a} = [@{$a{$m}},$a];
        }
    %a = %b;
    }
    return %a;
}

印刷します

sum(4 5 9 10) = sum(21 7)
sum(4 9 10 1) = sum(21 7 -4)

したがって、特に、元の問題で機能するソリューションが複数あります。

編集：ユーザーitzyは、この解決策が間違っていて、さらに悪いことに、複数の点で正しく指摘しました!! 大変申し訳ありませんが、上記の新しいコードでこれらの問題に対処できれば幸いです。それにもかかわらず、まだ 1 つの問題があります。つまり、特定の部分和について、可能な解の 1 つしか表示されないということです。単純なエラーであった以前の問題とは異なり、これは意図的な制限として分類されます。幸運を祈るとともに、バグに気をつけてください！

于 2009-01-14T17:38:45.003 に答える
1

すべての迅速な対応に感謝します!

動的計画法の解決策は、現在の網羅的なアプローチと実際には違いはありません。最適な解決策が必要な場合は、考えられるすべての組み合わせを検討する必要があると思いますが、この完全な合計のリストを生成するのにかかる時間は長すぎます..簡単なテストを行ったところ、x 個の要素について考えられるすべての合計を生成するのにかかる時間は、すぐに 1 分を超えました。

11 elements took - 0.015625 seconds
12 elements took - 0.015625 seconds
13 elements took - 0.046875 seconds
14 elements took - 0.109375 seconds
15 elements took - 0.171875 seconds
16 elements took - 0.359375 seconds
17 elements took - 0.765625 seconds
18 elements took - 1.609375 seconds
19 elements took - 3.40625 seconds
20 elements took - 7.15625 seconds
21 elements took - 14.96875 seconds
22 elements took - 31.40625 seconds
23 elements took - 65.875 seconds
24 elements took - 135.953125 seconds
25 elements took - 282.015625 seconds
26 elements took - 586.140625 seconds
27 elements took - 1250.421875 seconds
28 elements took - 2552.53125 seconds
29 elements took - 5264.34375 seconds

私たちが解決しようとしているビジネス上の問題については、これは実際には受け入れられません.. 製図板に戻って、本当にすべての解決策を知る必要があるのか​​ 、それとも 1 つだけで解決できるのかを確認します (最小/最大のサブセット、たとえば)代わりに、問題を単純に解決し、アルゴリズムを期待通りに実行できることを願っています。

ありがとうございます！

于 2009-01-15T15:22:17.913 に答える
0

サブセットの合計はNp完全であり、問​​題を多項式でそれに減らすことができるため、問題もNP完全です。

于 2009-01-14T16:47:59.503 に答える