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

Задача о сумме подмножеств — это важная задача в теории сложности алгоритмов и криптографии. Задача заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел этого подмножества равнялась нулю. Например, пусть задано множество <−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 N N), поскольку имеется 2 N подмножеств, а для проверки каждого подмножества необходимо сложить не более N элементов.

Более оптимальный алгоритм имеет время работы O(2 N/2 ). Этот алгоритм делит всё множество из N элементов на два подмножества по N/2 элементов в каждом. Для каждого из этих подмножеств строится набор сумм всех 2 N/2 возможных подмножеств. Оба списка сортируются. Если использовать простое сравнение для сортировки, получим время O(2 N/2 N). Однако можно применить метод слияния. Имея сумму для 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] .

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

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

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

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

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

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

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

Для каждого присвоения значение Q в правой части уже известно, поскольку либо оно занесено в таблицу предыдущих значений i, либо Q(i − 1, s − x_i) = Нет при s − x_i или 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, T и U всегда полиномиально зависим от N и 1/c и, следовательно, все операции над ними будут выполняться за полиномиальное время. Сохранить размер списков полиномиальным позволяет шаг исключения близких значений, на котором добавляется элемент z в список S, только если он больше предыдущего на cs/N и не больше s, что обеспечивает включение не более N/c элементов в список.

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

БлогNot. Задача о сумме подмножеств

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

. или subset sum problem по-ихнему, подробно описана в Вики. Ниже в консольном приложении Visual Studio 2015 мы решаем её с помощью рекурсии на тесте из Вики. Наше решение оказывается совсем простым, временная сложность алгоритма не оценивалась 🙂

Если хотим решить за (псевдо)полиномиальное время, платой за этой будет необходимость составлять дополнительные таблицы, вот подход к решению (не выводит подмножество, а только определяет, существует ли оно для некоторой суммы sum ).

27.05.2018, 12:34; рейтинг: 1072

Содержание

Доказательство NP-полноты [ править ]

Для доказательства того, что задаче о сумме подмножества (англ. Subset sum problem, [math]mathrm[/math] ) NP-полной, необходимо доказать два факта:

Доказательство принадлежности NP [ править ]

В качестве сертификата возьмем удовлетворяющее условию задачи множество [math]S'[/math] с суммой [math]s[/math] . Оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция проверит вхождение всех элементов [math]S'[/math] в множество [math]S[/math] за время [math]leftvert[/math] . Теперь [math]S'[/math] содержит уже [math]n[/math] чисел. Заметим, что для каждого "скобочного" разряда в уже набранной части [math]S'[/math] есть не менее одного и не более трех чисел, у которых в данном разряде стоит [math]1[/math] . Значит для каждого соответствующего паре скобок [math]C_[/math] разряда мы сможем выбрать одно или оба числа [math]d_[/math] и [math]e_[/math] так, чтобы сумма в данном разряде совпадала с требуемой (стала равна [math]4[/math] ). Добавим их в [math]S'[/math] . Также заметим, что суммы во всех "переменных" разрядах равны [math]1[/math] , так как для каждого [math]i[/math] выбиралось строго одно число из [math]v_[/math] и [math]u_[/math] . Значит, [math] sumlimits_ in S’>> = s[/math] .
Пусть теперь в наборе [math]S[/math] есть подмножество [math]S’:

sumlimits_ in S’>> = s[/math] . Тогда исходная формула [math]varphi[/math] выполнима. Действительно, если [math]v_ in S'[/math] , то установим переменную [math]x_=1[/math] . Если же [math]w_ in S'[/math] , то [math]x_=0[/math] . Покажем, что [math]varphi(x_<1>ldots x_) = 1 [/math] . Действительно, так как [math] sumlimits_ in S’>> = s[/math] , в каждой паре скобок хотя бы один терм равен [math]1[/math] . Значит каждый терм равен [math]1[/math] . А тогда и вся [math]varphi = 1[/math] .

Пример сведения [ править ]

Пусть исходная функция [math]varphi(x_ <1>ldots x_<4>) = (x_ <1>lor x_ <2>lor
eg x_<3>) land (
eg x_ <1>lor x_ <2>lor x_<4>)[/math] . Пометим разряды следующим образом (слева направо): [math]x_<1>,x_<2>,x_<3>,x_<4>,C_<1>,C_<2>[/math] . Тогда:

• [math]v_ <1>= 100010[/math]
• [math]w_ <1>= 100001[/math]

• [math]v_ <2>= 010011 = 10011[/math]
• [math]w_ <2>= 010000 = 10000[/math]

• [math]v_ <3>= 001000 = 1000[/math]
• [math]w_ <3>= 001010 = 1010[/math]

• [math]v_ <4>= 000101 = 101[/math]
• [math]w_ <4>= 000100 = 100[/math]

• [math]d_ <1>= 000010 = 10[/math]
• [math]e_ <1>= 000020 = 20[/math]

• [math]d_ <2>= 000001 = 1[/math]
• [math]e_ <2>= 000002 = 2[/math]

• [math]s = 111144[/math]

[math]S = (igcuplimits_^ <4>v_) cup (igcuplimits_^ <4>w_) cup (igcuplimits_^ <2>d_) cup (igcuplimits_^ <2>e_)[/math]

Тогда набору значений [math]Y = (0,0,0,1):

varphi(Y) = 1[/math] соответствует [math]S’ = <1>,

e_<2>>[/math] . И действительно, [math]100001 + 10000 + 1010 + 101 + 10 + 20 + 2 = 111144[/math] .