Hace relativamente poco tiempo hablé sobre los algoritmos voraces. En este post, os traigo un algoritmo voraz, concretamente el de Dijkstra.
En este algoritmo, podremos ver como navegamos por los nodos, obteniendo una búsqueda local optima, una vez recorrido todo el espacio de estados, podremos obtener la ruta mas optima.
Si vemos el grafo anterior, podemos ver claramente el camino más corto, el cual transcurre por A,C,D,F y G.
Por ahora este algoritmo es uno de los que más me gusta, aunque cada vez que veo uno nuevo me gusta más que el anterior.
Este algoritmo me parece muy curioso y casi todos se basan en el mismo punto, lista de visitados y pendientes, para evitar calcular dos veces y a más a mas podemos ver un sistema de «tagging» donde tendremos los resultados locales.
Veamos como se comporta y se obtienen los tags con las búsquedas locales:
El primer paso es decirle que nodos es el inicial y obviamente en este caso no tenemos sentido de dirección. Nodo inicial [0, »]
Algunos ejemplos podemos ver los nodos definidos como números, pero de esta manera se entiende mejor.
El orden dependerá si recorremos sendas listas/arrays de manera ordenada y cómo se ha construido el grafo. En este caso no creo que tenga mucha relevancia a no ser que tengamos espacios infinitos no sería muy relevante el orden como los creemos.
En cualquier momento podemos parar y obtener el máximo/mínimo local, no resulta interesante ?
En rojo he puesto el orden, tras el paso C, aunque no tiene mucho peso en este ejemplo.
Si entramos en más detalle de los pasos que componen este ejemplo, podemos ver como el TAG, va cambiando depende de donde estemos, recalcando en cada «local» un nuevo peso mínimo/máximo.
IMPLEMENTACION
No dudéis en jugar con los test, cambiar los valores y jugar con su comportamiento, super interesante!
