Aproximační algoritmy

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 | editovat zdroj]

Definice[editovat | editovat zdroj]

Ří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říklady[editovat | editovat zdroj]

Úrovňový algoritmus

Literatura[editovat | editovat zdroj]

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