Задача про суму підмножини
В інформатиці задача про суму підмножини є важливою проблемою вибору в теорії складності та криптографії. Суть проблеми така: для заданої мультимножини цілих чисел, чи існує непорожня підмножина, сума елементів якої дорівнює нулю. Наприклад, якщо дано множину { −7, −3, −2, 5, 8}, то відповідь Так, тому що сума елементів підмножини {−3, −2, 5} дорівнює нулю.
Еквівалентна проблема полягає в наступному: задано мультимножину цілих чисел і цільова сума S, чи існує підмножина, сума елементів якої дорівнює S[1]? Сума підмножини може також розглядатися як задача оптимізації: знайти підмножину, сума елементів якої найближче до S.
Сума підмножини може також розглядатися як особливий випадок задачі про рюкзак[2].
Цікавим особливим випадком цієї задачі є задача про розбиття, при цьому S становить половину від суми всіх елементів у множині (тобто, )[3].
Задача є NP-повною. Проте існує декілька алгоритмів, які на практиці дозволяють швидко знайти відповідь.
Складність проблеми суми підмножин залежність двох параметрів: N — кількості змінних рішення, і P — точності вирішення проблеми (вказується як кількість двійкових розрядів, що потрібні, щоб сформулювати завдання). (Примітка: тут літери N і P не мають нічого спільного з класом задач NP.)
Складність відомих алгоритмів експоненціально залежить від меншого з двох параметрів N і P. Таким чином, проблема є складнішою, якщо N і P мають один і той же порядок. Все спрощується тільки тоді, якщо N або P будуть дуже маленькими.
Якщо N (кількість змінних) є невеликою, то можна знайти рішення повним перебором варіантів. Якщо P (число розрядів) є невеликим фіксованим числом, то існують алгоритми динамічного програмування, які можуть вирішити це точно.
Ефективні алгоритми для випадків малих N і малих P наведено нижче.
Є кілька способів, щоб вирішити суму підмножини у експоненціальний час в N. Найпростіший спосіб — перебирати всі підмножини з N чисел і для кожної з них перевіряти, чи отримано потрібну суму. Час виконання буде порядку O(2NN), так як всього 2N підмножин і, щоб перевірити кожну підмножину потрібно додати N елементів.
Більш оптимальний алгоритм має час роботи О(2N/2). Цей алгоритм ділить всі множини з N елементів на дві підмножини по N/2 елементів у кожній. Для кожної з цих підмножин будується набір сум всіх 2N/2 можливих підмножин. Обидва списки сортуються. Якщо використовувати просте порівняння для сортування, отримаємо час О(2N/2N). Однак можна застосувати метод злиття. Маючи суму для k елементів, додамо (k + 1) елемент і отримаємо два сортованих списків, потім зробимо злиття списків (без доданого елемента і з доданим елементом). Тепер є список сум для (k + 1) елементів, і для його створення було потрібно O(2k) часу. Таким чином, кожен список може бути створений за час O(2N/2). Маючи два відсортованих списків, алгоритм може перевірити, чи можуть дати суми елементів першого і другого списку значення s за час O(2N/2). Для цього алгоритм переглядає перший список в порядку спадання (починаючи з найбільшого елемента), а другий список в порядку зростання (починаючи з найменшого елемента). Якщо сума поточних елементів більше s, алгоритм пересувається до наступного елемента в першому списку, а якщо менше s, до наступного елемента в другому списку. Якщо він менше s, то алгоритм переходить до наступного елементу другого масиву. Якщо ж сума дорівнює s, рішення знайдено і алгоритм зупиняється. Еліс Горовіц[en] (англ. Ellis Horowitz) і Сартаж Сахні[en] (англ. Sartaj Sahni) вперше опублікували цей алгоритм у 1972 році[4].
Завдання може бути розв'язане за допомогою динамічного програмування у псевдополіноміальний час. Нехай дана послідовність чисел
- x1, …, xN
і необхідно знайти, чи існує непорожня підмножина цієї послідовності з нульовою сумою елементів. Нехай A — сума від'ємних елементів і B — сума додатних. Визначимо булеву функцію Q(i, s), що приймає значення Так, якщо існує непорожня підмножина елементів x1, …, xi, що дає в сумі 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) := (x1 == s).
де == — це булева функція, яка повертає Так, якщо х1 дорівнює s, і Ні в іншому випадку.
Наразі для i = 2, …, N, покладемо
- Q(i, s) := Q(i − 1, s) чи (xi == s) чи Q(i − 1, s − xi), for A ≤ s ≤ B.
Для кожного присвоєння значення Q в правій частині вже відомо, оскільки або воно занесено в таблицю попередніх значень i, або Q(i − 1,s − xi) = Ні при s − xi < A чи s − xi > B. Таким чином, повний час арифметичних операцій становить O(N(B − A)). Наприклад, якщо всі значення порядку O(Nk) для деякого k, то необхідно час O(Nk+2).
Алгоритм легко модифікується для знаходження нульової суми, якщо така є.
Алгоритм не вважається поліноміальним, оскільки B − A не є поліноміальним від розміру задачі, в ролі якого виступає число біт. Алгоритм поліноміальний від значень A та B, а вони експоненціально залежать від числа біт.
Для випадку, коли всі xi позитивні і обмежені константою С, Пісінжер [Архівовано 2 січня 2009 у Wayback Machine.] знайшов лінійний алгоритм зі складністю O(NC) (в цьому випадку в задачі потрібно знайти ненульову суму, інакше завдання стає тривіальним)[5]. У 2015, Коіліаріс (Koiliaris) та Ху (Xu) знайшли алгоритм, що працює зі швидкістю , де — сума, яку потрібно знайти.[6]
Існує версія наближеного апроксимаційного алгоритму, що дає для заданої множини N елементів x1, x2, …, xN і числа s наступний результат:
- Так, якщо існує підмножина з сумою елементів s;
- Ні, якщо немає підмножини, що має суму елементів між (1 − c)s і s для деякого малого c > 0;
- Будь-яка відповідь (так чи ні), якщо існує підмножина з сумою елементів між (1 − c)s і s, але ця сума не дорівнює s.
Якщо всі елементи невід'ємні, алгоритм дає рішення за поліноміальний час, який залежить від N і 1/с.
Алгоритм забезпечує рішення вихідної задачі знаходження суми підмножин у разі, якщо числа малі (і, знову ж таки, невід'ємні). Якщо будь-яка сума чисел має не більше P біт, то рішення задачі c = 2−P еквівалентно знаходженню точного рішення. Таким чином, поліноміальний наближений алгоритм стає точним із часом виконання, залежать поліноміально від N та 2P (тобто експоненціально від 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.
- ↑ Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design (вид. 2nd). с. 491. ISBN 0-321-37291-3.
- ↑ Martello, Silvano; Toth, Paolo (1990). 4 Subset-sum problem. Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. с. 105–136. ISBN 0-471-92420-2. MR 1086874.
- ↑ 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.
{{cite news}}: Перевірте значення|doi=(довідка) - ↑ Ellis Horowitz, Sartaj Sahni. Computing partitions with applications to the knapsack problem // Journal of the Association for Computing Machinery. — 1974. — № 21. — С. 277—292. — DOI:.
- ↑ Pisinger D (1999). «Linear Time Algorithms for Knapsack Problems with Bounded Weights». Journal of Algorithms, Volume 33, Number 1, October 1999, pp. 1–14
- ↑ Koiliaris, Konstantinos; Xu, Chao (8 липня 2015). A Faster Pseudopolynomial Time Algorithm for Subset Sum. arXiv:1507.02318.
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 35.5 Задача про суму підмножини. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A3.2: SP13, pg.223.