Algoritmo Del Vendedor

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

...