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

Проблема принятия решений в информатике

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

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

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

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

Вычислительная твердость

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

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

Поскольку и n , и L растут, SSP становится NP-трудным. Сложность наиболее известных алгоритмов экспоненциально зависит от меньшего из двух параметров n и L. Проблема является NP-сложной, даже если все входные целые числа положительны (и целевая сумма T является частью входных данных). Это можно доказать прямым сокращением из 3SAT . ^[2] Это также можно доказать путем редукции из трехмерного сопоставления (3DM): ^[3]

• Нам дан экземпляр 3DM, где наборами вершин являются W, X, Y. Каждый набор имеет n вершин. Имеется m ребер, каждое из которых содержит ровно по одной вершине из каждого из W, X, Y. Обозначим L  := потолок(log ₂ ( m +1)), так что L больше количества битов, необходимых для представления количество ребер.
• Мы создаем экземпляр SSP с m положительными целыми числами. Целые числа описываются их двоичным представлением. Каждое входное целое число может быть представлено 3 битами nL , разделенными на 3 n зон по L бит. Каждая зона соответствует вершине.
• Для каждого ребра (w,x,y) в экземпляре 3DM существует целое число в экземпляре SSP, в котором ровно три бита равны «1»: младшие биты в зонах вершин w, x и й. Например, если n =10 и L=3 и W=(0,...,9), X=(10,...,19), Y=(20,...,29), то ребро (0, 10, 20) представлено числом (2 ⁰ +2 ³⁰ +2 ⁶⁰ ).
• Целевая сумма T в экземпляре SSP устанавливается в целое число с «1» в младшем бите каждой зоны, то есть (2 ⁰ +2 ¹ +...+2 ^3n-1 ).
• Если экземпляр 3DM имеет идеальное совпадение, то суммирование соответствующих целых чисел в экземпляре SSP дает ровно T.
• И наоборот, если экземпляр SSP имеет подмножество с суммой ровно T, то, поскольку зоны достаточно велики, чтобы не было «переносов» из одной зоны в другую, сумма должна соответствовать идеальному совпадению в экземпляре 3DM.

Следующие варианты также известны как NP-сложные:

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

Аналогичная задача подсчета #SSP, которая требует подсчитать количество подмножеств, суммирующихся с целью, является #P-complete . ^[4]

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

Существует несколько способов решения SSP в экспоненциальном времени от n . ^[5]

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

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

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

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

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

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

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

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

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

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

В 2010 году Хогрейв-Грэм и Жу ^[9] представили вероятностный алгоритм , который работает быстрее всех предыдущих — во времени с использованием пространства . Он решает только проблему решения, не может доказать отсутствие решения для данной суммы и не возвращает сумму подмножества, наиболее близкую к T . ${\displaystyle O(2^{0.337n})}$ ${\displaystyle O(2^{0.256n})}$

Впоследствии методы Хогрейва-Грэма и Жу были расширены ^[10], в результате чего временная сложность составила . ${\displaystyle O(2^{0.291n})}$

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

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

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

Мы определяем состояние как пару ( i , s ) целых чисел. Это состояние отражает тот факт, что

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

Каждое состояние ( i , s ) имеет два следующих состояния:

• ( i +1, s ), подразумевая, что он не включен в подмножество; ${\displaystyle x_{i+1}}$
• ( i +1, s + ), подразумевая, что он включен в подмножество. ${\displaystyle x_{i+1}}$ ${\displaystyle x_{i+1}}$

Начиная с начального состояния (0, 0), можно использовать любой алгоритм поиска по графу (например, BFS ) для поиска состояния ( N , T ). Если состояние найдено, то , возвращаясь назад, мы можем найти подмножество с суммой ровно T.

Время выполнения этого алгоритма не более чем линейно по числу состояний. Число состояний не более чем в N раз превышает количество различных возможных сумм. Пусть A будет суммой отрицательных значений, а B - суммой положительных значений; количество различных возможных сумм не превышает B - A , поэтому общее время выполнения находится в . Например, если все входные значения положительны и ограничены некоторой константой C , то B не превышает NC , поэтому необходимое время равно . ${\displaystyle O(N(B-A))}$ ${\displaystyle O(N^{2}C)}$

Это решение не считается полиномиальным временем в теории сложности, поскольку оно не является полиномиальным по размеру проблемы, то есть количеству битов, используемых для ее представления. Этот алгоритм является полиномиальным по значениям A и B , которые являются экспоненциальными по числу битов. Однако сумма подмножества, закодированная в унарном формате, находится в P, поскольку тогда размер кодирования является линейным в BA. Следовательно, Subset Sum лишь слабо NP-полна. ${\displaystyle B-A}$

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

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

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

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

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

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

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

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

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

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

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

инициализировать список L , чтобы он содержал один элемент 0.для каждого  i от 1 до n  пусть U i будет списком, содержащим все элементы y в L и все суммы x i + y для всех y в L . отсортировать U i в порядке возрастания сделать L пустым пусть y будет наименьшим элементом U i добавьте y к L  для каждого элемента z U i в порядке возрастания do // Обрезаем список, удаляя близкие друг к другу числа // и выбрасываем элементы, превышающие целевую сумму T . если y + ε T / n < z ≤ T , то y = z добавляем z к L      вернуть самый большой элемент в L.

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

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

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

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

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

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

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

• Задача о рюкзаке  - задача комбинаторной оптимизации - обобщение SSP, в котором каждый входной элемент имеет как значение, так и вес. Цель состоит в том, чтобы максимизировать значение с учетом ограничения общего веса .
• Задача о сумме нескольких подмножеств - обобщение SSP, в котором нужно выбрать несколько подмножеств.
• 3SUM  - Задача теории сложности вычислений
• Ранцевая криптосистема Меркла-Хеллмана  - одна из первых криптосистем с открытым ключом, изобретенная Ральфом Мерклем и Мартином Хеллманом в 1978 году. Идеи, лежащие в ее основе, проще, чем идеи, связанные с RSA, и она была взломана.Pages displaying wikidata descriptions as a fallback

Рекомендации

1. Кляйнберг, Джон; Тардос, Ева (2006). Разработка алгоритмов (2-е изд.). п. 491. ИСБН 0-321-37291-3.
2. Гудрич, Майкл. «Больше полных и сложных задач NP» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.
3. Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. МР  0519066. OCLC  247570676., раздел 3.1 и задача SP1 в Приложении А.3.1.
4. Filmus, Юваль (30 января 2016 г.). Ответ на вопрос: «Существует ли известный быстрый алгоритм подсчета всех подмножеств, сумма которых меньше определенного числа?». Обмен стеками теоретической информатики . Обратите внимание, что цитата Filmus в поддержку этого утверждения (Faliszewski, Piotr; Hemaspaandra, Lane (2009). «Сложность сравнения показателей мощности». Theoretical Computer Science . Elsevier. 410 : 101-107. DOI 10.1016/j.tcs .2008.09.034) на самом деле не доказывает это утверждение, вместо этого направляя читателей к другой цитате ( Papadimitriou, Christos (1994). Computational Complexity. Addison-Wesley: Reading, MA. Chapter 9. ISBN 0-201-53082-1  ​​— через Интернет-архив ), что также не доказывает это утверждение. Однако доказательство Пападимитриу о том, что SSP является NP-полным посредством редукции 3SAT , обобщается до редукции от #3SAT до #SSP. 
5. Ричард Э. Корф, Итан Л. Шрайбер и Майкл Д. Моффитт (2014). «Оптимальное последовательное многостороннее разделение номеров» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.{{cite web}}: CS1 maint: multiple names: authors list (link)
6. Горовиц, Эллис; Сахни, Сартадж (1974). «Расчет разделов с приложениями к задаче о рюкзаке» (PDF) . Журнал Ассоциации вычислительной техники . 21 (2): 277–292. дои : 10.1145/321812.321823. hdl : 1813/5989 . MR  0354006. S2CID  16866858. Архивировано (PDF) из оригинала 9 октября 2022 г.
7. «Задача двух сумм» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.
8. Шреппель, Ричард; Шамир, Ади (1 августа 1981 г.). «Алгоритм AT = O(2n/2), S = O(2n/4) для некоторых NP-полных задач». SIAM Journal по вычислительной технике . 10 (3): 456–464. дои : 10.1137/0210033. ISSN  0097-5397.
9. Хоугрейв-Грэм, Ник; Жу, Антуан (2010). «Новые универсальные алгоритмы для твердых рюкзаков». В Гилберте, Анри (ред.). Достижения в криптологии – EUROCRYPT 2010 . Конспекты лекций по информатике. Том. 6110. Берлин, Гейдельберг: Springer. стр. 235–256. дои : 10.1007/978-3-642-13190-5_12 . ISBN 978-3-642-13190-5.
10. Беккер, Аня; Жу, Антуан (2010). «Улучшенные общие алгоритмы для твердых рюкзаков». В Гилберте, Анри (ред.). Достижения в криптологии – EUROCRYPT 2011 . Конспекты лекций по информатике. Том. 6632. Берлин, Гейдельберг: Springer. стр. 364–385. дои : 10.1007/978-3-642-20465-4_21 . ISBN 978-3-642-20465-4.
11. Пизингер, Дэвид (1999). «Алгоритмы линейного времени для задач о рюкзаке с ограниченными весами». Журнал алгоритмов . 33 (1): 1–14. дои : 10.1006/jagm.1999.1034. МР  1712690.
12. Койлиарис, Константинос; Сюй, Чао (08 июля 2015 г.). «Более быстрый алгоритм псевдополиномиального времени для суммы подмножества». arXiv : 1507.02318 [cs.DS].
13. Брингманн, Карл (2017). «Почти линейный алгоритм псевдополиномиального времени для вычисления суммы подмножества». Кляйн, Филип Н. (ред.). Материалы двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2017) . СИАМ. стр. 1073–1084. arXiv : 1610.04712 . дои : 10.1137/1.9781611974782.69.
14. Кертис, В.В.; Санчес, CAA (январь 2016 г.). «Эффективное решение проблемы суммы подмножества на графическом процессоре: эффективное решение проблемы суммы подмножества на графическом процессоре». Параллелизм и вычисления: практика и опыт . 28 (1): 95–113. дои : 10.1002/cpe.3636. S2CID  20927927.
15. Кертис, В.В.; Санчес, CAA (июль 2017 г.). «Алгоритм с малым пространством для решения проблемы суммы подмножества на графическом процессоре». Компьютеры и исследования операций . 83 : 120–124. дои : 10.1016/j.cor.2017.02.006.
16. Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (1 февраля 2000 г.). «Проблема суммы множественного подмножества». SIAM Journal по оптимизации . 11 (2): 308–319. дои : 10.1137/S1052623498348481. ISSN  1052-6234.
17. Келлерер, Ганс; Мансини, Рената; Пферши, Ульрих; Сперанца, Мария Грация (01 марта 2003 г.). «Эффективная полностью полиномиальная схема аппроксимации для задачи о сумме подмножеств». Журнал компьютерных и системных наук . 66 (2): 349–370. дои : 10.1016/S0022-0000(03)00006-0. ISSN  0022-0000.
18. Ганс Келлерер; Ульрих Пферши; Дэвид Пизингер (2004). Проблемы с рюкзаком. Спрингер. п. 97. ИСБН 9783540402862.

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

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «35.5: Проблема суммы подмножества». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03293-7.
• Майкл Р. Гари и Дэвид С. Джонсон (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN 0-7167-1045-5.А3.2: СП13, стр.223.
• Лагариас, JC; Одлизко, А. М. (1 января 1985 г.). «Решение задач о сумме подмножеств низкой плотности». Журнал АКМ . 32 (1): 229–246. дои : 10.1145/2455.2461 . ISSN  0004-5411. S2CID  885632.
• Мартелло, Сильвано; Тот, Паоло (1990). «4 Проблема суммы подмножества». Задачи о рюкзаке: Алгоритмы и компьютерные интерпретации . Уайли-Интерсайенс. стр. 105–136. ISBN 0-471-92420-2. МР  1086874.