Taller 10: Cálculo de la ruta más corta entre dos direcciones de Bogotá

Objetivos

  • Analizar y comprender la estructura de un grafo dirigido, con costos asociados a cada uno de los arcos.
  • Realizar algoritmos sobre gratos que permitan encontrar el camino más corto entre dos nodos.
  • Entender la importancia, necesidad de uso y aplicación de un grafo en aplicaciones críticas, como el calculo de itinerarios entre dos ubicaciones geográficas .
  • Modelar y representar un problema a través de la abstracción e implementación del mismo, usando un grafo.

Descripción general

Este taller continua con el trabajo realizado en el taller 9 y añade la capacidad al sistema implementado de calcular la ruta más corta entre dos direcciones de la ciudad. El paso a paso de las rutas se presentaran en consola, pero también se creará un archivo que se puede importar a Google Maps para visualizar la ruta.

Descripción en detalle

Al menú principal se le ha añadido la opción 3:


Figura 1: Menú con nueva funcionalidad

Una vez esta opción ha sido seleccionada al usuario se le pide ingresar la dirección de destino y la de origen y luego en pantalla se le presenta el paso a paso de la siguiente manera:


Figura 2: Ejemplo de resultado en consola

Ya que estas instrucciones son complicadas de leer, también se crea un archivo output.kml en el directorio data que se puede importar a Google Maps.

Importación a Google Maps de archivos .kml

  1. Dirígase a My Maps de Google Maps
  2. Haga click en la opción "Crear un mapa nuevo"
  3. Ingrese con su cuenta Google
  4. Haga click en el botón importar


    Figura 2: Importar

  5. Arrastre el archivo output.kml o busquelo
  6. A continuación podrá ver la ruta en pantalla


    Figura 3: Ruta en pantalla

Instrucciones de desarrollo

Nota: Antes de iniciar, lea la sección 0. Envío de talleres: Términos y Condiciones, en esta sección se encuentran enumeradas las reglas y recomendaciones de desarrollo y envío de proyectos establecidas a lo largo del curso.

  1. Por favor, descargue el esqueleto del ejercicio
  2. Complete los TODO's de la clase MapDijkstraSP en el directorio estructuras.
  3. Complete el método getShortestPath() en la clase BogotaMap en el directorio mundo
  4. Verificar el funcionamiento completo de la aplicación. En caso de que algún inconveniente sea detectado, por favor realizar las correcciones pertinentes y adecuadas.

Preguntas

  1. ¿Qué característica cree que debería ser tenida en cuenta a la hora de agregar un elemento a la cola de prioridad? Recuerde que sólo se están tomando los arcos más cortos pero no se está teniendo en cuenta donde están ubicados los nodos de destino.
  2. ¿Cómo modificaría el algoritmo de Dijkstra para tener en cuenta la característica del caso 1 y así mejorar el rendimiento en el caso promedio? Piense sobre todo a modificar el método "relax()".

Reto (Opcional)

  • ¿Cómo solucionaría el problema de visitar varias direcciones en un mismo itinerario?
  • Investigue un poco sobre el Traveling Salesman Problem.
  • ¿En el caso de nuestros datos de Bogotá, cuando se demoraría encontrar el circuito más corto que pase por todos los nodos ?
  • Plantee un "algoritmo" así sea en pseudocódigo, que permita encontrar una "buen" circuito que pase por todos los nodos del grafo. Esta ruta no tiene que se la mejor, pero el algoritmo tiene que correr en una complejidad polinomial.

Entrega para bonificación

Fecha límite de entrega: Ver

  1. Verifique que su aplicación cumple con las condiciones descritas en Envío talleres.
  2. Realice pruebas unitarias para el funcionamiento de la aplicación. Estas deben encontrarse en el paquete taller.test. Como como mínimo sus pruebas deberían validar los siguientes casos:
    • El caso en el que se pide una dirección de un nodo a si mismo.
    • El cálculo entre dos puntos muy lejanos
  3. Responda las preguntas en el archivo 'README.md.
  4. En el archivo README.md coloque el origen y el destino de 5 rutas que calculó con la aplicación.
  5. Suba las capturas de pantallas de las rutas del punto 3 en Google Maps al directorio data/imagenes_rutas/
  6. Cargue el taller a su repositorio en Bitbucket. No olvide crear el archivo calificacion.txt