Cette page débute par une application permettant de parcourir des graphes ou de calculer des chemins entre des paires de sommets. Les différentes problématiques et les algorithmes utilisés sont détaillés dans la suite de la page.
Pour utiliser l'application : sélectionner un graphe, sélectionner un algorithme, le cas échéant, déplacer des sommets du graphe puis cliquer sur deux sommets pour démarrer.
Quelques définitions Un graphe (non-orienté) est la donnée d'un ensemble non-vide de sommets, et d'un ensemble d'arêtes, i.e. de couples de sommets. Deux sommets reliés par une arête sont dit voisins.
On peut de plus se munir d'une application de l'ensemble des arêtes dans $\mathbb{R}^+$ - on parle dans ce cas de graphe pondéré.
Les graphes interviennent dans de très nombreux domaines
de l'informatique. Il va être question ici d'algorithmes
de parcours (ou exploration) de graphes, permettant par
exemple de trouver un sommet, ou un chemin entre deux
sommets.
Voici une première tentative :
Parcours sans mémoire On se donne un sommet initial $S_i$, et un sommet cible
$S_c$.
Initialisation : $S \leftarrow S_i$.
Tant que $S\neq S_c$
$S \leftarrow $ un voisin de
$S$.
La question est de savoir comment on choisit le voisin de $S$.
On peut le choisir de façon déterministe -
par exemple en prenant le «premier» voisin (en
supposant que les voisins sont ordonnés entre eux). Dans ce cas, on court le risque d'entrer dans une
boucle infinie, et de ne jamais atteindre $S_c$. On dit que l'algorithme n'est pas complet. Vous pouvez tester cela avec l'algorithme «sans
mémoire, déterministe» de l'application.
On peut le choisit de façon aléatoire - en
tirant au sort l'un des voisins. On peut alors montrer que,
dans le cas d'un graphe ayant un nombre fini de
sommets, on finira par atteindre $S_c$ avec
probabilité 1 (s'il est accessible à partir de $S_i$. Sinon, l'algorithme va tourner indéfiniment, et on ne peut pas décider quand l'arrêterSi l'on décide d'arrêter au bout d'un certain nombre d'itérations, on court de le risque de s'arrêter trop tôt, et de rater $S_c$ dans des cas où il est accessible..). L'algorithme est donc complet - c'est
d'ailleurs un exemple où ajouter de l'aléatoire dans
un algorithme permet de le faire fonctionner. Mais le nombre d'itérations avant de l'atteindre peut être très important. Vous pouvez tester cela avec l'algorithme «sans
mémoire, aléatoire» de l'application. L'étude du temps moyen pour atteindre $S_c$ n'est pas évidente, et relève de l'étude des marches aléatoires sur les graphes, proches des chaînes de Markov.
On parle de processus sans mémoire car à tout
moment, l'évolution de l'algorithme ne dépend que du
présent, et pas du passé. En particulier, rien n'interdit
que l'algorithme repasse plusieurs fois par les mêmes
sommets, ce qui est inefficace. De plus, ces processus ne
permettent pas de renvoyer un chemin entre le sommet
initial et le sommet cible, car il ne s'en «souvient» pas.
Il parait donc souhaitable de disposer d'algorithmes
conservant une mémoire des sommets déjà explorés. Nous allons
utiliser le code couleur suivante pour les sommets dans la
suite.
Sommet blanc : pas encore exploré.
Sommet gris : à explorer. (on parle de frontière pour l'ensemble des sommets gris)
Sommet noir : déjà exploré.
Le schéma général des algorithmes étudiés dans cette
section est le suivant.
Algorithme général de parcours avec mémoire
On se donne un sommet initial $S_i$, et un sommet cible
$S_c$.
Colorier $S_i$ en gris (à explorer), et tous les autres sommets en blanc (non-explorés).
Tant qu'il reste des sommets gris :
Choisir un sommet gris // (1)
Le colorier en noir (exploré)
Si c'est $S_c$, l'algorithme se termine par un succès.
Colorier tous ses voisins blancs en gris (à explorer)
L'algorithme se termine par un échec ($S_c$
n'a pas été trouvé).
Un tel algorithme parvient toujours à trouver le sommet
cible $S_c$ si celui-ci est accessible.
Supposons le sommet $S_c$ accessible à partir de
$S_i$. Raisonnons par l'absurde, et supposons que
$S_c$ n'est pas trouvé par l'algorithme - i.e. qu'il
n'est pas colorié en noir à la fin de l'exécution.
Par hypothèse, il existe un chemin reliant $S_c$ à
$S_i$. Comme l'algorithme est terminé, il ne peut y
avoir de sommet gris sur ce chemin - les sommets y
sont donc noirs ou blancs. Comme $S_i$ est noir et
$S_c$ blanc, il existe sur le chemin deux sommets
voisins dont l'un est noir ($S$) et l'autre blanc ($S'$). C'est absurde, car au moment où $S$ a été colorié en noir, $S'$ a été colorié en gris, et n'a pas pu être recolorié en blanc par la suite.
Le choix du sommet gris dans la ligne $(1)$ va faire
la différence entre les différents algorithmes décrits
ci-dessous - que vous pouvez tous tester dans l'application.
Du parcours au chemin
Une fois mis en place un algorithme de parcours avec
mémoire, on peut le modifier pour obtenir un chemin (s'il
existe) du sommet initial vers le sommet cible.
Pour cela, à chaque fois qu'un sommet est colorié en gris, on va enregistrer son sommet père, i.e. le sommet en cours d'exploration. Une fois le sommet cible atteint, il suffira de remonter les pères jusqu'au sommet initial pour obtenir un chemin reliant la cible au sommet initial.
Algorithme de calcul de chemin
On se donne un sommet initial $S_i$, et un sommet cible
$S_c$.
Colorier $S_i$ en gris (à explorer), et tous les autres sommets en blanc (non-explorés).
Tant qu'il reste des sommets gris :
Choisir un sommet gris $S$
Le colorier en noir (exploré)
Si c'est $S_c$, renvoyer le chemin obtenu en remontant les pères de $S_c$ jusqu'à $S_i$.
Pour chaque voisin blanc $V$ de $S$
colorier $V$ en gris (à explorer)
$père(V)\leftarrow S$
L'algorithme se termine par un échec ($S_c$
n'a pas été trouvé).
Parcours de graphes non-pondérés
Parcours en profondeur
Les sommets gris sont stockés dans une structure de pile :
le sommet gris choisi est le dernier ajouté à la pile
(dans l'application, la pile apparait à côté du
nombre de sommets gris).
Lorsqu'on a atteint le sommet cible, la pile contient un chemin entre le sommet initial et celui-ci.
On montre facilement que la complexité de cet
algorithme est $O(nv)$ (où $n$ est le nombre de
sommets du graphe, et $v$ le nombre maximal de voisins
d'un sommet), ou encore $O(p)$ où $p$ est le nombre
d'arêtes.
Cet algorithme peut se prêter à une implémentation récursive (on peut alors se passer de la coloration en gris).
Parcours en profondeur récursif
On se donne un sommet initial $S_i$, et un sommet cible
$S_c$. On appelle alors la fonction suivante avec $S_i$ comme paramètre :
Parcours à partir de $S$
Si $S=S_c$, renvoyer vrai.
Colorier $S$ en noir. //marquer comme exploré
Pour chaque voisin blanc $S'$ de $S$
Appeler récursivement le parcours à partir de $S'$
Si le résultat de ce parcours est vrai, renvoyer vrai (sinon, continuer l'exécution de la boucle).
Les sommets gris sont stockés dans une structure de file :
le sommet gris choisi est le premier ajouté à la file.
On peut alors montrer que les sommets sont parcourus
de façon «concentrique» par rapport à $S_i$ :
d'abord les sommets voisins, puis les voisins des
voisins (i.e. ceux qui sont à distance 2), etc. Testez
par exemple un parcours en largeur de $F$ à $I$ sur le
graphe jouet à 9 sommets de l'application.
Au fil des itérations, on peut mettre à jour les
distance à $S_i$ de la façon suivante.
Initialement, $S_i$ a une distance 0
À chaque fois que l'on colorie un sommet en
gris, on met sa distance à $d+1$, où $d$ est la
distance du sommet courant.
On peut alors facilement trouver un plus court chemin (c'est-à-dire ayant un nombre minimal d'arêtes)
entre $S_i$ et $S_c$ en partant de $S_c$ (à distance
$d$), et en remontant vers un sommet ayant une
distance $d-1$. On recommence jusqu'à ce que l'on
arrive à $S_i$. (Ce qui est équivalent à construire un chemin à partir de la cible en suivant les pères, comme expliqué ci-dessus.)
On montre facilement que la complexité de cet
algorithme est $O(nv)$ (où $n$ est le nombre de
sommets du graphe, et $v$ le nombre maximal de voisins
d'un sommet), ou encore $O(p)$ où $p$ est le nombre
d'arêtes. Il parvient toujours à trouver le sommet
cible $S_c$ si celui-ci est accessible, et comme on
l'a vu, permet de calculer des cartes de distances et
des plus courts chemins.
Implémentation en Python
Le fichier ci-dessous contient des implémentations commentées en Python des
algorithmes de parcours en profondeur et largeur, ainsi
que des versions correspondantes permettant d'obtenir des
chemins.
parcoursgraphenonpondere.py
Parcours de graphes pondérés
Nous nous plaçons maintenant dans une situation où les arêtes possèdent une longueur -
et où l'on cherche à calculer un plus court chemin entre deux
sommets - c'est-à-dire un chemin dont la somme des longueurs
des arêtes est minimale. Dans les exemples de l'application,
la longeur des arêtes est simplement leur longueur
euclidienne (i.e. géométrique), mais ça n'est pas toujours le cas.
Le parcours en largeur répond au cas
particulier où les arêtes sont toutes de même longueur, mais
on se convainc facilement qu'il n'est pas suffisant dans le
cas général ! Voir par exemple un parcours en largeur sur cet exemple : en cherchant en largeur un chemin de A à D, on trouve ABCD, qui n'est pas optimal (AFGHD est plus court, mais est raté car il comporte plus d'arêtes).
Algorithme de Dijkstra
La structure de données utilisée pour stocker les sommets gris est une file de priorité. Chaque
sommet gris y est stocké avec une priorité, en
l'occurrence la distance du plus court chemin trouvé pour
l'instant entre $S_i$ et ce sommet. À chaque itération, on
sélectionne le sommet gris de priorité minimale.
Algorithme de Dijkstra
On se donne un sommet initial $S_i$, et un sommet cible
$S_c$.
Colorier $S_i$ en gris //(à explorer), et tous les autres sommets en blanc //(non explorés). Mettre $S_i$ dans une file de priorité initialement vide, avec la distance $d(S)=0$
Tant qu'il reste des sommets gris :
Choisir un sommet gris $S$ de priorité minimale.
Le colorier en noir //exploré
Si c'est $S_c$, l'algorithme se termine par un succès.
Pour chaque voisin $S'$ de $S$
Si $S'$ est blanc, le colorier en gris, l'ajouter à la file de priorité avec une distance $d(S')=d(S)+l(SS')$, où $l(SS')$ désigne la longueur de l'arête reliant $S$ à $S'$. Poser $père(S')=S$. // On a trouvé un chemin de $S_i$ à $S'$, passant par $S$.
Si $S'$ est gris, comparer $d(S')$ et $d(S)+l(SS')$. Si $d(S)+l(SS') < d(S')$, poser $d(S')=d(S)+l(SS')$ et $père(S')=S$. //On avait déjà trouvé un chemin de $S_i$ à $S'$, mais on vient d'en trouver un plus court passant par $S$.
L'algorithme se termine par un échec ($S_c$
n'a pas été trouvé).
Lorsqu'un sommet $S$ est colorié en noir, sa distance est
la longueur d'un plus court chemin entre $S_i$ et $S$. Un
tel plus court chemin est obtenu en suivant les «pères» à
partir de $S$. Preuve. L'algorithme
de Dijkstra permet donc de calculer des chemins optimaux
entre des sommets.
Sa complexité dépend de l'implémentation de la file de priorité. L'implémentation classique - pas tas permet
de réaliser toutes les opérations nécessaires (trouver le
sommet prioritaire, ajouter un sommet à la file de
priorité, mettre à jour la priorité d'un sommet) en un
temps au plus $O(\log(n))$, où $n$ est la longueur de la
file. On montre alors que la complexité de l'algorithme de
Dijkstra est quasi-linéaire, plus précisément en
$O((1+v)n\log(n))$ ou encore $O((p+n)\log(n))$, où $n$ est le
nombre de sommets du graphe, $v$ le nombre maximal de
voisins d'un sommet, et $p$ le nombre d'arêtes.
On suppose avoir une structure de file de priorité où les insertions, extraction de l'élément de priorité minimale, mise à jour d'une priorité s'effectue en temps $O(\log(n))$.
Chaque sommet est ajouté et extrait au plus une fois de la file de priorité. Le coût total des ajouts et extractions est donc $O(n\log(n))$.
Le nombre de mise à jour est majoré par $vn$. Donc le coût total des mises à jour est $O(vn\log(n))$.
On en déduit la complexité annoncée.
À noter que si la structure de priorité est implémentée à l'aide d'un tas de Fibonacci, on obtient une complexité $O(1)$ pour la mise à jour (et l'insertion), ce qui se traduit par une complexité $O(n\log(n)+vn)$ pour l'algorithme.
Dernière remarque sur le sujet, il existe des algorithme basés sur Dijkstra permettant de calculer des plus courts chemins dans des espaces continus et non plus sur les graphes. Voir par exemple cette page.
Algorithmes informés
Nous nous intéressons maintenant à des situations où l'on
peut guider les algorithmes pour calculer plus rapidement
un (plus court) chemin entre deux sommets. Dans les
exemples de l'application, les longueurs des arêtes sont
les longueurs euclidiennes. On peut donc utiliser la
distance euclidienne d'un sommet au sommet cible $S_c$
pour guider l'exploration plus rapidement vers $S_c$.
Best-first (Meilleur en premier)
Commençons par l'idée la plus simple. Reprenons le schéma général d'algorithme de parcours avec mémoire,
et en $(1)$, choisissons comme sommet gris celui qui est le plus proche (à vol d'oiseau) de $S_c$, le sommet cible.
L'algorithme est une variante d'une famille d'algorithmes appelé «best-first», i.e. meilleur en premier.
Testez-le sur un graphe aléatoire. Cet algorithme permet très rapidement d'obtenir un chemin entre les deux sommets cliqués, mais on constate que ce chemin n'est généralement pas du tout optimal.
Testez-le sur un graphe représentant une carte avec obstacles - en cliquant à droite et en dessous du «passage» sur la gauche, puis tout en bas à gauche. L'algorithme s'entête dans une direction qui ne va pas permettre de franchir l'obstacle, et il y a donc un grand nombre d'itérations qui paraissent inutiles.
Beam search (Recherche en faisceau)
Best-first étant trop glouton, Beam search en est
une tentative d'amélioration, basé sur un parcours en largeur.
À chaque fois que l'on termine l'exploration
de tous les sommets d'une profondeur donnée, on ne va
conserver que $n_{lim}$ sommets gris (où $n_{lim}$ est un
entier «petit», fixé à 3 dans l'application), les autres
étant à nouveau coloriés en blancs. Les $n_{lim}$ sommets
choisis sont ceux qui sont le plus proche à vol d'oiseaux
de la cible. Il s'agit donc d'une version du parcours en
largeur où l'on limite la taille du front de sommets gris.
Cet algorithme limite l'utilisation de la mémoire par rapport au best-first présenté ci-dessus, mais n'est pas completIl en existe cependant des variantes complètes. (i.e. il n'y a pas de
garantie qu'un sommet cible accessible sera trouvé) ni
optimal.
Algorithme A*
A* est un mélange d'algorithme de Dijkstra et de Best-first.
Il est guidé, comme Best-first, pour atteindre plus rapidement le sommet cible $S_c$.
Mais il s'appuie sur l'algorithme de Dijkstra, ce qui permet de garantir l'optimalité du chemin obtenu.
Le voici détaillé. Apparaissent en rouge les différences avec l'algorithme de Dijkstra.
Algorithme *
On se donne un sommet initial $S_i$, et un sommet cible
$S_c$.
Colorier $S_i$ en gris //(à explorer), et tous les autres sommets en blanc //(non explorés). Mettre $S_i$ dans une file de priorité initialement vide, avec la distance $d(S)=0$
Tant qu'il reste des sommets gris :
Choisir un sommet gris $S$ de priorité minimale.
Le colorier en noir (exploré)
Si c'est $S_c$, l'algorithme se termine par un succès.
Pour chaque voisin $S'$ de $S$
Si $S'$ est blanc, le colorier en gris, poser $d(S')=d(S)+l(SS')$ et ajouter $S'$ à la file de priorité avec une priorité $d(S')$$+d_C(S')$, où $l(SS')$ désigne la longueur de l'arête reliant $S$ à $S'$, et $d_C(S')$ est la distance euclidienne entre $S'$ et $S_c$ . Poser $père(S')=S$. // On a trouvé un chemin de $S_i$ à $S'$, passant par $S$.
Si $S'$ est gris, comparer $d(S')$ et $d(S)+l(SS')$. Si $d(S)+l(SS') < d(S')$, poser $d(S')=d(S)+l(SS')$, mettre à jour la priorité de $S'$ dans la file (à la valeur $d(S')$ $+d_C(S')$) et $père(S')=S$. //On avait déjà trouvé un chemin de $S_i$ à $S'$, mais on vient d'en trouver un plus court passant par $S$.
L'algorithme se termine par un échec ($S_c$
n'a pas été trouvé).
$d_C(S')$ est une appelé une heuristique :
c'est une fonction qui guide vers $S_c$ en modifiant l'ordre des sommets gris dans la file de priorité, de façon à «avantager» les sommets proches de la cible. Ici, c'est une
distance euclidienne, mais cela pourrait être remplacé par
une autre fonction $h(S')$ - nous verrons des exemples pertinents
plus tard. Considérons deux cas extrémaux :
Si l'on prend une heuristique $h(S')=0$, on retombe sur l'algorithme de Dijkstra - non-guidé.
Si l'on prend une heuristique $h(S')=\lambda d_C(S')$, où $\lambda$ est «grand», on se rapproche de Best-first : la priorité d'un sommet dépendra essentiellement de sa proximité avec $S_c$. Le choix du paramètre $\lambda$ permet donc de régler un compromis entre le fait de trouver un chemin rapidement ($\lambda$ grand), et le fait d'obtenir un plus court chemin (on peut montrer que cela se produit si et seulement si $\lambda\leq 1$). L'algorithme ainsi obtenu pour un paramètre $\lambda>1$ se nomme WA* (pour Weighted A*).
Si l'on pouvait prendre comme heuristique $h(S')$ la longueur du plus court chemin entre $S'$ et $S_c$, on montre que l'algorithme trouverait directement le chemin optimal (il serait guidé de façon parfaitement précise). C'est bien sûr impossible en pratique, vu que l'on cherche justement à calculer des plus courts chemins...
La version $h(S')=d_C(S')$ apparait donc comme une version
équilibrée, facilement calculable, et intuitive dans le
sens où $d(S)+l(SS')+d_C(S')$ est la meilleure évaluation
actuelle de la longueur d'un chemin de $S_i$ à $S_c$
passant par $S$ et $S'$.
On peut montrer que la condition pour qu'une heuristique donne un algorithme A* qui
calcule des chemins optimaux est que pour tous sommets
voisins $S$ et $S'$, $$h(S)\leq l(SS')+h(S')\ \ \ \ \ \ \text{(condition de monotonie)}$$
Pour notre choix de $h(S)=d_C(S)$, il s'agit d'une
inégalité triangulaire, qui est bien vérifiée.
On montre assez facilement que la condition de monotonie implique une condition appelée admissibilité (dans le cas - raisonnable - où l'heuristique du sommet cible est nulle),
qui affirme qu'une heuristique ne surestime pas le coût
pour atteindre le but - i.e. que $h(S)$ n'est jamais
supérieur à la longueur du plus court chemin entre $S$ et
$S_c$.
Testez cet algorithme sur l'application, d'abord sur un graphe jouet pour le voir se dérouler étape par étape, puis sur un graphe aléatoire.
La complexité de l'algorithme A* est la même
que celle de l'algorithme de Dijkstra (hors surcoût
éventuel lié au calcul de la fonction heuristique. Dans
notre cas, elle se calcule en temps constant).
La preuve d'optimalité des chemins trouvés par A* est non-triviale, et peut être trouvée dans l'article A Formal Basis for the Heuristic Determination of Mimimum Cost Paths,
de Hart, Nilsson et Raphael.
Algorithmes à mémoire limitée
Nous avons pour l'instant abordé les temps d'exécution
(complexité temporelle) des algorithmes, leur optimalité
(l'algorithme trouve-t-il toujours un plus court chemin ?),
mais pas l'occupation mémoire, i.e. la complexité
spatiale.
Si le graphe que l'on parcourt est déjà en mémoire, il n'y
a pas vraiment de question à se poser. Les structures
utilisées dans les algorithmes ci-dessus (piles, files,
files de priorité) n'auront jamais plus d'éléments que le
nombre de sommets du graphe, et ne seront donc pas un
facteur limitant en mémoire.
Mais il y a de nombreux problèmes d'exploration où le
graphe n'est pas en mémoire : il est calculé au fur
et à mesure. Peut-être est-il trop gros pour tenir en
mémoire, peut-être même a-t-il un nombre infini de
sommets ! Deux exemples.
Considérons un taquin en $n\times n$. Le nombre d'états possibles est $(n^2)!$ - dont seulement la moitié sont accessibles depuis la position à atteindreCela se montre à coup d'étude de groupes de permutations.. Pour $n=3$, on obtient 181440 états accessibles - et il est encore possible de les loger en mémoire (un état est une suite de 9 chiffres entre $0$ et $8$, et peut donc être codé sur $9\times 4=36$ bits, ce qui donne environ 800Ko pour stocker l'ensemble des états). Pour $n=4$, le nombre d'états accessibles est environ $10^{13}$ et il faudrait environ $50 To$ pour stocker ces états, ce qui commence à être moins raisonnable. La page suivante permet de tester les différents algorithmes de parcours décrits sur cette page sur des exemples de taquin.
Aux échecs, en début de partie, chaque joueur à le choix entre environ une trentaine de coups (un peu moins au premier coup). Si l'on veut explorer toutes les séquences de coups possibles jusqu'au 10ème (ce qui est une profondeur assez faible), on peut faire apparaitre environ $30^{10}$ positions (sans compter les positions atteintes par plusieurs séquences de coups), dont l'ordre de grandeur est $10^{15}$.
De façon générale, pour un jeu donné, si à chaque étape il y a $b$ coups possibles (on parle de facteur de branchement de $b$), le nombre de séquences de $n$ coups sera $b^n$ (le nombre de positions accessibles est plus faible si certaines positions peuvent être atteintes par plusieurs séquences de coups). L'application montre des exemples de graphes obtenus pour un facteur de branchement 2 et une profondeur 9 (2047 sommets), et un facteur de branchement 3 et une profondeur 6 (3280 sommets).
Dès que $b$ ou $n$ est grand, il devient irréaliste de stocker l'ensemble du graphe en mémoire.
Les algorithmes du style parcours en largeur ou
algorithme de Dijkstra vus ci-dessus vont également être
impraticables pour le même type de raisons : ils nécessitent
pour fonctionner de stocker d'une façon ou d'une autre la
frontière constituée des sommets gris. Si l'on explore un
graphe avec un facteur de branchement $b$, il y a de
l'ordre de $b^n$ sommets à distance $n$ de $S_i$, qu'il va
être impossible de stocker.
On va assister ici à une revanche de l'algorithme
de recherche en profondeur (ou plutôt de variantes
sur ce thème), dont l'utilité était à présent sujette à
caution. L'idée de départ est qu'un parcours en profondeur
nécessite de garder en mémoire moins de sommets à explorer
(les sommets gris de la frontière) qu'un algorithme de
parcours en largeur. Testez par exemple un parcours en
largeur sur un arbre en cliquant sur la racine puis sur un sommet
tout à droite à mi-hauteur, et la même chose avec un
parcours en profondeur, qui limite drastiquement le nombre de sommets gris lors du déroulement.
Backtracking (Retour arrière)
Les sommets noirs (déjà explorés) posent également
problème et ne peuvent pas tous être mémorisés pour les
raisons expliquées ci-dessus : si l'on explore tout un
arbre de profondeur $n$ avec un facteur de branchement de
$b$, il faudrait pouvoir stocker
$1+b+b^2+\dots+b^n=O(b^n)$ sommets.
Il est en revanche tout à fait envisageable de stocker un
chemin du sommet initial vers un autre sommet : en
effet la longueur d'un plus court chemin entre $S_i$ et un
sommet quelconque est au maximum $n$.
C'est l'idée de l'algorithme de backtracking ou retour arrière. On va effectuer un parcours en profondeur
en ne mémorisant que les sommets situés entre $S_i$ et le sommet courant (sous forme d'une pile);
et en se souvenant, pour tout sommet mémorisé, lesquels de ses voisins ont déjà été explorés.
Voici l'algorithme, où les coloriages sont donnés à titre
indicatif pour faire le lien avec les algorithmes
précédents et l'application, mais ne sont pas nécessaires
à son exécution. On suppose que chaque sommet peut être
muni d'un compteur indiquant quel est le prochain voisin à
explorer.
Backtracking
On se donne un sommet initial $S_i$, et un sommet cible
$S_c$.
Initialisation : on créé une pile vide $P$, et on empile $S_i$.
Tant que la pile $P$ n'est pas vide
$S \leftarrow $ l'élément en tête de la pile.
Si $S=S_c$, c'est terminé, et la pile contient un chemin de $S_i$ vers $S_c$
Sinon
Colorier $S$ en noir
S'il reste des voisins de $S$ à explorer
$S'\leftarrow$ le premier voisin à explorer non dans la pile (non-noir)
Empiler $S'$ sur $P$. //il va donc être traité à la prochaine itération
Sinon//i.e. si tous les voisins ont été exploré
Dépiler $S$, le colorier en blanc.
Si la pile est vide, c'est que $S_c$ n'était pas accessible à partir de $S_i$, on renvoie un échec.
Cliquer pour voir cet algorithme à l'oeuvre sur un graphe jouet (essayez entre H et G) (dans ce premier exemple, vous pouvez observer la pile dans le champs «sommets noirs»),
sur un arbre ou sur un graphe aléatoire. On
observe que l'algorithme se comporte comme un parours en
profondeur, qui, s'il arrive dans une impasse, revient sur
ses pas (d'où son nom) et essaye un chemin qu'il n'a pas
encore essayé.
À tout moment, on stocke uniquement en mémoire les sommets
situés sur le chemin entre $S_i$ et le sommet qui est
au sommet de la pile - et non pas tous les sommets déjà
explorés. L'avantage est qu'on limite l'encombrement
mémoire, mais l'inconvénient est que l'on risque
d'explorer plusieurs fois les mêmes sommets.
On peut montrer que cet algorithme est complet : s'il existe un chemin entre $S_i$ et $S_c$, il sera trouvé.
Cette technique se prête très bien à une implémentation récursive. La version itérative présentée précédemment gère en fait «à la main» la pile d'appels récursifs de la fonction suivante.
Backtracking récursif
On se donne un sommet initial $S_i$, et un sommet cible
$S_c$. On appelle alors la fonction suivante avec $S_i$ comme paramètre :
Backtracking à partir de $S$
Si $S=S_c$, renvoyer vrai.
Sinon, si $S$ est noir, renvoyer faux. //déjà exploré
Colorier $S$ en noir
Pour chaque voisin blanc $S'$ de $S$
Appeler récursivement le backtracking à partir de $S'$
Si le résultat de cet appel est vrai, renvoyer vrai (sinon, continuer l'exécution de la boucle).
Colorier $S$ en blanc
Renvoyer faux
Les coloriages sont laissés pour faire le lien avec
les algorithmes précédents, mais ici aussi seront
avantageusement gérés par une
pile. «Colorier en noir» se traduira par «empiler» et
«Colorier en blanc» par «dépiler». Dans tous les cas,
on évitera de maintenir une structure de taille
proportionnelle au nombre de sommets pour coder les
couleurs : on perdrait alors l'avantage en terme
de complexité spatiale du backtracking !
Cette méthode va typiquement être adapté à des problèmes de satisfactions de contraintes très structurés, où il n'y a pas de risque de boucler dans l'espace des états - rendant inutile la gestion des couleurs ou de la pile. Voir par exemple le problème des perles de Dijkstra, le problème des $n$ dames ou encore l'algorithme DPLL permettant de tester la satisfiabilité d'une formule logique - problème auquel se ramènent de nombreux autres problèmes.
Backtracking avec profondeur limitée incrémentale
Le backtracking a des inconvénients similaires à ceux du parcours en profondeur :
Il ne trouve pas nécessairement le chemin le plus court.
Il peut mettre beaucoup de temps à sortir d'une impasse dans laquelle il s'est engagé. Testez-le sur un graphe représentant une carte avec obstacles - en cliquant sur le sommet juste en dessous du sommet tout en haut à gauche, puis tout en bas à droite. L'algorithme va entrer dans le cul de sac en bas à gauche et va mettre un temps très long à en sortir.
Si on a un graphe très grand, voire infini, il
risque de générer un chemin très profond dans le
graphe, et de finalement saturer la mémoire ou de ne pas trouver
la cible $S_c$, qui n'était peut-être pas très éloignée du point de départ $S_i$.
Pour y remédier, on peut recycler une idée issue du parcours en largeur :
Backtracking avec profondeur limitée incrémentale
On se donne un sommet initial $S_i$, et un sommet cible
$S_c$.
On commence par lancer un backtracking depuis $S_i$, mais en limitant la profondeur des chemins à 1. Si l'on a trouvé $S_c$, c'est terminé. Sinon
On relance un backtracking depuis $S_i$ en limitant la profondeur des chemins à 2. Si l'on a trouvé $S_c$, c'est terminé. Sinon
On relance un backtracking depuis $S_i$ en limitant la profondeur des chemins à 3. Si l'on a trouvé $S_c$, c'est terminé. Sinon
Etc.
L'exploration se fait donc de façon concentrique.
On est ainsi assuré de trouver un chemin minimal en terme de nombre d'arêtes, et - dans le cas d'un graphe infini - que l'algorithme ne va pas se fourvoyer dans une branche infinie.
Testez le principe sur un graphe aléatoire, en cliquant sur des points séparés par 4 ou 5 arêtes, ou sur un arbre, en cliquant sur la racine et sur un sommet situé tout à droite.
L'inconvénient est que lorsque l'on relance un nouveau
backtracking, on refait l'exploration précédente en la
poussant plus loin. C'est le prix à payer pour le gain de
mémoire, et ce prix n'est en fait pas très cher en temps : si l'on explore un arbre ayant un facteur de branchement de $b$, le premier backtracking va explorer $1+b$ sommets, le deuxième $1+b+b^2$, le troisième $1+b+b^2+b^3$. Jusqu'au $n$ème, on aura donc exploré au total $O(b+b^2+b^3+\dots b^n)=O(b^n)$ sommets, et au $n+1$ème, on en explorera $b^{n+1}$, ce qui est du même ordre de grandeur. Les explorations déjà faites ne pèsent donc pas asymptotiquement sur la complexité de l'algorithme.
IDA*
Les algorithmes décrits précédemment permettent de réduire
l'occupation mémoire mais sont impraticables du point de vue de la
complexité temporelle si l'espace à explorer est très grand et avec un facteur de branchement important. Il
existe cependant des versions guidées (comme A*) de ces algorithmes, permettant de les orienter vers la cible et de les rendre efficaces en pratique. C'est le cas de l'algorithme IDA* (pour Iterative Deepening A*),
qui combine les différentes idées vues dans cette page.
Son principe est très proche de celui du backtracking avec profondeur limitée incrémentale. La
différence est que la quantité limité n'est plus la
profondeur d'exploration, mais la quantité $d(S)+h(S)$ (avec les notations définies dans la section sur A* - $f$ étant l'heuristique utilisée.
La limite $l$ est initialement mise à $h(S_i)$, et lorsque tous
les sommets $S$ vérifiant $d(S)+h(S)\leq l$ ont été
parcourus, celle-ci prend comme nouvelle valeur le minimum
des $d(S')+h(S')$, où $S'$ parcourt l'ensemble des
voisins des sommets parcourus (n'ayant pas eux même été
parcourus).
L'espace mémoire utilisé par l'algorithme IDA* est
comme pour le backtracking très faible (un seul chemin
depuis le sommet initial étant mémorisé à chaque instant),
et l'on peut montrer qu'il trouve un chemin optimal.
Cet algorithme n'est pas implémenté sur cette page, car sur des graphes avec la distance euclidienne comme heuristique, l'augmentation de la limite sera très lente, chaque sommet risquant d'avoir un $d(S)+h(S)$ différent (et donc à chaque augmentation de limite, on risque de n'explorer qu'un sommet de plus). Vous pourrez en revanche le tester sur la page du taquin -
où les $d(S)+h(S)$ prennent des valeurs entières et
«petites», ce qui rend son utilisation nettement plus pertinente.
(O)SMA*
SMA* est un algorithme à mémoire limité publié
en 1992 dont l'idée est d'utiliser toute la mémoire
disponible. En effet, IDA* utilise trop peu de mémoire, ce qui
l'oblige a effectuer des réexplorations très nombreuses et
pose problème du point de vue du temps d'exécution.
Les explications accompagnant SMA* (pour Simplified MA* -
son prédécesseur) ne m'ont pas permis de coder précisément
cet algorithme et de me persuader qu'il était correct -
trop de détails étant passés sous silence.
J'ai codé un algorithme très proche dans l'esprit, mais
qui me parait plus clair à comprendre - que j'appelle (O)SMA* (pour Over Simplified
MA*).
L'idée générale est de faire un parcours A*, et lorsque la mémoire est pleine (en pratique que le nombre de sommets en mémoire dépasse un nombre fixé dès le départ), les sommets moins prometteurs vont être supprimés pour pouvoir poursuivre l'exploration à des endroits plus prometteurs. L'implémentation est un peu délicate, et le détail en est fourni en annexe.
Il peut être testé sur un graphe jouet (de A à D), avec des limites de mémoire de 4 ou 5, ou sur un graphe aléatoire peu connecté, en cliquant sur un coin et environ au milieu du graphe.
Lemme 1
On considère un graphe i.e. où il existe un chemin allant de tout sommet à tout autre sommet.connexe,
et un sommet $S_i$. Pour tout sommet $S$, on note $U(S)$
la longueur du plus court chemin de $S_i$ à $S$. On note
$l(SS')$ la longueur d'une arête $SS'$. Alors
$U(S_i)=0$
Pour tout $S\neq S_i$, $U(S)=min_{S'\text{ voisin de }
S}U(S')+l(S'S)$.
Le premier point est immédiat. Pour le second, on
considère $S\neq S_i$.
Pour tout voisin $S'$ de $S$,
$U(S')+l(S'S)\geq U(S)$. En effet
$U(S')+l(S'S)$ est la longueur d'un chemin de
$S_i$ vers $S$ (dont l'avant dernier sommet
est $S'$), et cette longueur est donc
supérieure ou égale à celle du plus court
chemin de $S_i$ à $S$. On a donc montré que
$U_S \leq min_{S'\text{ voisin de }
S}U(S')+l(S'S)$
On considère maintenant un plus court chemin
$\mathcal{C}$ de $S_i$ à $S$ (qui est donc de
longueur $U(S')$), et on note $S'$ le sommet
avant $S$ dans ce chemin. La partie du chemin
de $S_i$ à $S'$ est un plus court chemin de
$S_i$ à $S'$ (sinon, $\mathcal{C}$ ne serait
pas un plus court chemin de $S_i$ à $S$), et
sa longueur est donc $U(S')$. On obtient donc
$U(S')+l(SS')=U(S)$. On a donc bien montré
l'égalité
Lemme 2
À tout moment de l'exécution de l'algorithme de Dijkstra,
pour tout sommet gris ou noir $S$, $d(S)\geq U(S)$.
Le résultat est immédiat sur $S$. On montre par une
récurrence facile sur les itérations que partir d'un sommet
gris ou noir $S\neq S_i$ et suivre successivement les pères
jusqu'à $S_i$ donne un chemin de longueur $d(S)$ entre $S_i$
et $S$. $U(S)$ étant la longueur d'un chemin minimal entre
$S_i$ et $S$, on obtient $d(S)\leq U(S)$.
On passe maintenant au plat principal :
À tout moment de l'exécution de l'algorithme, pour
tout sommet $S$ colorié en noir, $d(S) = U(S)$.
On montre que cette propriété est un invariant de boucle :
Elle est vraie avant le premier passage dans
la boucle, aucun sommet n'étant colorié en noir.
Supposons qu'elle est vraie au début d'un
passage dans la boucle, et montrons qu'elle
est toujours vraie à la fin. Il suffit donc de
montrer que, si $S$ est le sommet colorié en
noir à cette itération, $d(S)=U(S)$.
Considérons un sommet $S'$ blanc ou gris
minimisant $U(S')$ parmi les sommets blancs ou
gris. On sait que $U(S')=min_{S''\text{
voisin de } S}U(S'')+l(S''S')$. On en déduit
que $U(S')\geq min_{S''\text{ voisin noir de }
S}U(S'')+l(S''S')$
Considérons l'ensemble des opérations de
mise-à-jour de $S'$ qui ont eu lieu jusqu'à
présent. Pour tous les voisins noirs $S''$ de $S'$,
l'opération $d(S')\leftarrow min(d(S'),
d(S'')+l(S''S'))$ a eu lieu au moment où $S''$ était
colorié en noir. Donc $d(S')= min_{S''\text{ voisin
noir de } S'}d(S'')+l(S''S')=min_{S''\text{ voisin
noir de } S'}U(S'')+l(S''S')$ par hypothèse.
On en déduit que $U(S')\geq d(S')$. Le lemme 2 donnant
l'inégalité réciproque, on a donc $U(S')=d(S')$.
Pour tout sommet gris $S''$, $d(S'')\geq U(S'')\geq
U(S')=d(S')$, d'où $d(S'')\geq d(S')$. L'inégalité
est de plus stricte, sauf éventuellement si
$U(S'')=U(S')$. Donc l'ensemble des sommets de
distance évaluée minimale correspond à l'ensemble
des sommets de distance réelle minimale. On en
déduit que le sommet $S$ choisi à cette itération
est de distance réelle minimale. On peut donc
appliquer ce qui précède à $S'=S$, et on obtient
donc $U(S)=d(S)$.
Reste alors à montrer que
l'on obtient un plus court
chemin entre $S_i$ et tout
autre sommet $S$ en
partant de $S$ et en
remontant la liste des
pères. On commence par
remarquer que par
construction, pour tout
$S\neq S_i$,
$d(S)=d(père(S))+l(Spère(S))$,
d'où $U(S)=U(père(S))+l(Spère(S))$, puis si $père(S)\neq S_i$, $U(S)=U(père(père(S)))+l(père(S)père(père(S)))+l(Spère(S))$, etc.
Une récurrence immédiate montre alors que le chemin obtenu en partant de $S$ et suivant la liste des pères jusqu'à $S_i$Pourquoi est-on certain d'arriver jusqu'à $S_i$ ? est de longueur $U(S)$ - c'est donc bien un chemin de longueur minimale par définition de $U(S)$.
L'algorithme (O)SMA*
On fixe un entier strictement positif $mem_{max}$ -
qui correspond au nombre maximal de sommets qui seront en
mémoire à tout moment.
Différentes valeurs vont être stockées à chaque sommet $S$
en mémoire :
La principale est $f$ (appelée $f$-value dans la présentation originale de SMA*), qui correspond à un minorant (certain dans l'état actuel des connaissances) de la longueur minimale d'un chemin du sommet initial vers le sommet cible passant par $S$. Lorsqu'un sommet $S$ est exploré pour la première fois, cette quantité est initialisée à $d(S)+h(S)$ - où $d(S)$ est la distance du plus court chemin du sommet initial à $S$, et $h$ une heuristique monotone (cf les explications sur l'algorithme A*) - donc un minorant du chemin restant de $S$ au sommet cible.
On conserve également un pointeur vers le père de $S$ - comme dans les algorithmes précédents, on disposera donc à tout moment d'un chemin de tout sommet en mémoire vers le sommet initial - et ce chemin est le plus court possible dans l'état actuel des connaissances.
On conserve la distance de ce plus court chemin, ainsi que son nombre d'arêtes (i.e. la profondeur de $S$). Pour gagner encore sur la mémoire, on pourrait envisager de recalculer ces valeurs en remontant les pères jusqu'à $S_i$.
On se souvient des voisins de $S$ qui sont atteints par un plus court chemin ne passant pas par $S$ (et qu'il est donc inutile de réexplorer à partir de $S$).
On conserve enfin des informations sur les fils de
$S$ qui ont été explorés et oubliés (comme nous
allons le voir dans la suite, des sommets sont
oubliés pour pouvoir continuer l'exploration
lorsque la mémoire est pleine). Pour ces sommets,
on les «sauvegarde» dans $S$ en y conservant par
exemple une liste de couples (indice du voisin
oublié, valeur $f$ de ce voisin au moment de
l'oubli).C'est l'une des différences importantes avec SMA*, où n'est stockée qu'une information synthétique pour tous les fils oubliés. Je ne suis pas persuadé que cela soit suffisant pour garantir la correction de l'algorithme. La version que je propose est mieux guidée dans la réexploration des voisins oubliés, mais perd un peu de mémoire pour stocker cette liste.
Dans l'algorithme décrit ci-dessous, lorsqu'on parlera
d'un sommet voisin d'un sommet $S$ (distinct de son père), on dira qu'il
est :
exploré s'il est en mémoire ou s'il s'agit d'un fils oublié de $S$
exploré à partir de $S$ s'il est en mémoire et que son père est $S$,
ou s'il s'agit d'un fils oublié de $S$.
Enfin, on dira qu'un voisin $S'$ de $S$ est améliorable s'il est en mémoire, que son père n'est pas $S$, mais que le chemin actuel du sommet initial à $S'$ est plus long que le chemin passant par $S$ (il s'agit donc d'un sommet qui devra être mis-à-jour, comme dans les algorithmes de Dijkstra ou A*)
On commence par une fonction récursive de «mise à jour»
d'un sommet.
Mettre_à_jour($S$)
Si tous les voisins de $S$ n'ont pas encore été explorés, ou que $S$ a un voisin améliorable, quitter cette fonction sans rien faire.
Sinon $f(S)$ reçoit le minimum des valeurs $f$ de ces voisins explorés à partir de $S$ (on utilise éventuellement les valeurs sauvegardées pour les fils oubliés).
Si $S$ n'est pas le sommet initial, et $f(S)$ a été modifié par cette fonction, Mettre_à_jour(père($S$)).
Algorithme (O)SMA* (avec mémoire illimitée)
Initialisation : mettre le sommet
initial $S_i$ en mémoire. Poser $f(S_i)=h(S_i)$.
Tant que la valeur $f$ du sommet
initial est différente de $+\infty$, choisir
un sommet en mémoire de valeur $f$ minimale, et
parmi ceux de valeur minimale un qui soit de
profondeur maximale. On note $S$ ce sommet.
Si $S$ est le sommet cible, terminer sur un succès.
Si la valeur $f$ est $+\infty$, termine sur un échec.
Si la profondeur de $S$ est égale à $mem_{max} - 1$ (i.e. que le chemin du sommet initial à $S$ utilise toute la mémoire), $f(S)\leftarrow +\infty$, Mettre_à_jour(père($S$)), et passer à l'itération suivante.
Sélectionner un voisin $S'$ à explorer (qui n'est pas le père de $S$, et qui n'a pas déjà été atteint par un plus court chemin passant par ailleurs). Par ordre de préférence, on choisit :
Un voisin pas encore exploré à partir de $S$
Un voisin oublié de valeur $f$ (au moment de l'oubli) égale à $f(S)$ (il s'agit donc du meilleur voisin oublié dans l'état actuel des connaissances)
Si $S'$ n'est pas déjà en mémoire (1)
L'y ajouter
Mettre à jour sa distance à l'origine, sa profondeur, et son père
$f(S')\leftarrow \max(f(S), d(S')+h(S'))$ (le $\max$ avec $f(S)$ apportant de l'information lors de la réexploration d'une branche oublié.)
Mettre_à_jour($S$) (ce qui aura un effet seulement si l'on vient d'explorer le dernier voisin de $S$)
Si $S'$ est déjà en mémoire
S'il n'est pas améliorable, s'en souvenir, et ne rien faire de plus
Sinon, faire comme dans (1) (tout en «corrigeant» ce qui doit l'être concernant l'ancien père $S''$ de $S'$, Mettre_à_jour($S''$)).
Pour obtenir la version avec mémoire limitée $mem_max$,
avant chaque ajout en mémoire d'un sommet à partir d'un
sommet $S$, on vérifie si le nombre de sommets
actuellement en mémoire est égal à $mem_{max}$. Si c'est
le cas, on doit supprimer un sommet de la mémoire. Le
sommet supprimé $S'$ est une feuille (i.e. un sommet qui
n'est le père d'aucun autre sommet) de valeur $f$ la plus
grande possible, et parmi les sommets vérifiant cette
propriété, le plus profond possible. Son père doit être
mis à jour en conséquence (en particulier, comme indiqué
ci-dessus, on s'y souviendra de la valeur $f(S')$ du
sommet supprimé).
Afin de trouver les sommets à explorer et à supprimer rapidement, on peut utiliser des files de priorité.
Cet algorithme est complexe, et son analyse nécessiterait de s'intéresser à des compromis mémoire/vitesse non-triviaux (par exemple, vaut-il mieux utiliser des structures de files de priorité pour trouver le sommet à supprimer - et donc payer un surcoût en mémoire, ou bien payer un coût en temps si l'on n'utilise pas une telle structure ?).