Problém podmnožiny součtu je důležitý problém v teorii složitosti algoritmu a kryptografii . Problém je najít (alespoň jednu) neprázdnou podmnožinu nějaké množiny čísel tak, aby součet čísel v této podmnožině byl roven nule. Nechť je například dána množina {−7, −3, −2, 5, 8}, pak podmnožina {−3, −2, 5} sečte do nuly. Problém je NP-úplný .
Ekvivalentní je problém najít podmnožinu, jejíž součet prvků je roven nějakému danému číslu s . Problém součtu podmnožiny lze také považovat za nějaký speciální případ problému s batohem [1] . Zajímavým případem problému sčítání podmnožin je problém s oddíly , ve kterém se s rovná polovině součtu všech prvků množiny.
Výpočetní složitost úlohy součtu podmnožin závisí na dvou parametrech – počtu N prvků množiny a přesnosti P (definované jako počet binárních číslic v číslech tvořících množinu). Poznámka: zde písmena N a P nemají nic společného s třídou problémů NP .
Složitost nejznámějšího algoritmu je exponenciální v nejmenším ze dvou parametrů N a P. Úloha je tedy nejobtížnější, když N a P jsou stejného řádu. Úkol se stává snadným pouze pro velmi malé N nebo P .
Pokud je N (počet proměnných) malý, pak je vyčerpávající hledání docela přijatelné. Pokud je P (počet číslic v nastavených číslech) malý, lze použít dynamické programování .
Účinný algoritmus, který funguje, když jsou N i P malé, je diskutován níže.
Existuje několik způsobů, jak vyřešit problém v čase, který exponenciálně závisí na N . Nejjednodušší algoritmus prochází všechny podmnožiny a pro každou z nich kontroluje, zda je součet prvků podmnožiny vhodný. Doba běhu algoritmu se odhaduje na O (2 N N ), protože existuje 2 N podmnožin, a pro testování každé podmnožiny je třeba přidat nejvýše N prvků.
Optimálnější algoritmus má dobu běhu O (2 N /2 ). Tento algoritmus rozděluje celou množinu N prvků na dvě podmnožiny po N /2 prvků. Pro každou z těchto podmnožin je konstruována množina součtů všech 2 N /2 možných podmnožin. Oba seznamy jsou seřazeny. Pokud použijeme pro třídění jednoduché srovnání, dostaneme O (2 N /2 N ) čas. Můžete však použít metodu sloučení . Máte-li součet pro k prvků, přidejte ( k + 1)-tý prvek a získáte dva seřazené seznamy, poté seznamy sloučte (bez přidaného prvku as přidaným prvkem). Nyní máme seznam součtů pro ( k + 1) prvků a jeho vytvoření trvalo O (2 k ). Každý seznam lze tedy vytvořit v čase O (2 N /2 ). Jsou-li dány dva seřazené seznamy, může algoritmus zkontrolovat, zda součty prvků z prvního a druhého seznamu mohou dát hodnotu s v čase O (2 N /2 ). Za tímto účelem algoritmus prochází první seznam v sestupném pořadí (začíná největším prvkem) a druhý seznam ve vzestupném pořadí (začíná nejmenším prvkem). Pokud je součet aktuálních prvků větší než s , algoritmus se přesune na další prvek v prvním seznamu, a pokud je menší než s , na další prvek ve druhém seznamu. Je-li součet roven s , je řešení nalezeno a algoritmus se zastaví. Horowitz a Sartaj Sahni poprvé publikovali tento algoritmus v roce 1972 [2] .
Problém lze vyřešit pomocí dynamického programování . Nechť je dána posloupnost čísel
x 1 , …, x N ,a je nutné zjistit, zda existuje neprázdná podmnožina této posloupnosti s nulovým součtem prvků. Nechť A je součet negativních prvků a B součet pozitivních prvků. Definujme booleovskou funkci Q ( i , s ), která nabývá hodnoty Ano , pokud existuje neprázdná podmnožina prvků x 1 , …, x i , která dává součet s a jinak Ne .
Pak řešením úlohy bude hodnota Q ( N , 0).
Je jasné, že Q ( i , s ) = Ne , pokud s < A nebo s > B , takže tyto hodnoty není třeba počítat ani ukládat. Vytvořme pole obsahující hodnoty Q ( i , s ) pro 1 ⩽ i ⩽ N a A ⩽ s ⩽ B .
Pole lze naplnit jednoduchou rekurzí. Nejprve pro A ⩽ s ⩽ B nastavíme
Q (1, s ) := ( x 1 == s ).Nyní pro i = 2, …, N , nastavíme
Q ( i , s ) := Q ( i − 1, s ) nebo ( x i == s ) nebo Q ( i − 1, s − x i ) pro A ⩽ s ⩽ B .U každého přiřazení je již známa hodnota Q na pravé straně, protože buď je zapsána v tabulce předchozích hodnot i , nebo Q ( i − 1, s − x i ) = Ne pro s − x i < A nebo s − x i > B . Celková doba aritmetických operací je tedy O ( N ( B − A )). Například, pokud jsou všechny hodnoty řádu O ( N k ) pro některé k , pak je potřeba čas O ( N k +2 ).
Algoritmus lze snadno upravit tak, aby našel nulový součet, pokud existuje.
Algoritmus není považován za polynomiální, protože B − A není polynomiální ve velikosti problému, což je počet bitů v číslech. Algoritmus je polynomiální v hodnotách A a B a závisí exponenciálně na počtu bitů.
Pro případ, kdy jsou všechna x i kladná a ohraničená konstantou C , Pisinger našel lineární algoritmus se složitostí O ( NC ) [3] (v tomto případě je potřeba najít nenulový součet, jinak se problém stane triviální).
Existuje verze přibližného algoritmu, který dává následující výsledek pro danou množinu N prvků x 1 , x 2 , ..., x N a čísla s :
Pokud jsou všechny prvky nezáporné, algoritmus dává řešení v polynomiálním čase v N a 1/ c .
Algoritmus poskytuje řešení původního problému nalezení součtu podmnožin, pokud jsou čísla malá (a opět nezáporná). Pokud má libovolný součet čísel nejvýše P bitů, pak řešení problému s c = 2 − P je ekvivalentní nalezení přesného řešení. Algoritmus polynomiální aproximace se tak stane přesným s dobou běhu závislou polynomiálně na N a 2 P (tj. exponenciálně na P ).
Algoritmus pro přibližné řešení úlohy součtu množin funguje následovně:
Vytvoříme seznam S , zpočátku sestávající z jednoho prvku 0. Pro všechna i od 1 do N proveďte následující akce Vytvořte seznam T sestávající z x i + y pro všechna y z S Vytvořte seznam U rovný sjednocení T a S Seřadit U Prázdné S Nechť y je nejmenší prvek z U Vložte y do S Pro všechny prvky z z U , iterujeme je ve vzestupném pořadí, udělejme to Pokud y + cs / N < z ≤ s , vložte y = z a vložte z do seznamu S (takže vyloučíme blízké hodnoty a zahodíme hodnoty větší než s ) Pokud S obsahuje číslo mezi (1 − c ) sa s , říkáme Ano , v opačném případě - NeAlgoritmus má polynomiální běh, protože velikost seznamů S , T a U je vždy polynomiálně závislá na N a 1/ c , a proto budou všechny operace s nimi prováděny v polynomiálním čase. Zachování velikosti polynomu seznamů je možné s krokem eliminace blízkých hodnot, při kterém je prvek z přidán do seznamu S pouze v případě, že je větší než předchozí o cs / N a ne více než s , což zajišťuje, že v seznamu není zahrnuto více než N / c prvků.
Algoritmus je správný, protože každý krok dává celkovou chybu maximálně cs / N a N kroků dohromady dá chybu, která nepřesahuje cs .