Problem zbira podskupa

U računarstvu, problem zbira podskupa je značajan problem u teoriji kompleksnosti i kriptografiji. Problem je sledeći: dat je skup celih brojeva, da li postoji ne-prazan podskup čiji zbir je nula? Na primer, dat je skup { −7, −3, −2, 5, 8}, odgovor je DA zato što{ −3, −2, 5} iznosi nula. Problem je NP kompletan.

Ekvivalentan problem je ovo: dat je skup celih brojeva i ceo broj s, da li bilo koji ne-prazan podskup sumira do s? Zbir podskupa može da se posmatra kao poseban slučaj problema ranca. Jedan zanimljiv slučaj poseban zbir podskupa podela problema, u kojem je s polovina sume svih elemenata u skupu.

Složenost

Teorija kompleksnosti (složenost) problema zbira podskupa može se posmatrati u zavisnosti od parametra, N, broj donosilaca promenljivih, i P, preciznost problema (naveden kao broj vrednosti binarnih mesta koja je potrebno za problem).

Složenost najpoznatijih algoritama je eksponencijalno manji od dva parametra N i P. Dakle, problem je veoma teško, ako N i P su istog reda. To samo postaje lako ako bilo N ili P postanu veoma mali.

Ako je N (broj promenljivih) mali, tada je iscrpljujuća pretraga praktična za rešenje. Ako je P (broj mesta vrednosti) mali fiksirani broj, tada algoritmi dinamičkog programiranja mogu da ga reše tačno.

Efikasni algoritmi za male N i male P slučajeve su dati u nastavku.

Algoritam eksponencijalnog vremena

Postoji nekoliko načina da se reši zbir podskupa u eksponencijalnom vremenu u N. Naivni algoritam bi bio ciklus kroz sve podgrupe N brojeva i za svaki od njih, proverite da li postoji zbir podskupa za pravi broj. Vreme rada je u O(2^NN), jer postoje 2^N podskupi i, da proverite svaki podskup, moramo da zaključimo najviše N elemenata.

Bolje poznatiji eksponencijalni algoritam je onaj koji radi u vremenu O(2^N/2). Algoritam deli proizvoljno N elemente u dva seta N/2 svaki. Za svaki od ova dva skupa, čuva se spisak sume od svih 2^N/2 mogućih podskupa njenih elemenata. Svaka od ove dve liste se zatim sortira. Koristeći standardni poređenje sortiranja algoritam za ovaj korak će biti potrebno vreme O(2^N/2N). Međutim, s obzirom sortirani spisak iznosa za k elemenata, spisak se može proširiti na dve sortirane liste sa uvođenjem (k + 1)st elementa, i ove dve sortirane liste mogu da budu spojene za vreme O(2^k). Prema tome, svaka lista može biti generisana u sortiranom obliku u vremenu O(2^N/2). Imajući u vidu dva sortirane liste, algoritam može da proveri da li se element prvog niza i element drugog niza dobija za s u vremenu O(2^N/2). Da biste to uradili, algoritam prolazi kroz prvi niz u opadajućem redosledu (počevši od najvećeg elementa) i drugi niz u rastućem redosledu (počevši od najmanjeg elementa). Kad god je suma trenutnog elementa u prvom nizu i trenutni element u drugom nizu više od s,algoritam prelazi na sledeći element u prvom nizu. Ako je to manje od s, algoritam prelazi na sledeći element u drugom nizu. Ako su dva elementa sa sumom s nađena, onda se zaustavlja. Horowitz and Sahni prvi put objavili ovaj algoritam u tehničkom izveštaju 1972.

Dinamičko programiranje

Problem se može rešiti na sledeći način korišćenjem dinamičkog programiranja. Pretpostavimo da je red

x₁, ..., x_N

i želimo da se utvrdi da li postoji neprazan podskup koji sumira na nulu. Neka A bude zbir negativnih vrednosti i B zbir pozitivnih vrednosti. Definišemo bulovsku funckiju Q(i,s) da ima vrednosti (tačno ili netačno)

"postoji neprazan podskup x₁, ..., x_i koji sumira do s".

Dakle, rešenje problema je vrednost Q(N,0).

Jasno, Q(i,s) = false ako s < A ilis > B tako da ove vrednosti ne moraju da se čuvaju ili izračunavaju. Kreiranje niza za održavanje vrednosti Q(i,s) za 1 ≤ i ≤ N iA ≤ s ≤ B.

Niz se sada može popuniti pomoću jednostavne rekurzije. U početku, zaA ≤ s ≤ B, postaviti

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

Zatim, za i = 2, …, N, postaviti

Q(i,s) := Q(i − 1,s) ili (x_i == s) ili Q(i − 1,s − x_i)   za A ≤ s ≤ B.

Za svaki zadatak, vrednosti Q na desnoj strani su već poznati, ili zato što su bili uskladišteni u tabeli za prethodnu vrednost i ili zbog Q(i − 1,s − x_i) = false ako s − x_i < A ili s − x_i > B. Dakle, ukupan broj aritmetičkih operacija je O(N(B − A)). Na primer, ako su sve vrednosti O(N^k) za neko k, onda je potrebno vreme O(N^k+2).

Ovaj algoritam se lako modifikuje da vrati podskup sume sa 0 ako postoji.

Ovo rešenje se ne računa kao polinomijalno vreme u teoriji složenosti, jer B − A nije polinomilno u veličini problema, što je broj bitova koji se koriste za reprezentaciju. Ovaj algoritam je polinom u vrednostima A i B, koji je eksponencijalanu u broju bitova.

Algoritam aproksimacije u polinomijalnom vremenu

Aproksimovana verzija zbira podskupa će biti: dat je skup od N brojeva x₁, x₂, ..., x_N i broj s, izlaz

• Da, ako postoji podskup koji sumira do s;
• No, ako ne postoji podskup koji sumira između (1 − c)s i s za veoma male c > 0;
• bilo kakav odgovor, ako postoji podskup koji sumira između (1 − c)s i s ali ne i podskup do s.

Ako su svi brojevi ne-negativni, približan zbir podskupa je rastvorljiv u vremenskom polinomu u N i 1/c.

Rešenje za zbir podskupa takođe pruža rešenje za problem prvobitnog zbira podskupa u slučaju gde su brojevi su mali (opet, za ne negativne brojeva).Ako neki zbir brojeva može se odrediti sa najviše P bitova, zatim rešavanje problema sa približno c = 2^−P je ekvivalentnoda se reši tačno. Zatim, polinomijalni algoritam za približni zbir podskupa postaje tačan algoritam sa polinomijalnim vremenom izvršavanja N' i 2P .

Algoritam za aproksimaciju problema zbira podskupa je sledeći:

 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

Algoritam je polinojalnog vremena zato šsto liste S, T i U uvek ostaju na veličini polinoma u N i 1/c i, dok su veličine od polinoma, sve operacije na njima mogu da se urade u polinomijalnom vremenu. Veličina lista čuva polinom po korak, u kojoj samo uključuje broj z u S ako je veći od prethodnog za cs/N a ne veći od s.

Ovaj korak obezbeđuje da svaki element u S je manji od sledećeg najmanje cs/N i ne sadrže elemente veće od s. Svaka lista sa tom osobinom se sastoji od više od N/c elemenata.

Algoritam je korektan jer svaki korak uvodi grešku za najviše cs/N i N koraka zajedno uvodeći grešku za najviše cs.

Vidi još

• 3SUM

Literatura

• Martello, Silvano; Toth, Paolo (1990). „4 Subset-sum problem”. Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. стр. 105-136. ISBN 978-0-471-92420-3. MR 1086874. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „35.5: The subset-sum problem”. Introduction to Algorithms (2nd изд.). MIT Press and 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 978-0-7167-1045-5.  A3.2: SP13, pg.223.