Plus court chemin

Problèmes de cheminement

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.

Sommaire

1 Algorithmes de résolution du problème classique de plus court chemin
2 Présentation théorique des algorithmes de cheminement
3 Liens internes

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.

Présentation théorique des algorithmes de cheminement

Q-semi anneau

Un Q-semi anneau est un triplet $(Q,\oplus,\otimes)$ , Q étant un ensemble non vide, $\oplus$ et $\otimes$ deux lois binaires internes. A 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

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 z=0 et e=1.

Matrice associée à un graphe

É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-anneaux 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

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 $Γ 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 $Γ i, j$ et permet donc de définir le chemin minimal pour cette relation.

Algorithme de Warshall généralisé

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

$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)}\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)}$ où $p=d_{i,j}^{(n)}$ , etc.
On détermine ainsi de proche en proche les divers sommets jusqu'au sommet terminal choisi.

Applications

Détermination des chemins joignant un sommet

On prend l'algèbre de Boole Q={0,1}, $\oplus=\vee$ et $\otimes=\wedge$ . A 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

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

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

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

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 à $τ$ (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'un loi min pondérée entre temps et prix ...). Dans tous les cas, l'algorithme de Dijkstra permet une résolution efficace.

Liens internes

Plus courts chemins à origine unique :

Plus courts chemins pour tout couple de sommets :

Informatique théorique

Théorie du calcul

Calculabilité	Décidabilité et indécidabilité • Ensemble récursif • Problème de l'arrêt • Récursivement énumérable
Modèle de calcul	Automate fini • Automate cellulaire • Machine de Turing • Thèse de Church
Modes de calcul	Concurrence • Parallèlisme • Théorie de l'ordonnancement
Mesure et échelle de complexité	Réduction polynomiale • Problème NP-complet

Logique, syntaxe et sémantique

Logique mathématique	Assistant de preuve • Calcul des prédicats • Correspondance de Curry-Howard • Fonction récursive • Lambda-calcul • Théorème d'incomplétude de Gödel • Théorie des types
Grammaire formelle et systèmes de réécriture	Compilation • Expression rationnelle • Grammaire formelle • Langage rationnel • Théorie des langages
Sémantique	Sémantique des langages de programmation • Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle
Spécifier, vérifier et concevoir des programmes	Interprétation abstraite • Méthodes formelles • Model checking

Algorithmique, complexité et mathématiques discrètes

Algorithmique	Algorithme génétique • Algorithme glouton • Algorithme probabiliste • Complexité algorithmique • Diviser pour régner • Heuristique • Programmation dynamique
Problèmes et algorithmes numériques	Algorithme du simplexe • Géométrie algorithmique • Algorithme d'Euclide • Test de primalité
Problèmes et algorithmes non-numériques	Algorithmes de la théorie des graphes • Arbre (informatique) • Liste (informatique) • Table de hachage • Tas (informatique)
Théorie des graphes	Coloration de graphe • Problèmes de cheminement
Recherche opérationnelle	Optimisation • Optimisation combinatoire • Théorie de l'ordonnancement
Données et codage	Codage • Codage de l'information • Compression de données • Cryptage • Cryptanalyse • Cryptographie • Théorie de l'information

Portail des mathématiques

Ce document provient de « Probl%C3%A8mes de cheminement ».

Catégorie : Théorie des graphes

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Plus court chemin de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

chemin — [ ʃ(ə)mɛ̃ ] n. m. • 1080; du lat. pop. °camminus, mot gaulois I ♦ A ♦ (Concret) 1 ♦ Voie qui permet d aller d un lieu à un autre (⇒ route, voie); spécialt Bande déblayée assez étroite qui suit les accidents du terrain (opposé à route, allée).⇒… … Encyclopédie Universelle
court — court, courte (kour, kour t ; usage variable pour la liaison du t ; les uns disent : un kour espace de temps ; les autres : un kour t espace de temps ; au pluriel, même incertitude pour l s ; quelques uns disant : les kour espaces de temps ; plus … Dictionnaire de la Langue Française d'Émile Littré
court — COURT, COURTE. adj. Qui a peu de longueur. Il est opposé à Long. Trop court. Bien court. Fort court. Un peu court. Extrêmement court. Cheveux courts. Queue courte. Cerises à courte queue. Cheval à courte queue. Il a le cou fort court, le cou… … Dictionnaire de l'Académie Française 1798
court — 1. court, courte [ kur, kurt ] adj. et adv. • 1640; curt 1080; lat. curtus I ♦ Adj. 1 ♦ Qui a peu de longueur d une extrémité à l autre (relativement à la taille normale ou par comparaison avec une autre chose). Herbe courte. ⇒ 3. ras. Avoir les… … Encyclopédie Universelle
COURT — COURTE. adj. Qui a peu de longueur, ou Qui n a pas la même longueur qu une autre chose. Il est opposé à Long. Trop court. Bien court. Fort court. Un peu court. Extrêmement court. Cheveux courts. Queue courte. Cerises à courte queue. Cheval à… … Dictionnaire de l'Academie Francaise, 7eme edition (1835)
court — I. COURT. Courte. adj. Qui n est pas si long qu une autre chose de mesme espece, qui a moins de longueur. Trop court. bien court. fort court. un peu court. extremement court. cheveux courts. queüe courte. le col court. habit court. manteau court … Dictionnaire de l'Académie française
CHEMIN — n. m. Voie, route pratiquée pour communiquer, pour aller d’un lieu à un autre. Chemin battu, frayé. Chemin uni. Chemin pierreux, raboteux, fangeux. Chemin creux. Chemin de traverse. Chemin vicinal, Celui qui va d’une commune à l’autre et qui est… … Dictionnaire de l'Academie Francaise, 8eme edition (1935)
Chemin (théorie des graphes) — Pour les articles homonymes, voir Chemin. Dans un graphe orienté, un chemin d origine x et d extrémité y est défini par une suite finie d arcs consécutifs, reliant x à y. La notion correspondante dans les graphes non orientés est celle de chaîne … Wikipédia en Français
chemin — Chemin, Via, Aditus, Veha. Chemin, ou Ruë, Via. Aisé chemin, Facilis et plana via. Beau chemin où on ne se heurte point, Via inoffensa. Chemin de Paradis, Sacra via. Chemin à quartier, Itinera deuia. Villages qui ne sont pas sur les chemins, Pagi … Thresor de la langue françoyse
plus — [ plys ] adv. • 980; mot lat. « une grande quantité » ♦ Mot servant de comparatif à beaucoup et entrant dans la formation des comparatifs de supériorité et dans celle du superlatif relatif de supériorité. I ♦ (Compar.; cf. aussi III) A ♦… … Encyclopédie Universelle

Dictionnaires et Encyclopédies sur 'Academic'

Plus court chemin

Problèmes de cheminement

Sommaire

Algorithmes de résolution du problème classique de plus court chemin