Aproximační algoritmy

(přesměrováno z Aproximační algoritmus)

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í algoritmusEditovat

DefiniceEditovat

Říkáme, že algoritmus   problému maximalizace kriteriální funkce   je k-aproximační, jestliže pro číslo   takové, že pro všechny instance   daného problému platí   (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říkladyEditovat

Úrovňový algoritmus

LiteraturaEditovat

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