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

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

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

Примеры

Если дано множество 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. На рисунке синяя стрелка из одного блока в другой, если значение конечного блока может зависеть от значения исходного блока. Эта зависимость является свойством рекуррентного отношения.

Зависимости ячеек (i, j) таблицы

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].

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

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

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

Существуют некоторые эвристические алгоритмы для аппроксимации оптимизационной задачи разбиения. Они могут быть расширены до точных алгоритмов линейного времени^[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)}}}$ ^[3]. Таким образом, мы имеем приближенную схему полиномиального времени (PTAS) для задачи разбиения на несколько частей, хотя это не полностью приближенная схема полиномиального времени (время работы экспоненциально для желаемого уровня гарантированной аппроксимации). Однако существуют варианты этой идеи, которые являются полностью приближенными схемами полиномиального времени для задачи о сумме подмножеств, а следовательно, и для задачи разбиения^[4][5].

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

Другой эвристический алгоритм — метод наибольшей разности (МНР, 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 (подробности — в статье Задача разбиения).

Примечания

1. Hayes, 2002.
2. Korf, 2009.
3. 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.

Литература

• Silvano Martello, Paolo Toth. 4 Subset-sum problem // Knapsack problems: Algorithms and computer interpretations. — Wiley-Interscience, 1990. — ISBN 0-471-92420-2.
• Ron L. Graham. Bounds on multiprocessor timing anomalies // SIAM J. Appl. Math.. — 1969. — Т. 17, вып. 2.
• Richard E. Korf. Multi-Way Number Partitioning // IJCAI. — 2009.
• Wil Michiels, Jan Korst, Emile Aarts. Performance ratios for the Karmarkar–Karp differencing method // Electronic Notes in Discrete Mathematics. — 2003. — Т. 13.
• Michael Garey, David Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. — 1979. — ISBN 0-7167-1045-5.
• Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack problems. — Springer, 2004. — С. 97. — ISBN 9783540402862.
• Brian Hayes. The Easiest NP Hard Problem // American Scientist. — 2002. — May–June.
• Narenda Karmarkar, Richard M. Karp. The Differencing Method of Set Partitioning. — Technical Report UCB/CSD 82/113. — University of California at Berkeley: Computer Science Division (EECS), 1982.
• Ian Gent, Toby Walsh. Phase Transitions and Annealed Theories: Number Partitioning as a Case Study. — John Wiley and Sons, 1996. — С. 170–174.
• Ian Gent, Toby Walsh. Analysis of Heuristics for Number Partitioning // Computational Intelligence. — 1998. — Т. 14, вып. 3. — С. 430–451. — doi:10.1111/0824-7935.00069.
• Stephan Mertens. Phase Transition in the Number Partitioning Problem // Physical Review Letters. — 1998. — Ноябрь (т. 81, вып. 20). — С. 4281. — doi:10.1103/PhysRevLett.81.4281. — Bibcode: 1998PhRvL..81.4281M. — arXiv:cond-mat/9807077.
• Stephan Mertens. A physicist's approach to number partitioning // Theoretical Computer Science. — 2001. — Т. 265, вып. 1-2. — С. 79–108. — doi:10.1016/S0304-3975(01)00153-0.
• Stephan Mertens. The Easiest Hard Problem: Number Partitioning // Computational complexity and statistical physics / Allon Percus, Gabriel Istrate, Cristopher Moore. — Oxford University Press US, 2006. — С. 125. — ISBN 9780195177374.
• Christian Borgs, Jennifer Chayes, Boris Pittel. Phase transition and finite-size scaling for the integer partitioning problem // Random Structures and Algorithms. — 2001. — Т. 19, вып. 3-4. — С. 247–288. — doi:10.1002/rsa.10004.
• Richard E. Korf. A complete anytime algorithm for number partitioning // Artificial Intelligence. — 1998. — Т. 106, вып. 2. — С. 181–203. — ISSN 0004-3702. — doi:10.1016/S0004-3702(98)00086-1.
• Stephan Mertens. A complete anytime algorithm for balanced number partitioning. — 1999. — Bibcode: 1999cs........3011M. — arXiv:cs/9903011.