optimizar caminos en el mapa de la simulación juan ramón pérez pérez mª del puerto paule ruiz...
TRANSCRIPT
![Page 1: Optimizar caminos en el mapa de la simulación Juan Ramón Pérez Pérez Mª del Puerto Paule Ruiz Esta obra es publicada bajo una licencia Creative Commons.licencia](https://reader035.vdocumento.com/reader035/viewer/2022081817/5665b4631a28abb57c911f26/html5/thumbnails/1.jpg)
Optimizar caminos en el mapa de la simulación
Juan Ramón Pérez PérezMª del Puerto Paule Ruiz
Esta obra es publicada bajo una licencia Creative Commons.
Módulo 2. Prácticas de Estructura de Datos y de la Información
![Page 2: Optimizar caminos en el mapa de la simulación Juan Ramón Pérez Pérez Mª del Puerto Paule Ruiz Esta obra es publicada bajo una licencia Creative Commons.licencia](https://reader035.vdocumento.com/reader035/viewer/2022081817/5665b4631a28abb57c911f26/html5/thumbnails/2.jpg)
Nodos fuente, sumidero y aislados
Prácticas EDI - © Juan Ramón Pérez2
Devuelven un array con la lista de nodos que cumplen las condiciones: Object [] buscarFuente() Object [] buscarSumidero() Object [] buscarAislado()
2
5
1
Fuente
Sumidero
3
Aislado
![Page 3: Optimizar caminos en el mapa de la simulación Juan Ramón Pérez Pérez Mª del Puerto Paule Ruiz Esta obra es publicada bajo una licencia Creative Commons.licencia](https://reader035.vdocumento.com/reader035/viewer/2022081817/5665b4631a28abb57c911f26/html5/thumbnails/3.jpg)
Ampliación de la clase Grafo
Prácticas EDI - Juan Ramón Pérez3
Grafo
Object[] nodos; // Vector de nodosboolean[][] aristas; // Matriz de aristasObject [][] pesos; // Matriz de pesos…
…Object [] buscarFuente()Object [] buscarSumidero()Object [] buscarAislado()
![Page 4: Optimizar caminos en el mapa de la simulación Juan Ramón Pérez Pérez Mª del Puerto Paule Ruiz Esta obra es publicada bajo una licencia Creative Commons.licencia](https://reader035.vdocumento.com/reader035/viewer/2022081817/5665b4631a28abb57c911f26/html5/thumbnails/4.jpg)
Caminos mínimos entre los nodos
Prácticas EDI - Juan Ramón Pérez4
Disponemos de un grafo con nodos y aristas que cargamos en el fichero red.xml
Las aristas deben tener un valor numérico o un equivalente
Utilizamos el algoritmo de Floyd para buscar caminos óptimos
Resultado de Floyd: Matriz A, costes de Floyd, diagonal principal a 0. Matriz P, trayectoria de nodos intermedios para llegar
desde un origen a un destino. Podemos calcular distancia desde el nodo actual
a un nodo destino cualquiera (en la matriz A). Usar la matriz P para ver los nodos intermedios
por los que tengo que pasar para ir del nodo actual al destino.
![Page 5: Optimizar caminos en el mapa de la simulación Juan Ramón Pérez Pérez Mª del Puerto Paule Ruiz Esta obra es publicada bajo una licencia Creative Commons.licencia](https://reader035.vdocumento.com/reader035/viewer/2022081817/5665b4631a28abb57c911f26/html5/thumbnails/5.jpg)
Ampliación de la clase Grafo
Prácticas EDI - Juan Ramón Pérez5
Grafo
…float [][] A; // costes de Floydint [][] P; // trayectoria de nodos intermedios
…calcularFloyd(); // Calcula las matrices A y P de FloydverDistanciaMinima(Object origen, Object destino): floatverTrayectoria(Object origen, Object destino): Lista
// Lista con los intermedios nodos
![Page 6: Optimizar caminos en el mapa de la simulación Juan Ramón Pérez Pérez Mª del Puerto Paule Ruiz Esta obra es publicada bajo una licencia Creative Commons.licencia](https://reader035.vdocumento.com/reader035/viewer/2022081817/5665b4631a28abb57c911f26/html5/thumbnails/6.jpg)
Tareas
Prácticas EDI - © Juan Ramón Pérez6
Buscar nodos: fuente, sumidero y aislados En la simulación
se debe comprobar que el grafo del fichero red.xml no contiene nodos fuente, ni sumidero, ni aislados
Para que el trabajo posterior con el mapa sea correcto.
![Page 7: Optimizar caminos en el mapa de la simulación Juan Ramón Pérez Pérez Mª del Puerto Paule Ruiz Esta obra es publicada bajo una licencia Creative Commons.licencia](https://reader035.vdocumento.com/reader035/viewer/2022081817/5665b4631a28abb57c911f26/html5/thumbnails/7.jpg)
Tareas (2)
Prácticas EDI - © Juan Ramón Pérez7
Leer mapa de fichero: Plantear un grafo con pocas aristas, que
permita distintos caminos para ir de un nodo a otro.
Aplicar Floyd sobre el mapa Comprobar caminos mínimos