Un algoritmo de búsqueda best-first que ordena la expansión de nodos por una función de coste f(n)=g(n)+h(n), donde g(n) es el coste desde el inicio hasta el nodo n y h(n) es una estimación heurística del coste desde n hasta una meta; con una heurística admisible (y preferiblemente consistente), A* encuentra rutas de coste mínimo de forma eficiente.

Principio

Priorizar nodos con el menor coste total estimado (g + h); la admisibilidad de h (no sobreestimar el coste real) asegura que la primera vez que se extrae un nodo meta de la frontera sea óptimo, y la consistencia (monotonía) simplifica la contabilidad y garantiza valores f no decrecientes a lo largo de los caminos.

Demostración

Búsqueda de caminos en una rejilla: usar g(n) como longitud de camino hasta ahora y h(n) como distancia Manhattan hasta el objetivo. A* expande nodos que parecen prometedores según f; si h es la distancia Manhattan en movimientos ortogonales 4-conectados, A* encontrará el camino más corto en la rejilla sin explorar todas las celdas. En robótica, A* planifica rutas discretas sobre mapas de ocupación.

Aplicación incorrecta

Usar una heurística no admisible (que sobreestima) puede producir rutas subóptimas; heurísticas pobres (cercanas a cero) degradan A* al algoritmo de Dijkstra, provocando demasiadas expansiones y alto uso de memoria; ignorar límites de memoria puede hacer impracticable A* en grafos grandes.

Consecuencia

Cuando existe una buena heurística admisible, A* reduce ampliamente las expansiones de nodos en comparación con la búsqueda no informada y produce rutas óptimas; también ofrece un marco flexible para variantes (A* ponderado, IDA*) que intercambian optimalidad por velocidad o memoria.

Inversión

El algoritmo de Dijkstra corresponde a A* con h=0 (no informada) y es óptimo, pero puede explorar más; la búsqueda codiciosa best-first usa f=h y puede ser más rápida pero no garantiza optimalidad.

Límite

Diseñado para búsqueda en espacios de estado discretos y problemas de camino mínimo con costes de arista no negativos y pruebas de objetivo bien definidas; problemas continuos requieren discretización o variantes continuas especializadas; la optimalidad depende de las propiedades heurísticas y las suposiciones de coste.

Tensión semántica

Tensión entre admisibilidad/optimalidad y velocidad práctica: las heurísticas admisibles garantizan optimalidad pero pueden ser conservadoras; heurísticas ponderadas o no admisibles aceleran la búsqueda pero arriesgan soluciones subóptimas. También hay tensión entre consumo de memoria (tamaño de la frontera) y tasa de expansión.

Síntesis

A* combina el coste real desde el inicio y el coste heurístico por recorrer en un orden que, con una heurística admisible, produce una búsqueda óptima y a menudo eficiente; su uso práctico requiere equilibrar diseño heurístico, restricciones de memoria y compromisos aceptables entre velocidad y optimalidad.