Přesný algoritmus - Exact algorithm
v počítačová věda a operační výzkum, přesné algoritmy jsou algoritmy které vždy vyřeší problém s optimalizací do optimality.
Ledaže P = NP, přesný algoritmus pro NP-tvrdé optimalizační problém nemůže běžet v nejhorším případě polynomiální čas. Tam byl rozsáhlý výzkum na hledání přesných algoritmů, jejichž doba běhu je exponenciální s nízkou základnou.[1][2]
Viz také
- Redukce zachovávající aproximaci
- APX je třída problémů s nějakým algoritmem aproximace konstantním faktorem
- Heuristický algoritmus
- PTAS - typ aproximačního algoritmu, který bere aproximační poměr jako parametr
Reference
- ^ Fomin, Fedor V .; Kaski, Petteri (březen 2013), „Přesné exponenciální algoritmy“, Komunikace ACM, 56 (3): 80–88, doi:10.1145/2428556.2428575.
- ^ Fomin, Fedor V .; Kratsch, Dieter (2010). Přesné exponenciální algoritmy. Springer. str.203. ISBN 978-3-642-16532-0.