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

Reference

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.