Aproximační algoritmy

Aproximační algoritmy je druh algoritmů používaných při řešení optimalizačního problému, kdy nepožadujeme nutně optimální řešení, ale spokojíme se i s řešením, které je optimálnímu velmi blízké.

k-aproximační algoritmus

Definice

Říkáme, že algoritmus ${\displaystyle A}$ problému maximalizace kriteriální funkce ${\displaystyle F}$ je k-aproximační, jestliže pro číslo ${\displaystyle k\geq 1}$ takové, že pro všechny instance ${\displaystyle I}$ daného problému platí ${\displaystyle F^{A}(I)\geq {\frac {1}{k}}F^{opt}(I)}$ (analogicky se definuje pro algoritmy minimalizace kriteriální funkce).^[1]

Zjednodušeně řečeno: k-aproximační algoritmus optimalizačního problému nalezne vždy řešení, které je nejhůře k-krát horší než řešení optimální.

Příklady

Úrovňový algoritmus