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.[1] 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(2NN), jer postoje 2N 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(2N/2). Algoritam deli proizvoljno N elemente u dva seta N/2 svaki. Za svaki od ova dva skupa, čuva se spisak sume od svih 2N/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(2N/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(2k). Prema tome, svaka lista može biti generisana u sortiranom obliku u vremenu O(2N/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(2N/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.[2]

Dinamičko programiranje[уреди]

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

x1, ..., xN

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 x1, ..., xi 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 ≤ iN iAsB.

Niz se sada može popuniti pomoću jednostavne rekurzije. U početku, zaAsB, postaviti

Q(1,s) := (x1 == s).

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

Q(i,s) := Q(i − 1,s) ili (xi == s) ili Q(i − 1,sxi)   za AsB.

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,sxi) = false ako sxi < A ili sxi > B. Dakle, ukupan broj aritmetičkih operacija je O(N(BA)). Na primer, ako su sve vrednosti O(Nk) za neko k, onda je potrebno vreme O(Nk+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 BA 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 x1, x2, ..., xN 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 = 2P 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 < zs, 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š[уреди]



Reference[уреди]

  1. ^ 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. 
  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 


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.; Charles E. Leiserson, Ron Rivest L. , Clifford Stein (2001) [1990]. „35.5: The subset-sum problem“. Introduction to Algorithms (2nd ed.). 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.