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

Проблема суммы подмножества - это проблема решения в информатике . В его наиболее общей формулировке существует мультимножество S целых чисел и целевая сумма T , и вопрос состоит в том, чтобы решить, суммируется ли какое-либо подмножество целых чисел в точности с T. ^[1] Проблема, как известно, является NP-полной . Более того, некоторые ее ограниченные варианты тоже являются NP-полными, например: ^[1]

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

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

Задача о рюкзаке - это обобщение суммы подмножества. ^[2]

Вычислительная стойкость [ править ]

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

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

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

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

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

Есть несколько способов решить сумму подмножества по экспоненте по времени от n . ^[5]

Включение-исключение [ править ]

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

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

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

Горовиц и Сахни [ править ]

Горовиц и Сахни ^[6] опубликовали более быстрый алгоритм экспоненциального времени, который работает во времени , но требует гораздо больше места - . Алгоритм произвольно разбивает n элементов на два набора каждого из них. Для каждого из этих двух наборов он хранит список сумм всех возможных подмножеств его элементов. Затем каждый из этих двух списков сортируется. Использование стандартного алгоритма сортировки сравнения для этого шага потребует времени . Однако, учитывая отсортированный список сумм для элементов, список может быть расширен до двух отсортированных списков с введением ( ) -го элемента, и эти два отсортированных списка могут быть объединены во времени . Таким образом, каждый список может быть сформирован в отсортированном виде по времени.${\ 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})}$. Учитывая два отсортированных списка, алгоритм может проверить, суммируются ли элемент первого массива и элемент второго массива до T во времени . Для этого алгоритм проходит через первый массив в порядке убывания (начиная с самого большого элемента) и второй массив в порядке увеличения (начиная с самого маленького элемента). Когда сумма текущего элемента в первом массиве и текущего элемента во втором массиве больше T , алгоритм переходит к следующему элементу в первом массиве. Если он меньше T , алгоритм переходит к следующему элементу во втором массиве. Если найдены два элемента, сумма которых равна T , он останавливается.${\ Displaystyle О (2 ^ {п / 2})}$

Шреппель и Шамир [ править ]

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

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

Хоугрейв-Грэм и Жу [ править ]

Howgrave-Graham и Joux ^[8] представили вероятностный алгоритм, который работает быстрее всех предыдущих - по времени . Это решает только задачу принятия решения, не может доказать , что нет никакого решения для данной суммы, и не возвращает сумму подмножества ближе к Т .${\ Displaystyle О (2 ^ {п / 3})}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приблизительный алгоритм полиномиального времени [ править ]

^{[ необходима цитата ]}

Приближенная версия суммы подмножества будет: задано множество чисел и число , выход:${\displaystyle N}$${\displaystyle x_{i},\ldots ,x_{N}}$${\displaystyle s}$

• Да, если есть подмножество, которое в сумме составляет до .${\displaystyle s}$
• Нет, если нет подмножества, суммирующего число между и для некоторого малого .${\displaystyle (1-\epsilon )s}$${\displaystyle s}$${\displaystyle \epsilon >0}$
• Любой ответ, если есть подмножество, суммирующее до числа между и, но не подмножество, суммирующее до .${\displaystyle (1-\epsilon )s}$${\displaystyle s}$${\displaystyle s}$

Если все числа неотрицательны, приблизительная сумма подмножества разрешима за полиномиальное время от и .${\displaystyle N}$${\displaystyle 1/\epsilon }$

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

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

инициализировать список S, содержащий один элемент 0.для каждого  I от 1 до N  делать пусть T будет список , состоящий из й я + у для всех у в S пусть U объединение T и S рода U сделать S опорожнить пусть y будет наименьшим элементом U добавить y к S  для каждого элемента z из U в порядке возрастания do // Обрезаем список, удаляя близкие друг к другу числа // и выбрасываем элементы больше s . если  y + ε s / N < z ≤ s,  то  y = z добавить z к Sесли  S содержит число от (1 - ε) s  до  s,  тогда верните да, иначе верните нет

Алгоритм полиномиальное время , так как списки , и всегда остаются размерным полином и , и до тех пор , как они полиномиального размера, все операции по ним можно сделать за полиномиальное время. Размер списков остается полиномиальным за счет шага обрезки, на котором мы включаем число только в том случае, если оно больше предыдущего на и не больше чем .${\displaystyle S}$${\displaystyle T}$${\displaystyle U}$${\displaystyle N}$${\displaystyle 1/\epsilon }$${\displaystyle z}$${\displaystyle S}$${\displaystyle \epsilon s/N}$${\displaystyle s}$

Этот шаг гарантирует, что каждый элемент в меньше, чем следующий, по крайней мере, и не содержит элементов больше, чем . Любой список с этим свойством состоит не более чем из элементов.${\displaystyle S}$${\displaystyle \epsilon s/N}$${\displaystyle s}$${\displaystyle N/\epsilon }$

Алгоритм правильный, потому что каждый шаг вносит аддитивную ошибку максимум, а шаги вместе дают ошибку максимум .${\displaystyle \epsilon s/N}$${\displaystyle N}$${\displaystyle \epsilon s}$

См. Также [ править ]

• 3SUM
• Ранцевая криптосистема Меркла – Хеллмана

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (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.