Задача про суму підмножин

В інформатиці задача про суму підмножини є важливою проблемою вибору в теорії складності та криптографії. Суть проблеми така: для заданої мультимножини цілих чисел, чи існує непорожня підмножина, сума елементів якої дорівнює нулю. Наприклад, якщо дано множину { −7, −3, −2, 5, 8}, то відповідь Так, тому що сума елементів підмножини {−3, −2, 5} дорівнює нулю.

Еквівалентна проблема полягає в наступному: задано мультимножину цілих чисел і цільова сума S, чи існує підмножина, сума елементів якої дорівнює S? Сума підмножини може також розглядатися як задача оптимізації: знайти підмножину, сума елементів якої найближче до S.

Сума підмножини може також розглядатися як особливий випадок задачі про рюкзак.

Цікавим особливим випадком цієї задачі є задача про розбиття, при цьому S становить половину від суми всіх елементів у множині (тобто, ${\displaystyle S={\frac {1}{2}}(a_{1}+\dots +a_{n})}$).

Задача є NP-повною. Проте існує декілька алгоритмів, які на практиці дозволяють швидко знайти відповідь.

Складність

Складність проблеми суми підмножин залежність двох параметрів: N — кількості змінних рішення, і P — точності вирішення проблеми (вказується як кількість двійкових розрядів, що потрібні, щоб сформулювати завдання). (Примітка: тут літери N і P не мають нічого спільного з класом задач NP.)

Складність відомих алгоритмів експоненціально залежить від меншого з двох параметрів N і P. Таким чином, проблема є складнішою, якщо N і P мають один і той же порядок. Все спрощується тільки тоді, якщо N або P будуть дуже маленькими.

Якщо N (кількість змінних) є невеликою, то можна знайти рішення повним перебором варіантів. Якщо P (число розрядів) є невеликим фіксованим числом, то існують алгоритми динамічного програмування, які можуть вирішити це точно.

Ефективні алгоритми для випадків малих N і малих P наведено нижче.

Експоненціальний алгоритм

Є кілька способів, щоб вирішити суму підмножини у експоненціальний час в N. Найпростіший спосіб — перебирати всі підмножини з N чисел і для кожної з них перевіряти, чи отримано потрібну суму. Час виконання буде порядку O(2^NN), так як всього 2^N підмножин і, щоб перевірити кожну підмножину потрібно додати N елементів.

Більш оптимальний алгоритм має час роботи О(2^N/2). Цей алгоритм ділить всі множини з N елементів на дві підмножини по N/2 елементів у кожній. Для кожної з цих підмножин будується набір сум всіх 2^N/2 можливих підмножин. Обидва списки сортуються. Якщо використовувати просте порівняння для сортування, отримаємо час О(2^N/2N). Однак можна застосувати метод злиття. Маючи суму для k елементів, додамо (k + 1) елемент і отримаємо два сортованих списків, потім зробимо злиття списків (без доданого елемента і з доданим елементом). Тепер є список сум для (k + 1) елементів, і для його створення було потрібно O(2^k) часу. Таким чином, кожен список може бути створений за час O(2^N/2). Маючи два відсортованих списків, алгоритм може перевірити, чи можуть дати суми елементів першого і другого списку значення s за час O(2^N/2). Для цього алгоритм переглядає перший список в порядку спадання (починаючи з найбільшого елемента), а другий список в порядку зростання (починаючи з найменшого елемента). Якщо сума поточних елементів більше s, алгоритм пересувається до наступного елемента в першому списку, а якщо менше s, до наступного елемента в другому списку. Якщо він менше s, то алгоритм переходить до наступного елементу другого масиву. Якщо ж сума дорівнює s, рішення знайдено і алгоритм зупиняється. ^[en] (англ. Ellis Horowitz) і ^[en] (англ. Sartaj Sahni) вперше опублікували цей алгоритм у 1972 році.

Розв'язання за допомогою динамічного програмування з псевдополіноміальним часом

Завдання може бути розв'язане за допомогою динамічного програмування у псевдополіноміальний час. Нехай дана послідовність чисел

x₁, …, x_N

і необхідно знайти, чи існує непорожня підмножина цієї послідовності з нульовою сумою елементів. Нехай A — сума від'ємних елементів і B — сума додатних. Визначимо булеву функцію Q(i, s), що приймає значення Так, якщо існує непорожня підмножина елементів x₁, …, x_i, що дає в сумі s, і Ні в іншому випадку.

Тоді рішенням завдання буде значення Q(N, 0).

Зрозуміло, що Q(i, s) = Ні, якщо s < A або s > B, так що ці значення немає необхідності обчислювати або зберігати. Створимо масив, що містить значення Q(i, s) для 1 ≤ i ≤ N і A ≤ s ≤ B.

Масив може бути заповнений за допомогою простої рекурсії. Спочатку, для A ≤ s ≤ B, покладемо

Q(1, s) := (x₁ == s).

де == — це булева функція, яка повертає Так, якщо х₁ дорівнює s, і Ні в іншому випадку.

Наразі для i = 2, …, N, покладемо

Q(i, s) := Q(i − 1, s) чи (x_i == s) чи Q(i − 1, s − x_i),  for A ≤ s ≤ B.

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

Алгоритм легко модифікується для знаходження нульової суми, якщо така є.

Алгоритм не вважається поліноміальним, оскільки B − A не є поліноміальним від розміру задачі, в ролі якого виступає число біт. Алгоритм поліноміальний від значень A та B, а вони експоненціально залежать від числа біт.

Для випадку, коли всі x_i позитивні і обмежені константою С, Пісінжер [Архівовано 2 січня 2009 у Wayback Machine.] знайшов лінійний алгоритм зі складністю O(NC) (в цьому випадку в задачі потрібно знайти ненульову суму, інакше завдання стає тривіальним). У 2015, Коіліаріс (Koiliaris) та Ху (Xu) знайшли алгоритм, що працює зі швидкістю ${\displaystyle {\tilde {O}}(s{\sqrt {N}})}$, де ${\displaystyle s}$ — сума, яку потрібно знайти.

Приблизний алгоритм поліноміального часу

Існує версія наближеного апроксимаційного алгоритму, що дає для заданої множини N елементів x₁, x₂, …, x_N і числа s наступний результат:

• Так, якщо існує підмножина з сумою елементів s;
• Ні, якщо немає підмножини, що має суму елементів між (1 − c)s і s для деякого малого c > 0;
• Будь-яка відповідь (так чи ні), якщо існує підмножина з сумою елементів між (1 − c)s і s, але ця сума не дорівнює  s.

Якщо всі елементи невід'ємні, алгоритм дає рішення за поліноміальний час, який залежить від N і 1/с.

Алгоритм забезпечує рішення вихідної задачі знаходження суми підмножин у разі, якщо числа малі (і, знову ж таки, невід'ємні). Якщо будь-яка сума чисел має не більше P біт, то рішення задачі c = 2^−P еквівалентно знаходженню точного рішення. Таким чином, поліноміальний наближений алгоритм стає точним із часом виконання, залежать поліноміально від N та 2^P (тобто експоненціально від P).

Алгоритм наближеного розв'язання задачі про суму множин працює таким чином:

Створюємо список S, що спочатку складається з одного елемента 0. Для всіх i від 1 до N виконаємо наступні дії Створюємо список T, що складається з xi + y для всіх y з S Створюємо список U, рівний об'єднанню T і S Сортуємо U Спустошуємо S Нехай y – найменший елемент U Внесемо y в S Для всіх елементів z з U, перебираючи їх у порядку зростання, виконаємо //тим самим ми виключаємо близькі значення і //відкидаємо значення, що перевищують s Якщо y + cs/N < z ≤ s, покладемо y = z і внесемо z у список S Якщо s містить число між (1 − c)s і s, виводиться Так, у противному випадку - Ні 

Алгоритм має поліноміальний час роботи, оскільки розмір списків S, T та U завжди поліноміально залежить від N і 1/c і, отже, всі операції над ними виконуватимуться за поліноміальний час. Зберегти розмір поліноміальних списків дозволяє крок виключення близьких значень, на якому додається елемент z у список S, тільки якщо він більше попереднього на cs/N і не більше s, що забезпечує включення не більш N/c елементів в список.

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

Примітки

1. Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design (вид. 2nd). с. 491. ISBN .
2. Martello, Silvano; Toth, Paolo (1990). 4 Subset-sum problem. Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. с. 105–136. ISBN . MR 1086874.
3. Cieliebak, Mark; Eidenbenz, Stephan; Pagourtzis, Aris T.; Schlude, Konrad (1 вересня 2008). On the complexity of variations of equal sum subsets. Nordic Journal of Computing. Т. 14, № 3. с. 151—172. doi:10.5555/1737763.1737764. ISSN 1236-6064. Процитовано 29 листопада 2020. {{}}: Перевірте значення |doi= ()
4. Ellis Horowitz, Sartaj Sahni. Computing partitions with applications to the knapsack problem // Journal of the Association for Computing Machinery. — 1974. — № 21. — С. 277—292. — DOI:10.1145/321812.321823.
5. Pisinger D (1999). «Linear Time Algorithms for Knapsack Problems with Bounded Weights». Journal of Algorithms, Volume 33, Number 1, October 1999, pp. 1–14
6. Koiliaris, Konstantinos; Xu, Chao (8 липня 2015). A Faster Pseudopolynomial Time Algorithm for Subset Sum. arXiv:1507.02318.

Див. також

• ^[en]
• Ранцева криптосистема Меркле — Геллмана

Джерела

• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 35.5 Задача про суму підмножини. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN . A3.2: SP13, pg.223.