lunes, 3 de noviembre de 2014

Problema Algoritmo de la ruta más corta

La administración de SEervada Park necesita encontrar la ruta más corta desde la entrada del parque (nodo O) al mirador (nodo T) a través del sistema de caminos que se muestra en la figura 10.1. En la tabla 10.2 se encuentran los resultados obtenidos al aplicar el algoritmo anterior a este problema (en donde el empate para el segundo nodo más cercano). La primera columna (n) indica el número de la iteración. La segunda columna da una lista de los nodos resueltos para comenzar la iteración actual, después de quitar los que no sirven (aquellos que no tienen conexión directa con nodo no resueltos). La tercera columna da los candidatos para el n-ésimo nodo más cercano (los nodos no resueltos con la ligadura más corta  al nodo resuelto). La cuarta columna calcula la distancia de la ruta más corta desde el origen a cada uno de los estos candidatos (esto es, la distancia al nodo resuelto más la distancia de la ligadura que va al candidato). El candidato con la suma de distancias más pequeñas es el n-ésimo nodo más cercano al origen, el cual se indica en la quinta columna. Las dos últimas columnas resumen la información de este último nodo resuelto necesaria para pasar las iteraciones siguientes (a saber, la distancia de la ruta más corta desde el origen a este nodo y la última rama en esta ruta más corta).

La ruta más corta desde es el nodo destino hasta el origen se puede rastrear hacia atrás en la última columna de la tabla 10., con lo que se obtiene T→D→E→B→A→O o bien T→D→B→A→O. Por tanto,, se identificaron las dos opciones para la ruta más corta desde el origen hasta el destino como las cadenas O→A→B→E→D→T y O→A→B→D→T, con una distancia total de 13 millas en cualquiera de las dos rutas.

1 comentario: