Bajo la hipótesis de que P ≠ NP (véase el artículo ¿P es igual a NP?), por desgracia, para algunos problemas de optimización no existen algoritmos de resolución eficaces. Sin embargo, como ocurre a menudo en matemáticas, su formulación es a veces tan sencilla que no se imagina la dificultad que esconden. Tomemos, por ejemplo, el célebre problema del viajante de comercio: dado un conjunto de ciudades, ¿qué recorrido de distancia mínima permite visitar todas las ciudades y regresar al punto de partida? Pese a su sencillez, no existe ningún algoritmo que permita resolver eficazmente este problema: incluso el mejor de ellos necesitará un tiempo que crece exponencialmente con el número de ciudades. ¿Qué hacer cuando se quiere resolver un problema «de gran tamaño» (del tipo de los que se encuentran en la práctica) en un tiempo «aceptable» (del orden de unos minutos)?
Las heurísticas… -----------------
La primera solución consiste en utilizar heurísticas (del griego heuriskein, que significa «encontrar»). El objetivo de una heurística es hallar una solución que respete las restricciones del problema y sea «de buena calidad» según el criterio de optimización considerado. La solución no será necesariamente óptima, pero una heurística eficaz trata de hallar una solución de buena calidad en el tiempo de resolución asignado.
Por ejemplo, para el problema del viajante de comercio, la heurística del vecino más cercano es sencilla: se selecciona la siguiente ciudad que se va a visitar de modo que la distancia entre la ciudad actual y la siguiente sea mínima, hasta haber visitado todas las ciudades. Después se vuelve a la primera ciudad visitada para obtener un recorrido (o circuito). Esta heurística es rápida, pero en la práctica da resultados bastante malos: nada garantiza que la última ciudad visitada esté «cerca» de la primera, lo que puede dar lugar a un recorrido final demasiado largo.