Algorithme pour déterminer l'itinéraire le plus rapide?

17

Supposons que nous passions de 1 à 5. L'itinéraire le plus court sera le 1-4-3-5 (total: 60 km).

Graphique

On peut utiliser l'algorithme de Dijkstra pour ce faire.

Maintenant, le problème est que l'itinéraire le plus court n'est pas toujours le plus rapide, en raison des embouteillages ou d'autres facteurs.

Par exemple:

  • 1-2 est connu pour avoir des embouteillages fréquents, il doit donc être évité.
  • Tout à coup, un accident de voiture se produit le long de 4-3, il faut donc également l'éviter.
  • Etc...

Donc, nous pouvons probablement accélérer sur la route 1-4-5, en raison d'aucun embouteillage / accident, nous arriverons donc à 5 plus rapidement.

Eh bien, c'est l'idée générale, et je n'ai pas encore pensé à plus de détails.

Existe-t-il un algorithme pour résoudre ce problème?

graph dijkstra anta40
la source
3
Est-ce des devoirs? N'est-ce pas simplement en.wikipedia.org/wiki/Travelling_salesman_problem pour parcourir un graphique pondéré?
StuperUser
9
@StuperUser: Non, TSP est un circuit de tous les nœuds sans doublons. Dans l'exemple de cas, il n'est pas nécessaire d'appuyer sur le nœud 2, par exemple.
David Thornley
2
@DavidThornley je vois. Donc Dijkstra est pour l'itinéraire le plus court sur un graphique pondéré? Et TSP parcourt-il tous les nœuds?
StuperUser
1
@Stuper: Traversée la plus courte, oui
BlueRaja - Danny Pflughoeft
2
@StuperUser, juste FYI, TSP est un problème fortement NP-Complete sans solution qui peut être exécutée en temps polynomial. ... Alors maintenant tu sais.
riwalk

Réponses:

5

Depuis que vous avez mis de la congestion dans l'image, faites attention à ne pas vous faire prendre par le paradoxe de Braess . Si tout le monde choisit le chemin optimal, cela se traduit par une diminution du temps de trajet pour tout le monde.

Michael Brown
la source
49

Oui: Dijkstra

Dijkstra fonctionne aussi bien pour cette situation.
Vous utilisez simplement le temps plutôt que la distance comme poids de chaque arc.

Martin York
la source
9
En règle générale, la «distance» à Dijkstra serait pondérée pour toutes sortes de choses, les coûts / péages, les préférences d'autoroute, les limites de vitesse - utiliser uniquement la distance n'est que l'approche niave la plus simple. C'est ce qui rend l'algorithme si intelligent
Martin Beckett
6
Bien que Dijsktra fera l'affaire, je choisirais généralement A * pour tout travail d'orientation sérieux; l'heuristique aidera beaucoup.
Mircea Chirea
6
Lien: Un algorithme de recherche * . C'est une extension de la méthode de Dijkstra.
mgkrebbs
Tant qu'il y aura une heuristique applicable, A * sera supérieur à Dijkstra (en termes de performances).
bummzack
Une heuristique admissible serait quelque peu difficile à trouver ici étant donné que nous semblons prendre en compte de nombreux facteurs (tels que les embouteillages).
pwny
16

Oui. L'algorithme de Dijkstra résoudra ce problème.

Le problème dans votre cas est que vous supposez automatiquement que le chemin le plus court équivaut à la distance parcourue, alors qu'en fait il correspond de manière plus appropriée au COÛT de prendre un itinéraire.

Si un chemin a un barrage routier, son COÛT doit être plus élevé et l'algorithme s'applique toujours.

maple_shaft
la source
Ouais désolé si je n'ai pas utilisé le bon libellé. Ce que je veux dire, c'est «l'itinéraire le plus pratique» (coût le plus
bas
11

Vous devriez simplement pouvoir remplacer votre distance par le temps entre les nœuds et la résoudre de la même manière.

DKnight
la source
10

Dijkstra

Comme dit précédemment, il n'est pas seulement utilisé pour la distance la plus courte. Je crois que cette animation donne une bonne compréhension du "pouvoir" (faute d'un meilleur mot) de Dijkstra:

Dijkstra

Dynamique
la source