La historia de la IA

Algoritmo A*

Etapa 2 · Nace la IA (1943–1979) › IA simbólica

Linaje
Símbolos y lógica
Tipo
Publicación

Quién

Stanford Research Institute

Qué ocurrió

Peter Hart, Nils Nilsson y Bertram Raphael, del Stanford Research Institute, publican «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» en las IEEE Transactions on Systems Science and Cybernetics.

Qué aportó

A* busca el camino más corto guiándose por una estimación de lo que falta. Si la estimación nunca exagera, encuentra siempre el óptimo. Nació para que el robot Shakey planeara sus trayectorias.

Desarrollo

Shakey tenía que moverse por varias habitaciones esquivando obstáculos, y para eso necesitaba encontrar rutas cortas sin examinar todas las posibles. Nilsson propuso primero un método basado en el Graph Traverser, y Raphael sugirió puntuar cada punto del recorrido sumando dos cantidades.

La primera, g, es el coste del camino ya recorrido desde el origen. La segunda, h, es una estimación del coste que falta hasta el destino, por ejemplo la distancia en línea recta. El algoritmo amplía siempre el punto con menor suma f = g + h. Si h fuera cero, sería el algoritmo de Dijkstra, de 1959, que avanza por igual en todas direcciones; con una buena estimación, se dirige hacia la meta y examina muchos menos puntos.

La aportación de Hart fue demostrar cuándo el método es fiable. Si la estimación nunca supera el coste real, lo que llamó una heurística admisible, A* encuentra siempre el camino óptimo.

A* se convirtió en el algoritmo de búsqueda de caminos por excelencia: está en los navegadores, en la robótica y en casi todos los videojuegos en los que un personaje busca su ruta. También fijó un ejemplo de cómo dar garantías formales a una heurística.

Un camino quebrado va del inicio a un nodo n; es el coste g(n). Desde n, una línea discontinua recta llega a la meta; es la estimación h(n). Debajo, la fórmula f(n) = g(n) + h(n).

A* puntúa cada punto con lo ya recorrido, g, más una estimación de lo que falta, h, y amplía antes el de menor suma.

Nivel técnico

A* guarda una lista de puntos abiertos ordenada por f(n) = g(n) + h(n). En cada paso saca el de menor f. Si es la meta, termina; si no, calcula g y f de sus vecinos y los añade a la lista.

Con h = 0 el orden depende solo de g, y el algoritmo es el de Dijkstra. Si h nunca supera el coste real que falta, la heurística es admisible y el primer camino que llega a la meta es el más corto.

Hart, Nilsson y Raphael demostraron además que, con una heurística admisible que cumpla una condición de coherencia, ningún algoritmo que use la misma información amplía menos puntos que A* sin arriesgarse a perder el camino óptimo.

Viene de

  • Shakey (marzo de 1966)

    Influencia directa documentada

    Ambos se crearon dentro del proyecto

Hilos que pasan por aquí

Bibliografía

Cómo citar

«Algoritmo A*». En La historia de la IA, revisión del 13 de noviembre de 2026. https://thehistoryofai.com/es/hito/algoritmo-a-estrella

Última revisión de esta ficha: 13 de noviembre de 2026.

Abrir en la cronología interactiva