Recherche de chemin


Définition

La recherche de chemin, couramment appelée pathfinding consiste à trouver comment se déplacer dans un environnement entre un point de départ et un point d’arrivée en prenant en compte différentes contraintes.

Définition d’un graphe valué
Un graphe valué est un graphe aux arcs desquels on associe un nombre réel appelé longueur de l’arc.
On notera w(x,y) la longueur de l’arc (x,y) entre les sommets x et y.
Par analogie avec la matrice d’adjacence, on peut représenter un graphe valué par une matrice carrée, dont les coefficients correspondent à la valuation des arcs.
Soit un graphe valué dont on a numéroté les sommets de 1 à n . La matrice de valuation de G est la matrice carrée M =mij,de taille n*n, définie par
13
En voici un exemple :
14
Nous pouvons donc en déduire le programme linéaire suivant, avec xij=1 si l’arc fait parti du plus court chemin, 0 sinon :
  • minimize \sum_{ij \in A} w_{ij} x_{ij} avec A l’ensemble des arcs
  • subject to x \ge 0

and for all i, \sum_j x_{ij} - \sum_j x_{ji} = \begin{cases}1, &\text{if }i=s;\\ -1, &\text{if }i=t;\\ 0, &\text{ otherwise.}\end{cases}

Bien qu’il s’agisse de programmation linéaire, cette méthode peut être très couteuse en mémoire, et même impossible à mettre en place dans certains cas (par exemple s’il s’agit d’un système distribué). Une autre méthode pour connaitre le plus court chemin serait de connaitre le plus petit de tous les chemins d’un sommet vers un autre.
On définit le poids d’un chemin c=(u,…,v)
comme la somme des poids des arcs qui le constituent noté w(c).On définit alors la distance minimum (plus court chemin) entre deux sommets u et v par :
12

Nous aimerions disposer d’une méthode capable, pour tout graphe et pour toute paire de sommets x et y, de déterminer le plus court chemin entre eux. Pour cela, nous devons comprendre et de caractériser au mieux la structure d’une solution : quelles sont les propriétés d’un plus court chemin ?

Lemme de Koenig. Un plus court chemin entre 2 sommets est élémentaire. Un chemin est élémentaire si chacun des sommets du parcours est visité une seule fois.

Parmi tous les chemins reliant x à y, choisissons ainsi un chemin comportant le moins d’arêtes. Supposons par l’absurde que p n’est pas élémentaire. Il existe alors un sommet z apparaissant au moins 2 fois le long du chemin. Soient i et j les 2 premiers indices tels que et :

Pour obtenir une contradiction, il suffit de supprimer le cycle entre et . Alors est un chemin, reliant x à y. Sa longueur est strictement inférieure à celle de p, ce qui contredit notre choix de p comme étant un plus court chemin

Le fait d’énumérer tous les chemins pour déterminer le plus court révèle un grave défaut : son temps d’exécution. Si le nombre de chemins élémentaires est bien fini, il n’en demeure pas moins très grand, de l’ordre de n! sur un graphe d’ordre n.

Nous avons besoin d’une seconde propriété, fondamentale, la sous-optimalité (voir Programmation Dynamique). Il s’agit de remarquer qu’être un plus court chemin est récursif : une séquence d’un plus court chemin est encore un plus court chemin entre ses extrémités. Ou encore si le trajet le plus rapide entre u et v passe par 2 sommets x et y, ce trajet emprunte nécessairement le plus court chemin entre x et y.

Si p=(u,…,v) est un plus court chemin entre u et v, alors pour tout sommet x sur le chemin p :

  • le sous-chemin de p jusqu’à x, (u,…,x), est un plus court chemin de u à x
  • le sous-chemin de p depuis x, (x,…,v), est un plus court chemin de x à v

Par l’absurde supposons qu’il existe par exemple entre u et x un chemin q de longueur strictement inférieur à celle de p=(u,…,x,…,v). Alors nous pouvons construire un nouveau chemin p’ entre u et v en substituant q sur (u,…,x) dans le chemin p. La longueur de p’ est alors strictement inférieure à celle de p, ce qui contredit que p est un plus court chemin de u à v.

Publicités