Проблем збира подскупа

У рачунарству, проблем збира подскупа је значајан проблем у теорији комплексности и криптографији. Проблем је следећи: дат је скуп целих бројева, да ли постоји не-празан подскуп чији збир је нула? На пример, дат је скуп { −7, −3, −2, 5, 8}, одговор је ДА зато што{ −3, −2, 5} износи нула. Проблем је НП комплетан.

Еквивалентан проблем је ово: дат је скуп целих бројева и цео број с, да ли било који не-празан подскуп сумира до с? Збир подскупа може да се посматра као посебан случај проблема ранца. Један занимљив случај посебан збир подскупа подела проблема, у којем је с половина суме свих елемената у скупу.

Сложеност

Теорија комплексности (сложеност) проблема збира подскупа може се посматрати у зависности од параметра, Н, број доносилаца променљивих, и П, прецизност проблема (наведен као број вредности бинарних места која је потребно за проблем).

Сложеност најпознатијих алгоритама је експоненцијално мањи од два параметра Н и П. Дакле, проблем је веома тешко, ако Н и П су истог реда. То само постаје лако ако било Н или П постану веома мали.

Ако је Н (број променљивих) мали, тада је исцрпљујућа претрага практична за решење. Ако је П (број места вредности) мали фиксирани број, тада алгоритми динамичког програмирања могу да га реше тачно.

Ефикасни алгоритми за мале Н и мале П случајеве су дати у наставку.

Алгоритам експоненцијалног времена

Постоји неколико начина да се реши збир подскупа у експоненцијалном времену у Н. Наивни алгоритам би био циклус кроз све подгрупе Н бројева и за сваки од њих, проверите да ли постоји збир подскупа за прави број. Време рада је у О(2^НН), јер постоје 2^Н подскупи и, да проверите сваки подскуп, морамо да закључимо највише Н елемената.

Боље познатији експоненцијални алгоритам је онај који ради у времену О(2^Н/2). Алгоритам дели произвољно Н елементе у два сета Н/2 сваки. За сваки од ова два скупа, чува се списак суме од свих 2^Н/2 могућих подскупа њених елемената. Свака од ове две листе се затим сортира. Користећи стандардни поређење сортирања алгоритам за овај корак ће бити потребно време О(2^Н/2Н). Међутим, с обзиром сортирани списак износа за к елемената, списак се може проширити на две сортиране листе са увођењем (к + 1)ст елемента, и ове две сортиране листе могу да буду спојене за време О(2^к). Према томе, свака листа може бити генерисана у сортираном облику у времену О(2^Н/2). Имајући у виду два сортиране листе, алгоритам може да провери да ли се елемент првог низа и елемент другог низа добија за с у времену О(2^Н/2). Да бисте то урадили, алгоритам пролази кроз први низ у опадајућем редоследу (почевши од највећег елемента) и други низ у растућем редоследу (почевши од најмањег елемента). Кад год је сума тренутног елемента у првом низу и тренутни елемент у другом низу више од с,алгоритам прелази на следећи елемент у првом низу. Ако је то мање од с, алгоритам прелази на следећи елемент у другом низу. Ако су два елемента са сумом с нађена, онда се зауставља. Хороwитз анд Сахни први пут објавили овај алгоритам у техничком извештају 1972.

Динамичко програмирање

Проблем се може решити на следећи начин коришћењем динамичког програмирања. Претпоставимо да је ред

x₁, ..., x_Н

и желимо да се утврди да ли постоји непразан подскуп који сумира на нулу. Нека А буде збир негативних вредности и Б збир позитивних вредности. Дефинишемо буловску фунцкију Q(и,с) да има вредности (тачно или нетачно)

"постоји непразан подскуп x₁, ..., x_и који сумира до с".

Дакле, решење проблема је вредност Q(Н,0).

Јасно, Q(и,с) = фалсе ако с < А илис > Б тако да ове вредности не морају да се чувају или израчунавају. Креирање низа за одржавање вредности Q(и,с) за 1 ≤ и ≤ Н иА ≤ с ≤ Б.

Низ се сада може попунити помоћу једноставне рекурзије. У почетку, заА ≤ с ≤ Б, поставити

Q(1,с) := (x₁ == с).

Затим, за и = 2, …, Н, поставити

Q(и,с) := Q(и − 1,с) или (x_и == с) или Q(и − 1,с − x_и)   за А ≤ с ≤ Б.

За сваки задатак, вредности Q на десној страни су већ познати, или зато што су били ускладиштени у табели за претходну вредност и или због Q(и − 1,с − x_и) = фалсе ако с − x_и < А или с − x_и > Б. Дакле, укупан број аритметичких операција је О(Н(Б − А)). На пример, ако су све вредности О(Н^к) за неко к, онда је потребно време О(Н^к+2).

Овај алгоритам се лако модификује да врати подскуп суме са 0 ако постоји.

Ово решење се не рачуна као полиномијално време у теорији сложености, јер Б − А није полиномилно у величини проблема, што је број битова који се користе за репрезентацију. Овај алгоритам је полином у вредностима А и Б, који је експоненцијалану у броју битова.

Алгоритам апроксимације у полиномијалном времену

Апроксимована верзија збира подскупа ће бити: дат је скуп од Н бројева x₁, x₂, ..., x_Н и број с, излаз

• Да, ако постоји подскуп који сумира до с;
• Но, ако не постоји подскуп који сумира између (1 − ц)с и с за веома мале ц > 0;
• било какав одговор, ако постоји подскуп који сумира између (1 − ц)с и с али не и подскуп до с.

Ако су сви бројеви не-негативни, приближан збир подскупа је растворљив у временском полиному у Н и 1/ц.

Решење за збир подскупа такође пружа решење за проблем првобитног збира подскупа у случају где су бројеви су мали (опет, за не негативне бројева).Ако неки збир бројева може се одредити са највише П битова, затим решавање проблема са приближно ц = 2^−П је еквивалентнода се реши тачно. Затим, полиномијални алгоритам за приближни збир подскупа постаје тачан алгоритам са полиномијалним временом извршавања Н' и 2П .

Алгоритам за апроксимацију проблема збира подскупа је следећи:

 initialize a list S to contain one element 0.
 for each i from 1 to N do
   let T be a list consisting of xi + y, for all y in S
   let U be the union of T and S
   sort U
   make S empty 
   let y be the smallest element of U 
   add y to S 
   for each element z of U in increasing order do
      //trim the list by eliminating numbers close to one another
      //and throw out elements greater than s
     if y + cs/N < z ≤ s, set y = z and add z to S 
 if S contains a number between (1 − c)s and s, output yes, otherwise no

Алгоритам је полинојалног времена зато шсто листе С, Т и У увек остају на величини полинома у Н и 1/ц и, док су величине од полинома, све операције на њима могу да се ураде у полиномијалном времену. Величина листа чува полином по корак, у којој само укључује број з у С ако је већи од претходног за цс/Н а не већи од с.

Овај корак обезбеђује да сваки елемент у С је мањи од следећег најмање цс/Н и не садрже елементе веће од с. Свака листа са том особином се састоји од више од Н/ц елемената.

Алгоритам је коректан јер сваки корак уводи грешку за највише цс/Н и Н корака заједно уводећи грешку за највише цс.

Види још

• 3СУМ

Литература

• Мартелло, Силвано; Тотх, Паоло (1990). „4 Субсет-сум проблем”. Кнапсацк проблемс: Алгоритхмс анд цомпутер интерпретатионс. Wилеy-Интерсциенце. стр. 105-136. ИСБН 978-0-471-92420-3. МР 1086874. 
• Цормен, Тхомас Х.; Леисерсон, Цхарлес Е.; Ривест, Роналд L.; Стеин, Цлиффорд (2001) [1990]. „35.5: Тхе субсет-сум проблем”. Интродуцтион то Алгоритхмс (2нд изд.). МИТ Пресс анд МцГраw-Хилл. ИСБН 0-262-03293-7. 
• Мицхаел Р. Гареy анд Давид С. Јохнсон (1979). Цомпутерс анд Интрацтабилитy: А Гуиде то тхе Тхеорy оф НП-Цомплетенесс. W.Х. Фрееман. ИСБН 978-0-7167-1045-5.  А3.2: СП13, пг.223.