Algoritmo de búsqueda de caminos A

Vista previa del material en texto

El algoritmo de búsqueda de caminos A* es un algoritmo de búsqueda informada que se utiliza 
para encontrar la ruta más corta entre dos puntos en un grafo ponderado. Combina el uso de 
información heurística y el coste acumulado para tomar decisiones inteligentes sobre qué 
nodos explorar y qué ruta seguir. 
 
El algoritmo A* sigue los siguientes pasos: 
 
Inicialización: Se establecen los nodos de inicio y destino. Además, se crea una estructura de 
datos llamada "lista abierta" (open list) para almacenar los nodos que se deben explorar y una 
"lista cerrada" (closed list) para almacenar los nodos ya explorados. 
 
Cálculo de las funciones de evaluación: Para cada nodo, se calculan dos funciones de 
evaluación. La primera es el coste acumulado desde el nodo inicial hasta el nodo actual, 
conocido como "g(n)". La segunda es una estimación del coste desde el nodo actual hasta el 
nodo destino, conocido como "h(n)". La función "f(n)" se calcula sumando "g(n)" y "h(n)". 
 
Exploración de los nodos: Se selecciona el nodo de la lista abierta con el valor más bajo de 
"f(n)" y se marca como nodo actual. Se mueve el nodo actual de la lista abierta a la lista 
cerrada. 
 
Expansión de nodos adyacentes: Para cada nodo adyacente al nodo actual, se calculan los 
valores de "g(n)", "h(n)" y "f(n)". Si el nodo adyacente ya está en la lista cerrada y el nuevo 
camino no mejora su "f(n)" actual, se descarta. Si el nodo adyacente no está en la lista abierta 
o el nuevo camino mejora su "f(n)", se actualizan los valores y se establece el nodo actual 
como el padre del nodo adyacente. 
 
Comprobación del destino: Si el nodo destino se encuentra en la lista cerrada, se ha 
encontrado la ruta más corta. Si no, se continúa explorando los nodos. 
 
Reconstrucción de la ruta: Una vez que se ha encontrado el nodo destino, se reconstruye la 
ruta desde el nodo destino hasta el nodo inicial siguiendo los padres de cada nodo. 
 
El algoritmo A* es efectivo debido al uso de la función de evaluación "f(n)" que combina 
información heurística ("h(n)") y el coste acumulado ("g(n)") para guiar la búsqueda hacia la 
ruta más prometedora. La heurística proporciona una estimación del coste restante desde el 
nodo actual hasta el nodo destino, y el coste acumulado permite elegir rutas con menor coste 
hasta el momento. 
 
El algoritmo A* es ampliamente utilizado en problemas de búsqueda de caminos, como en 
sistemas de navegación GPS, juegos con inteligencia artificial y planificación de rutas en 
robótica. Sin embargo, es importante tener en cuenta que el rendimiento del algoritmo puede 
verse afectado por la elección de la heurística y la estructura del grafo. 
 
En resumen, el algoritmo de búsqueda de caminos A* se utiliza para encontrar la ruta más 
corta entre dos puntos en un grafo ponderado. Combina información heurística y coste 
acumulado para guiar la búsqueda hacia la ruta más prometedora. El algoritmo A* es 
ampliamente utilizado en problemas de búsqueda de caminos y es especialmente útil cuando 
se dispone de información heurística sobre el problema. Comprender este algoritmo nos 
permite encontrar rutas eficientes y optimizadas en diversos contextos.