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).
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í
- Shakey y sus algoritmos (paso 2 de 3)
Bibliografía
Fuente original
- A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), pp. 100-107 (se abre en una pestaña nueva). Peter E. Hart, Nils J. Nilsson y Bertram Raphael, 1968
Estudios y contexto
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.