Projeto 3 - Uber pool - versão 2

1 Como escolher caronas.

Vamos assumir que 2 passageiros do UBER aceitam dividir a viagem - carona.

Passageiro 1 quer ir de A para B e o passageiro 2 quer ir de C para D.

Então há varias alternativas assumido que eles vão dividir a viagem:

pega passageiro 1 em A, pega o 2 em C, deixa 1 em B e deixa 2 em D
de A para C para D para B
de C para A, para D, para B
e de C para A, para B, para D

Se T(A,B) é o tempo de viagem de A para B, e se T(A,C,B) é o tempo de viagem de A para C para B, então a inconveniência para um passageiro por estar dividindo a viagem é a razão do tempo da viagem com carona pelo tempo da viagem sem carona.

Para o primeiro caso, a inconveniência para o passageiro 1 é T(A,C,B)/T(A,B). Para o passageiro 2 a inconveniência é T(C,B,D)/T(C,D).

No segundo caso, a inconveniência para 1 é T(A,C,D,B)/T(A,B), e para o passageiro 2, T(C,D)/T(C,D) = 1.

A uber ira escolher o percurso da carona de tal forma que a maior inconveniência para os 2 passageiros seja a menor possível (ou seja a uber minimiza o máximo da inconveniência para os 2 passageiros). A uber também definiu que a inconveniência máxima para um passageiro é 1.4, ou seja, usando a carona, nunca voce terá um acréscimo maior que 40% no tempo de viagem.

Assim, se nenhum dos percursos acima tiver uma inconveniência maxima para os 2 passageiros menor que 1.4 então não será feito a viagem dividida e cada passageiro fará uma viagem individual.

1.1 exemplo

T(A,B)	40
T(C,D)	15
T(A,C)	5
T(A,D)	10
T(C,A)	8
T(C,B)	40
T(D,B)	35
T(B,D)	30

percurso A,C,D,B, incov1 = 5+15+35/40 = 1.375, incov2 = 15/15 = 1
percurso A,C,B,D, incov1 = 5+40/40 = 1.125, incov2 = 40+30/15 = 4.66
percurso C,A,D,B, incov1 = 10+35/40 = 1.125, incov2 = 8+10/15 = 1.2
percurso C,A,B,D, incov1 = 1 , incov2 = 8+40+30/15 = 5.2

A inconveniencia máxima do percurso 1 é 1.375, a do 2 é 4.66, a do 3 é 1.2 e a do 4 é 5.2.

O percurso 2 e 4 não vão ser aceitos pois a inconveniencia máxima é maior que 1.4. Entre os percursos 1 e 3, o sistema escolherá o percurso 2, pois ele tem a menor inconveniencia maxima.

1.2 Viagens em andamento

Pode acontecer que um passageiro ja esta em viagem. Digamos que passageiro A esta indo para B mas a viagem ja esta em andamento, e ele esta em X no momento. O outro passageiro quer ir de de C para D não esta em viagem. Assim se houver uma viagem dividida, ela ja começou em A, (esta agora em X) e portanto os únicos 2 percursos possíveis são A,X,C,B,D ou A,X,C,D,B. A inconveniencia para o passageiro 2 é calculada normalmente. Para o passageiro 1 a inconveniencia deve ser calculada usando o tempo restante da viagem e não o tempo total. Assim a inconveniencia do passageiro 1 para o primeiro percurso é T(X,C,B,D)/T(X,D) e para o outro T(X,C,D)/T(X,D)

2 Projeto

O program lera do standard input dados no formato

As primeiras linhas informam o tempo de percurso entre vértices de um grafo. Os vértices são inteiros, 0,1, etc. O grafo é direcionado.

Uma linha vazia separa o segundo bloco de informação, que são as requisições de viagens e as viagens em andamento.

0 10 indica um requisição de viagem, que um passageiro quer ir do vertice 0 a 10. Esse passageiro sera denominado passageiro 1.

20 45 sera a requisição do passageiros 2.

30 28 12 indica uma viagem em andamento, que saiu do vertice 30 para o vertice 28 e se encontra agora no vertice 12.

2.1 Algoritmos

Voce pode usar o Dijkstra para calcular os T(X,Y) das formulas.

Ou voce pode usar o Floyd–Warshall algorithm para calcular de uma vez só os tempos mínimos entre todos os vértices. Uma ideia talvez interessante é implementar o Floyd-Warshall usando operações em matrizes.

Mas considere o caso onde pode haver 2 nos para os quais nao ha um caminho entre eles. Obviamente isso nao acontece numa cidade, mas para testar o programa podemos pensar em um grafo com subgrafos desconexos.

2.2 Saída

A saída deve ser uma lista dos percursos propostos. No máximo 2 passageiros farão uma viagem compartilhada, e assuma uma estratégia gulosa. Escolha o par de passageiros cuja percurso gera o menor inconveniencia maxima, depois o próximo par de passageiros, e assim por diante.

A saida deve ser no seguinte formato

passageiros 3 e 2 percurso: 12 20 45 28
passageiros 1 e 4 percurso: 0 50 35 10
passageiro 5 percurso: 23 34

que indicam que os passageiros 3 e 2 faro uma viajem compartilhada. O percurso (que indica apenas os nos iniciais e finais) começa no 34 onde ou o uber pega o passageiro 3 ou ele ja esta numa viajem em andamento, passa pelo no 12 para pegar o passageiro 2. O resto do percurso indica que a viajem vai ate o no 45 onde um dos passageiros desce e finalmente ate o 8 onde o outro desce.

A segunda linha da saida indica que 1 e 4 nessa ordem, fazem uma viajem compartilhada, e finalmente a ultima linha indica que o passageiro 5 faz a viajem sozinho.

2.3 Execucao

O programa sera rodado com a chamada

python proj3.py entrada1.txt

ou seja o nome do arquivo com a entrada sera parte da chamada (não usarei o standard input como nos outros 2 porjetos). Assim o seu programa deve acessar a linha de execução para sys.argv para descobrir o nome do arquivo de dados.

Se voce esta usando uma bibloteca nao padrao (como o numpy ou outras) avise-o no email de submissao.