subset sum problem

Angol

subset sum problem (tsz. subset sum problems)

(informatika) A Részhalmaz‐összeg (Subset Sum) probléma a kombinatorikus optimalizálás és az elméleti számítástudomány egyik alapfeladata. Lényege: adott egy egész számokból álló halmaz és egy célösszeg, van-e olyan részhalmaz, amelynek az elemei pontosan a célösszeget adják?

Döntési verzió
- Bemenet: Egy véges, nemnegatív egész számokból álló halmaz ${\textstyle \,S=\{x_{1},x_{2},\dots ,x_{n}\}}$ és egy célösszeg ${\textstyle T}$ .
- Kérdés: Létezik-e olyan ${\textstyle S'\subseteq S}$ , hogy
  
  $\sum _{x\in S'}x\;=\;T\;?$
Optimalizációs verzió
- Cél: Olyan ${\textstyle S'\subseteq S}$ megtalálása, melynek elemei összege a lehető legnagyobb, de nem haladja meg ${\textstyle T}$ -t:
  
  $\max _{S'\subseteq S}\;\sum _{x\in S'}x\quad {\text{úgy, hogy}}\quad \sum _{x\in S'}x\leq T.$

A döntési verzió NP‐teljes (az eredeti Karp-listán szerepel).
NP‐teljesség azt jelenti, hogy ha valaki ad egy jelölt részhalmazt, polinomiális idő alatt ellenőrizhető, hogy valóban összegezi-e ${\textstyle T}$ -t, ám nincs ismert polinomiális algoritmus az összes eset megoldására (és ezt valószínűleg nem is létezik, hacsak ${\textstyle P\neq NP}$ ).

Bár NP‐nehéz, létezik egy pseudopolinomiális (a célösszegtől is függő) dinamikus programozás-eljárás, ami sok gyakorlati esetben hatékony:

DP‐tábla definiálása Legyen dp igaz, ha az első i elemből van olyan részhalmaz, amely pontosan s-t ad.
Inicializálás
- dp = igaz (0 elem összege 0).
- dp = hamis.
Rekurzió Minden ${\textstyle i=1,\dots ,n}$ és minden ${\textstyle s=0,\dots ,T}$ esetén:
```
dp = dp
         OR (s >= x_i ÉS dp)
```
Azaz vagy kihagyjuk ${\textstyle x_{i}}$ -t, vagy – ha belefér – beleszámítjuk.
Eredmény
- Döntési verzió: dp
- Optimalizációs verzió: keressük a legnagyobb ${\textstyle s\leq T}$ -t, ahol dp = igaz.
Futásidő és memória ${\textstyle O(nT)}$ idő, ${\textstyle O(T)}$ hely (ha a dp tömböt csak egy dimenzióban görgetjük).

Ha az elemek száma ${\textstyle n}$ közepes ( ${\textstyle n\approx 40}$ ) de az értékek nagyok, egy ${\textstyle O(2^{n/2})}$ idejű algoritmus:

Felosztás: bontsuk a halmazt két, kb. ${\textstyle n/2}$ -es részre.
Első félegyüttes: számoljuk ki mindkét rész összes lehetséges részhalmaz-összegét ( ${\textstyle 2^{n/2}}$ összeget), és rendezzük a listát.
Második félegyüttes: minden részhalmaz-összeg ${\textstyle s_{2}}$ esetén keressük bináris kereséssel az első lista legnagyobb ${\textstyle s_{1}}$ -jét, hogy ${\textstyle s_{1}+s_{2}\leq T}$ .
Kombinálás: így megtaláljuk a legjobb megoldást sokkal kevesebb, mint ${\textstyle 2^{n}}$ próbálkozással.

Mivel NP‐nehéz, gyakran alkalmaznak közelítő vagy heurisztikus eljárásokat:

FPTAS (Full Polynomial-Time Approximation Scheme) A feladatot ${\textstyle \varepsilon }$ -pontossággal, ${\textstyle O(n\,\mathrm {poly} (1/\varepsilon ))}$ időben közelíti: a célösszeget kicsit lekerekítjük, így gyorsabb a DP.
Mohó módszerek Csökkenő sorrendben felveszünk elemeket, amíg lehet – gyors, de nem garantál optimálisat.
Meta-heurisztikák Simulated annealing, genetikus algoritmusok, tabu search stb., tetszőleges nagy példányokon is gyakorlati megoldást adnak.

Kriptográfia: korai nyilvános kulcsú rendszerek (Merkle–Hellman-type) alapjául szolgált.
Erőforrás-elosztás: feladatok ütemezése idő- vagy költségkeretben.
Terheléskiegyenlítés: munkák súlyainak felosztása két vagy több csoport között (specializált eset, ha a cél a teljes súly fele).
Pénzügy: portfólió összeállítása, hogy egy előre meghatározott értéket közelítsünk.

A Részhalmaz-összeg probléma könnyen érthető, de NP‐teljes.
Pseudopolinomiális DP hatékony, ha a célösszeg ${\textstyle T}$ mérsékelt.
Meet-in-the-Middle jól skálázódik közepes ${\textstyle n}$ -re, nagy értékeknél.
FPTAS és heurisztikák adnak gyakorlati, közel optimális megoldásokat nagy instanciákra.
A probléma széles körben alkalmazható a számítástudománytól a gyakorlati területekig.

A Részhalmaz‐összeg probléma és megoldásai alapot nyújtanak a bonyolultabb zsák- (knapsack-) és kombinatorikus optimalizálási feladatok megértéséhez.