Задача разбиения множества чисел

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

Существует

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

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

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

Представим вход алгоритма как список вида:

S=x₁, ..., x_n

Пусть N — число элементов в множестве S. Пусть K — сумма всех элементов из множества S. То есть K=x₁ + ... + x_n. Мы построим алгоритм, который определяет, существует ли подмножество S, сумма элементов которого равна ${\displaystyle \lfloor K/2\rfloor }$. Если подмножество существует, то:

если K чётно, то остаток множества S также даст ${\displaystyle \lfloor K/2\rfloor }$

если K нечётно, остаток множества S даст сумму ${\displaystyle \lceil K/2\rceil }$. Это лучшее возможное решение.

Мы хотим определить, существует ли подмножество S, сумма элементов которого равна ${\displaystyle \lfloor K/2\rfloor }$. Пусть:

p(i, j) принимает значение True, если среди { x₁, ..., x_j } существует такое подмножество, элементы которого в сумме дают i и False в противном случае.

Тогда p(${\displaystyle \lfloor K/2\rfloor }$, n) принимает значение True тогда и только тогда, когда существует подмножество S, сумма которого равна ${\displaystyle \lfloor K/2\rfloor }$. Цель нашего алгоритма — вычислить p(${\displaystyle \lfloor K/2\rfloor }$, n). Для достижения этого мы имеем следующие рекуррентные формулы:

p(i, j) принимает значение True, если либо p(i, j − 1) принимает значение True, либо p(i − x_j, j − 1) принимает значение True

p(i, j) принимает значение False в противном случае

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

x₁, ..., x_j

тогда и только тогда, когда одно из двух верно:

существует подмножество { x₁, ..., x_j-1 }, дающее сумму i;

существует подмножество { x₁, ..., x_j-1 }, дающее сумму i − x_j, поскольку x_j + сумма этого подмножества=i.

Алгоритм строит таблицу размера ${\displaystyle \lfloor K/2\rfloor }$ на n, содержащую значения рекурсии, где ${\displaystyle K}$ — сумма значений, а ${\displaystyle n}$ — число элементов. Когда вся таблица заполнена, возвращаем ${\displaystyle P(\lfloor K/2\rfloor ),n)}$. Ниже приведена таблица P. На рисунке синяя стрелка из одного блока в другой, если значение конечного блока может зависеть от значения исходного блока. Эта зависимость является свойством рекуррентного отношения.

INPUT:  Список целых чисел S
OUTPUT: True, если S может быть разбито на два подмножества, имеющих одинаковые суммы
1 функция найти_разбиение(S):
2     n ← |S|
3     K ← sum(S)
4     P ← пустая булева таблица размера (${\displaystyle \lfloor K/2\rfloor }$ + 1) by (n + 1)
5     инициализируем верхнюю строку (P(0,x)) таблицы P значениями True
6     инициализируем крайний левый столбец (P(x, 0)) таблицы P, за исключением ячейки P(0, 0) значениями False
7     для i от 1 до ${\displaystyle \lfloor K/2\rfloor }$
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(${\displaystyle \lfloor K/2\rfloor }$, n)

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

Этот алгоритм работает за время O(K N), где N — число элементов во входном множестве, а K — сумма элементов во входном множестве.

Алгоритм может быть распространён на задачу мультиразбиения на k частей, но требует памяти O(n(k − 1)m^{k − 1}), где m является наибольшим числом во входном множестве, что делает алгоритм практически бессмысленным даже для k = 3, если только на вход не подаются очень маленькие числа^[2].

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

Существуют некоторые

Один из подходов к задаче, имитирующий способ ребёнка партнёра для игры, жадный алгоритм, который перебирает числа в порядке убывания и добавляет каждое число к меньшей сумме. Этот подход имеет время работы O(n log n). Этот эвристический алгоритм работает хорошо на практике, если числа в множестве примерно одного порядка, однако алгоритм не гарантирует получение лучшего возможного разбиения. Например, если в качестве входа дано множество S={4, 5, 6, 7, 8}, этот жадный алгоритм привёл бы к разбиению S на подмножества {4, 5, 8} и {6, 7}. Однако S имеет точное сбалансированное разбиение на подмножества {7, 8} и {4, 5, 6}.

Известно, что этот жадный подход даёт 7⁄6-аппроксимацию относительно оптимального решения оптимизационной версии. То есть, если вывод жадного алгоритма даёт два множестваs A и B, тогда ${\displaystyle \max(\sum {A},\sum {B})\leq {\tfrac {7}{6}}OPT}$, где OPT — размер наибольшего множества в лучшем разбиении^[3]. Ниже приведён пример (на языке Python) жадного алгоритма.

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)

Алгоритм может быть распространён на случаи k > 2 множеств — выбираем k наибольших элементов, распределяем их по k множествам, затем перебираем оставшиеся числа в порядке убывания и добавляем их к множеству с меньшей суммой (простая версия выше соответствует k = 2). Эта версия работает за время O(2^k n²) и известно, что она даёт аппроксимацию ${\displaystyle {\tfrac {(k+2)}{(k+1)}}}$

Другой эвристический алгоритм — метод наибольшей разности (МНР, 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 — размер множества, то при ${\displaystyle m/n<1}$ задача чаще имеет много решений, а при ${\displaystyle m/n>1}$ задача чаще имеет одно решение, либо не имеет решения вообще. Когда n и m становятся больше, вероятность хорошего разбиения стремится к 1, а плохого к 0 соответственно. Этот факт первоначально основывался на эмпирических результатах Гента и Уолша^[10], затем на методах статистической физики (Мертенс^[11][12]) и, наконец, факт доказали Боргс, Чайес^[англ.] и Питтель^[13].

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

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

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

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

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.