Введение
NP-полная задача в информатике
В теории чисел и информатике задача о разбиении, или разделении чисел, заключается в определении, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2 так, чтобы сумма чисел в S1 была равна сумме чисел в S2. Хотя задача о разбиении является NP-полной, существует псевдополиномиальное решение с использованием динамического программирования, а также эвристики, которые решают задачу во многих случаях оптимально или приближенно. По этой причине её называют «самой простой сложной задачей». Существует оптимизационная версия задачи о разбиении, которая заключается в разбиении мультимножества S на два подмножества S1 и S2 таким образом, чтобы разница между суммой элементов в S1 и суммой элементов в S2 была минимальной. Оптимизационная версия является NP-трудной, но может быть эффективно решена на практике. Задача о разбиении является частным случаем двух связанных задач:
In number theory and computer science, the partition problem, or number partitioning, is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the partition problem is NP complete, there is a pseudo polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem". There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized. The optimization version is NP hard, but can be solved efficiently in practice. The partition problem is a special case of two related problems:
В задаче о сумме подмножеств цель состоит в том, чтобы найти подмножество S, сумма которого равна заданному целевому числу T (задача о разбиении является частным случаем, когда T равна половине суммы S). В задаче о многостороннем разбиении чисел существует целочисленный параметр k, и цель состоит в том, чтобы определить, можно ли разбить S на k подмножеств с одинаковой суммой (задача о разбиении является частным случаем, когда k = 2). Однако она существенно отличается от задачи о разбиении на 3 части: в этой задаче количество подмножеств не фиксировано заранее – оно должно быть равно |S|/3, где каждое подмножество должно содержать ровно 3 элемента. Разбиение на 3 части значительно сложнее, чем разбиение – для него не существует псевдополиномиального алгоритма, если P ≠ NP.
Примеры
При 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}.
Вычислительная твердость
Проблема разделения является NP-трудной. Это можно доказать сведением из задачи о сумме подмножества. Экземпляр задачи о сумме подмножества (SubsetSum) состоит из множества S положительных целых чисел и целевой суммы T; цель состоит в том, чтобы определить, существует ли подмножество S, сумма элементов которого равна T.
Для данного экземпляра построим экземпляр задачи о разделении (Partition), в котором входное множество содержит исходное множество плюс два элемента: z1 и z2, где z1 = sum(S) и z2 = 2T. Сумма этого входного множества равна sum(S) + z1 + z2 = 2*sum(S) + 2T, следовательно, целевая сумма для задачи о разделении равна sum(S) + T.
Предположим, существует решение S′ для экземпляра задачи о сумме подмножества. Тогда sum(S′) = T, следовательно, sum(S′ + z1) = sum(S) + T, и S′ + z1 является решением экземпляра задачи о разделении. Обратно, предположим, существует решение S′′ для экземпляра задачи о разделении. Тогда S′′ должно содержать либо z1, либо z2, но не оба, поскольку их сумма превышает sum(S) + T. Если S′′ содержит z1, то оно должно содержать элементы из S с суммой, равной T, следовательно, S′′ без z1 является решением экземпляра задачи о сумме подмножества. Если S′′ содержит z2, то оно должно содержать элементы из S с суммой, равной sum(S) − T, следовательно, остальные элементы из S являются решением экземпляра задачи о сумме подмножества.
Алгоритмы приближения
Как упоминалось выше, задача о разбиении является частным случаем многопутевого разбиения и задачи о сумме подмножеств. Следовательно, её можно решить алгоритмами, разработанными для каждой из этих задач. Алгоритмы, разработанные для многопутевого разбиения чисел, включают: жадный алгоритм разбиения чисел – перебирает числа и помещает каждое число в множество с наименьшей текущей суммой. Если числа не отсортированы, то время работы составляет O(n), а коэффициент приближения не превышает 3/2 (коэффициент приближения означает большую сумму в выходных данных алгоритма, деленную на большую сумму в оптимальном разбиении). Сортировка чисел увеличивает время работы до O(n log n) и улучшает коэффициент приближения до 7/6. Если числа распределены равномерно в [0,1], то коэффициент приближения почти наверняка не превышает 1, а в среднем – 1. Метод наибольшей разности (также называемый алгоритмом Кармакара-Карпа) сортирует числа в порядке убывания и многократно заменяет числа их разностями. Временная сложность составляет O(n log n). В худшем случае его коэффициент приближения аналогичен – не более 7/6. Однако в среднем случае он работает намного лучше, чем жадный алгоритм: когда числа распределены равномерно в [0,1], его коэффициент приближения в среднем не превышает 1. Он также показывает лучшие результаты в экспериментах по моделированию. Алгоритм Multifit использует двоичный поиск в сочетании с алгоритмом упаковки в контейнеры. В худшем случае его коэффициент приближения равен 8/7. Для задачи о сумме подмножеств существует FPTAS, который также можно использовать для задачи о разбиении, установив целевую сумму равной sum(S)/2.
Greedy number partitioning – loops over the numbers, and puts each number in the set whose current sum is smallest. If the numbers are not sorted, then the runtime is O(n) and the approximation ratio is at most 3/2 ("approximation ratio" means the larger sum in the algorithm output, divided by the larger sum in an optimal partition). Sorting the numbers increases the runtime to O(n log n) and improves the approximation ratio to 7/6. If the numbers are distributed uniformly in [0,1], then the approximation ratio is at most almost surely, and in expectation. Largest Differencing Method (also called the Karmarkar–Karp algorithm) sorts the numbers in descending order and repeatedly replaces numbers by their differences. The runtime complexity is O(n log n). In the worst case, its approximation ratio is similar – at most 7/6. However, in the average case it performs much better than the greedy algorithm: when numbers are distributed uniformly in [0,1], its approximation ratio is at most in expectation. It also performs better in simulation experiments. The Multifit algorithm uses binary search combined with an algorithm for bin packing. In the worst case, its approximation ratio is 8/7. The subset sum problem has an FPTAS which can be used for the partition problem as well, by setting the target sum to sum(S)/2.
Трудные экземпляры и фазовый переход
Наборы, содержащие только одну или ни одной партиции, как правило, наиболее сложны (или требуют наибольших затрат) для решения по отношению к их размеру. Когда значения элементов малы по сравнению с размером набора, полные партиции более вероятны. Известно, что задача демонстрирует "фазовый переход", будучи вероятной для одних наборов и маловероятной для других. Если *m* – это количество бит, необходимое для представления любого числа в наборе, а *n* – размер набора, то склонна иметь множество решений, а – мало или не иметь решений вовсе. С увеличением *n* и *m* вероятность существования полной партиции стремится к 1 или 0 соответственно. Это было первоначально обосновано на основе эмпирических данных Гентом и Уолшем, затем с использованием методов статистической физики Мертенсом, а впоследствии доказано Боргсом, Чейсом и Питтелем.
Вероятностная версия
Связанная проблема, в некоторой степени напоминающая парадокс дней рождения, заключается в определении размера входного набора данных, при котором вероятность наличия решения составляет одну вторую, при условии, что каждый элемент набора данных выбирается случайным образом с равномерным распределением между 1 и заданным значением. Решение этой задачи может оказаться неинтуитивным, как и в случае с парадоксом дней рождения.
Варианты и обобщения
Равный по кардинальности раздел – это вариант, в котором обе части должны содержать одинаковое количество элементов, помимо того, что у них одинаковая сумма. Этот вариант также является NP-трудным. Ковалёв и Песх обсуждают общий подход к доказательству NP-трудности задач типа разбиения.
Приложения
Одно из применений задачи о разбиении — манипулирование выборами. Предположим, есть три кандидата (А, В и С). Один кандидат должен быть избран по правилу голосования, основанному на оценках, например, по правилу вето (каждый избиратель отклоняет голос за одного кандидата, и побеждает кандидат, получивший наименьшее количество отклосов). Если коалиция хочет обеспечить избрание С, им следует разделить свои голоса между А и В таким образом, чтобы максимизировать минимальное количество отклосов, которое получит каждый из них. Если голоса имеют вес, то задача сводится к задаче о разбиении и, следовательно, может быть эффективно решена с помощью алгоритма CKK. То же справедливо и для любого другого правила голосования, основанного на оценках.