Користувач:Ружанська А.В. КС-12/Задача про суму підмножини (1)

В інформатиці задача про суму підмножини є важливою проблемою в теорії складності та криптографії. Суть проблеми така: дано набір (або мультимножина) цілих чисел, існує непорожня підмножина, сума яких дорівнює нулю. Наприклад, дано множину {−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 чисел і для кожного з них перевіряти, якщо підмножина сумує потрібну кількість. Час виконання порядку , так як є 2^N підмножини і, щоб перевірити кожну підмножину ми повинні підвести в самий N елементів.

Кращи експоненційний час відомий алгоритм, який працює за час О(2^N/2). Алгоритм розбивається довільно на n елементів на дві групи по N/2 кожен. Для кожного з цих двох наборів, він зберігає список із суми всіх 2^N/2 можливих підмножин її елементів. Кожен з цих двох списків, потім сортують. З допомогою стандартного порівняння алгоритм сортування для цього кроку потрібно час О(2^N/2N). Однак, враховуючи відсортований список сум для до елементів, то список можна розширити до двох відсортованих списків з введення (до + 1) - го елемента, і цих двох відсортованих списків можуть бути об'єднані в часі про(2^к). Таким чином, кожен список може бути створений в рассортированном вигляді в Час годин(2^N/2). Дано два відсортованих списків, алгоритм може перевірити, якщо елемент першого масиву і елемент другого масивів суму до ов під час Про(2^N/2). Щоб зробити це, алгоритм проходить через перший масив в порядку убування (починаючи з найбільшого елемента) і другого масиву в порядку зростання (починаючи з найменшого елемента). Всякий раз, коли суму поточного елемента в першому масиві і поточний елемент другого масивів більше, ніж з, то алгоритм переходить на наступний елемент у першому масиві. Якщо він менше х, то алгоритм переходить до наступного елементу другого масиву. Якщо два елементи з сумою и не знайшли, він зупиняється. Горовіц і Ахни вперше опублікував цей алгоритм в технічний звіт у 1972 році.^[2]

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

Складність ред.

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 {{citation}}: Вказано більш, ніж один |DOI= та |doi= (довідка); Вказано більш, ніж один |MR= та |mr= (довідка)Вказано більш, ніж один |mr= та |MR= (довідка); Вказано більш, ніж один |DOI= та |doi= (довідка)

Подальше читання ред.

Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (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.

[[Категорія:Динамічне програмування]]

[MartelloToth-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] 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 {{citation}}: Вказано більш, ніж один |DOI= та |doi= (довідка); Вказано більш, ніж один |MR= та |mr= (довідка)Вказано більш, ніж один |mr= та |MR= (довідка); Вказано більш, ніж один |DOI= та |doi= (довідка)

[1]

[2]