El algoritmo A*, pronunciado A-star o A-estrella, se utiliza para encontrar el mejor camino que nos lleve de un sitio a otro, dentro de una red de puntos. El mejor camino estará determinado por el menor coste necesario para llegar, así que primero tendremos que definir estos costes.
Veamos qué necesitamos para aplicar el algoritmo:
– Nodos: Necesitamos una red de puntos por los que nos podamos mover, y a los que llamaremos nodos. Estos nodos, pueden ser las casillas de una cuadrícula o bien un conjunto arbitrario de puntos, como por ejemplo, las ciudades de un mapa. Para el ejemplo, yo he elegido la rejilla cuadrada por simplicidad.
– Nodos vecinos: Cada nodo está conectado a los otros nodos a los que podemos movernos. Por ejemplo en una cuadrícula, cada casilla (nodo) estará conectado a las 4 casillas de alrededor: arriba, abajo, izquierda y derecha. Si permitimos movimientos diagonales, serían 8 casillas vecinas.
– Coste: Para pasar de un nodo a otro, se establecen unos costes, que pueden ser de tipo geométrico (distancia entre los nodos), esfuerzo (dificultad de tránsito del terreno), dinero (pago de aduanas)… en cualquier caso, se trata de asignar una cifra que sirva para valorar cómo de apetecible es ir a ese nodo. Cuanto menor sea el coste de un nodo, más apetecible será moverse a él.
– Nodo inicial y final: Son el punto desde el que empezamos y el punto al que queremos llegar. Para alcanzar este nodo final, intentaremos que la suma de costes de todos los nodos intermedios sea la mínima posible. En esto consiste el algoritmo A*.
Vamos a ver una primera aproximación del funcionamiento.
Empezamos desde el nodo inicial. Elegimos de los nodos vecinos aquel que tenga el menor coste. Tachamos el nodo en el que estamos (para no usarlo más) y nos movemos al nodo elegido. De este nuevo nodo, volvemos a elegir el nodo de menor coste sin contar los que ya estén tachados (esto evitará que volvamos atrás).
Si llegamos a un punto que no podamos hacer nada, volvemos al nodo anterior y probamos otro camino, pero siempre eligiendo el de menor coste de los posibles nodos. Así hacemos una típica ramificación que probará todas las opciones posibles, hasta que lleguemos al destino.
Como estrategia vale, pero esto no está muy optimizado, veamos por qué. Imagina que estás a mitad de camino de la cima de una montaña y quieres llegar arriba del todo. Después de establecer una serie de puntos estratégicos por los que puedes pasar, pones en marcha el algoritmo. El primer nodo al que te querrías mover (el de menor coste) sería hacia abajo, porque subir tiene un coste mayor debido a la elevación del terreno. El siguiente paso te volvería a llevar hacia abajo, y el siguiente también, y el siguiente también… A la larga, después de agotar todos los caminos que empiezan bajando, conseguirías llegar a la cima, pero está claro que necesitamos algo mejor.
Bien, pues este será el nuevo plan, al coste de cada nodo le sumaremos una cantidad extra que llamaremos función heurística, y cuyo valor será mayor cuanto más lejos esté del objetivo. Para entenderlo mejor, en el ejemplo anterior sería como un «remordimiento de conciencia» por no ir hacia donde tienes que ir. Como este valor se suma al coste del nodo, las direcciones que se alejan del destino serán menos apetecibles. Esta función heurística podría ser simplemente la distancia al objetivo, ya que obviamente, la distancia aumenta si te alejas.
Bien, veamos un par de cosas más antes de pasar al algoritmo en detalle.
– Lista abierta: Usaremos una lista de nodos que llamaremos lista abierta, para llevar la cuenta de los nodos candidatos a ser usados. Los nodos que están en esta lista, serán revisados en algún momento.
– Lista cerrada: También usaremos otra lista que llamaremos lista cerrada, donde meteremos los nodos que ya son definitivos. Estos no se volverán a revisar.
– Nodo activo: El nodo que estamos evaluando en la iteración actual.
Ahora vamos a ver el algoritmo paso a paso, solamente queda decir que a medida que vayamos confeccionando los posibles caminos, tendremos que guardar ciertos valores en cada nodo por el que vayamos pasando. Estos valores serán distintos si llegamos al nodo por caminos distintos:
– G: Cada nodo tiene un valor G, que es el coste total para ir desde el nodo inicial hasta dicho nodo. Es decir, la suma de todos los costes intermedios.
– H: Es la función heurística. Como dije, una buena opción es usar la distancia desde el nodo que sea, al nodo final, pero como es meramente orientativo, es muy típico usar la distancia Manhattan, que es más rápida de calcular.
– F: En cada nodo, sumamos su valor G y H para obtener el valor F.
– Padre: Además cada nodo tiene un indicador de cuál es su padre, o dicho en otras palabras desde qué nodo se ha llegado a ese nodo. Ten en cuenta que este valor es útil cuando el nodo está en la lista abierta, y como veremos luego, para estar en la lista abierta se debe haber llegado desde otro nodo.
Ya está todo definido, podemos ir al grano. Lista de pasos del algoritmo A*:
- Cogemos el nodo inicial y lo metemos en la lista abierta.
- Cogemos de la lista abierta, el nodo con menor valor de F (coste total).
- El elegido (nodo activo) lo pasamos a la lista cerrada.
- Cogemos los nodos vecinos del nodo activo y con cada uno hacemos lo siguiente:
– Si no está en la lista abierta: Lo metemos, le ponemos como padre el nodo activo y le calculamos los valores de G, H y F.
– Si ya está en la lista abierta: Verificamos si el camino por el que acabamos de llegar es mejor que el camino por el que llegamos anteriormente. Para eso vemos si su G es mejor que la G que le correspondería ahora. Si su G es mayor que la nueva G, es que el camino actual es mejor, así que le ponemos como padre el nodo activo y le asignamos los nuevos valores de G, H y F. - Si alguno de los nodos del punto 4 era el nodo final, hemos terminado.
- Si quedan nodos en la lista abierta, volvemos al punto 2
- Si no quedan nodos en la lista abierta y no hemos llegado al final, el destino es inalcanzable.
Por cierto, cuando lleguemos al final, hay que rehacer el camino completo desde el último nodo hasta el primero mirando la información del padre de cada nodo.