Задача о сумме подмножеств

Задача о сумме подмножеств — это важная задача в теории сложности алгоритмов и криптографии. Задача заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел этого подмножества равнялась нулю. Например, пусть задано множество {−7, −3, −2, 5, 8}, тогда подмножество {−3, −2, 5} даёт в сумме ноль. Задача является NP-полной.

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

СложностьПравить

Вычислительная сложность задачи о сумме подмножеств зависит от двух параметров — числа N элементов множества и точности P (определяется как число двоичных разрядов в числах, составляющих множество). Замечание: здесь буквы N и P не имеют ничего общего с классом задач NP.

Сложность наилучшего известного алгоритма экспоненциальна по наименьшему из двух параметров N и P. Таким образом, задача наиболее трудна, когда N и P имеют один порядок. Задача становится лёгкой только при очень маленьких N или P.

Если N (число переменных) мало, то полный перебор вполне приемлем. Если P (число разрядов в числах множества) мало, можно использовать динамическое программирование.

Эффективный алгоритм, работающий, когда и N и P малы, рассмотрен ниже.

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

Имеется несколько способов решения задачи за время, экспоненциально зависящее от N. Наиболее простой алгоритм просматривает все подмножества и для каждого из них проверяет, является ли сумма элементов подмножества подходящей. Время работы алгоритма оценивается как O(2^NN), поскольку имеется 2^N подмножеств, а для проверки каждого подмножества необходимо сложить не более N элементов.

Более оптимальный алгоритм имеет время работы O(2^N/2). Этот алгоритм делит всё множество из N элементов на два подмножества по N/2 элементов в каждом. Для каждого из этих подмножеств строится набор сумм всех 2^N/2 возможных подмножеств. Оба списка сортируются. Если использовать простое сравнение для сортировки, получим время O(2^N/2N). Однако можно применить метод слияния. Имея сумму для k элементов, добавим (k + 1)-й элемент и получим два сортированных списка, затем совершим слияние списков (без добавленного элемента и с добавленным элементом). Теперь имеется список сумм для (k + 1) элементов, и для его создания потребовалось O(2^k) времени. Таким образом, каждый список может быть создан за время O(2^N/2). Имея два сортированных списка, алгоритм может проверить, могут ли дать суммы элементов из первого и второго списка значение s за время O(2^N/2). Для этого алгоритм просматривает первый список в порядке убывания (начиная с самого большого элемента), а второй список в порядке возрастания (начиная с наименьшего элемента). Если сумма текущих элементов больше s, алгоритм передвигается к следующему элементу в первом списке, а если меньше s, к следующему элементу во втором списке. Если же сумма равна s, решение найдено и алгоритм останавливается. Горовиц (Horowitz) и Сани (Sartaj Sahni) впервые опубликовали этот алгоритм в 1972 году^[2].

Решение с помощью динамического программирования с псевдополиномиальным временемПравить

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

x₁, …, x_N,

и необходимо найти, существует ли непустое подмножество этой последовательности с нулевой суммой элементов. Пусть A — сумма отрицательных элементов и B — сумма положительных. Определим булевскую функцию Q(i, s), принимающее значение Да, если существует непустое подмножество элементов x₁, …, x_i, дающих в сумме s, и Нет в противном случае.

Тогда решением задачи будет значение Q(N, 0).

Ясно, что Q(i, s) = Нет, если s < A или s > B, так что эти значения нет необходимости вычислять или хранить. Создадим массив, содержащий значения Q(i, s) для 1 ⩽ i ⩽ N и A ⩽ s ⩽ B.

Массив может быть заполнен с помощью простой рекурсии. Первоначально, для A ⩽ s ⩽ B, положим

Q(1, s) := (x₁ == s).

Теперь для i = 2, …, N, положим

Q(i, s) := Q(i − 1, s) или (x_i == s) или Q(i − 1, s − x_i) для A ⩽ s ⩽ B.

Для каждого присвоения значение Q в правой части уже известно, поскольку либо оно занесено в таблицу предыдущих значений i, либо Q(i − 1, s − x_i) = Нет при s − x_i < A или s − x_i > B. Таким образом, полное время арифметических операций составляет O(N(B − A)). Например, если все значения порядка O(N^k) для некоторого k, то необходимо время O(N^k+2).

Алгоритм легко модифицируется для нахождения нулевой суммы, если такая есть.

Алгоритм не считается полиномиальным, поскольку B − A не является полиномиальным от размера задачи, в качестве которого выступает число бит в числах. Алгоритм полиномиален от значений A и B, а они экспоненциально зависят от числа бит.

Для случая, когда все x_i положительны и ограничены константой C, Писинжер (Pisinger) нашёл линейный алгоритм со сложностью O(NC)^[3] (в этом случае в задаче требуется найти ненулевую сумму, иначе задача становится тривиальной).

Приближенный алгоритм, работающий за полиномиальное времяПравить

Существует версия приближенного алгоритма, дающего для заданного множества из N элементов x₁, x₂, …, x_N и числа s следующий результат:

Да, если существует подмножество с суммой элементов s;
Нет, если нет подмножества, имеющего сумму элементов между (1 − c)s и s для некоторого малого c > 0;
Любой ответ (да или нет), если существует подмножество с суммой элементов между (1 − c)s и s, но эта сумма не равна s.

Если все элементы неотрицательны, алгоритм даёт решение за полиномиальное от N и 1/c время.

Алгоритм обеспечивает решение исходной задачи нахождения суммы подмножеств в случае, если числа малы (и, опять же, неотрицательны). Если любая сумма чисел имеет не более P бит, то решение задачи с c = 2^−P эквивалентно нахождению точного решения. Таким образом, полиномиальный приближенный алгоритм становится точным со временем выполнения, зависящим полиномиально от N и 2^P (то есть экспоненциально от P).

Алгоритм приближенного решения задачи о сумме множеств работает следующим образом:

 Создаем список S, первоначально состоящий из одного элемента 0.
 Для всех i от 1 до N выполним следующие действия
   Создаем список T, состоящий из x_i + y для всех y из S
   Создаем список U, равный объединению T и S
   Сортируем U
   Опустошаем S 
   Пусть y – наименьший элемент U 
   Внесем y в S 
   Для всех элементов z из U, перебирая их в порядке возрастания, выполним
     Если y + cs/N < z ≤ s, положим y = z и внесем z в список S
     (тем самым мы исключаем близкие значения и отбрасываем значения, превосходящие s) 
 Если S содержит число между (1 − c)s и s, говорим Да, в противном случае - Нет

Алгоритм имеет полиномиальное время работы, поскольку размер списков S, T и U всегда полиномиально зависим от N и 1/c и, следовательно, все операции над ними будут выполняться за полиномиальное время. Сохранить размер списков полиномиальным позволяет шаг исключения близких значений, на котором добавляется элемент z в список S, только если он больше предыдущего на cs/N и не больше s, что обеспечивает включение не более N/c элементов в список.

Алгоритм корректен, поскольку каждый шаг дает суммарную ошибку не более cs/N и N шагов вместе дадут ошибку, не превосходящую cs.

См. такжеПравить

ПримечанияПравить

↑ Silvano Martello, Paolo Toth. 4 Subset-sum problem // Knapsack problems: Algorithms and computer interpretations. — Wiley-Interscience, 1990. — С. 105—136. — ISBN 0-471-92420-2.
↑ Ellis Horowitz, Sartaj Sahni. Computing partitions with applications to the knapsack problem // Journal of the Association for Computing Machinery. — 1974. — № 21. — С. 277—292. — doi:10.1145/321812.321823.
↑ Pisinger D. Linear Time Algorithms for Knapsack Problems with Bounded Weights // Journal of Algorithms. — 1999. — Т. 1, № 33. — С. 1—14.

ЛитератураПравить

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Chapter 35.5: The subset-sum problem // Introduction to Algorithms, 3rd Edition. — MIT Press, 2009. — ISBN 978-0-262-03384-8.
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness (англ.). — W.H. Freeman (англ.) (рус., 1979. — ISBN 0-7167-1045-5. A3.2: SP13, pg.223.

[MartelloToth-1] Silvano Martello, Paolo Toth. 4 Subset-sum problem // Knapsack problems: Algorithms and computer interpretations. — Wiley-Interscience, 1990. — С. 105—136. — ISBN 0-471-92420-2.

[2] Ellis Horowitz, Sartaj Sahni. Computing partitions with applications to the knapsack problem // Journal of the Association for Computing Machinery. — 1974. — № 21. — С. 277—292. — doi:10.1145/321812.321823.

[Pisinger09-3] Pisinger D. Linear Time Algorithms for Knapsack Problems with Bounded Weights // Journal of Algorithms. — 1999. — Т. 1, № 33. — С. 1—14.

[1]

[2]

[3]