Trabajo final de algoritmos avanzados

SI169 - Algoritmos Avanzados TF - Trabajo Final Construyendo un UPC-Maps Ciclo: 2010-2 Sección: Todas

La tecnología va avanzando cada día más y más. Hoy en día, ya podemos de disponer de un sistema de direccionamiento (a través GPS) que nos permite llegar a donde sea optimizando las rutas, en función a la distancia, sentido del tráfico, etc. ¿Pero como funcionan internamente todos estosprogramas? Facil y simple: ¡Utilizan grafos! Se le pide implementar un sistema que permita obtener rutas rápidas y eficientes para una parte de Lima.

Usted debe modelar un área específica de lima de aprox. 12km2. Esta área debe tener las siguientes condiciones:     Debe contener un óvalo. (Ejm: Quiñones, Higuereta, Gutierrez, Plaza Bolognesi) Debe ser un área de alta densidad de tráfico. Debeestar en un distrito céntrico de conocimiento común. (No en los conos) Debe tener por lo menos 8 sitios de interés común (Museos, Ministerios, Embajadas, Teatros, centros comerciales, etc.)  Debe contener una autopista o vía expresa. Esta parte del mapa deberá poder mostrarse en una interfaz visual. Importante, el mapa deberá permitir poder realizar un zoom de 2x. Es decir la imagen podrá acercarsehasta 2 veces. Ver imagen adjunta:

Sugerencia: No es necesario (y tampoco es considerado como puntaje adicional) el hecho de que usted cree la imagen de la cuidad a partir del modelado que usted realice. Usted puede utilizar imágenes ya generadas por otros sistemas (Google Maps, Bing Maps, Google Earth, etc) y mapearse a través de coordenadas. Lo que sí es importante es que usted tengamodelado la estructura de la cuidad en estructuras de datos (Grafos) para que pueda realizar los cálculos necesarios para los algoritmos. Requerimiento 1: Una vez que ya haya definido el modelado adecuado de la cuidad. Usted deberá implementar una solución que permita hallar la ruta más corta desde un punto de origen a un punto de destino CAMINANDO. Para esto el aplicativo debe permitir configurar lospuntos de origen y de destino a libertad del usuario. Bajo las siguiente premisas.  El sentido del tráfico de las calles no interesa, pues se realiza caminando.  La velocidad del movimiento es constante. (5km/h)  La optimización de la ruta se realiza a través de la distancia, ya que al ser la velocidad constante, esta es la única variable que afecta mi recorrido.  Se puede considerar un tiempopromedio de retraso constante para toda la ruta (Causado por cruces de semáforos y otras interrupciones)

 Usted deberá indicar gráficamente la ruta a seguir. Como el tiempo y la distancia que le tomará llegar a dicho destino.  La ruta debe evitar cruzar autopistas por el medio de la calle. De lo contrario la persona morirá en el intento (Por ejemplo, Javier Prado, Via Expresa, Av.Evitamiento, etc). Obviamente, solo podemos cruzar estas avenidas por puentes.

Requerimiento 2: Se deberá implementar el algoritmo para hallar la ruta más RÁPIDA para ir en AUTOMOVIL. Al igual que el caso anterior el aplicativo debe permitir configurar el punto de origen y el punto de destino. Todo esto bajo las siguientes premisas:  El sentido del tráfico de las calles SI interesa.  No nos va ainteresar si existe tráfico o congestión en las calles. Para este caso se asumirá que son las 3am y las vías está casi libres.  El tiempo de movimiento NO es constante. Cada tramo de la avenida tiene una velocidad promedio de recorrido. Por ejemplo, yo puedo ir por la vía expresa con una velocidad máxima de 80km/h (siguiendo el reglamento claro). Sin embargo no puedo realizar esta misma proeza por laavenida Petit Thouars ya que en cada esquina podría chocarme con algún otro carro. Para esta avenida debería ir a unos 40km/h aprox.  La optimización de la ruta se realiza a través del TIEMPO en que me demoró en llegar, al tener una velocidad variable la distancia más corta no necesariamente será la más rápida.  Se puede considerar un tiempo promedio de retraso constante para toda la ruta...