5. Profondeur, largeur et Dijkstra

5. Profondeur, largeur et Dijkstra

5.1 Recherche en profondeur d’abord

Les enfants sont ajoutés au début de OUVERTS. La collection agit comme une pile : la recherche descend le plus loin possible dans une branche, puis revient au dernier embranchement encore ouvert.

Dans l’exemple pédagogique à neuf nœuds, l’ordre est a,b,e,f,c,g,h,d,i.

Selon le cadre présenté dans le cours, elle est exacte, complète lorsque l’espace est fini et les boucles détectées, non optimale, et son temps est O(n) lorsque chaque nœud est visité une fois. Le cours présente aussi un espace O(n) en tenant compte des structures conservées et de la récursivité.

5.2 Recherche en largeur d’abord

Les enfants sont ajoutés à la fin de OUVERTS. La collection agit comme une file : tous les états d’un niveau sont développés avant ceux du niveau suivant.

Dans le même exemple, l’ordre est a,b,c,d,e,f,g,h,i.

Dans le cadre générique du cours, elle est exacte et complète, mais qualifiée de non optimale. Son temps est O(n) dans le parcours exhaustif présenté et son espace dépend de la largeur maximale w, soit O(w). À l’extérieur de ce cadre, la largeur est optimale en nombre d’arcs lorsque tous les arcs ont le même coût; il ne faut pas généraliser cette propriété à des coûts variables.

5.3 Dijkstra

Dijkstra cherche les plus courts chemins depuis un sommet initial dans un graphe à poids positifs.

1. attribuer la distance 0 au sommet initial et ∞ aux autres;
2. sélectionner le sommet non visité de plus petite distance provisoire;
3. pour chaque voisin, calculer une distance candidate par le sommet courant;
4. remplacer l’ancienne distance si la candidate est plus petite;
5. marquer le sommet courant comme visité;
6. poursuivre jusqu’à stabilisation ou jusqu’au traitement du but.

Dans l’exemple de A à E :

• depuis A : B=7, D=15;
• depuis B : C=11, E=23;
• depuis C : D=13, E=14;
• depuis D : le détour vers E coûterait 22, donc E=14 demeure.

Le chemin optimal est A → B → C → E, de coût 14. L’ordre de traitement peut être A,B,C,D,E, mais D n’appartient pas au chemin optimal. Il faut toujours distinguer :

• la liste des états visités ou développés;
• le chemin solution reconstruit;
• le coût de ce chemin.