Algoritmo para determinar a rota mais rápida?

17

Digamos que vamos de 1 a 5. O caminho mais curto será 1-4-3-5 (total: 60 km).

Gráfico

Podemos usar o algoritmo de Dijkstra para fazer isso.

Agora, o problema é que a rota mais curta nem sempre é a mais rápida, devido a congestionamentos ou outros fatores.

Por exemplo:

  • Sabe-se que o 1-2 tem congestionamentos frequentes, por isso deve ser evitado.
  • De repente, um acidente de carro acontece ao longo de 4-3, por isso deve ser evitado também.
  • Etc ...

Então, provavelmente, podemos acelerar na rota 1-4-5, por causa de nenhum engarrafamento / acidente, por isso chegamos às 5 mais rapidamente.

Bem, essa é a ideia geral, e ainda não pensei em mais detalhes.

Existe algum algoritmo para resolver esse problema?

graph dijkstra anta40
fonte
3
Isso é lição de casa? Isso não é apenas en.wikipedia.org/wiki/Travelling_salesman_problem para percorrer um gráfico ponderado?
StuperUser
9
@StuperUser: Não, o TSP é um circuito de todos os nós sem duplicatas. No caso de amostra, não há necessidade de acessar o nó 2, por exemplo.
David Thornley
2
@DavidThornley eu vejo. Então Dijkstra é a rota mais curta em um gráfico ponderado? E o TSP é transversal visitando todos os nós?
StuperUser
1
@Stuper: Travessia mais curta, sim
BlueRaja - Danny Pflughoeft
2
@StuperUser, apenas FYI, TSP é um problema fortemente NP-Complete, sem solução que possa ser executada em tempo polinomial. ... Então agora você sabe.
riwalk

Respostas:

5

Como você trouxe congestionamento para a foto, tenha cuidado para não ser pego pelo paradoxo de Braess . Se todos escolherem o caminho ideal, isso resultará em um tempo de viagem pior para todos.

Michael Brown
fonte
49

Sim: Dijkstra

Dijkstra funciona tão bem quanto nesta situação.
Você apenas usa o tempo, e não a distância, como o peso de cada arco.

Martin York
fonte
9
Normalmente, a 'distância' em Dijkstra seria ponderada para todos os tipos de coisas, custo / pedágio, preferência por rodovias e limites de velocidade - usar apenas a distância é apenas a abordagem mais simples. Isto é o que torna o algoritmo tão inteligente #
Martin Beckett
6
Embora Dijsktra funcione, eu geralmente escolheria A * para qualquer trabalho sério de busca de caminhos; heurísticas ajudará muito.
Mircea Chirea
6
Link: um algoritmo de busca * . É uma extensão do método de Dijkstra.
mgkrebbs
Enquanto houver uma heurística aplicável, A * será superior à de Dijkstra (em termos de desempenho).
bummzack
Uma heurística admissível seria um pouco difícil de encontrar aqui, considerando que parecemos levar em consideração muitos fatores (como engarrafamentos).
pwny
16

Sim. O algoritmo de Dijkstra resolverá esse problema.

O problema no seu caso é que você assume automaticamente que o caminho mais curto equivale à distância percorrida, quando na verdade equivale mais apropriadamente ao CUSTO de fazer uma rota.

Se um caminho possui um roadblock, seu COST deve ser maior e o algoritmo ainda se aplica.

maple_shaft
fonte
Sim, desculpe se eu não usei as palavras corretas. O que quero dizer é a 'rota mais conveniente' (custo mínimo)
anta40 20/12/2011
11

Você deve poder substituir sua distância pelo tempo entre os nós e resolvê-lo da mesma maneira.

DKnight
fonte
10

Dijkstra

Como dito anteriormente, ele não é usado apenas para a menor distância. Eu acredito que esta animação oferece uma boa compreensão do "poder" (por falta de uma palavra melhor) do Dijkstra:

Dijkstra

Dinâmico
fonte