Problèmes de cheminement
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de  |
Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
Les problèmes de cheminement sont des problèmes classiques de la théorie des graphes. L'objectif est de calculer une route entre des sommets d'un graphe qui minimise ou maximise un certaine fonction économique.
Le problème le plus classique consiste à chercher le chemin qui minimise la somme des valuations des arêtes traversées. Il existe des algorithmes polynomiaux pour résoudre ce problème, comme l'algorithme de Dijkstra. En revanche, lorsqu'on ajoute des contraintes supplémentaires comme des fenêtres de temps, le problème devient NP-difficile.
[modifier] Algorithmes de résolution du problème classique de plus court chemin
Lorsque le graphe ne comporte pas de cycle, on utilisera l'algorithme de Bellman. Lorsque les valuations sont positives, l'algorithme le plus couramment utilisé est l'algorithme de Dijkstra. Pourtant, il semble que la méthode dite en anglais threshold method, proposée par Glover, Glover et Klingman en 1984, est plus efficace en pratique, même si sa complexité est supérieure.
[modifier] Algorithmes de résolution du problème de plus court chemin avec fenêtres de temps
Plusieurs algorithmes ont été proposés pour résoudre ce problème.
