Algoritmo A*

El algoritmo A* [24]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.


h(n) se trata de una función heurística, expresa la idea de cuán lejos aún se está de alcanzar el nodo destino, y de su correcta elección dependerá en gran medida el rendimiento del algoritmo A* al aplicarlo en una red. Así, en el caso de que esta función heurística nunca sobreestime el valor de la distancia real entre el nodo y el destino, se dice que es admisible, y está garantizada la solución óptima. Por el contario, en el caso en que la función no sea admisible no se puede garantizar el hallazgo de la solución óptima para el problema del camino más corto.

A la función de evaluación f que caracteriza a un nodo y que sirve para etiquetarlo, también se la conoce como mérito de ese nodo, y expresa la probabilidad del nodo de estar en el camino más corto. Cuanto menor sea el mérito de un nodo, es decir, cuanto menor sea el valor de su función de evaluación, más probable será que el camino más corto atraviese ese nodo. En este mérito de los diferentes todos se basará el funcionamiento del algoritmo A*. El algoritmo irá explorando nodos de la red y sus sucesores (aquellos nodos con lo que les une algún enlace) basándose en su valor de mérito. Es decir, mantendrá una lista ordenada por valor creciente de mérito de los nodos que pueden ser explorados, y de ahí seleccionará el de menor valor, que será el primero de la lista. El algoritmo empezará analizando el nodo que se toma como origen para el problema del camino más corto. Calculará su mérito, y a continuación pasará a explorar sus nodos sucesores, es decir, los nodos con los que esté unido por un enlace este nodo fuente. Para estos nodos se calculará su mérito, y se seleccionará aquél de ellos que presente un menor valor, que será el que se someterá a análisis. Ahora el algoritmo continuará su ejecución explorando los nodos vecinos de ese nodo con merito menor, y así sucesivamente, hasta llegar al caso donde el nodo a analizar sea el nodo destino del problema, momento en que el algoritmo termina y ya se dispone de la solución. Para llevar a cabo este funcionamiento será necesario un registro donde el algoritmo ira guardando el conjunto de nodos que han sido explorados con sus valores correspondientes de mérito, y de donde se irán eliminando aquellos que sean seleccionados para ser analizados.

El funcionamiento anteriormente descrito del algoritmo A*, puede ser esquematizado mediante la siguiente sucesión de pasos:

 

Algoritmo A*
  • 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.

Comentarios

Hey there! Do you know if they make any plugins to Brunke

Hey there! Do you know if they make any plugins to Lipkind