0

Setを指定し、和の差が最小になるようSにセットを互いに素なサブセットに分割します。k

と言うと、S = {1,2,3,4,5}それらk = 2の{ {3,4}, {1,2,5} }合計{7,8}の差は最小限であるためです。合計の差S = {1,2,3}, k = 2が であるためです。{{1,2},{3}}0

この問題は、The Algorithm Design Manual のThe Partition Problemに似ています。ただし、 Steven Skienaが再配置せずに解決する方法について説明しています。

シミュレーテッドアニーリングを試してみました。だから、もっと良い方法があったのだろうか？

前もって感謝します。

4

2 に答える 2

3

ナップザックの疑似ポリタイム アルゴリズムを に使用できますk=2。私たちができる最善のことは、sum(S)/2 です。ナップザック アルゴリズムを実行する

for s in S:
    for i in 0 to sum(S):
        if arr[i] then arr[i+s] = true;

次に、sum(S)/2、次に sum(S)/2 +/- 1 などを見てください。

'k>=3' の場合、これは 3 分割問題のように NP 完全であると思います。

k>=3 に対してそれを行う最も簡単な方法は、力ずくで実行することです。これが 1 つの方法です。 

import copy
arr = [1,2,3,4]

def t(k,accum,index):
    print accum,k
    if index == len(arr):
        if(k==0):
            return copy.deepcopy(accum);
        else:
            return [];

    element = arr[index];
    result = []

    for set_i in range(len(accum)):
        if k>0:
            clone_new = copy.deepcopy(accum);
            clone_new[set_i].append([element]);
            result.extend( t(k-1,clone_new,index+1) );

        for elem_i in range(len(accum[set_i])):
            clone_new = copy.deepcopy(accum);
            clone_new[set_i][elem_i].append(element)
            result.extend( t(k,clone_new,index+1) );

    return result

print t(3,[[]],0);

シミュレーテッド アニーリングは良いかもしれませんが、特定の解の「近傍」が明確ではないため、遺伝的アルゴリズムの方が適している可能性があります。サブセットのグループをランダムに選択することから始め、サブセット間で数値を移動することで「変異」します。

于 2011-03-28T20:26:45.023 に答える
0

セットが大きい場合、私は間違いなく確率的検索に行きます。「近所が明確に定義されていない」と書くとき、spinning_plateが何を意味するのか正確にはわかりません。もちろん、それは---あるセットから別のセットにアイテムを移動するか、2つの異なるセットからアイテムを交換するかのいずれかであり、これは単純な近傍です。私は確率的検索で両方の操作を使用します（実際にはタブー検索またはシミュレーテッドアニーリングである可能性があります）。

于 2011-04-06T05:42:08.660 に答える