Проблема суммы подмножества - Subset sum problem

Проблема суммы подмножества (SSP) - это проблема решения в информатике . В его наиболее общей формулировке существует мультимножество целых чисел и целевая сумма , и вопрос состоит в том, чтобы решить, с какой суммой какое-либо подмножество целых чисел точно . Как известно, проблема NP-полная . Более того, некоторые его ограниченные варианты тоже являются NP-полными, например: ${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle T}$

• Вариант, при котором все входы положительны.
• Вариант, в котором входы могут быть положительными или отрицательными, и . Например, если набор , ответ да потому , что подмножество суммы к нулю.${\ displaystyle T = 0}$${\ displaystyle \ {- 7, -3, -2,9000,5,8 \}}$${\ displaystyle \ {- 3, -2,5 \}}$
• Вариант, при котором все входы положительны, а целевая сумма составляет ровно половину суммы всех входов, т . Е .. Этот частный случай SSP известен как проблема разделения .${\ Displaystyle Т = {\ гидроразрыва {1} {2}} (а_ {1} + \ точки + а_ {п})}$

SSP также можно рассматривать как задачи оптимизации : найти подмножество, сумма которого составляет не более T , и при условии , что к, как можно ближе к Т . Это NP-сложно , но есть несколько алгоритмов, которые позволяют достаточно быстро решить эту проблему на практике.

SSP - это частный случай задачи о ранце и задачи о сумме нескольких подмножеств .

Вычислительная сложность

Время выполнения сложности ССП зависит от двух параметров:

п

количество вводимых целых чисел

• Если n (количество целых чисел) - небольшое фиксированное число, то целесообразен исчерпывающий поиск решения.

L

точность задачи, выраженная как количество двоичных разрядов, необходимых для постановки задачи.

• Если L (количество двоичных цифр) - небольшое фиксированное число, то существуют алгоритмы динамического программирования , которые могут его точно решить.

Когда и n, и L велики, SSP NP-сложен. Сложность из наиболее известных алгоритмов является экспоненциальной в меньшей из двух параметров п и L . Как известно, NP-трудными являются следующие варианты:

• Все входные целые числа положительны (и целевая сумма T является частью входных данных). Это можно доказать прямым сокращением из 3SAT .
• Входные целые числа могут быть как положительными, так и отрицательными, а целевая сумма T = 0. Это может быть доказано сокращением от варианта с положительными целыми числами. Обозначьте этот вариант SubsetSumPositive, а текущий вариант - SubsetSumZero. Принимая во внимание экземпляр ( S , Т ) из SubsetSumPositive, построить экземпляр SubsetSumZero путем добавления одного элемента со значением - T . Учитывая решение для экземпляра SubsetSumPositive, добавление - T дает решение для экземпляра SubsetSumZero. И наоборот, учитывая решение экземпляра SubsetSumZero, оно должно содержать - T (поскольку все целые числа в S положительны), поэтому для получения нулевой суммы он также должен содержать подмножество S с суммой + T , что является решением экземпляра SubsetSumPositive.
• Входные целые числа положительны, и T = sum ( S ) / 2. Это также можно доказать редукцией от общего варианта; увидеть проблему с разделом .

Алгоритмы экспоненциального времени

Есть несколько способов решить SSP по экспоненте во времени от n .

Включение-исключение

Самый наивный алгоритм - это перебрать все подмножества из n чисел и для каждого из них проверить, суммируется ли подмножество до нужного числа. Время выполнения имеет порядок , поскольку есть подмножества, и для проверки каждого подмножества нам нужно суммировать не более n элементов. ${\ Displaystyle О (2 ^ {п} \ cdot п)}$${\ displaystyle 2 ^ {n}}$

Алгоритм может быть реализован путем поиска в глубину двоичного дерева: каждый уровень в дереве соответствует входному номеру; левая ветвь соответствует исключению числа из набора, а правая ветвь соответствует включению числа (отсюда и название «Включение-исключение»). Требуемая память есть . Время выполнения можно улучшить с помощью нескольких эвристик: ${\ Displaystyle О (п)}$

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

Горовиц и Сахни

Горовиц и Сахни опубликовали более быстрый алгоритм экспоненциального времени, который работает во времени , но требует гораздо больше места - . Алгоритм произвольно разбивает n элементов на два набора каждого из них. Для каждого из этих двух наборов он хранит список сумм всех возможных подмножеств его элементов. Затем каждый из этих двух списков сортируется. При использовании даже самого быстрого алгоритма сортировки сравнения Mergesort для этого шага потребует времени . Однако, учитывая отсортированный список сумм для элементов, список может быть расширен до двух отсортированных списков с введением ( ) -го элемента, и эти два отсортированных списка могут быть объединены во времени . Таким образом, каждый список может быть сформирован в отсортированном по времени виде . Учитывая два отсортированных списка, алгоритм может проверить, суммируются ли элемент первого массива и элемент второго массива до T во времени . Для этого алгоритм проходит через первый массив в порядке убывания (начиная с самого большого элемента) и второй массив в порядке увеличения (начиная с самого маленького элемента). Когда сумма текущего элемента в первом массиве и текущего элемента во втором массиве больше T , алгоритм переходит к следующему элементу в первом массиве. Если он меньше T , алгоритм переходит к следующему элементу во втором массиве. Если найдены два элемента, сумма которых равна T , он останавливается. ${\ Displaystyle О (2 ^ {п / 2} \ cdot (п / 2))}$${\ Displaystyle О (2 ^ {п / 2})}$${\ displaystyle n / 2}$${\ Displaystyle 2 ^ {п / 2}}$${\ Displaystyle О (2 ^ {п / 2} п)}$${\ displaystyle k}$${\ displaystyle k + 1}$${\ displaystyle O (2 ^ {k})}$${\ Displaystyle О (2 ^ {п / 2})}$${\ Displaystyle О (2 ^ {п / 2})}$

Шрёппель и Шамир

Шроппель и Шамир представили алгоритм, основанный на Горовитце и Санхи, который требует аналогичного времени выполнения - но гораздо меньше места - . Вместо того, чтобы заранее генерировать и хранить все подмножества из n / 2 элементов, они разделяют элементы на 4 набора по n / 4 элемента в каждом и динамически генерируют подмножества из n / 2 пар элементов, используя минимальную кучу, которая дает указанное выше время и пространство. сложности , так как это может быть сделано в и пространстве с учетом 4 списков длины к. ${\ Displaystyle О (2 ^ {п / 2} \ cdot (п / 4))}$${\ Displaystyle О (2 ^ {п / 4})}$${\ Displaystyle О (к ^ {2} \ журнал (к))}$${\ Displaystyle О (к)}$

Из-за нехватки места алгоритм HS применим примерно для 50 целых чисел, а алгоритм SS применим до 100 целых чисел.

Хоугрейв-Грэм и Жу

Хоугрейв-Грэм и Жу представили вероятностный алгоритм, который работает быстрее, чем все предыдущие - во времени с использованием пространства . Это решает только задачу принятия решения, не может доказать , что нет никакого решения для данной суммы, и не возвращает сумму подмножества ближе к Т . ${\ displaystyle O (2 ^ {. 337n})}$${\ displaystyle O (2 ^ {. 256n})}$

Впоследствии методы Хоугрейва-Грэма и Жу были расширены, что привело к временной сложности . ${\ Displaystyle O (2 ^ {. 291n})}$

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

SSP может быть решен за псевдополиномиальное время с помощью динамического программирования . Также наблюдается, что это само по себе подразумевает, что сумма подмножества, закодированная в унарном формате, находится в P, поскольку с этого момента размер кодирования является линейным по отношению к размеру целевого числа. Следовательно, Subset Sum лишь слабо NP-полна. Предположим, у нас есть следующая последовательность элементов в экземпляре:

${\ Displaystyle x_ {1}, \ ldots, x_ {N}}$

отсортированы в порядке возрастания, и мы хотим определить, существует ли непустое подмножество, сумма которого равна нулю. Определите булевозначную функцию как значение ( истина или ложь ) ${\ Displaystyle Q (я, s)}$

«есть непустое подмножество, сумма которого равна s ».${\ displaystyle x_ {1}, \ ldots, x_ {i}}$

Таким образом, решение проблемы «Для данного набора целых чисел существует непустое подмножество, сумма которого равна нулю?» это значение . ${\ Displaystyle Q (N, 0)}$

Пусть A будет суммой отрицательных значений, а B - суммой положительных значений. Ясно, что . Таким образом, эти значения не нужно хранить или вычислять. ${\ displaystyle Q (i, s) = {\ textit {false}} {\ text {, if}} s <A {\ text {или}} s> B}$

Создайте массив для хранения значений . ${\ Displaystyle Q (я, s) {\ текст {for}} 1 \ leq i \ leq N {\ text {и}} A \ leq s \ leq B}$

Теперь массив можно заполнить простой рекурсией. Изначально для набора ${\ Displaystyle A \ leq s \ leq B}$

${\ Displaystyle Q (1, s): = (x_ {1} == s)}$

где - логическая функция, которая возвращает истину, если она равна s , и ложь в противном случае. ${\ displaystyle ==}$${\ displaystyle x_ {1}}$

Тогда для положим ${\ Displaystyle я = 2, \ ldots, N}$

${\ displaystyle Q (i, s): = Q (i-1, s) {\ text {или}} ((x_ {i} == s) {\ text {and}} Q (i-1, s) -x_ {i})), {\ text {for}} A \ leq s \ leq B}$.

Для каждого присваивания значения Q справа уже известны либо потому, что они были сохранены в таблице для предыдущего значения i, либо потому, что . Следовательно, общее количество арифметических операций равно . Например, если все значения указаны для некоторого k , то необходимое время равно . ${\ Displaystyle Q (я-1, s-x_ {i}) = {\ textit {false}} \ {\ text {if}} s-x_ {i} <A {\ text {или}} s-x_ {i}> B}$${\ Displaystyle О (Н (БА))}$${\ displaystyle O (N ^ {k})}$${\ Displaystyle О (N ^ {к + 2})}$

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

Решение динамического программирования имеет время выполнения, где s - это сумма, которую мы хотим найти в наборе из N чисел. Это решение не считается полиномиальным временем в теории сложности, потому что не является полиномиальным по размеру проблемы, то есть количеству битов, используемых для ее представления. Этот алгоритм полиномиален от значений A и B , которые экспоненциальны по количеству битов. ${\ Displaystyle O (sN)}$${\ displaystyle BA}$

Для случая, когда каждый из них положителен и ограничен фиксированной константой C , Пизингер нашел алгоритм линейного времени, имеющий временную сложность (обратите внимание, что это для версии задачи, где целевая сумма не обязательно равна нулю, иначе проблема была бы тривиальной. ). В 2015 году Койлиарис и Сюй нашли детерминированный алгоритм для задачи о сумме подмножеств, где s - это сумма, которую нам нужно найти. В 2017 году Брингманн нашел алгоритм рандомизированного времени. ${\ displaystyle x_ {i}}$${\ Displaystyle O (NC)}$${\ displaystyle {\ tilde {O}} (s {\ sqrt {N}})}$${\ Displaystyle {\ тильда {O}} (s + N)}$

В 2014 году Кертис и Санчес обнаружили простую рекурсию с высокой степенью масштабируемости в SIMD- машинах, имеющих время и пространство, где p - количество обрабатывающих элементов, а это наименьшее целое число. Это лучшая теоретическая параллельная сложность из известных на сегодняшний день. ${\ Displaystyle О (Н (м-х _ {\ мин}) / п)}$${\ Displaystyle О (Н + м-х _ {\ мин})}$${\ Displaystyle м = \ мин (s, \ сумма x_ {i} -s)}$${\ displaystyle x _ {\ min}}$

Сравнение практических результатов и решение жестких примеров SSP обсуждается Кертисом и Санчесом.

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

Предположим, что все входы положительны. Алгоритм аппроксимации для целей SSP , чтобы найти подмножество S с суммой не более Т и по меньшей мере г раз оптимальной суммы, где г представляет собой число в (0,1) называется отношение аппроксимации .

Простое 1/2 приближение

Следующий очень простой алгоритм имеет коэффициент приближения 1/2:

• Упорядочить входные данные по убыванию значения;
• Поместите следующий по величине вход в подмножество, если он там подходит.

Когда этот алгоритм завершается, либо все входы находятся в подмножестве (что, очевидно, оптимально), либо есть вход, который не подходит. Первый такой вход меньше, чем все предыдущие входы, входящие в подмножество, поэтому он должен быть меньше, чем T / 2. Следовательно, сумма входов в подмножестве больше, чем T / 2, что, очевидно, больше, чем OPT / 2.

Полностью полиномиальная схема аппроксимации по времени

Следующий алгоритм обеспечивает для каждого коэффициент аппроксимации . Его время работы полиномиально от n и . Напомним, что n - это количество входов, а T - это верхняя граница суммы подмножества. ${\ displaystyle \ epsilon> 0}$${\ displaystyle (1- \ epsilon)}$${\ displaystyle 1 / \ epsilon}$

initialize a list L to contain one element 0.

for each i from 1 to n do
    let Ui be a list containing all elements y in L, and all sums xi + y for all y in L.
    sort Ui in ascending order
    make L empty 
    let y be the smallest element of Ui
    add y to L
    for each element z of Ui in increasing order do
        // Trim the list by eliminating numbers close to one another
        // and throw out elements greater than the target sum T.
        if y +  ε T/n < z ≤ T then
            y = z
            add z to L

return the largest element in L.

Обратите внимание, что без шага обрезки (внутренний цикл «для каждого») список L будет содержать суммы всех подмножеств входных данных. Шаг обрезки выполняет две функции: ${\ displaystyle 2 ^ {n}}$

• Это гарантирует, что все суммы, оставшиеся в L , меньше T , поэтому они являются допустимыми решениями проблемы подмножества сумм.
• Это гарантирует, что список L будет «разреженным», то есть разница между каждыми двумя последовательными частичными суммами будет не менее .${\ displaystyle \ epsilon T / n}$

Эти свойства вместе гарантируют, что список L содержит не более элементов; поэтому время выполнения полиномиально от . ${\ Displaystyle п / \ эпсилон}$${\ Displaystyle п / \ эпсилон}$

Когда алгоритм завершается, если оптимальная сумма находится в L , она возвращается, и все готово. В противном случае он должен быть удален на предыдущем этапе обрезки. Каждый шаг обрезки вносит аддитивную ошибку максимум , поэтому n шагов вместе дают ошибку максимум . Следовательно, возвращенное решение - это по крайней мере то, что есть по крайней мере . ${\ displaystyle \ epsilon T / n}$${\ displaystyle \ epsilon T}$${\ displaystyle {\ text {OPT}} - \ epsilon T}$${\ displaystyle (1- \ epsilon) {\ text {OPT}}}$

Вышеупомянутый алгоритм обеспечивает решение исходной проблемы суммы подмножества в случае, когда числа малы (опять же, для неотрицательных чисел). Если любая сумма чисел может быть указана не более чем с P битами, то решение задачи приблизительно с помощью эквивалентно ее точному решению. Затем алгоритм полиномиального времени для приблизительной суммы подмножества становится точным алгоритмом с полиномом времени выполнения по n и (т. Е. Экспоненциальным по P ). ${\ displaystyle \ epsilon = 2 ^ {- P}}$${\ displaystyle 2 ^ {P}}$

Келлерер, Мансини, Пферши и Сперанца и Келлерер, Пферши и Пизингер представляют другие FPTAS-ы для суммы подмножества.

Смотрите также

• Задача о рюкзаке - обобщение SSP, в котором каждый входной элемент имеет как значение, так и вес. Цель состоит в том, чтобы максимизировать значение таким образом, чтобы общий вес был ограничен.
• Задача суммы множественных подмножеств - обобщение SSP, в котором нужно выбрать несколько подмножеств.
• 3SUM
• Ранцевая криптосистема Меркла – Хеллмана
• Алгоритм решения SSP низкой плотности с высокой вероятностью.
• Задача о сумме 4 подмножеств.

использованная литература

дальнейшее чтение

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «35.5: проблема суммы подмножества». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03293-7.
• Майкл Р. Гарей и Дэвид С. Джонсон (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . WH Freeman. ISBN 0-7167-1045-5. A3.2: SP13, стр. 223.