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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Складність[ред. | ред. код]

Складність проблеми суми підмножин залежність двох параметрів: 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(2к) часу. Таким чином, кожен список може бути створений за час O(2N/2). Маючи два відсортованих списків, алгоритм може перевірити, чи можуть дати суми елементів першого і другого списку значення s за час O(2N/2). Для цього алгоритм переглядає перший список в порядку спадання (починаючи з найбільшого елемента), а другий список в порядку зростання (починаючи з найменшого елемента). Якщо сума поточних елементів більше s, алгоритм пересувається до наступного елемента в першому списку, а якщо менше s, до наступного елемента в другому списку. Якщо він менше s, то алгоритм переходить до наступного елементу другого масиву. Якщо ж сума дорівнює s, рішення знайдено і алгоритм зупиняється. Еліс Горовіц[en] (англ. Ellis Horowitz) і Сартаж Сахні[en] (англ. Sartaj Sahni) вперше опублікували цей алгоритм у 1972 році[2].

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

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

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, sxi),  for AsB.

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

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

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

Для випадку, коли всі xi позитивні і обмежені константою С, Пісінжер знайшов лінійний алгоритм зі складністю O(NC) (в цьому випадку в задачі потрібно знайти ненульову суму, інакше завдання стає тривіальним)[3]. У 2015, Коіліаріс (Koiliaris) та Ху (Xu) знайшли алгоритм, що працює зі швидкістю , де  — сума, яку потрібно знайти.[4]

Приблизний алгоритм поліноміального часу[ред. | ред. код]

Існує версія наближеного апроксимаційного алгоритму[en], що дає для заданої множини N елементів x1, x2, …, xN і числа s наступний результат:

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

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

Алгоритм забезпечує рішення вихідної задачі знаходження суми підмножин у разі, якщо числа малі (і, знову ж таки, невід'ємні). Якщо будь-яка сума чисел має не більше 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, перебираючи їх у порядку зростання, виконаємо
      //тим самим ми виключаємо близькі значення і
      //відкидаємо значення, що перевищують s
     Якщо y + cs/N < zs, покладемо 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. 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. 
  2. 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.
  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
  4. Koiliaris, Konstantinos; Xu, Chao (2015-07-08). «A Faster Pseudopolynomial Time Algorithm for Subset Sum». arXiv:1507.02318. 

Див. також[ред. | ред. код]

Подальше читання[ред. | ред. код]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd Edition. — MIT Press, 2009. — ISBN 978-0-262-03384-8.
  • 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.