Користувач:Ружанська А.В. КС-12/Задача про суму підмножини
В інформатиці задача про суму підмножини є важливою проблемою в теорії складності та криптографії. Суть проблеми така: дано набір (або мультимножина) цілих чисел, існує непорожня підмножина, сума яких дорівнює нулю. Наприклад, дано множину {−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 і малих Р випадків наведено нижче.
Експонентний алгоритм[ред. | ред. код]
Є кілька способів, щоб вирішити суму підмножини у експоненціальний час в N. Метод «грубої сили» буде перебирати всі підмножини з N чисел і для кожного з них перевіряти, якщо підмножина сумує потрібну кількість. Час виконання порядку , так як є 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, рішення знайдено і алгоритм зупиняється. Горовіц (Horowitz) і Сани (Sartaj Sahni) вперше опублікували цей алгоритм у 1972 році.[2]
Розв'язання за допомогою динамічного програмування з псевдополіноміальним часом[ред. | ред. код]
Завдання може бути розв'язане за допомогою динамічного програмування. Нехай дана послідовність чисел
- х1, ..., хN
і необхідно знайти, чи існує непорожня підмножина цієї послідовності з нульовою сумою елементів.Нехай 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(i, s) = false, якщо s < A або s > B. Тому ці цінності не повинні зберігатися або обчислюватися.
Еквівалентна проблема полягає в наступному: задано множину цілих чисел і ціле число s, чи додається будь-яка непорожня підмножина до s? Сума підмножин може також розглядатися як особливий випадок задачі про рюкзак.[1] Одним цікавим особливим випадком суми підмножин є проблема розподілу, в якому s становить половину від суми всіх елементів у наборі.
Складність[ред. | ред. код]
- Щ(1, х) := (х1 == х)
де == - це булева функція, яка повертає True, якщо х1 дорівнює З, і false в іншому випадку.
Завдання може бути вирішена за допомогою динамічного програмування. Проблема може бути вирішена в псевдо-полиномиальное час за допомогою динамічного програмування. Припустимо, що послідовність
References[ред. | ред. код]
- ↑ а б 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.
- ↑ 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, MR 0354006
Подальше читання[ред. | ред. код]
- Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2001) [1990]. 35.5: The subset-sum problem. Вступ до алгоритмів (вид. 2nd). MIT Press і McGraw-Hill. ISBN 0-262-03293-7.
- 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. А3.2: sp13 справжнє, ПГ.223.
[[Категорія:Динамічне програмування]]