¿Qué busca el algoritmo A*?

Podemos definir un algoritmo como una serie de instrucciones sencillas que se llevan a cabo para solventar un problema. De hecho, esta es la definición que nos ofrece la RAE: 'Conjunto ordenado y finito de operaciones que permite hallar la solución de un problema'.  O, como enuncia Ricardo Peña Marí, autor del libro De Euclides a Java, la historia de los algoritmos y de los lenguajes de programación: 'Conjunto de reglas que, aplicada sistemáticamente a unos datos de entrada apropiados, resuelven un problema en un numero finito de pasos elementales'. Este profesor de la Facultad de Informática de la Universidad Complutense añade que "es importante notar que el algoritmo tiene que ser finito y que ejecuta las instrucciones de manera sistemática, es decir, que es ciego ante lo que está haciendo, y que los pasos con los que opera son elementales". Es decir, tenemos un estado inicial, deseamos llegar a un estado objetivo, y entre ambos están las instrucciones u operaciones que nos permitirán conseguirlo.

Según su función, hay distintos tipos de algoritmos. Por ejemplo: 

Nos centraremos en los algoritmos de búsqueda y, en concreto, en el algoritmo A* ('A asterisco', 'A estrella' o 'A star'). Fue presentado en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael y es el algoritmo que utilizó el supercomputador de IBM Deeper Blue para vencer al ajedrecista Gary Kasparov en 1997. Se clasifica dentro de los algoritmos de búsqueda de grafos de tipo heurístico o informado. Un heurístico, como hemos visto en clase, es una regla o conjunto de reglas que permite (o permiten) escoger aquellas ramas del espacio de estados que presumiblemente llevan hacia una solución aceptable del problema. 

El algoritmo A* encuentra, siempre que se cumplan unas determinadas condiciones, la ruta de menor coste entre un nodo origen y uno objetivo. Así, se trata de un algoritmo muy utilizado para buscar un camino posible y eficiente entre dos puntos. Por ejemplo, para que personajes como los de la imagen de cabecera se muevan por el escenario del juego. Su funcionamiento se explica de manera detallada en este vídeo:

El algoritmo A* evalúa en cada paso el coste desde el nodo inicial hasta el actual y desde el actual hasta el final, y se favorecen los nodos que están más cerca del nodo inicial y del destino. Esto lo hace teniendo en cuenta ambos factores: el valor heurístico de los nodos y el coste real del recorrido. Para ello, utiliza la siguiente función de evaluación: f(n) = g(n) + h(n), donde g(n) es el coste de los movimientos realizados y h(n) la función heurística, la estimación hasta llegar a la meta. Y cada vez que existen nodos más prometedores, se cambia de camino de búsqueda. 

Como se comentaba arriba, una aplicación de este algoritmo son los videojuegos. También para encontrar el camino más corto entre dos puntos o para resolver el cubo de Rubik con los mínimos movimientos. Un inconveniente del algoritmo es que guarda en memoria todos los nodos vecinos y los caminos explorados (lista abierta y lista cerrada), por lo que supone un elevado consumo de memoria. Y cuantos más nodos tiene el problema, mayores son los recursos necesarios para resolverlo.

Imagen de cabecera: www.habbo.es/