将一个集合划分为 k 个不相交子集

Question

给定一个集合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 。

该问题类似于算法设计手册中的分区问题。除了Steven Skiena讨论了一种无需重新排列即可解决该问题的方法。

我本来打算尝试模拟退火。所以我想知道是否有更好的方法？

提前致谢。

Answer 1

背包的伪多时间算法可用于 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”，我相信这是 NP 完全问题，就像 3 划分问题一样。

对于 k>=3 来说，最简单的方法就是暴力破解，这是一种方法，不确定它是否是最快的或最干净的。

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);

模拟退火可能很好，但由于特定解决方案的“邻居”并不真正清楚，因此遗传算法可能更适合于此。您首先会随机选择一组子集，然后通过在子集之间移动数字来“变异”。

Answer 2

如果集合很大，我肯定会选择随机搜索。当写“邻居没有明确定义”时，不知道 spin_plate 到底是什么意思。当然是——你要么将一个项目从一组移动到另一组，要么交换两个不同组中的项目，这是一个简单的邻域。我会在随机搜索中使用这两种操作（实际上可以是禁忌搜索或模拟退火。）