Osajoukkosummaongelma on tärkeä ongelma algoritmien kompleksisuusteoriassa ja kryptografiassa . Ongelmana on löytää (ainakin yksi) ei-tyhjä osajoukko jostain lukujoukosta niin, että tämän osajoukon lukujen summa on nolla. Oletetaan esimerkiksi joukko {−7, −3, −2, 5, 8}, jolloin osajoukon {−3, −2, 5} summa on nolla. Ongelma on NP-täydellinen .
Ekvivalentti on ongelma löytää osajoukko, jonka elementtien summa on yhtä suuri kuin jokin annettu luku s . Osajoukkosummaongelmaa voidaan pitää myös repputehtävän erikoistapauksena [ 1] . Mielenkiintoinen tapaus osajoukon summausongelmasta on osiotehtävä , jossa s on yhtä suuri kuin puolet joukon kaikkien elementtien summasta.
Osajoukon summaongelman laskennallinen monimutkaisuus riippuu kahdesta parametrista - joukon alkioiden lukumäärästä N ja tarkkuudesta P (määritelty binäärinumeroiden lukumääränä joukon muodostavissa luvuissa). Huomaa: tässä kirjaimilla N ja P ei ole mitään tekemistä tehtäväluokan NP kanssa .
Tunnetuimman algoritmin monimutkaisuus on eksponentiaalinen kahdesta parametrista N ja P pienimmässä. Siten tehtävä on vaikein, kun N ja P ovat samaa luokkaa. Tehtävästä tulee helppo vain hyvin pienille N tai P .
Jos N (muuttujien määrä) on pieni, niin tyhjentävä haku on varsin hyväksyttävää. Jos P (asetettujen numeroiden numeroiden määrä) on pieni, voidaan käyttää dynaamista ohjelmointia .
Alla käsitellään tehokasta algoritmia, joka toimii, kun sekä N että P ovat pieniä.
On olemassa useita tapoja ratkaista ongelma ajassa, joka riippuu eksponentiaalisesti N :stä . Yksinkertaisin algoritmi käy läpi kaikki osajoukot ja tarkistaa jokaisen osajoukon osalta, onko osajoukon elementtien summa sopiva. Algoritmin ajoajaksi on arvioitu O (2 N N ), koska osajoukkoja on 2 N ja jokaisen osajoukon testaamiseksi pitää lisätä enintään N elementtiä.
Optimaalisemman algoritmin ajoaika on O (2 N /2 ). Tämä algoritmi jakaa koko N elementin joukon kahdeksi N /2 elementin osajoukoksi. Jokaiselle näistä osajoukoista muodostetaan joukko kaikkien 2 N /2 mahdollisen osajoukon summia. Molemmat listat on lajiteltu. Jos käytämme lajitteluun yksinkertaista vertailua, saadaan O (2 N /2 N ) aika. Voit kuitenkin käyttää yhdistämismenetelmää . Kun k elementille on summa , lisää ( k + 1):s elementti ja saat kaksi lajiteltua listaa ja yhdistä listat (ilman lisättyä elementtiä ja lisätyn elementin kanssa). Meillä on nyt lista ( k + 1) elementtien summista, ja sen luomiseen meni O (2 k ) aikaa. Jokainen lista voidaan siis luoda O (2 N /2 ) -ajassa. Kun on annettu kaksi lajiteltua listaa, algoritmi voi tarkistaa, voivatko ensimmäisen ja toisen listan elementtien summat antaa arvon s O ( 2 N /2 ) -ajassa. Tätä varten algoritmi käy läpi ensimmäisen luettelon laskevassa järjestyksessä (alkaen suurimmasta elementistä) ja toisen luettelon nousevassa järjestyksessä (alkaen pienimmästä elementistä). Jos nykyisten elementtien summa on suurempi kuin s , algoritmi siirtyy ensimmäisen listan seuraavaan elementtiin ja jos se on pienempi kuin s , toisen listan seuraavaan elementtiin. Jos summa on yhtä suuri kuin s , ratkaisu löytyy ja algoritmi pysähtyy. Horowitz ja Sartaj Sahni julkaisivat tämän algoritmin ensimmäisen kerran vuonna 1972 [2] .
Ongelma voidaan ratkaista käyttämällä dynaamista ohjelmointia . Olkoon numerosarja annettu
x 1 , …, x N ,ja on tarpeen selvittää, onko tässä sekvenssissä ei-tyhjä osajoukkoa, jossa elementtien summa on nolla. Olkoon A negatiivisten elementtien summa ja B positiivisten elementtien summa. Määritellään Boolen funktio Q ( i , s ), joka saa arvon Kyllä , jos elementtien x 1 , …, x i osajoukko on ei-tyhjä , jonka summa on s ja Ei muuten.
Tällöin tehtävän ratkaisu on Q :n arvo ( N , 0).
On selvää, että Q ( i , s ) = Ei , jos s < A tai s > B , joten näitä arvoja ei tarvitse laskea tai tallentaa. Luodaan taulukko, joka sisältää arvot Q ( i , s ) arvoille 1 ⩽ i ⩽ N ja A ⩽ s ⩽ B .
Taulukko voidaan täyttää yksinkertaisella rekursiolla. Aluksi asetetaan arvolle A ⩽ s ⩽ B
Q (1, s ) := ( x1 == s ) .Nyt i = 2, …, N , asetamme
Q ( i , s ) := Q ( i − 1, s ) tai ( x i == s ) tai Q ( i − 1, s − x i ) kun A ⩽ s ⩽ B .Jokaiselle tehtävälle oikealla puolella oleva Q :n arvo on jo tiedossa, koska joko se on syötetty i :n aikaisempien arvojen taulukkoon tai Q ( i − 1, s − x i ) = Ei s − x :lle i < A tai s − x i > B . Näin ollen aritmeettisten operaatioiden kokonaisaika on O ( N ( B − A )). Esimerkiksi, jos kaikki arvot ovat luokkaa O ( N k ) jollekin k :lle , tarvitaan O ( N k +2 ) aika.
Algoritmia on helppo muokata nollasumman löytämiseksi, jos sellainen on.
Algoritmia ei pidetä polynomina, koska B − A ei ole polynomi tehtävän koossa , joka on lukujen bittien lukumäärä. Algoritmi on polynominen A:n ja B :n arvoissa , ja ne riippuvat eksponentiaalisesti bittien määrästä.
Tapaukselle, jossa kaikki x i ovat positiivisia ja niitä rajoittaa vakio C , Pisinger löysi lineaarisen algoritmin, jonka monimutkaisuus on O ( NC ) [3] (tässä tapauksessa ongelman on löydettävä nollasta poikkeava summa, muuten ongelmasta tulee triviaali).
On olemassa versio likimääräisestä algoritmista, joka antaa seuraavan tuloksen annetulle N elementin joukolle x 1 , x 2 , ..., x N ja luvulle s :
Jos kaikki alkiot ovat ei-negatiivisia, algoritmi antaa ratkaisun polynomiajassa N ja 1/ c .
Algoritmi tarjoaa ratkaisun alkuperäiseen ongelmaan löytää osajoukkojen summa, jos luvut ovat pieniä (ja jälleen ei-negatiivisia). Jos missä tahansa lukujen summassa on enintään P bittiä, niin tehtävän ratkaiseminen c = 2 − P vastaa tarkan ratkaisun löytämistä. Siten polynomin approksimaatioalgoritmista tulee tarkka, kun ajoaika riippuu polynomiaalisesti N :stä ja 2P :stä (eli eksponentiaalisesti P :stä ).
Joukkojen summan ongelman likimääräisen ratkaisun algoritmi toimii seuraavasti:
Luomme listan S , joka koostuu aluksi yhdestä elementistä 0.Suorita seuraavat toimenpiteet kaikille i :lle 1:stä N: ään Luo lista T , joka koostuu x i + y :stä kaikille y : lle S :stä Luo lista U , joka on yhtä suuri kuin T :n ja S :n liitto Lajittele U Tyhjä S Olkoon y U :n pienin elementti. Lisää y kohtaan S Kaikille elementeille z alkaen U , toistetaan niitä nousevassa järjestyksessä , tehdään Jos y + cs / N < z ≤ s , laita y = z ja laita z listaan S (täten suljemme pois läheiset arvot ja hylkäämme arvot, jotka ovat suuremmat kuin s ) Jos S sisältää luvun välillä (1 − c ) s ja s , sanomme Kyllä , muuten - EiAlgoritmilla on polynominen ajoaika, koska listojen S , T ja U koko on aina polynomiriippuvainen N :stä ja 1/ c :stä ja siksi kaikki niille tehtävät toiminnot suoritetaan polynomiajassa. Listojen koon pitäminen polynomina on mahdollista läheisten arvojen eliminointivaiheella, jossa elementti z lisätään listaan S vain, jos se on suurempi kuin edellinen arvolla cs / N ja enintään s , mikä varmistaa, että luettelossa ei ole enempää kuin N / c elementtejä.
Algoritmi on oikea, koska jokainen vaihe antaa enintään cs / N :n kokonaisvirheen ja N askelta yhdessä antaa virheen, joka ei ylitä cs .