Intuición
A* utiliza heurística, información sobre el dominio del problema que ayuda a guiar su búsqueda. Estas heurísticas a menudo se denominan heurísticas admisibles o de distancia, porque nunca sobreestiman el costo real para alcanzar la meta. En muchos casos, A* encuentra soluciones óptimas, aunque no siempre se garantiza que así sea.
¿Cómo funciona A*?
A* mantiene dos conjuntos de nodos durante su búsqueda:ABIERTO (Fringe) y CERRADO
ABIERTO contiene todos los nodos que se han generado, pero que aún no se han evaluado por completo. Está ordenado por la puntuación F (que se analiza a continuación) de sus miembros, con la puntuación F más baja al frente.
CERRADO contiene todos los nodos que han sido evaluados completamente.
El algoritmo comienza colocando el nodo inicial en ABIERTO, mientras que el nodo objetivo reside inicialmente en CERRADO. En cada paso del algoritmo, A* elimina el nodo en OPEN con la puntuación F más baja, lo expande y agrega todos sus vecinos a OPEN. Si un vecino aún no está en ABIERTO o CERRADO, A* calcula una puntuación G (el costo real para llegar al vecino desde el nodo inicial) y una puntuación H (una estimación del costo para alcanzar la meta desde el vecino) para él. y lo agrega a OPEN. Si un vecino ya está en ABIERTO, la nueva puntuación G se compara con la puntuación G actual y, si la nueva puntuación G es inferior, se actualiza el vecino. Si un vecino ya está en CERRADO, la nueva puntuación G se compara con la puntuación G actual y, si la nueva puntuación G es inferior, el vecino pasa de CERRADO a ABIERTO y se actualiza.
Terminación
El algoritmo termina de una de dos maneras. Primero, si el objetivo es un vecino del nodo que se está expandiendo, el algoritmo devuelve la ruta al objetivo. En segundo lugar, si OPEN queda vacío, el algoritmo finaliza sin éxito, lo que indica que no existe una ruta válida desde el nodo inicial hasta el objetivo.
Complejidad
La complejidad temporal del peor de los casos del algoritmo A* es exponencial en el tamaño del gráfico. Sin embargo, en la práctica, A* funciona bien en muchos problemas y, a menudo, encuentra soluciones óptimas en un período de tiempo razonable.