A* ALGORITMO

Algoritmo A*

El algoritmo A*es un algoritmo de búsqueda que puede ser empleado para el cálculo de caminos mínimos en una red. Se va a tratar de un algoritmo heurístico, ya que una de sus principales características es que hará uso de una función de evaluación heurística, mediante la cual etiquetará los diferentes nodos de la red y que servirá para determinar la probabilidad de dichos nodos de pertenecer al camino óptimo.

Esta función de evaluación que etiquetará los nodos de la red estará compuesta a su vez por otras dos funciones. Una de ellas indicará la distancia actual desde el nodo origen hasta el nodo a etiquetar, y la otra expresará la distancia estimada desde este nodo a etiquetar hasta el nodo destino hasta el que se pretende encontrar un camino mínimo. Es decir, si se pretende encontrar el camino más corto desde el nodo origen s, hasta el nodo destino t, un nodo intermedio de la red n tendría la siguiente función de evaluación f(n) como etiqueta:

f(n)= g(n) + h(n)

Donde:

• g(n) indica la distancia del camino desde el nodo origen s al n.
• h(n) expresa la distancia estimada desde el nodo n hasta el nodo destino t.

1.- Establecer el nodo s como origen. Hacer f(s)=0, y f(i)=∞ para todos los nodos i diferentes del nodo s. Iniciar el conjunto Q vacío. 2.- Calcular el valor de f(s) y mover el nodo s al conjunto Q . 3.- Seleccionar el nodo i del conjunto Q que presente menor valor de la función f(i) y eliminarlo del conjunto Q. 4.- Analizar los nodos vecinos j de i. Para cada enlace (i, j) con coste cij hacer: 4.1.-Calcular: f(j)’=g(i)+cij +h(j) 4.2.-Si f(j)’<f(j), 4.2.1.-Actualizar la etiqueta de j y su nuevo valor será: f(j)= g(i)+cij +h(i) 4.2.2.-Insertar el nodo j en Q 4.3.-Si f(j)’≥f(j) 4.3.1.-Dejar la etiqueta de j como está, con su valor f(j) 5.- Si Q está vacío el algoritmo se termina. Si no está vacío, volver al paso 3.

Este algoritmo permite una implementación conservadora de memoria puesto que sólo necesita almacenar en su estado los nodos visitados según lo indica su heurística.