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 A problému maximalizace kriteriální funkce F je k-aproximační, jestliže pro číslo k\geq1 takové, že pro všechny instance I daného problému platí F^A(I)\geq\frac{1}{k}F^{opt}(I) (analogicky se definuje pro algoritmy minimalizace kriteriální funkce).

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

[url=http://www.algoritmy.net/article/37826/Urovnovy-algoritmus]Úrovňový algoritmus[/url]

Reference

Kategorie:Algoritmy