Разделите набор на k непересекающихся подмножеств

Задайте множество 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.

Проблема похожа на Проблему с разделами из Руководства по проектированию алгоритмов. За исключением того, что Стивен Скиена обсуждает способ решения этой проблемы без перестановки.

Я собирался попробовать имитация отжига. Так что мне интересно, если бы был лучший метод?

Заранее спасибо.


set sum algorithm data-partitioning subset
person st0le    schedule 28.03.2011    source источник
comment
Эта проблема дурь. обязательно подумаю =)   -  person Phonon    schedule 28.03.2011
comment
Что вы подразумеваете под "без переделки"?   -  person dfb    schedule 29.03.2011
comment
@spinning_plate, в версии для скиены порядок элементов имел значение, их нельзя было перетасовать....так что это не было задано.   -  person st0le    schedule 29.03.2011
comment
Как определить разность их сумм при k > 2?   -  person mbeckish    schedule 29.03.2011
comment
@mbeckish, я бы сказал что-то вроде max(sum(A)-sum(B)) для всех A,B   -  person dfb    schedule 29.03.2011
comment
@spinning_plate - Значит, вы пытаетесь свести к минимуму самую большую разницу между суммами двух подмножеств?   -  person mbeckish    schedule 29.03.2011
comment
@mbeckish - конечно, или мы могли бы сделать что-то вроде sum( avg(all X) - y ) для всех y. Это может иметь значение для определенных функций (например, глупых оптимизаций, таких как min( avg(max(subset)) для каждого подмножества(y)) для всех y, но для этих двух я не думаю, что это имеет значение.   -  person dfb    schedule 29.03.2011

Ответы (2)


arrow_upward
3
arrow_downward

Псевдополитический алгоритм для рюкзака можно использовать для k=2. Лучшее, что мы можем сделать, это суммировать (S)/2. Запустите алгоритм рюкзака

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

затем посмотрите на сумму (S)/2, затем на сумму (S)/2 +/- 1 и т. д.

Для 'k>=3' я считаю, что это NP-полное, как проблема с тремя разделами.

Самый простой способ сделать это для 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);

Имитация отжига может быть хороша, но, поскольку «соседи» конкретного решения не совсем ясны, для этого может лучше подойти генетический алгоритм. Вы начнете со случайного выбора группы подмножеств и «мутируете», перемещая числа между подмножествами.

person dfb    schedule 28.03.2011

arrow_upward
0
arrow_downward

Если наборы большие, я бы определенно пошел на стохастический поиск. Не знаю точно, что означает spinning_plate, когда пишет, что «окрестность четко не определена». Конечно же --- вы либо перемещаете один предмет из одного набора в другой, либо меняете местами предметы из двух разных наборов, и это простое соседство. Я бы использовал обе операции в стохастическом поиске (который на практике может быть табу-поиском или имитацией отжига).

person Antti Huima    schedule 06.04.2011