Меню

Главная
Случайная статья
Настройки
Задача разбиения множества чисел
Материал из https://ru.wikipedia.org

Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2. Хотя задача разбиения чисел является NP-полной, существует решение псевдополиномиального времени методом динамического программирования и существуют эвристические алгоритмы решения для многих конкрентных задач либо оптимально, либо приближённо. По этой причине задачу называют "простейшей NP-трудной задачей"[1].

Существует оптимизационная версия задачи разбиения, в которой требуется разбить мультимножество S на два подмножества S1 и S2, таких, что разность между суммой элементов S1 и суммой элементов S2 минимальна. Оптимизационная версия является NP-трудной задачей, но на практике может быть решена эффективно[2].

Содержание

Примеры

Если дано множество S={3,1,1,2,2,1}, допустимым решением задачи разбиения являются два множества S1={1,1,1,2} и S2={2,3}. Оба множества имеют сумму 5, и они являются разбиением множества S. Заметим, что это решение не уникально. S1={3,1,1} и S2={2,2,1} является другим решением.

Не любое мультимножество положительных целых чисел имеет разбиение на две части с равными суммами. Пример такого множества — S={2,5}.

Алгоритм псевдополиномиального времени

Задача может быть решена с помощью динамического программирования, если размер множества и размер суммы целых чисел в множестве не слишком велики, чтобы требования в памяти не стали невыполнимыми.

Представим вход алгоритма как список вида:
S=x1, ..., xn


Пусть N — число элементов в множестве S. Пусть K — сумма всех элементов из множества S. То есть K=x1 + ... + xn. Мы построим алгоритм, который определяет, существует ли подмножество S, сумма элементов которого равна . Если подмножество существует, то:
если K чётно, то остаток множества S также даст
если K нечётно, остаток множества S даст сумму . Это лучшее возможное решение.


Рекуррентные соотношения

Мы хотим определить, существует ли подмножество S, сумма элементов которого равна . Пусть:
p(i, j) принимает значение True, если среди { x1, ..., xj } существует такое подмножество, элементы которого в сумме дают i и False в противном случае.


Тогда p(, n) принимает значение True тогда и только тогда, когда существует подмножество S, сумма которого равна . Цель нашего алгоритма — вычислить p(, n). Для достижения этого мы имеем следующие рекуррентные формулы:
p(i, j) принимает значение True, если либо p(i, j 1) принимает значение True, либо p(i xj, j 1) принимает значение True
p(i, j) принимает значение False в противном случае


Причина этому следующая: существует некоторое подмножество S, сумма которого равна i для чисел
x1, ..., xj


тогда и только тогда, когда одно из двух верно:
существует подмножество { x1, ..., xj-1 }, дающее сумму i;
существует подмножество { x1, ..., xj-1 }, дающее сумму i xj, поскольку xj + сумма этого подмножества=i.


Псевдополиномиальный алгоритм

Алгоритм строит таблицу размера на n, содержащую значения рекурсии, где — сумма значений, а — число элементов. Когда вся таблица заполнена, возвращаем . Ниже приведена таблица P. На рисунке синяя стрелка из одного блока в другой, если значение конечного блока может зависеть от значения исходного блока. Эта зависимость является свойством рекуррентного отношения. 
INPUT:  Список целых чисел S
OUTPUT: True, если S может быть разбито на два подмножества, имеющих одинаковые суммы
1 функция найти_разбиение(S):
2     n  |S|
3     K  sum(S)
4     P  пустая булева таблица размера ( + 1) by (n + 1)
5     инициализируем верхнюю строку (P(0,x)) таблицы P значениями True
6     инициализируем крайний левый столбец (P(x, 0)) таблицы P, за исключением ячейки P(0, 0) значениями False
7     для i от 1 до 
8         для j от 1 до n
9             если (i-S[j-1]) >= 0
10               P(i, j)  P(i, j-1) или P(i-S[j-1], j-1)
11            иначе
12               P(i, j)  P(i, j-1)
13    вернуть значение P(, n)


Пример

Ниже приведена таблица P для использованного выше множества S={3, 1, 1, 2, 2, 1}:

Анализ

Этот алгоритм работает за время O(K N), где

Алгоритм может быть распространён на задачу мультиразбиения на

Специальный случай задачи о сумме подмножеств

Задача о разбиении можно рассматривать как частный случай задачи о сумме подмножеств и решение методом псевдополиномиального времени динамического программирования, данное выше обобщается до решения задачи о сумме подмножеств.

Аппроксимирующие алгоритмы

Существуют некоторые эвристические алгоритмы для аппроксимации оптимизационной задачи разбиения. Они могут быть расширены до точных алгоритмов линейного времени[2].

Жадный алгоритм

Один из подходов к задаче, имитирующий способ ребёнка партнёра для игры, жадный алгоритм, который перебирает числа в порядке убывания и добавляет каждое число к меньшей сумме. Этот подход имеет время работы

Известно, что этот жадный подход даёт 76-аппроксимацию относительно оптимального решения оптимизационной версии. То есть, если вывод жадного алгоритма даёт два множестваs 
def find_partition(int_list):
    "Разбиваем `int_list` на два множества с одинаковыми суммами "
    A=set()
    B=set()
    for n in sorted(int_list, reverse=True):
        if sum(A) < sum(B):
           A.add(n)
        else:
           B.add(n)
    return (A, B)


Алгоритм может быть распространён на случаи

Разностный алгоритм

Другой эвристический алгоритм — метод наибольшей разности (МНР, en:Largest Differencing Method, LDM)[6], который называется эвристическим методом Кармаркара–Карпа[2], по имени учёных, опубликовавших метод в 1982[7]. МНР имеет две фазы. Первая фаза алгоритма берёт два наибольших числа из входа и заменяет их разностью. Повторяем операцию, пока не останется одно число. Замена представляет решение разместить два числа в разные подмножества, но в какие множества эти числа размещаются, решение не принимается. В конце первой фазы оставшееся единственное число является разностью двух сумм подмножеств. На втором этапе строится актуальное решение[1].

Разностный эвристический алгоритм работает лучше, чем жадный алгоритм, но остаётся плохим для задач, в которых числа экспоненционально зависят от размера множества[1].

Следующий код на Java представляет первую фазу алгоритма Кармаркара – Карпа. Алгоритм использует кучу для эффективного поиска пары наибольших чисел среди оставшихся. 
int karmarkarKarpPartition(int[] baseArr) {	
    // create max heap	
    PriorityQueue<Integer> heap=new PriorityQueue<Integer>(baseArr.length, REVERSE_INT_CMP);

    for (int value : baseArr) {		
        heap.add(value);	
    }

    while(heap.size() > 1) {
        int val1=heap.poll();	
        int val2=heap.poll();	
        heap.add(val1 - val2);
    }

    return heap.poll();
}


Другие подходы

Существуют также алгоритмы с отсечением по времени[англ.], основанные на разностной эвристической схеме, которые сначала находят решение, полученное разностной эвристической схемой, затем находится поступательно лучшие решения, если время позволяет (возможен экспоненциальный рост времени работы для получения оптимального решения в худшем случае)[8][9].

Сложные случаи

Множества с только одним или отсутствием разбиений чаще всего наиболее сложны (или наиболее расточительны) для получения решения относительно размера входа. Если значения малы по сравнению с размером множества, хорошие разбиения наиболее вероятны. Известно, что задача претерпевает «фазовый переход», когда хорошие разбиения наиболее вероятны для одних множеств и маловероятны для других. Если m — число бит, необходимых для выражения любого числа из множества, а n — размер множества, то при задача чаще имеет много решений, а при задача чаще имеет одно решение, либо не имеет решения вообще. Когда n и m становятся больше, вероятность хорошего разбиения стремится к 1, а плохого к 0 соответственно. Этот факт первоначально основывался на эмпирических результатах Гента и Уолша[10], затем на методах статистической физики (Мертенс[11][12]) и, наконец, факт доказали Боргс, Чайес[англ.] и Питтель[13].

Варианты и обобщения

Существует задача о 3-разбиении множества чисел[англ.], которая ищет разбиение множества S на |S|/3 тройки, каждая тройка с той же суммой. Эта задача совершенно отличается от задачи разбиения и не имеет алгоритма с псевдополиномиальным временем работы, если только не P=NP[14].

Задача разбиения на несколько множеств обобщает оптимизационную версию задачи разбиения. Здесь целью является разбиение множества или мультимножества n целых чисел на заданное число k подмножеств, минимизируя разность между наименьшей и наибольшей суммой чисел в подмножествах[2].

Дальнейшие обобщения задачи разбиения можно найти в статье «Задача об упаковке в контейнеры».

Вероятностная версия

Связанная задача, в чём-то похожая на парадокс дней рождения, заключается в поиске размера входного множества, для которого вероятность существования решения равна 0,5 при условии, что каждый элемент множества случайно выбран между 1 и некоторым заданным значением.

Решение этой задачи может быть парадоксальным. Например, при выборе случайно целых чисел между 1 и одним миллионом, многие люди считают, что ответом будет тысячи, десятки тысяч, или даже сотни тысяч, хотя, на самом деле, правильным ответом будет примерно 23 (подробности — в статье Задача разбиения).

Примечания
  1. 1 2 3 Hayes, 2002.
  2. 1 2 3 4 5 Korf, 2009.
  3. 1 2 Graham, 1969, с. 416–429.
  4. Kellerer, Pferschy, Pisinger, 2004, с. 94.
  5. Martello, Toth, 1990, с. 105–136.
  6. Michiels, Korst, Aarts, 2003, с. 71–75.
  7. Karmarkar, Karp, 1982.
  8. Korf, 1998.
  9. Mertens, 1999.
  10. Gent, Walsh, 1996.
  11. Mertens, 1998.
  12. Mertens, 2001.
  13. Borgs, Chayes, Pittel, 2001.
  14. Garey, Johnson, 1979, с. 96–105.


Литература
Downgrade Counter