A részhalmazösszeg probléma fontos probléma az algoritmusok komplexitáselméletében és a kriptográfiában . A probléma az, hogy meg kell találni (legalább egy) nem üres részhalmazt néhány számhalmaznak úgy, hogy ebben a részhalmazban a számok összege nulla legyen. Például legyen adott a {−7, −3, −2, 5, 8} halmaz, akkor a {−3, −2, 5} részhalmaz összege nulla. A probléma NP-teljes .
Az ekvivalens egy olyan részhalmaz megtalálásának problémája, amelynek elemeinek összege egy adott s számmal egyenlő . A részhalmazösszeg-probléma a hátizsák-probléma néhány speciális esetének is tekinthető [1] . A részhalmaz-összegzési probléma érdekes esete a partíciós probléma , amelyben s egyenlő a halmaz összes eleme összegének felével.
A részhalmazösszeg probléma számítási bonyolultsága két paramétertől függ - a halmaz elemeinek N számától és a P pontosságtól (amely a halmazt alkotó számok bináris számjegyeinek számaként definiálható). Megjegyzés: itt az N és P betűknek semmi közük az NP feladatosztályhoz .
A legismertebb algoritmus összetettsége a két N és P paraméter közül a legkisebbnél exponenciális . Így a feladat akkor a legnehezebb, ha N és P azonos sorrendű. A feladat csak nagyon kis N vagy P esetén válik könnyűvé .
Ha N (a változók száma) kicsi, akkor a kimerítő keresés teljesen elfogadható. Ha P (a számjegyek száma a beállított számokban) kicsi, akkor dinamikus programozás használható .
Az alábbiakban egy hatékony algoritmust tárgyalunk , amely akkor működik, ha N és P is kicsi.
A probléma időben történő megoldásának többféle módja van, amely exponenciálisan függ N -től . A legegyszerűbb algoritmus az összes részhalmazt végignézi, és mindegyiknél ellenőrzi, hogy a részhalmaz elemeinek összege megfelelő-e. Az algoritmus futási ideje a becslések szerint O (2 N N ), mivel 2 N részhalmaz van, és az egyes részhalmazok teszteléséhez legfeljebb N elemet kell hozzáadni.
Egy optimálisabb algoritmus futásideje O (2 N /2 ). Ez az algoritmus a teljes N elemből álló halmazt két N /2 elemből álló részhalmazra osztja. Ezen részhalmazok mindegyikéhez létrejön az összes 2 N /2 lehetséges részhalmaz összegeinek halmaza. Mindkét lista rendezve van. Ha egyszerű összehasonlítást használunk a rendezéshez, akkor O (2 N /2 N ) időt kapunk. Alkalmazhatja azonban az egyesítési módszert is . Ha k elemre van egy összeg , adjuk hozzá a ( k + 1)-edik elemet, és kapjunk két rendezett listát, majd egyesítsük a listákat (a hozzáadott elem nélkül és a hozzáadott elemmel). Most van egy listánk a ( k + 1) elemek összegeiről, és O (2 k ) időbe telt a létrehozása. Tehát minden lista O (2 N /2 ) idő alatt elkészíthető. Két rendezett lista esetén az algoritmus ellenőrizni tudja, hogy az első és a második lista elemeinek összege adja-e az s értéket O (2 N /2 ) időben. Ehhez az algoritmus csökkenő sorrendben megy végig az első listán (a legnagyobb elemtől kezdve), a másodikon pedig növekvő sorrendben (a legkisebb elemtől kezdve). Ha az aktuális elemek összege nagyobb, mint s , akkor az algoritmus az első lista következő elemére lép, ha pedig kisebb, mint s , akkor a második lista következő elemére. Ha az összeg egyenlő s -vel , akkor a megoldás megtalálható és az algoritmus leáll. Horowitz és Sartaj Sahni először 1972-ben publikálta ezt az algoritmust [2] .
A probléma dinamikus programozással megoldható . Legyen adott egy számsorozat
x 1 , …, x N ,és meg kell találni, hogy van-e ennek a sorozatnak egy nem üres részhalmaza nulla elemösszeggel. Legyen A a negatív elemek összege, B pedig a pozitív elemek összege. Definiáljunk egy Q ( i , s ) logikai függvényt, amely akkor veszi fel az Igen értéket , ha van egy nem üres részhalmaza az x 1 , …, x i elemeknek, amelyek összege s , egyébként pedig a No.
Ekkor a feladat megoldása Q ( N , 0) értéke lesz.
Nyilvánvaló, hogy Q ( i , s ) = Nem , ha s < A vagy s > B , tehát ezeket az értékeket nem kell kiszámítani vagy tárolni. Hozzunk létre egy tömböt, amely tartalmazza a Q ( i , s ) értékeket 1 ⩽ i ⩽ N és A ⩽ s ⩽ B esetén .
Egy tömb egyszerű rekurzióval tölthető fel. Kezdetben A ⩽ s ⩽ B esetén beállítjuk
Q (1, s ) := ( x 1 == s ).Most i = 2, …, N esetén beállítjuk
Q ( i , s ) := Q ( i − 1, s ) vagy ( x i == s ) vagy Q ( i − 1, s − x i ) A ⩽ s ⩽ B esetén .Minden hozzárendelésnél a jobb oldali Q értéke már ismert, mert vagy be van írva az i korábbi értékeinek táblázatába , vagy Q ( i − 1, s − x i ) = Nem s − x esetén i < A vagy s − x i > B . Így az aritmetikai műveletek teljes ideje O ( N ( B − A )). Például, ha minden érték O ( N k ) nagyságrendű valamilyen k esetén, akkor O ( N k +2 ) időre van szükség.
Az algoritmus könnyen módosítható, hogy megtalálja a nulla összeget, ha van ilyen.
Az algoritmust nem tekintjük polinomiálisnak, mert B − A nem polinomiális a feladat méretében , ami a számok bitjeinek száma. Az algoritmus A és B értékeiben polinomiális , és exponenciálisan függenek a bitek számától.
Abban az esetben, ha minden x i pozitív és a C konstans határolja , Pisinger talált egy O ( NC ) bonyolultságú lineáris algoritmust [3] (ebben az esetben a feladatnak nem nulla összeget kell találnia, különben a probléma jelentéktelen).
Létezik egy közelítő algoritmus egy olyan változata, amely a következő eredményt adja egy adott N elemből álló x 1 , x 2 , ..., x N halmazra és az s számra :
Ha minden elem nem negatív, akkor az algoritmus polinomiális időben ad megoldást N és 1/ c értékben .
Az algoritmus megoldást ad arra az eredeti problémára, hogy megtaláljuk a részhalmazok összegét, ha a számok kicsik (és ismételten nem negatívak). Ha a számok bármely összege legfeljebb P bites, akkor a feladat megoldása c = 2 − P -vel egyenértékű a pontos megoldás megtalálásával. Így a polinomiális közelítési algoritmus pontossá válik, ha a futásidő polinomiálisan függ N -től és 2 P -től (vagyis exponenciálisan P -től ).
A halmazok összegének problémájának közelítő megoldására szolgáló algoritmus a következőképpen működik:
Létrehozunk egy S listát , amely kezdetben egy 0 elemből áll. Minden i -re 1-től N-ig hajtsa végre a következő műveleteket Hozzon létre egy T listát , amely x i + y -ból áll minden y -re S -ből Hozzon létre egy U listát, amely megegyezik T és S unióval. Rendezés U Üres S Legyen y U legkisebb eleme Szúrjon be y -t S -be Minden z elemhez U - ból , megismételjük őket növekvő sorrendben, tegyük Ha y + cs / N < z ≤ s , tegye y = z -t , és tegye z -t az S listába (így a közeli értékeket kizárjuk és az s -nél nagyobb értékeket eldobjuk ) Ha S egy (1 − c ) s és s közötti számot tartalmaz , akkor igent mondunk , ellenkező esetben - NemAz algoritmusnak polinomiális futásideje van, mivel az S , T és U listák mérete mindig polinomiálisan függ N -től és 1/ c -től, ezért az összes műveletet polinomiális időben hajtjuk végre. A listák méretének polinomban tartása a közeli értékek kiküszöbölésének lépésével lehetséges, amelynél a z elem csak akkor kerül az S listába , ha cs / N -el nagyobb az előzőnél és legfeljebb s , ami biztosítja, hogy legfeljebb N / c elem szerepel a listán.
Az algoritmus helyes, mivel minden lépés összesen legfeljebb cs / N hibát ad, és N lépés együtt olyan hibát ad, amely nem haladja meg a cs -t .