Algoritmo exacto - Exact algorithm
En la investigación de operaciones y ciencias de la computación , los algoritmos exactos son algoritmos que siempre resuelven un problema de optimización de manera óptima.
A menos que P = NP , no se puede ejecutar un algoritmo exacto para un problema de optimización NP-hard en el peor de los casos polinomiales . Se ha realizado una extensa investigación para encontrar algoritmos exactos cuyo tiempo de ejecución sea exponencial con una base baja.
Ver también
- Reducción de preservación de 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
