Projeto de Haskell - Waze para transporte público
versão 1
Data de entrega: 1/10 até as 8:00
Individual ou em grupos de 2
Escreva um programa em Haskell que vai calcular o caminho mais rápido entre uma origem em um destino dado usando uma combinação de caminhar e usar transporte público. O programa recebe um grafo direcionado com um label e um valor nas arestas. O label indica o modo de transporte: "a pé", "linha 370", "linha 4567", "metro linha azul", etc. E o valor, o tempo em minutos para percorrer aquela aresta usando aquele modo.
O programa recebe o grafo (com as múltiplas arestas entre vértices), a origem e o destino, e deve imprimir a sequencia de vértices e modos, e o tempo esperado para chegar ao destino.
Por exemplo a saída:
a a-pe b a-pe c linha-370 f a-pe h a-pe i 17.5
indica que a pessoa deve ir a pé de a
para b
, de b
para c
, pegar a
linha 370 em c
, descer em f
, e de la, andar para h
e i
. O percurso
todo demorará 17.5 minutos (ou unidades de tempo)
Mas, como sabemos, há um custo em tempo em pegar um ônibus ou metro - temos que esperar até o ônibus chegar. Para esse projeto vamos assumir que o custo é fixo e é metade do período do ônibus - se o ônibus sai a cada 15 minutos do ponto inicial, em média esperaremos 7.5 minutos no ponto para pegar o ônibus. Assim para cada modo (que não a-pe) há um custo de "entrar no modo" (mas não há custo em sair do modo).
Os dados tem a seguinte forma:
a b a-pe 0.4 b a a-pe 0.6 b c a-pe 0.5 c b a-pe 0.5 c d a-pe 0.3 d c a-pe 0.3 a d linha-370 0.1 d f a-pe 3 f h linha-567 1.2 f h a-pe 12.3 linha-370 15.0 linha-567 12.0 a h
A primeira linha indica que a-pe de a
para b
demora 0.4. Na outra direção (de
b
para a
) demora mais (subida?).
A linhas 9 e 10 indicam que de f
para h
demora 12 minutos a pe e 1.2
minutos no ônibus "linha-567".
Uma linha em branco separa as informações sobre cada linha de onibus: um onibus da linha-370 sai a cada 15 minutos, um onibus da linha-567 sai a cada 12 minutos
E uma linha em branco separa a origem e destino: encontre o caminho
que sai de a
e vai até h
.
Obviamente buscar o caminho mais curto num grafo implica em usar Dijkstra mas há talvez 2 problemas um usar o Dijkstra direto:
- possivelmente há mais de uma aresta entre dois vértices: os
diferentes modos de transporte que percorrem a aresta de
a
parab
. - o custo de pegar um desses modos de transporte que não a-pe.
Talvez a parte mais difícil desse projeto é como incorporar desses 2 problemas no Dijkstra.
Seu programa será executado como
runhaskell prog1.hs < arq1.in
So as bibliotecas padrão deverão ser usadas, e a entrada é feita pelo standard input.