Problema sumei submulțimii este o problemă importantă în teoria complexității algoritmilor și criptografie . Problema este de a găsi (cel puțin un) submulțime nevidă a unui set de numere, astfel încât suma numerelor din această submulțime să fie egală cu zero. De exemplu, să fie dată mulțimea {−7, −3, −2, 5, 8}, apoi submulțimea {−3, −2, 5} se însumează până la zero. Problema este NP-complet .
Echivalent este problema găsirii unei submulțimi a cărei sumă de elemente este egală cu un număr dat s . Problema sumei submulțimii poate fi considerată și ca un caz special al problemei rucsacului [1] . Un caz interesant al problemei de însumare a submulților este problema partiției , în care s este egal cu jumătate din suma tuturor elementelor mulțimii.
Complexitatea de calcul a problemei sumei submulțimii depinde de doi parametri - numărul N de elemente ale mulțimii și precizia P (definită ca numărul de cifre binare din numerele care alcătuiesc mulțimea). Notă: aici literele N și P nu au nimic de-a face cu clasa de probleme NP .
Complexitatea celui mai cunoscut algoritm este exponențială în cel mai mic dintre cei doi parametri N și P. Astfel, sarcina este cea mai dificilă atunci când N și P sunt de același ordin. Sarcina devine ușoară numai pentru N sau P foarte mici .
Dacă N (numărul de variabile) este mic, atunci căutarea exhaustivă este destul de acceptabilă. Dacă P (numărul de cifre din numerele setate) este mic, se poate folosi programarea dinamică .
Un algoritm eficient care funcționează atunci când atât N cât și P sunt mici este discutat mai jos.
Există mai multe moduri de a rezolva problema în timp care depinde exponențial de N . Cel mai simplu algoritm analizează toate submulțimile și pentru fiecare dintre ele verifică dacă suma elementelor submulțimii este adecvată. Timpul de rulare al algoritmului este estimat a fi O (2 N N ), deoarece sunt 2 N submulțimi, iar pentru a testa fiecare submulțime trebuie adăugate cel mult N elemente.
Un algoritm mai optim are un timp de rulare de O (2 N /2 ). Acest algoritm împarte întregul set de N elemente în două subseturi de N /2 elemente fiecare. Pentru fiecare dintre aceste submulțimi, se construiește un set de sume ale tuturor celor 2 N /2 submulțimi posibile. Ambele liste sunt sortate. Dacă folosim o comparație simplă pentru sortare, obținem timp O (2 N /2 N ). Cu toate acestea, puteți aplica metoda de îmbinare . Având o sumă pentru k elemente, adăugați elementul ( k + 1) și obțineți două liste sortate, apoi îmbinați listele (fără elementul adăugat și cu elementul adăugat). Avem acum o listă de sume pentru ( k + 1) elemente și a fost nevoie de O (2 k ) timp pentru ao crea. Deci fiecare listă poate fi creată în timp O (2 N /2 ). Având în vedere două liste sortate, algoritmul poate verifica dacă sumele elementelor din prima și a doua listă pot da valoarea s în timp O (2 N /2 ). Pentru a face acest lucru, algoritmul parcurge prima listă în ordine descrescătoare (începând cu cel mai mare element) și a doua listă în ordine crescătoare (începând cu cel mai mic element). Dacă suma elementelor curente este mai mare decât s , algoritmul trece la următorul element din prima listă, iar dacă este mai mică decât s , la următorul element din a doua listă. Dacă suma este egală cu s , se găsește soluția și algoritmul se oprește. Horowitz și Sartaj Sahni au publicat pentru prima dată acest algoritm în 1972 [2] .
Problema poate fi rezolvată folosind programarea dinamică . Să fie dată o succesiune de numere
x 1 , …, x N ,și este necesar să aflăm dacă există o submulțime nevidă a acestei secvențe cu sumă zero de elemente. Fie A suma elementelor negative și B suma celor pozitive. Să definim o funcție booleană Q ( i , s ) care ia valoarea Da dacă există o submulțime nevidă de elemente x 1 , …, x i care se adună la s , iar Nu în caz contrar.
Atunci soluția problemei va fi valoarea lui Q ( N , 0).
Este clar că Q ( i , s ) = Nu dacă s < A sau s > B , deci aceste valori nu trebuie să fie calculate sau stocate. Să creăm o matrice care să conțină valorile Q ( i , s ) pentru 1 ⩽ i ⩽ N și A ⩽ s ⩽ B .
O matrice poate fi populată cu recursivitate simplă. Inițial, pentru A ⩽ s ⩽ B , setăm
Q (1, s ) := ( x 1 == s ).Acum, pentru i = 2, …, N , setăm
Q ( i , s ) := Q ( i − 1, s ) sau ( x i == s ) sau Q ( i − 1, s − x i ) pentru A ⩽ s ⩽ B .Pentru fiecare atribuire, valoarea lui Q din partea dreaptă este deja cunoscută, deoarece fie este introdusă în tabelul cu valorile anterioare ale lui i , fie Q ( i − 1, s − x i ) = Nu pentru s − x i < A sau s − x i > B . Astfel, timpul total al operațiilor aritmetice este O ( N ( B − A )). De exemplu, dacă toate valorile sunt de ordinul O ( N k ) pentru unele k , atunci este nevoie de timp O ( N k +2 ).
Algoritmul este ușor de modificat pentru a găsi suma zero, dacă există.
Algoritmul nu este considerat polinom deoarece B − A nu este polinom în dimensiunea problemei, care este numărul de biți din numere. Algoritmul este polinom în valorile lui A și B și depind exponențial de numărul de biți.
Pentru cazul în care toate x i sunt pozitive și mărginite de constanta C , Pisinger a găsit un algoritm liniar cu complexitatea O ( NC ) [3] (în acest caz, problema trebuie să găsească o sumă diferită de zero, altfel problema devine banal).
Există o versiune a unui algoritm aproximativ care dă următorul rezultat pentru un set dat de N elemente x 1 , x 2 , ..., x N și numărul s :
Dacă toate elementele sunt nenegative, algoritmul oferă o soluție în timp polinomial în N și 1/ c .
Algoritmul oferă o soluție la problema inițială de a găsi suma submulților dacă numerele sunt mici (și, din nou, nenegative). Dacă orice sumă de numere are cel mult P biți, atunci rezolvarea problemei cu c = 2 − P este echivalentă cu găsirea soluției exacte. Astfel, algoritmul de aproximare polinomială devine exact cu timpul de rulare depinzând polinomial de N și 2 P (adică exponențial de P ).
Algoritmul pentru rezolvarea aproximativă a problemei sumei mulțimilor funcționează după cum urmează:
Creăm o listă S , formată inițial dintr-un element 0. Pentru toate i de la 1 la N, efectuați următoarele acțiuni Creați o listă T constând din x i + y pentru tot y din S Creați o listă U egală cu uniunea dintre T și S Sortați U Gol S Fie y cel mai mic element al lui U Introduceți y în S Pentru toate elementele z din U , repetarea peste ele în ordine crescătoare, să facem Dacă y + cs / N < z ≤ s , puneți y = z și puneți z în lista S (astfel excludem valorile apropiate și aruncăm valorile mai mari decât s ) Dacă S conține un număr între (1 - c ) s și s , spunem Da , în caz contrar - NuAlgoritmul are un timp de rulare polinomial, deoarece dimensiunea listelor S , T și U este întotdeauna dependentă polinomial de N și 1/ c și, prin urmare, toate operațiile asupra acestora vor fi efectuate în timp polinomial. Păstrarea mărimii polinomului listelor este posibilă cu pasul eliminării valorilor apropiate, la care elementul z se adaugă la lista S numai dacă este mai mare decât precedentul cu cs / N și nu mai mult de s , ceea ce asigură că nu mai mult de N / c elemente sunt incluse în listă.
Algoritmul este corect, deoarece fiecare pas dă o eroare totală de cel mult cs / N și N pași împreună vor da o eroare care nu depășește cs .