Implementación de Algoritmo A*

Implementación Algoritmo A*

Lange Julián A., Pérez Oliva Simón, Romero Caballero Facundo

Inteligencia Artificial I,

Universidad Gaston Dachary,

Posadas (Misiones), Argentina

{julianlange36, faroni1930}@gmail.com jsimon_perezoliva@hotmail.com

Resumen. A lo largo de este trabajo se expondrá el funcionamiento del Algoritmo A* (A Estrella) que se ha utilizado en el diseño e implementación para poner a punto el programa ejecutable. En una primera instancia se introduce al tema como una breve reseña sobre el algoritmo para luego exponer el desarrollo por el cual se ha optado al momento de decidir cómo realizarlo, como así también las diferentes modificaciones sobre el algoritmo para poder unir la interfaz gráfica. Posteriormente, se presenta la implementación en software, con sus configuraciones para poder ejecutar el programa. Además, consta de un apartado de Simulaciones y Resultados en el cual se concluirán las diferentes pruebas realizadas sobre el algoritmo y cómo él mismo fue resolviendo y generando los diferentes árboles.

Palabras Claves: Algoritmo, heurística, nodos, a estrella, árboles, búsqueda

1. Introducción

El algoritmo A* es un algoritmo de búsqueda que encuentra la ruta de menor coste entre dos puntos siempre y cuando se cumplan una serie de condiciones. “Es ampliamente utilizado en las ciencias de la computación para encontrar rutas y que tan transitable es una gráfica, es decir, se refiere al problema de visitar todos los nodos en una gráfica dada de forma particular, esto no es más que el proceso de trazado de la ruta más eficiente entre unos puntos llamados nodos, según [1]. Lo que realiza el algoritmo es construir todos los caminos desde un punto inicial hasta encontrar alguno que llegue al nodo final. De este modo solamente construye aquellos caminos que son candidatas a formar una solución desde el nodo inicial hasta el nodo final. Para poder determinar qué caminos son los que tienen mayor probabilidad de llegar al nodo final, el algoritmo utiliza una heurística, y, en este trabajo se implementa la distancia en línea recta (DLR) entre el nodo actual -el que se está evaluando- y el nodo final u objetivo.

representa a cada nodo en particular y debido a que se utilizará distanciaℎen(𝑛línea) recta, la La heurística es una función matemática definida de la siguiente manera , donde “n” función heurística será igual a la función propuesta por Pitágoras para hallar una recta entre dos puntos en un espacio de dos dimensiones, que es la siguiente: 2 + 𝑑𝑦2),

donde “dx” y “dy” son la diferencia entre las coordenadas en el𝐷𝐿𝑅eje de=las√(ordenadas𝑑𝑥 al orígen de el nodo final y el nodo inicial, y “dy”, la diferencia entre las coordenadas en el eje de las abscisas  de el nodo final y el nodo inicial.

1. Desarrollo del Algoritmo

Al momento de comenzar el algoritmo, hemos definido diferentes variables que serán las que vamos a utilizar para ir controlando la revisión del árbol a medida que vayamos realizando el recorrido del mismo. Estas variables son: tope(cantidad de nodos captados en la gráfica), nodoIni (es el nodo por cual debe comenzar el camino), nodoFin (es el nodo final u objetivo); además se declaran cinco listas de tipo ArrayList, las cuales son nodos (representa la lista de todos los nodos), aristas (representa las conexiones entre nodos), listaAbierta (es un arreglo de los nodos disponibles para explorar), listaCerrada (compuesta por los nodos explorados o expandidos) y finalmente una listaObjetivo (contendrá los nodos correspondiente al camino que se deberá mostrar). El procedimiento que se siguió para llevar a cabo el desarrollo del algoritmo es el siguiente:

Primeramente, se busca y guarda los nodos inicio y final respectivamente a través de la función Buscar Nodo Por Nombre (2.1), a la cual se le indica el nodo inicial, final y la lista de nodos y, en forma simultánea y paralela, se llama al método Resultados (2.5). Se cargan los valores de heurística a través de la función (2.2) a la cual se le envían valores de coordenadas en x y coordenadas en y de los nodos a evaluar (el nodo en la primera iteración es el inicial y en cualquier iteración el nodo final siempre será el mismo). Como setea en cero (0) y su valor de 𝑓(𝑛) será igual a el valor obtenido por la𝑔función heurística se trata de la primera iteración, el nodo inicial no tiene costo acumulado , por lo cual se lo

solamente. Terminado esto, se lo agrega a la lista abierta.

Definimos tres variables, “fn”, “gn” y “hn” que contendrán los valores de la sumatoria de los costos y heurística, el valor del costo acumulado y el valor que devuelva la función heurística respectivamente. Creamos una variable de tipo nodo, a la cual le denominaremos menor de lista abierta, ya que justamente en ella estará el nodo que tenga mejor “fn” de los que estén en la lista abierta.

El ciclo del algoritmo comienza ahora, ya que iremos a recorrer la lista abierta mientras almacenamos en nuestra variable “menor de lista abierta”.𝑓(𝑛)Agregamos este nodo a la lista no esté vacía, calculamos cuál nodo tiene mejor con la función (2.3) y lo

cerrada, lo removemos de la lista abierta. Ahora, debemos recorrer la lista cerrada en toda su extensión, comparando si el nodo que ingresé, es el nodo final, y de serlo, se debe terminar en ese momento el ejercicio. De lo contrario, es decir, hemos recorrido toda la lista cerrada y el nodo que acabamos de ingresar no es igual al nodo final, entonces debemos expandirlo o explorarlo, con intenciones de ir armando el árbol. Por lo cual lo que sigue es añadir todas las aristas que le corresponda al menor de la lista abierta, para ello, se realiza lo siguiente: recorreremos la lista de aristas (conexiones) declarada anteriormente e iremos preguntando y controlando si: el padre del nodo a expandir es no nulo, de cumplirse, se corrobora que el nombre del padre en la arista sea diferente al nombre del padre del menor de la lista abierta y que también sea diferente el hijo en la arista comparándolo con el nombre del menor de la lista abierta; cumpliendo estas dos condiciones, se consulta si el padre en la arista es igual al nombre del menor de la lista abierta, si coincide se busca en la lista de nodos a ese nodo conexión, utilizando la función (2.1). Si ese nodo conexión es no nulo, osea que existe en la lista de nodos, se le coloca el costo acumulado obtenido y al nodo menor de la lista abierta se le agrega la arista que lo conecta al nodo conexión.

...