Разделить набор на k непересекающееся подмножество - PullRequest
Новая
       30

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

0 голосов
/ 28 марта 2011

Дайте набор 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.

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

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

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

Ответы [ 2 ]

3 голосов
/ 29 марта 2011

Алгоритм псевдополитайма для ранца можно использовать для 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-полная, как проблема с 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);

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

0 голосов
/ 06 апреля 2011

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

...