ARTP - 03 - Problém batohu. Polynomiálne aproximačné schémy.

Zhrnutie prednášky

Prednáška po rekapitulácii dovtedy preberaných aproximačných algoritmov (obchodný cestujúci, vrcholové pokrytie, pokrývanie množinami s faktorom O(log n)) zavádza polynomiálne aproximačné schémy. Ide o triedu algoritmov, ktoré dostanú okrem vstupu aj parameter epsilon a vedia sa priblížiť optimu ľubovoľne blízko, no nie na faktor 1; zlepšenie presnosti sa platí časom rastúcim s 1/epsilon, pričom závislosť od veľkosti vstupu zostáva polynomiálna. Ako príklad slúži problém batohu s celočíselnými váhami a cenami, ktorý sa rieši dynamickým programovaním s podproblémom K(i, b) a rekurenciou maxima z variantov zobrať alebo nezobrať i-ty predmet. Zložitosť O(n·B) vedie k diskusii, že nejde o polynomiálny algoritmus vzhľadom na dĺžku zápisu čísla B, keďže tá je približne log B.

• - Polynomiálna aproximačná schéma berie na vstupe aj epsilon a dosiahne faktor 1+epsilon, nikdy však presne 1.
• - Za lepšiu aproximáciu sa platí časom, ktorý rastie s 1/epsilon, ale zostáva polynomiálny vo veľkosti vstupu.
• - Problém batohu: n predmetov s celočíselnou váhou a cenou, maximalizuje sa cena pri súčte váh najviac B.
• - Dynamické programovanie: K(i, b) = max(K(i-1, b), K(i-1, b-w_i) + c_i), základný prípad s 0 predmetmi dáva cenu 0.
• - Časová zložitosť riešenia je O(n·B), resp. s aritmetikou veľkých čísel O(n·B·log B).
• - Algoritmus je pseudopolynomiálny, lebo B je exponenciálne voči dĺžke svojho zápisu (log B), takže NP-ťažkosť problému tým nie je vyvrátená.
• - Konštantný čas aritmetických operácií s ľubovoľne veľkými číslami by narušil teóriu zložitosti, preto sa niekedy treba pozerať na bitovú dĺžku čísel.

Zhrnutie pripravené s pomocou AI z prepisu videa.