Optimisation d'un trajet [Fermé]

Signaler
Messages postés
1
Date d'inscription
lundi 21 juin 2010
Statut
Membre
Dernière intervention
21 juin 2010
-
Messages postés
3245
Date d'inscription
jeudi 23 août 2007
Statut
Membre
Dernière intervention
19 mai 2013
-
Bonjour,

Existe-t-il un programme donnant le trajet minimal entre différentes villes dont on connait la distance entre chacune d'elle ? j'aimerai bien connaitre cet algorithme...

1 réponse

Messages postés
3245
Date d'inscription
jeudi 23 août 2007
Statut
Membre
Dernière intervention
19 mai 2013
633
l'algorithme exact existe et est calculable : le premier et le plus connu est l'algorithme de Dijkistra. https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
(je préfère l'article en anglais personnellement : https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ). Il est un peu long à calculer, mais il est tout de même à temps polynomial. Il y en a d'autres et en général ils fonctionnent à peu près de la même manière.

mais dans les jeux en temps réels par exemple, il est quand même trop long et on utilise divers algorithmes d'approximation à la place. ils marchent en général très bien et très vite mais ils peuvent avoir quelques problèmes dans certains cas.
1
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 65492 internautes nous ont dit merci ce mois-ci