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 nehledáme 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 A problému maximalizace kriteriální funkce F je k-aproximační, jestliže existuje čí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 věta platí 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á optimalice.