10

私が作っているゲームの場合、数字のリスト（[7、4、9、1、15、2]（Aこれにちなんで名付けられた））と別の数字のリスト（[11、18） 、14、8、3]（名前付きB）–私に提供されました。目標は、の数の合計が。の数のすべての組み合わせを見つけることAですB。例えば：

  • 1 + 2 = 3
  • 1 + 7 = 8
  • 2 + 9 = 11
  • 4 + 7 = 11
  • 1 + 2 + 4 + 7 = 14
  • 1 + 2 + 15 = 18
  • 2 + 7 + 9 = 18

...等々。（この目的のために、はと1 + 2同じ2 + 1です。）

このような小さなリストの場合、組み合わせをブルートフォースするのは簡単ですが、これらの数が数千から数万になる可能性に直面しており、アプリケーションの存続期間にわたってこのルーチンを繰り返し使用します。100％のカバレッジで妥当な時間でこれを達成するために利用できるエレガントなアルゴリズムはありますか？これに失敗した場合、妥当な時間内に「十分に良い」組み合わせのセットを提供できる、適切なヒューリスティックを見つけることができますか？

私は、擬似コードまたはまともな人気があり読みやすい言語（そこにある「and」に注意してください....;）、またはこの種の検索の実装方法についての英語の説明でさえ、アルゴリズムを探しています。

追加するために編集：

これまでに提供された多くの良い情報。みんなありがとう！今のところ要約：

  • 問題はNP完全であるため、妥当な時間で100％の精度を得るにはブルートフォースが不足することはありません。
  • この問題は、サブセット和問題またはナップサック問題のいずれかの変形と見なすことができます。この問題に適応できる可能性のある、両方のよく知られたヒューリスティックがあります。

アイデアを続けてください！そして、もう一度ありがとう！

4

4 に答える 4

5

この問題はNP完全です...これは、NP完全であることが知られているサブセット和問題のバリエーションです（実際には、サブセット和問題はあなたの問題よりも簡単です）。

詳細については、こちらをお読みください：http: //en.wikipedia.org/wiki/Subset_sum_problem

于 2010-07-05T10:55:51.300 に答える
2

コメントで述べたように、1から30までの範囲の数字で、問題は迅速に解決されます。私はそれをCでテストしました、そしてあなたの与えられた例のためにそれはミリ秒だけを必要とし、そして非常にうまくスケーリングします。複雑さはO（n + k）です。ここで、nはリストAの長さ、kはリストの長さですBが、一定の係数が高くなります（1から30までの合計を取得できる可能性は28.598あります）。

#define WIDTH 30000
#define MAXNUMBER 30

int create_combination(unsigned char comb[WIDTH][MAXNUMBER+1], 
                       int n, 
                       unsigned char i, 
                       unsigned char len, 
                       unsigned char min, 
                       unsigned char sum) {
    unsigned char j;

    if (len == 1) {
        if (n+1>=WIDTH) {
            printf("not enough space!\n");
            exit(-1);
        }
        comb[n][i] = sum;
        for (j=0; j<=i; j++)
            comb[n+1][j] = comb[n][j];
        n++;
        return n;
    }

    for (j=min; j<=sum/len; j++) {
        comb[n][i] = j;
        n = create_combination(comb, n, i+1, len-1, j, sum-j);
    }

    return n;
}

int main(void)
{
    unsigned char A[6] = { 7, 4, 9, 1, 15, 2 };
    unsigned char B[5] = { 11, 18, 14, 8, 3 };

    unsigned char combinations[WIDTH][MAXNUMBER+1];
    unsigned char needed[WIDTH][MAXNUMBER];
    unsigned char numbers[MAXNUMBER];
    unsigned char sums[MAXNUMBER];
    unsigned char i, j, k;
    int n=0, m;

    memset(combinations, 0, sizeof combinations);
    memset(needed, 0, sizeof needed);
    memset(numbers, 0, sizeof numbers);
    memset(sums, 0, sizeof sums);

    // create array with all possible combinations
    // combinations[n][0] stores the sum
    for (i=2; i<=MAXNUMBER; i++) {
        for (j=2; j<=i; j++) {
            for (k=1; k<=MAXNUMBER; k++)
                combinations[n][k] = 0;
            combinations[n][0] = i;
            n = create_combination(combinations, n, 1, j, 1, i);
        }
    }

    // count quantity of any summands in each combination
    for (m=0; m<n; m++)
        for (i=1; i<=MAXNUMBER && combinations[m][i] != 0; i++)
            needed[m][combinations[m][i]-1]++;

    // count quantity of any number in A
    for (m=0; m<6; m++)
        if (numbers[A[m]-1] < MAXNUMBER)
            numbers[A[m]-1]++;

    // collect possible sums from B
    for (m=0; m<5; m++)
        sums[B[m]-1] = 1;

    for (m=0; m<n; m++) {
        // check if sum is in B
        if (sums[combinations[m][0]-1] == 0)
            continue;

        // check if enough summands from current combination are in A
        for (i=0; i<MAXNUMBER; i++) {
            if (numbers[i] < needed[m][i])
                break;
        }

        if (i<MAXNUMBER)
            continue;

        // output result
        for (j=1; j<=MAXNUMBER && combinations[m][j] != 0; j++) {
            printf(" %s %d", j>1 ? "+" : "", combinations[m][j]);
        }
        printf(" = %d\n", combinations[m][0]);
    }

    return 0;
}

1 + 2 = 3
1 + 7 = 8
2 + 9 = 11
4 + 7 = 11
1 + 4 + 9 = 14
1 + 2 + 4 + 7 = 14
1 + 2 + 15 = 18
2 + 7 + 9 = 18
于 2010-07-05T19:30:48.473 に答える
1

ナップサック問題のように聞こえます（http://en.wikipedia.org/wiki/Knapsack_problemを参照してください。そのページでは、問題は一般にNP完全であるとも説明されています。

これは、すべての有効な組み合わせを見つけたい場合は、多くの時間が必要であることを意味すると思います。

于 2010-07-05T10:55:22.653 に答える
1

これは、部分和問題の小さな一般化です。一般に、NP完全ですが、すべての数値が整数であり、の最大数Bが比較的小さい限り、リンクしたWikipediaの記事で説明されている疑似多項式ソリューションでうまくいくはずです。

于 2010-07-05T11:03:32.990 に答える