4.4. Técnicas heurísticas.
Existen muchos problemas para los cuales no se conocen algoritmos que puedan encontrar la solución de forma eficiente: problemas NP-completos.
La solución exacta puede requerir un orden factorial o exponencial: el problema de la explosión combinatoria.
Se hace necesario utilizar algoritmos heurísticos:
Un algoritmo heurístico (o, simplemente, una heurística) puede producir una buena solución (posiblemente la óptima) pero también puede que no produzca ninguna solución o dar una solución no muy buena. Normalmente, se basa en un conocimiento intuitivo del programador sobre un determinado problema.
La estructura de algoritmo voraz se puede utilizar para construir procedimientos heurísticos: hablamos de heurísticas voraces.
Objetivo: obtener buenas soluciones en un tiempo de ejecución corto.