Page principale

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.

Explications : Parcours en profondeur

Itérations :  Arêtes explorées : 
Sommets noirs :  Sommets gris : 

Table des matières des algorithmes


Parcours de graphes

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 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.
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).
  • Renvoyer faux


Le parcours en profondeur est à la base de nombreux algorithmes importants sur les graphes : détection de
cycle, tri topologique, calcul de composantes fortement connexes.

Parcours en largeur

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. 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$.
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))$. 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.

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. 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 :
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. 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.

A contrario, si l'on ne retient rien, on retombe sur les parcours sans mémoire dont il est question au début de la page.

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 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$
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 : 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.


Applications





Références





Annexes

Correction de l'algorithme de Dijkstra

Commençons par deux lemmes.
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
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 :
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 : On commence par une fonction récursive de «mise à jour» d'un sommet.
Mettre_à_jour($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)
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 ?).