В інформатиці задача про суму підмножини є важливою проблемою вибору в теорії складності та криптографії. Суть проблеми така: для заданої мультимножини цілих чисел, чи існує непорожня підмножина, сума елементів якої дорівнює нулю. Наприклад, якщо дано множину { −7, −3, −2, 5, 8}, то відповідь Так, тому що сума елементів підмножини {−3, −2, 5} дорівнює нулю.
Еквівалентна проблема полягає в наступному: задано мультимножину цілих чисел і цільова сума S, чи існує підмножина, сума елементів якої дорівнює S? Сума підмножини може також розглядатися як задача оптимізації: знайти підмножину, сума елементів якої найближче до S.
Сума підмножини може також розглядатися як особливий випадок задачі про рюкзак.
Цікавим особливим випадком цієї задачі є задача про розбиття, при цьому S становить половину від суми всіх елементів у множині (тобто, ).
Задача є 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 році.
Розв'язання за допомогою динамічного програмування з псевдополіноміальним часом
Завдання може бути розв'язане за допомогою динамічного програмування у псевдополіноміальний час. Нехай дана послідовність чисел
- 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) (в цьому випадку в задачі потрібно знайти ненульову суму, інакше завдання стає тривіальним). У 2015, Коіліаріс (Koiliaris) та Ху (Xu) знайшли алгоритм, що працює зі швидкістю , де — сума, яку потрібно знайти.
Приблизний алгоритм поліноміального часу
Існує версія наближеного апроксимаційного алгоритму, що дає для заданої множини 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 .
- Martello, Silvano; Toth, Paolo (1990). 4 Subset-sum problem. Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. с. 105–136. ISBN . 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.
{{}}
: Перевірте значення|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 .
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN . A3.2: SP13, pg.223.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V informaticizadacha pro sumu pidmnozhini ye vazhlivoyu problemoyu viboru v teoriyi skladnosti ta kriptografiyi Sut problemi taka dlya zadanoyi multimnozhini cilih chisel chi isnuye neporozhnya pidmnozhina suma elementiv yakoyi dorivnyuye nulyu Napriklad yaksho dano mnozhinu 7 3 2 5 8 to vidpovid Tak tomu sho suma elementiv pidmnozhini 3 2 5 dorivnyuye nulyu Ekvivalentna problema polyagaye v nastupnomu zadano multimnozhinu cilih chisel i cilova suma S chi isnuye pidmnozhina suma elementiv yakoyi dorivnyuye S Suma pidmnozhini mozhe takozh rozglyadatisya yak zadacha optimizaciyi znajti pidmnozhinu suma elementiv yakoyi najblizhche do S Suma pidmnozhini mozhe takozh rozglyadatisya yak osoblivij vipadok zadachi pro ryukzak Cikavim osoblivim vipadkom ciyeyi zadachi ye zadacha pro rozbittya pri comu S stanovit polovinu vid sumi vsih elementiv u mnozhini tobto S 1 2 a 1 a n displaystyle S frac 1 2 a 1 dots a n Zadacha ye NP povnoyu Prote isnuye dekilka algoritmiv yaki na praktici dozvolyayut shvidko znajti vidpovid SkladnistSkladnist problemi sumi pidmnozhin zalezhnist dvoh parametriv N kilkosti zminnih rishennya i P tochnosti virishennya problemi vkazuyetsya yak kilkist dvijkovih rozryadiv sho potribni shob sformulyuvati zavdannya Primitka tut literi N i P ne mayut nichogo spilnogo z klasom zadach NP Skladnist vidomih algoritmiv eksponencialno zalezhit vid menshogo z dvoh parametriv N i P Takim chinom problema ye skladnishoyu yaksho N i P mayut odin i toj zhe poryadok Vse sproshuyetsya tilki todi yaksho N abo P budut duzhe malenkimi Yaksho N kilkist zminnih ye nevelikoyu to mozhna znajti rishennya povnim pereborom variantiv Yaksho P chislo rozryadiv ye nevelikim fiksovanim chislom to isnuyut algoritmi dinamichnogo programuvannya yaki mozhut virishiti ce tochno Efektivni algoritmi dlya vipadkiv malih N i malih P navedeno nizhche Eksponencialnij algoritmYe kilka sposobiv shob virishiti sumu pidmnozhini u eksponencialnij chas v N Najprostishij sposib perebirati vsi pidmnozhini z N chisel i dlya kozhnoyi z nih pereviryati chi otrimano potribnu sumu Chas vikonannya bude poryadku O 2NN tak yak vsogo 2N pidmnozhin i shob pereviriti kozhnu pidmnozhinu potribno dodati Nelementiv Bilsh optimalnij algoritm maye chas roboti O 2N 2 Cej algoritm dilit vsi mnozhini z N elementiv na dvi pidmnozhini po N 2 elementiv u kozhnij Dlya kozhnoyi z cih pidmnozhin buduyetsya nabir sum vsih 2N 2 mozhlivih pidmnozhin Obidva spiski sortuyutsya Yaksho vikoristovuvati proste porivnyannya dlya sortuvannya otrimayemo chas O 2N 2N Odnak mozhna zastosuvati metod zlittya Mayuchi sumu dlya k elementiv dodamo k 1 element i otrimayemo dva sortovanih spiskiv potim zrobimo zlittya spiskiv bez dodanogo elementa i z dodanim elementom Teper ye spisok sum dlya k 1 elementiv i dlya jogo stvorennya bulo potribno O 2k chasu Takim chinom kozhen spisok mozhe buti stvorenij za chas O 2N 2 Mayuchi dva vidsortovanih spiskiv algoritm mozhe pereviriti chi mozhut dati sumi elementiv pershogo i drugogo spisku znachennya s za chas O 2N 2 Dlya cogo algoritm pereglyadaye pershij spisok v poryadku spadannya pochinayuchi z najbilshogo elementa a drugij spisok v poryadku zrostannya pochinayuchi z najmenshogo elementa Yaksho suma potochnih elementiv bilshe s algoritm peresuvayetsya do nastupnogo elementa v pershomu spisku a yaksho menshe s do nastupnogo elementa v drugomu spisku Yaksho vin menshe s to algoritm perehodit do nastupnogo elementu drugogo masivu Yaksho zh suma dorivnyuye s rishennya znajdeno i algoritm zupinyayetsya en angl Ellis Horowitz i en angl Sartaj Sahni vpershe opublikuvali cej algoritm u 1972 roci Rozv yazannya za dopomogoyu dinamichnogo programuvannya z psevdopolinomialnim chasomZavdannya mozhe buti rozv yazane za dopomogoyu dinamichnogo programuvannya u psevdopolinomialnij chas Nehaj dana poslidovnist chisel x1 xN i neobhidno znajti chi isnuye neporozhnya pidmnozhina ciyeyi poslidovnosti z nulovoyu sumoyu elementiv Nehaj A suma vid yemnih elementiv i B suma dodatnih Viznachimo bulevu funkciyu Q i s sho prijmaye znachennya Tak yaksho isnuye neporozhnya pidmnozhina elementiv x1 xi sho daye v sumi s i Ni v inshomu vipadku Todi rishennyam zavdannya bude znachennya Q N 0 Zrozumilo sho Q i s Ni yaksho s lt A abo s gt B tak sho ci znachennya nemaye neobhidnosti obchislyuvati abo zberigati Stvorimo masiv sho mistit znachennya Q i s dlya 1 i N i A s B Masiv mozhe buti zapovnenij za dopomogoyu prostoyi rekursiyi Spochatku dlya A s B poklademo Q 1 s x1 s de ce buleva funkciya yaka povertaye Tak yaksho h1 dorivnyuye s i Ni v inshomu vipadku Narazi dlya i 2 N poklademo Q i s Q i 1 s chi xi s chi Q i 1 s xi for A s B Dlya kozhnogo prisvoyennya znachennya Q v pravij chastini vzhe vidomo oskilki abo vono zaneseno v tablicyu poperednih znachen i abo Q i 1 s xi Ni pri s xi lt A chi s xi gt B Takim chinom povnij chas arifmetichnih operacij stanovit O N B A Napriklad yaksho vsi znachennya poryadku O Nk dlya deyakogo k to neobhidno chas O Nk 2 Algoritm legko modifikuyetsya dlya znahodzhennya nulovoyi sumi yaksho taka ye Algoritm ne vvazhayetsya polinomialnim oskilki B A ne ye polinomialnim vid rozmiru zadachi v roli yakogo vistupaye chislo bit Algoritm polinomialnij vid znachen A ta B a voni eksponencialno zalezhat vid chisla bit Dlya vipadku koli vsi xi pozitivni i obmezheni konstantoyu S Pisinzher 2 sichnya 2009 u Wayback Machine znajshov linijnij algoritm zi skladnistyuO NC v comu vipadku v zadachi potribno znajti nenulovu sumu inakshe zavdannya staye trivialnim U 2015 Koiliaris Koiliaris ta Hu Xu znajshli algoritm sho pracyuye zi shvidkistyu O s N displaystyle tilde O s sqrt N de s displaystyle s suma yaku potribno znajti Pribliznij algoritm polinomialnogo chasuIsnuye versiya nablizhenogo aproksimacijnogo algoritmu sho daye dlya zadanoyi mnozhini N elementiv x1 x2 xN i chisla s nastupnij rezultat Tak yaksho isnuye pidmnozhina z sumoyu elementiv s Ni yaksho nemaye pidmnozhini sho maye sumu elementiv mizh 1 c s i s dlya deyakogo malogo c gt 0 Bud yaka vidpovid tak chi ni yaksho isnuye pidmnozhina z sumoyu elementiv mizh 1 c s i s ale cya suma ne dorivnyuye s Yaksho vsi elementi nevid yemni algoritm daye rishennya za polinomialnij chas yakij zalezhit vid N i 1 s Algoritm zabezpechuye rishennya vihidnoyi zadachi znahodzhennya sumi pidmnozhin u razi yaksho chisla mali i znovu zh taki nevid yemni Yaksho bud yaka suma chisel maye ne bilshe P bit to rishennya zadachi c 2 P ekvivalentno znahodzhennyu tochnogo rishennya Takim chinom polinomialnij nablizhenij algoritm staye tochnim iz chasom vikonannya zalezhat polinomialno vid N ta 2P tobto eksponencialno vid P Algoritm nablizhenogo rozv yazannya zadachi pro sumu mnozhin pracyuye takim chinom Stvoryuyemo spisok S sho spochatku skladayetsya z odnogo elementa 0 Dlya vsih i vid 1 do N vikonayemo nastupni diyi Stvoryuyemo spisok T sho skladayetsya z xi y dlya vsih y z S Stvoryuyemo spisok U rivnij ob yednannyu T i S Sortuyemo U Spustoshuyemo S Nehaj y najmenshij element U Vnesemo y v S Dlya vsih elementiv z z U perebirayuchi yih u poryadku zrostannya vikonayemo tim samim mi viklyuchayemo blizki znachennya i vidkidayemo znachennya sho perevishuyut s Yaksho y cs N lt z s poklademo y z i vnesemo z u spisok S Yaksho s mistit chislo mizh 1 c s i s vivoditsya Tak u protivnomu vipadku Ni Algoritm maye polinomialnij chas roboti oskilki rozmir spiskiv S T ta U zavzhdi polinomialno zalezhit vid N i 1 c i otzhe vsi operaciyi nad nimi vikonuvatimutsya za polinomialnij chas Zberegti rozmir polinomialnih spiskiv dozvolyaye krok viklyuchennya blizkih znachen na yakomu dodayetsya element z u spisok S tilki yaksho vin bilshe poperednogo na cs N i ne bilshe s sho zabezpechuye vklyuchennya ne bilsh N c elementiv v spisok Algoritm korektnij oskilki kozhen krok daye sumarnu pomilku ne bilshe cs N i N krokiv razom dadut pomilku yaka ne perevershuye cs PrimitkiKleinberg Jon Tardos Eva 2006 Algorithm Design vid 2nd s 491 ISBN 0 321 37291 3 Martello Silvano Toth Paolo 1990 4 Subset sum problem Knapsack problems Algorithms and computer interpretations Wiley Interscience s 105 136 ISBN 0 471 92420 2 MR 1086874 Cieliebak Mark Eidenbenz Stephan Pagourtzis Aris T Schlude Konrad 1 veresnya 2008 On the complexity of variations of equal sum subsets Nordic Journal of Computing T 14 3 s 151 172 doi 10 5555 1737763 1737764 ISSN 1236 6064 Procitovano 29 listopada 2020 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite news title Shablon Cite news cite news a Perevirte znachennya doi dovidka Ellis Horowitz Sartaj Sahni Computing partitions with applications to the knapsack problem Journal of the Association for Computing Machinery 1974 21 S 277 292 DOI 10 1145 321812 321823 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 lipnya 2015 A Faster Pseudopolynomial Time Algorithm for Subset Sum arXiv 1507 02318 Div takozh en Ranceva kriptosistema Merkle GellmanaDzherelaTomas Kormen Charlz Lejzerson Ronald Rivest Kliford Stajn 2009 1990 35 5 Zadacha pro sumu pidmnozhini Vstup do algoritmiv vid 3rd MIT Press i 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