Hispanopedia WikiEn informática e investigación de operaciones , los algoritmos exactos son algoritmos que siempre resuelven un problema de optimización de manera óptima.
A menos que P = NP , un algoritmo exacto para un problema de optimización NP-hard no puede ejecutarse en el tiempo polinomial del peor caso . Se han realizado investigaciones exhaustivas para encontrar algoritmos exactos cuyo tiempo de ejecución sea exponencial con una base baja. [1] [2]
Véase también
- Reducción que preserva la aproximación
- APX es la clase de problemas con algún algoritmo de aproximación de factor constante.
- Algoritmo heurístico
- PTAS : un tipo de algoritmo de aproximación que toma la relación de aproximación como parámetro
Referencias
- ^ Fomin, Fedor V.; Kaski, Petteri (marzo de 2013), "Algoritmos exponenciales exactos", Communications of the ACM , 56 (3): 80–88, doi :10.1145/2428556.2428575.
- ^ Fomin, Fedor V.; Kratsch, Dieter (2010). Algoritmos exponenciales exactos . Saltador. pag. 203.ISBN 978-3-642-16532-0.
