recicla

EL 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 susprincipales 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 dichosnodos 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 elnodo 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 sepretende 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 queesta 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 quela 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 paraetiquetarlo, 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...