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

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

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

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

Цікавим особливим випадком цієї задачі є задача про розбиття, при цьому S становить половину від суми всіх елементів у множині (тобто, $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, рішення знайдено і алгоритм зупиняється. Шаблон:Нп (Шаблон:Lang-en) і Шаблон:Нп (Шаблон:Lang-en) вперше опублікували цей алгоритм у 1972 році.

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

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

x₁, …, x_N

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

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

Зрозуміло, що Шаблон:Nowrap, якщо Шаблон:Nowrap або Шаблон:Nowrap, так що ці значення немає необхідності обчислювати або зберігати. Створимо масив, що містить значення 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) = Ні при Шаблон:Nowrap чи Шаблон:Nowrap Таким чином, повний час арифметичних операцій становить O(N(B − A)). Наприклад, якщо всі значення порядку O(N^k) для деякого k, то необхідно час O(N^k+2).

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

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

Для випадку, коли всі x_i позитивні і обмежені константою С, Пісінжер Шаблон:Webarchive знайшов лінійний алгоритм зі складністю O(NC) (в цьому випадку в задачі потрібно знайти ненульову суму, інакше завдання стає тривіальним). У 2015, Коіліаріс (Koiliaris) та Ху (Xu) знайшли алгоритм, що працює зі швидкістю $\tilde{O}(s\sqrt{N})$, де $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.

Див. також

• Шаблон:Нп
• Ранцева криптосистема Меркле — Геллмана

Джерела

• Шаблон:CLRS
• Шаблон:Cite book A3.2: SP13, pg.223.