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 editovat

Definice editovat

Říkáme, že algoritmus $A$ problému maximalizace kriteriální funkce $F$ je k-aproximační, jestliže pro číslo $k\geq 1$ 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).^[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 editovat

Úrovňový algoritmus

Reference editovat

↑ HANZÁLEK, Zdeněk. Kombinatorická optimalizace.

Pahýl

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.

[KO-1] HANZÁLEK, Zdeněk. Kombinatorická optimalizace.

[1]