Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations

Les bases de l’intelligence artificielle en images : ce qu’est l’espace d’états, comment fonctionnent BFS, DFS, UCS, la recherche gloutonne et A*, ce qu’est une heuristique et le lien avec l’apprentissage automatique.

14 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 21 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

Quand on parle aujourd’hui d’intelligence artificielle, la plupart des gens pensent aux réseaux de neurones et aux grands modèles de langage. Pourtant, bien avant que les machines n’apprennent à partir de données, elles savaient chercher. La navigation sur une carte, un coup aux échecs, le plan d’un robot dans un entrepôt — tout cela revient à chercher un chemin dans un espace de possibilités. La recherche dans l’espace d’états est le premier chapitre de tout manuel d’intelligence artificielle, et vous en retrouverez les idées dans l’apprentissage automatique : heuristiques, optimisation, recherche de la meilleure solution.

Chaque notion apparaît ici deux fois : d’abord une définition mathématique précise, puis juste en dessous la même chose en termes simples. Toutes les animations sont l’exécution réelle de l’algorithme — rien n’est dessiné à la main.

1. Qu’est-ce que l’espace d’états

Avant de chercher quoi que ce soit, il faut décrire le problème de façon à ce qu’un ordinateur le comprenne. C’est le rôle du problème de recherche :

Définition — problème de recherche

Un problème de recherche est un sextuplet P = (S, s₀, A, T, G, c), où

• S est l’ensemble des états,
• s₀ ∈ S est l’état initial,
• A(s) est l’ensemble des actions applicables dans l’état s,
• T : S × A → S est la fonction de transition ; l’état s′ = T(s, a) est un successeur de l’état s,
• G ⊆ S est l’ensemble des états buts,
• c : S × A → ℝ⁺ est le coût d’une action, toujours positif.

Définition — chemin, solution, optimum

Un chemin de longueur k est une suite s₀, a₁, s₁, …, a_k, s_k, où s_i = T(s_i−1, a_i).

Le coût du chemin est la somme des coûts des actions : g = ∑_i=1^k c(s_i−1, a_i).

Une solution est un chemin qui se termine dans un but : s_k ∈ G. Une solution optimale est une solution de coût minimal ; ce coût est noté C*.

Les états reliés par les actions forment un graphe orienté : les états sont les sommets, les actions des arcs de poids c. Chercher une solution revient donc à trouver dans le graphe un chemin de s₀ vers l’un des sommets de G. L’exemple classique est le taquin à 8 pièces : les pièces 1 à 8 dans un cadre 3 × 3 et une case vide. Un état est la disposition des pièces, une action le déplacement de la case vide, et le but les pièces remises dans l’ordre :

Cela paraît anodin, mais le taquin à 8 pièces compte 181 440 états atteignables, et son grand frère, le taquin à 15 pièces, plus de dix mille milliards. On ne construit donc jamais le graphe en entier à l’avance. L’algorithme le découvre au fur et à mesure — à partir de la fonction de transition, il ne calcule que les successeurs de l’état sur lequel il se trouve.

2. Énoncé : traverser un labyrinthe

Nous allons montrer tous les algorithmes sur le même problème. Nous avons un labyrinthe de 9 × 14 cases et voulons aller du départ au but au moindre coût. D’abord, ce que signifie chaque case :

• Case libre — y entrer coûte 1
• Boue — on peut la traverser, mais y entrer coûte 5
• Mur — on ne peut pas y entrer
• S Départ (start) — l’état initial, la case (0, 0)
• G But (goal) — la case (8, 13)
• Case explorée — l’algorithme l’a développée
• Chemin trouvé — le résultat de l’algorithme

Énoncé formel

Une case s’écrit comme un couple (r, s) — ligne r ∈ {0, …, 8}, colonne s ∈ {0, …, 13}. Notons Z l’ensemble des murs et B l’ensemble des cases de boue.

• États : S = {(r, s) : (r, s) ∉ Z} — toutes les cases sauf les murs.
• État initial : s₀ = (0, 0). But : G = {(8, 13)}.
• Actions : A = {↑, →, ↓, ←}. Une action est applicable dans un état seulement si elle mène à une case de la grille qui n’est pas un mur.
• Transition : T((r, s), →) = (r, s + 1), et de même pour les autres directions.
• Coût : c(x, a) = 5 si T(x, a) ∈ B, sinon 1 — on paie pour la case dans laquelle on entre.
• Tâche : trouver une solution de coût minimal C*.

La boue est placée exprès sur le trajet le plus direct. Nous verrons que tous les algorithmes ne la remarquent pas : certains ne comptent que les pas, d’autres le coût réel.

3. Le squelette commun à tous les algorithmes

Tous les algorithmes de cet article partagent le même squelette. Ils ne diffèrent que par une seule décision.

Définition — frontière, états fermés, développement

La frontière (frontier) F ⊆ S est l’ensemble des états que l’algorithme a déjà découverts mais pas encore développés.

Les états fermés E ⊆ S sont les états déjà développés.

Développer un état s signifie calculer tous ses successeurs {T(s, a) : a ∈ A(s)} et ajouter à F ceux qui ne sont pas dans E.

frontier = [start]
closed = {}
tant que frontier n’est pas vide :
    state = choose_from(frontier)  # ← c’est ici que les algorithmes diffèrent
    si state est le but : terminé
    ajouter state à closed
    pour chaque successeur de state :
        s’il n’est pas encore fermé : l’ajouter à frontier

Toute la différence entre les algorithmes tient en une seule ligne : quel état de la frontière choisir ensuite. Une file, une pile, ou une file de priorité selon un certain nombre. Tout le reste en découle.

4. Parcours en largeur (BFS)

Définition — BFS

La frontière F est une file (FIFO) : on développe l’état qui a été ajouté à F en premier.

Conséquence : les états sont développés par ordre de profondeur d(s) — le nombre d’actions depuis s₀. BFS trouve donc la solution comportant le moins d’actions.

Si b est le facteur de branchement (le nombre maximal de successeurs d’un état) et d la profondeur de la solution la moins profonde, BFS génère au plus b + b² + … + b^d = O(b^d) états et en garde autant en mémoire.

Dans le labyrinthe, l’onde se voit bien — elle se répand dans toutes les directions jusqu’à atteindre le but :

Remarquez toutefois que le chemin passe en plein dans la boue. BFS compte les actions, pas le coût — pour lui, un pas dans la boue vaut un pas sur la terre ferme. Le chemin le plus court fait ainsi 25 pas, mais coûte 37. BFS n’est optimal que si toutes les actions ont le même coût.

from collections import deque

def bfs(start, goal, successors):
    frontier = deque([start])
    parent = {start: None}
    while frontier:
        state = frontier.popleft()          # file : premier entré, premier sorti
        if state == goal:
            return path(parent, goal)
        for nxt in successors(state):
            if nxt not in parent:
                parent[nxt] = state
                frontier.append(nxt)
    return None

def path(parent, state):
    result = []
    while state is not None:
        result.append(state)
        state = parent[state]
    return result[::-1]

5. Parcours en profondeur (DFS)

Définition — DFS

La frontière F est une pile (LIFO) : on développe l’état qui a été ajouté à F en dernier.

Si m est la profondeur maximale de l’espace d’états, DFS ne garde en mémoire que la branche courante et ses voisines : O(b · m) états. Le temps est, dans le pire des cas, O(b^m).

DFS n’est pas optimal et, dans un espace infini, il n’est même pas complet — il peut descendre indéfiniment.

Dans l’arbre, on le voit à l’ordre : A, B, D, H, I — et seulement ensuite E. Dans le labyrinthe :

Ici, DFS a eu de la chance et a atteint le but sans explorer beaucoup de cases. Mais le chemin est inutilement long — 31 pas au lieu de 25, pour un coût de 59.

Définition — approfondissement itératif (IDDFS)

Pour ℓ = 0, 1, 2, … lancer un DFS qui ne développe pas les états plus profonds que ℓ. S’arrêter à la première solution trouvée.

Les états de profondeur i sont générés (d − i + 1) fois, soit au total ∑_i=1^d (d − i + 1) · bⁱ = O(b^d) — autant que BFS, mais avec une mémoire de seulement O(b · d).

6. Recherche à coût uniforme (UCS)

Définition — UCS

Pour un état n, notons g(n) le coût du chemin le moins cher trouvé jusqu’ici de s₀ à n.

La frontière est une file de priorité ordonnée selon g : on développe l’état de plus petit g(n).

Si tous les coûts d’action sont ≥ ε > 0, UCS développe les états par ordre de g croissant (au sens large), et il est donc complet et optimal. Le nombre d’états développés est O(b^{1 + ⌊C*/ε⌋}).

UCS a contourné la boue. Il a trouvé un chemin avec le même nombre de pas que BFS, mais d’un coût de 25 au lieu de 37 — et celui-ci est garanti le moins cher, donc C* = 25. Le prix à payer : il explore à l’aveugle dans toutes les directions. Il ne sait pas où se trouve le but, et se propage donc aussi dans la direction opposée.

7. Heuristique : estimer le chemin vers le but

Les algorithmes ci-dessus sont non informés — du but, ils savent seulement qu’ils le reconnaîtront en marchant dessus. Les algorithmes informés reçoivent en plus une estimation de ce qu’il reste à parcourir.

Définition — heuristique

Notons h*(n) le coût du chemin optimal de l’état n jusqu’au but le plus proche. Une heuristique est une fonction h : S → ℝ_≥0 qui estime h*(n), avec h(n) = 0 pour n ∈ G.

h est admissible si elle ne surestime jamais : ∀n ∈ S : h(n) ≤ h*(n).

h est cohérente (consistante) si pour tout état n, toute action a et tout successeur n′ = T(n, a) on a h(n) ≤ c(n, a) + h(n′). Toute heuristique cohérente est admissible.

Dans notre labyrinthe, la distance de Manhattan s’impose — le nombre de cases à l’horizontale plus à la verticale, comme quand on marche dans les rues à angle droit de Manhattan :

8. Recherche gloutonne

Définition — recherche gloutonne

La frontière est une file de priorité selon f(n) = h(n) : on développe l’état estimé le plus proche du but. Le coût accumulé g(n) n’est pas pris en compte.

La recherche gloutonne n’est pas optimale ; avec détection des états répétés, elle est complète dans un espace fini.

La recherche gloutonne explore peu de cases, mais elle va là où cela semble plus proche, et finit sur un chemin long et coûteux — 31 pas, coût 59.

9. A* : le meilleur des deux mondes

Définition — A*

La frontière est une file de priorité selon f(n) = g(n) + h(n) — l’estimation du coût du chemin complet, du départ au but en passant par n.

Théorème. Si h est cohérente, les valeurs de f ne décroissent pas le long d’un chemin, A* développe les états par ordre de f croissant (au sens large), et le premier état but développé se trouve sur un chemin optimal de coût C*. Ce faisant, il développe tout état tel que f(n) < C* et aucun état tel que f(n) > C*.

Pour h ≡ 0, A* est identique à UCS ; sans g, ce serait la recherche gloutonne.

Même coût de 25 qu’UCS, mais A* a exploré 37 cases au lieu de 49. Dans un petit labyrinthe, cela fait quelques cases d’écart ; sur une carte avec des millions de carrefours, c’est la différence entre une réponse instantanée et une minute d’attente. C’est pourquoi on trouve A* (et ses variantes) dans les GPS, les jeux vidéo et la planification de mouvement des robots.

import heapq

def a_star(start, goal, successors, h):
    frontier = [(h(start), 0, start)]        # (f, g, état)
    g = {start: 0}
    parent = {start: None}
    while frontier:
        _, cost, state = heapq.heappop(frontier)
        if state == goal:
            return path(parent, goal), cost
        if cost > g[state]:
            continue                       # entrée périmée, on connaît déjà moins cher
        for nxt, step in successors(state):
            new = cost + step
            if new < g.get(nxt, float("inf")):
                g[nxt] = new
                parent[nxt] = state
                heapq.heappush(frontier, (new + h(nxt), new, nxt))
    return None

10. Comparaison des algorithmes

Définition — propriétés d’un algorithme

Un algorithme est complet si, pour tout problème qui a une solution, il renvoie une solution.

Un algorithme est optimal si la solution renvoyée a pour coût C*.

b — facteur de branchement, d — profondeur de la solution la moins profonde, m — profondeur maximale de l’espace. O(·) indique comment le temps ou la mémoire croissent avec ces paramètres.

* Dans un espace fini, avec détection des états répétés, ils trouvent toujours une solution. ** Avec une heuristique cohérente.

11. Recherche locale : quand le chemin n’importe pas

Pour certains problèmes, le chemin ne nous intéresse pas — nous voulons seulement un bon état final. Un emploi du temps, le placement de composants sur une carte électronique, le réglage de paramètres.

Définition — recherche locale

On se donne une fonction objectif f : S → ℝ et un voisinage N(s) ⊆ S de chaque état. On cherche s* = argmax_{s ∈ S} f(s).

Un état s est un maximum local si f(s) ≥ f(s′) pour tout s′ ∈ N(s), et un maximum global si cela vaut pour tout s′ ∈ S.

Algorithme de la colline : répéter s ← argmax_{s′ ∈ N(s)} f(s′) tant que f augmente.

Pour éviter de rester bloqué, on utilise le redémarrage aléatoire (lancer le grimpeur depuis différents points), les algorithmes génétiques, qui croisent et font muter toute une population de solutions, ou le recuit simulé :

Recuit simulé

Choisir un voisin aléatoire s′ ∈ N(s) et calculer Δ = f(s′) − f(s). Si Δ > 0, passer à s′ ; sinon, y passer avec la probabilité e^Δ/T, où la « température » T décroît progressivement vers zéro.

Et c’est ici que la boucle se referme avec l’apprentissage automatique. Entraîner un réseau de neurones, c’est faire une recherche locale dans l’espace de ses poids θ : la descente de gradient répète θ ← θ − η ∇L(θ) — un pas de taille η dans la direction où la fonction d’erreur L décroît le plus vite. C’est un grimpeur la tête en bas qui, au lieu du plus haut sommet, cherche la vallée la plus basse — et se heurte aux mêmes problèmes : les minima locaux et les plateaux.

12. En résumé

• Un problème de recherche est un sextuplet (S, s₀, A, T, G, c). Une solution est un chemin dans le graphe des états, la solution optimale est la moins chère.
• Les algorithmes ne diffèrent que par l’état qu’ils choisissent dans la frontière : file (BFS), pile (DFS), plus petit g (UCS), plus petit h (glouton), plus petit g + h (A*).
• BFS trouve le moins de pas, UCS le coût le plus bas, A* le coût le plus bas en explorant le moins — à condition d’avoir une heuristique cohérente.
• Quand ce n’est pas le chemin qui compte mais le résultat, place à la recherche locale — et de là, il n’y a qu’un pas jusqu’à la descente de gradient et l’apprentissage automatique.

Envie de manipuler ces algorithmes vous-même ? Demandez à un agent IA d’écrire votre propre visualisation — puis cherchez dans le code la seule ligne qui les distingue.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.