Búsqueda Heurística

La búsqueda heurística, o búsqueda informada, es una familia de algoritmos que explora un espacio de estados usando una función heurística —una estimación del coste que falta para llegar al objetivo— para dirigirse hacia las regiones más prometedoras, en lugar de explorar a ciegas. Esa función aporta conocimiento del problema: en un mapa, por ejemplo, la distancia en línea recta al destino.

Los algoritmos, con su notación

La búsqueda voraz por el mejor primero se guía solo por la heurística, f(n) = h(n): es rápida, pero no garantiza encontrar el mejor camino. El algoritmo A* (A-estrella) combina el coste ya recorrido con la estimación de lo que falta: f(n) = g(n) + h(n), donde g(n) es el coste real acumulado desde el inicio y h(n) la estimación hasta el objetivo. Con ello garantiza el camino óptimo bajo las condiciones del algoritmo si la heurística es admisible, es decir, si nunca sobreestima el coste real. En búsqueda en grafo, cerrar estados sin reabrirlos exige además condiciones como la consistencia para conservar la garantía. Existen variantes como IDA*, que usa mucha menos memoria, o el A* ponderado, que sacrifica la optimalidad a cambio de velocidad.

No confundir con las metaheurísticas

Conviene deslindar la búsqueda heurística clásica de las metaheurísticas de optimización, como el recocido simulado, los algoritmos genéticos o la búsqueda tabú. Aunque ambas usen la palabra «heurística» en sentido amplio, son cosas distintas: la búsqueda informada recorre un espacio de estados guiada por h(n), mientras que las metaheurísticas exploran un espacio de soluciones candidatas —a menudo de forma estocástica— para aproximar un óptimo cuando la búsqueda exacta es inviable, sin garantía de optimalidad.

Para qué sirve

La búsqueda heurística es la base de la planificación automática, del cálculo de rutas y la navegación —A* es el estándar en videojuegos y sistemas de GPS— y de la resolución de puzles como el 15-puzzle o el cubo de Rubik. Es una técnica de búsqueda, distinta de otros campos de la inteligencia artificial con los que a veces se mezcla.