Problèmes de cheminement

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Plus court chemin)
Aller à : navigation, rechercher

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 une 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 de complexité en temps polynomiale pour le résoudre, 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.

Algorithmes de résolution du problème classique de plus court chemin[modifier | modifier le code]

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.

Présentation théorique des algorithmes de cheminement[modifier | modifier le code]

Q-semi anneau[modifier | modifier le code]

Un Q-semi anneau est un triplet (Q,\oplus,\otimes), Q étant un ensemble non vide, \oplus et \otimes deux lois binaires internes. À tout couple (a,b) d'éléments de Q, ces deux lois binaires associent un élément de Q noté respectivement a\oplus b et a \otimes b. La loi \oplus est associative, commutative et admet un élément neutre z. La loi \otimes est associative et distributive par rapport à \oplus. Elle admet un élément neutre e (à gauche et à droite).

Exemple[modifier | modifier le code]

L'algèbre de Boole est un Q-semi anneau en prenant Q={0,1},\oplus=\vee (ou) et \otimes=\wedge(et). Les éléments neutres sont respectivement z=0 et e=1.

Matrice associée à un graphe[modifier | modifier le code]

Étant donné un graphe, on associe à chaque arc un poids qui pourra être une longueur au sens de la théorie des graphes, une distance (au sens métrique), une densité de trafic maximum, ou plus généralement des éléments pris dans un Q-semi-anneau plus ou moins simple selon la nature du problème à traiter. Dans chacun de ces cas, l'ensemble Q sera choisi différemment, pouvant être l'ensemble {0,1}, \mathbb{R}_+, ... On construit alors une matrice A associée au graphe en associant à chaque arc (i,j) l'élément (i,j) de la matrice égal à son poids si l'arc existe et à z s'il n'existe pas.

Chemin optimal[modifier | modifier le code]

Un chemin de longueur d dans le graphe s'écrit comme une suite de sommets k = (k_i)_{i \in [1, d]} du graphe. On peut définir le poids d'un chemin comme le produit des poids des arêtes parcourues : \omega(k) = \bigotimes_{i=1}^{d-1} a_{k_i, k_{i+1}}

Si l'on note \Gamma_{i,j} l'ensemble des chemins reliant i à j, le problème du plus court chemin consiste à minimiser \bigoplus_{k \in \Gamma_{i,j}} \omega(k).

Dans le cas où \oplus = \min et \otimes = +, c'est le poids minimal d'un chemin reliant i à j. En pratique, ce calcul n'a d'intérêt que dans les semi-anneaux sélectifs et idempotents, c'est-à-dire tels que \forall x,y \in Q, x \oplus x = x et x \oplus y \in \{x,y\}, ce qui permet d'effectivement comparer les chemins : on peut dire que k \preceq k' si et seulement si, \omega(k) \oplus \omega(k') = \omega(k), ce qui définit une relation d'ordre total sur \Gamma_{i,j} et permet donc de définir le chemin minimal pour cette relation.

Algorithme de Warshall généralisé[modifier | modifier le code]

P. Robert et J. Ferland ont montré que, étant donné un graphe de matrice associée A d'ordre n, on peut définir :

  • une suite de matrices A^{(k)} par :
A^{(0)}=A et
A^{(k)}=\left(a_{i,j}^{(k)}\right) avec a_{i,j}^{(k)}=a_{i,j}^{(k-1)}\oplus \left(a_{i,k}^{(k-1)}\otimes a_{k,j}^{(k-1)}\right).
Cette suite de matrices est telle que les éléments a_{i,j}^{(n)} de la matrice A^{(n)} sont égaux au poids du chemin de X_i à X_j.
  • une autre suite de matrices D^{(k)} par :
d_{i,j}^{(0)} = \left\{\begin{matrix} j & \mbox{ si } a_{i,j}^{(0)} \neq z \\ 0 & \mbox{ autrement dans } D^{(0)} \end{matrix}\right.
d_{i,j}^{(k)} = \left\{\begin{matrix} d_{i,j}^{(k-1)} & \mbox{ si } a_{i,j}^{(k)} = a_{i,j}^{(k-1)} \\ d_{i,k}^{(k-1)} & \mbox{ sinon } \end{matrix}\right.
Cette suite de matrices est telle que les éléments d_{i,j}^{(k)} ont pour valeur l'indice du premier point intermédiaire du chemin de X_i à X_j à l'étape k.


Il s'ensuit que :

  • d_{i,j}^{(n)} est l'indice p du premier sommet intermédiaire entre X_i et X_j.
  • Le second sommet est donné par d_{p,j}^{(n)}p=d_{i,j}^{(n)}, etc.
  • On détermine ainsi de proche en proche les divers sommets jusqu'au sommet terminal choisi.

Applications[modifier | modifier le code]

Détermination des chemins joignant un sommet[modifier | modifier le code]

On prend l'algèbre de Boole Q={0,1}, \oplus=\vee et \otimes=\wedge. À chaque arc reliant X_i à X_j on affecte le poids 1 et 0 s'il n'existe pas. Après calcul de A^{(n)}, il existe un chemin entre X_i et X_j si le coefficient a_{i,j} est non nul. Le chemin n'existe pas si le coefficient est nul.

Détermination des chemins à densité de trafic maximum entre deux sommets[modifier | modifier le code]

On prend Q=\mathbb{R}_+, \oplus=maximum de deux réels, \otimes=minimum de deux réels. On affecte à chaque arc (X_i,X_j) la densité de trafic maximum si elle existe et 0 autrement. Après le calcul de A^{(n)}, à l'intersection de la ligne i et de la colonne j, a_{i,j}^{(n)} représente la densité de trafic maximum entre i et j.

Détermination de la distance minimum entre deux sommets[modifier | modifier le code]

On prend Q=\mathbb{R}_+, \oplus=minimum de deux réels, \otimes=addition des réels. a_{i,j}^{(n)} représente la distance minimum entre i et j.

Plus court chemin pour des valuations dynamiques[modifier | modifier le code]

Dans certains problèmes de transport, les valuation ne sont pas des scalaires, mais des fonctions, par exemple du temps si l'on veut considérer des fluctuations du trafic. Dans ce cas, il suffit de choisir comme Q-semi-anneau l'ensemble des endomorphismes croissants sur un dioïde (D, \oplus, \otimes) avec pour somme \hat \oplus telle que \forall f,g \in Q, \forall x \in D, (f \hat \oplus g)(x) = f(x)\oplus g(x), et la composition pour produit. Par croissant, on entend que \forall f \in Q, \forall x,y \in D, f(x \oplus y) = f(x) \oplus f(y).

Ainsi, si l'on cherche à trouver le chemin le plus rapide dans un réseau où le trafic est variable en fonction de l'heure de départ, on peut appliquer les algorithmes usuels en valuant chaque route par une fonction donnant l'heure d'arrivée en fonction de l'heure de départ, et en considérant pour \oplus le minimum d'une fonction prise à l'heure de départ.

Plus court chemin avec contraintes temporelles[modifier | modifier le code]

Il arrive, en particulier dans les réseaux de transports en commun, que certains arcs ne puissent être parcourus que dans certaines contraintes horaires. On suppose que les temps de parcours de chaque arête (i,j) est fixé, ainsi qu'un ensemble de plages horaires H_{i,j} où il est possible d'emprunter cette arête. Pour résoudre le problème, on pourra considérer le dioïde des endomorphismes pris sur les intervalles de temps définis ainsi : si D_{i} est l'intervalle de temps où l'on souhaite partir du sommet i, \tau_{i,j}(D_i) = \{d_{i,j} + t | t \in D_i \cap H_{i,j}\} est l'intervalle de temps où il est possible d'arriver au sommet j relié à i. Il est en outre possible d'ajouter facilement d'autres contraintes à \tau (par intersection avec des plages horaires pour éviter certaines périodes, en ajoutant des contraintes de prix par produit cartésien avec la matrice des coûts de transport muni d'une loi min pondérée entre temps et prix ...). Dans tous les cas, l'algorithme de Dijkstra permet une résolution efficace.

Liens internes[modifier | modifier le code]

Plus courts chemins à origine unique :

Plus courts chemins pour tout couple de sommets :