Algoritmo de búsqueda A*
A* es un conjunto de pasos (un algoritmo) que los ordenadores pueden utilizar para averiguar cómo llegar rápidamente a algún lugar entre dos sitios. Si tienes una lista de lugares, y lo difícil que es llegar de uno a otro, el uso de A* puede decirte rápidamente el camino más rápido. Está relacionado con el algoritmo de Dijkstra, pero hace conjeturas inteligentes para no pasar tanto tiempo intentando caminos lentos. Es una buena serie de pasos si sólo quieres el camino entre dos lugares. Si vas a pedir muchos caminos del mismo mapa, entonces hay formas más rápidas, que encuentran todas las respuestas a la vez, como el algoritmo de Floyd-Warshall. A* no funcionará si quieres visitar varios lugares en un solo viaje (el problema del vendedor ambulante).
Los pasos
A* necesita primero una lista de todos los lugares a los que puedes ir, y luego necesita una lista de la distancia que hay entre cada uno de ellos. A continuación, te dirá cuál es el camino más rápido para ir del lugar A al lugar Z.
Como ejemplo, diremos que A está conectado a los lugares B y C, y que B y C están conectados a D y E. D y E están conectados a Z. Hay 4 formas posibles de ir de A a Z. Puedes ir A-B-D-Z, A-C-D-Z, A-B-E-Z, o A-C-E-Z. Un ordenador que utiliza A* primero mira lo difícil que es ir de A a B, y de A a C. Este es el "coste" de esos lugares. El coste de un lugar significa lo difícil que es llegar de A a ese lugar. Después de anotar ambos costes, el ordenador mira lo difícil que es ir de B a D, y lo añade al coste de B. Lo anota como coste de D. A continuación, el ordenador observa lo que cuesta ir de C a D y lo añade al coste de C. Esto es un coste diferente para D, y si es menor que el que ya tiene, reemplazará el antiguo. El ordenador sólo quiere conocer el mejor camino, por lo que ignora el camino con mayor coste. Sólo recordará uno de A-B-D y A-C-D, el que sea más rápido.
El ordenador continúa y encuentra el camino más rápido para llegar a E. Finalmente, va de D a Z, y encuentra un coste, y de E a Z y encuentra un coste. Obtiene un coste final para Z, y éste es el coste más pequeño que puede obtener. Ahora el ordenador sabe qué camino es el más rápido, y tiene la respuesta. El ordenador puede hacer una serie de pasos similares, pero con muchos más lugares. Cada vez, mirará el lugar más cercano a A, y sumará los costes de los vecinos de ese lugar.
La gente llama a esta serie de pasos el algoritmo de Dijkstra. El algoritmo de Dijkstra puede ser lento, porque buscará en muchos lugares que podrían ir en la dirección equivocada desde Z. Si le preguntas al ordenador cómo ir de una ciudad a otra cercana, el algoritmo de Dijkstra podría acabar buscando en otro estado.
A* soluciona este problema. A* te permite decirle al ordenador una estimación de la distancia que habrá desde cada lugar hasta el final. El ordenador puede utilizar la estimación para saber aproximadamente la distancia que se tardará en llegar desde un lugar determinado a Z. En lugar de elegir simplemente el lugar más cercano a A para mirar, mirará el que probablemente tendrá el total más bajo. El total se obtiene sumando el coste a la distancia prevista que queda. De esta manera, puede mirar sólo en la dirección en la que las cosas probablemente mejoren. No pasa nada si la suposición no es perfecta, pero incluso una simple suposición errónea puede hacer que el programa vaya mucho más rápido. Si estás tratando de encontrar un camino entre dos lugares en el mundo real, una buena suposición es sólo la distancia entre ellos en línea recta. El camino real sobre las carreteras será más largo, pero esto permite al programa adivinarlo, y no irá en la dirección equivocada.
En la literatura matemática o informática, esta conjetura suele ser una función del lugar, y se denomina heurística. Cada lugar es un vértice, y cada camino entre dos lugares es una arista. Son palabras de la teoría de grafos.
