Pretende-se construir um sistema de apoio aos visitantes de uma localidade, que tenha por
base o armazenamento do mapa da localidade e dos locais de interesse para o visitante,
e que d?e resposta as quest?oes normalmente colocadas pelos visitantes, como por exemplo: indicar percursos tur´ısticos, indicar o melhor caminho para chegar a um dado local, indicar os restaurantes mais pr´oximos, etc. Vamos simplificar o problema, partindo do princ´ıpio que os visitantes se v?ao deslocar unicamente a p´e. Esta simplifica¸c?ao leva a que o mapa possa ser representado por um grafo n?ao orientado, dado que os pe?oes podem sempre circular nas ruas, nos dois sentidos. Assim, sugerimos que o conjunto de ruas e avenidas da localidade seja representado por um grafo n?ao orientado e pesado, em que o peso de cada arco seja a informa¸c?ao sobre a dist?ancia entre dois cruzamentos na mesma rua, assim como o tempo m´edio necess´ario para se percorrer essa dist?ancia. Os arcos devem ainda ser anotados com os locais de interesse tur´ıstico que estejam presentes no tro¸co da rua que esse arco representa. Pode ainda anotar os arcos com informa¸c?ao adicional sobre a rua, como por exemplo, o valor arquitect´onico dos seus edif´ıcios, ou se ´e uma rua de com´ercio. Alternativamente, poder´a representar esta informa¸c?ao como um grafo n?ao pesado em que os v´ertices correspondemas ruas e onde 2 ruas est?ao ligadas sse existir um entroncamento que
as une. Note que ao usar esta representa¸c?ao alternativa ter´a de adptar muitos dos algoritmos
estudados, de forma a ter custos associados a v´ertices e n?ao a arestas.
Informa¸c?ao adicional sobre os locais de interesse pode estar armazenada numa estrutura de
dados independente. Poder?ao ser considerados locais de interesse, postos de turismo, museus,
jardins, monumentos, farm´acias, hospitais, correios, centros comerciais, edif´ıcios de valor arquitect
´onico, monumentos, restaurantes, caf´es/confeitarias, teatros, …
A partir da informa¸c?ao guardada, o sistema deve ser capaz de responder `as seguintes quest?oes.
(Note que dever´a definir uma classifica¸c?ao para os v´arios locais de interesse que permita
estabelecer crit´erios de selec¸c?ao.)
? Dados um ponto (cruzamento) de partida e um ponto de chegada, indicar:
? o percurso mais curto, a sua dist?ancia e o tempo que demora a percorrer a p´e;
? o percurso que passa por melhores zonas de com´ercio, sem que se exceda uma
dada dist?ancia de percurso;
? o percurso mais r´apido para chegar a um dado local (monumento, restaurante,
hotel, etc);
? o percurso de maior valor arquitect´onico, hist´orico e paisag´ıstico, sem que o
acr´escimo de dist?ancia exceda os x % do caminho mais curto.
? O percurso de maior valor arquitect´onico, para gastar x minutos a caminhar a partir
de um dado ponto e com regresso ao ponto de partida.
? Dado um ponto (cruzamento) saber:
? num raio de x metros, quais os locais de interesse tur´ıstico que poderemos encontrar;
? quais os n restaurantes mais pr´oximos e as respectivas dist?ancias.
? Dados n pontos (cruzamentos), determinar um percurso (mais curto?) que passa por
esses pontos, preferencialmente apenas uma vez.
? Saber informa¸c?ao sobre um dado local (monumento, restaurante, …)
? Saber qual o comprimento total de uma rua (que pode ser constitu´ıda por v´arios tro¸cos).
Tarefas
- Comece por definir um formato (textual) para guardar/ler a informa¸c?ao num ficheiro.
- Defina tamb´em como a informa¸c?ao deve ser armazenada de forma a poder calcular os
percursos acima mencionados (e outros que julgue importantes). - Defina fun¸c?oes de leitura e escrita da informa¸c?ao em ficheiro.
- Defina fun¸c?oes que lhe permitam responder
as quest?oes indicadas acima. Extras Depois de resolvidas as tarefas obrigat´orias e de fazer o relat´orio, poder´a estender o problema proposto da forma que entender conveniente. Relat´orio e apresenta¸c?ao Dever´a elaborar um relat´orio sucinto onde constem: ? Descri¸c?ao e an´alise do problema. ? Defini¸c?ao das estruturas de dados de suportea solu¸c?ao implementada.
? Indica¸c?ao dos algoritmos usados na resolu¸c?ao dos problemas propostos. Para cada um
deve ser apresentada uma breve an´alise da sua complexidade (pior e melhor casos).
? Conclus?oes.
Na apresenta¸c?ao do trabalho dever´a trazer, pelo menos, um exemplo de m´edia dimens?ao.
(Sugest?ao: implemente um fragmento do mapa de Braga.)
2
