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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

x1, ..., xN

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

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

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

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

Q(1,s) := (x1 == s).

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

Q(i,s) := Q(i − 1,s) или (xi == s) или Q(i − 1,sxi)   для AsB.

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

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

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

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

Приближенный алгоритм, работающий за полиномиальное время[править | править исходный текст]

Существует версия приближенного алгоритма, дающего для заданного множества из N элементов x1, x2, ..., xN и числа s следующий результат:

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

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

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

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

 Создаем список S, первоначально  состоящий из одного элемента 0.
 Для всех i от 1 до N выполним следующие действия
   Создаем список T, состоящий из xi + y для всех y из S
   Создаем список U, равный объединению T и S
   Сортируем U
   Опустошаем S 
   Пусть y – наименьший элемент U 
   Внесем y в S 
   Для всех элементов z из U, перебирая их в порядке  возрастания выполним
     Если y + cs/N < zs, положим 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.

Дальнейшее чтение[править | править исходный текст]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein; Introduction to Algorithms, 3rd Edition, 2009, MIT Press, ISBN: 978-0-262-03384-8; chapter=35.5: The subset-sum problem
  • 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.

Ссылки[править | править исходный текст]

  1. 4 Subset-sum problem // Knapsack problems: Algorithms and computer interpretations. — Wiley-Interscience, 1990. — P. 105–136. — ISBN 0-471-92420-2
  2. Horowitz, Ellis & Sahni, Sartaj (1974), "«Computing partitions with applications to the knapsack problem»", Journal of the Association for Computing Machinery Т. 21: 277–292, DOI 10.1145/321812.321823 
  3. Pisinger D (1999). "Linear Time Algorithms for Knapsack Problems with Bounded Weights". Journal of Algorithms, Volume 33, Number 1, October 1999, pp. 1–14

Смотрите также[править | править исходный текст]