El algoritmo A* es un algoritmo tipo "pathfinder" que busca y traza un camino para llegar a meta, dibujando un recorrido lo más corto posible. El espacio donde se crea el camino es un grafo con casillas conocidas y el algoritmo va desplazándose de un nodo a otro, desde la casilla de inicio hasta la meta, teniendo en cuenta el valor heurístico y el coste real de desplazarse de un nodo a otro.
Toma en cuenta la heurística. Utiliza las características de cada nodo, para llegar a meta. La información del nodo se va actualizando y es la suma de la cantidad de desplazamientos de casilla en vertical y horizontal y el movimiento a la casilla anterior. Esta última se refiere al coste real del recorrido; para que el recorrido sea mínimo, tiene que calcular de donde viene el nodo. Así, el algoritmo viendo qué coste tiene cada movimiento de casilla en casilla cuál es el recorrido posible para ello, traza un camino.
Es un buen algoritmo para resolver una ruta compleja eficientemente, pero, para recorrer ese itinerario, es necesario conocer toda la información de los nodos todo el rato y esta es mucha información quizás para una memoria no muy grande.
Otra desventaja puede ser que el coste de una casilla no pueda estar definida adecuadamente,es decir, que no pueda fijarse, y por tanto, no se pueda utilizar en este algoritmo.
Por último, el algoritmo depende de la función heurística y si esta es lenta, el algoritmo también lo será, tardando más en llegar a meta.
Comments