Boletín Técnico de Ingeniería
Figura 9. Ejemplo de árbol etiquetado24.
Foto fuente: <https://elisa.dyndns-web.com/teaching/mat/discretas/md.html>
Evaluados y actualizados los costes de los respectivos nodos, se ejecuta un algoritmo voraz25 que en función
de los costes obtenidos para cada nodo, identificará la ruta óptima (menor coste en tiempo) existente entre
cada nodo balsa y los respetivos nodos que alberguen al menos un agente que trata de alcanzar esta misma
balsa.
Este proceso tratará la emulación del proceso de modo inverso al real, es decir, el algoritmo voraz no «empujará
» al agente hacia su correspondiente balsa a lo largo de la ruta óptima, sino que por el contrario, «tirará
» del agente desde su nodo de partida hasta su correspondiente balsa, a través de la ruta óptima identificada.
Este proceso repetitivo de reevaluación de costes, localización de agentes y su posterior desplazamiento a lo
largo de las rutas óptimas, tendrá lugar hasta que todos los agentes intervinientes logren alcanzar su correspondiente
nodo sumidero (balsa de rescate), modelando en resumidas cuentas el proceso de simulación
public static void daemon(ref nodo arbol, byte balsa, double costeAcumulado, byte ordenArbol)
{
if ((arbol != null) && (!arbol.estado))
{
if (arbol.cola.Count > 0)
{
costeAcumulado += arbol.cola.Count * costes.costeRecorridoNodo(arbol.tipo);
if ((arbol.abierto) && (!costes.identificaCorredor(arbol.tipo)))
costeAcumulado -= costes.costeInicialNodo(arbol.tipo);
}
if (costeAcumulado < arbol.costesBalsabalsa) arbol.costesBalsabalsa = costeAcumulado;
arbol.estado = true;
for (byte z = 0; z < ordenArbol; z++)
{
costeAcumulado = arbol.costesEnlacez + arbol.costesBalsabalsa;
daemon(ref arbol.siguientez, balsa, costeAcumulado, ordenArbol);
}
arbol.estado = false;
}
}
Figura 10. Fragmento de código del método de evaluación de costes. Fuente GIMOE 2020.
24 Teoría de Grafos. Grafos que dispensan un peso a sus aristas o un etiquetado en los vértices.
25 Estrategia de búsqueda que se sigue una heurística consistente en elegir la opción óptima, en cada paso local, al
objeto de alcanzar una solución general óptima.
49
implementado.