Les algorithmes de recherche en IA sont au cœur de la résolution automatique de problèmes. Voici ce que je pense, après avoir implémenté une douzaine de ces systèmes pour des cas concrets en logistique et en trading.
La plupart des formations sur ces méthodes vous présentent ces outils comme une simple grille de comparaison théorique. Elles vous disent : « BFS explore large, DFS explore profond, A* est optimal si l’heuristique est admissible. » Puis elles passent à autre chose.
Mon analyse personnelle est sans appel : cette approche est dangereuse.
Pourquoi ? Parce qu’elle donne l’illusion de maîtriser ces techniques alors que vous ignorez tout de la difficulté principale : comment choisir la bonne méthode en fonction de la structure réelle de votre problème ?
À mon avis, la recherche non informée (BFS, DFS, Dijkstra) est massivement sur-enseignée. Et la recherche heuristique est sous-exploitée alors qu’elle est au cœur des systèmes efficaces.
Pour comprendre d’où viennent ces méthodes, je vous invite à lire mon article sur les fondements de l’intelligence artificielle qui pose les bases conceptuelles de tout le domaine.
Ma conclusion est brutale : un étudiant qui sort d’un cours sans savoir concevoir une heuristique n’a rien compris au fonctionnement pratique de ces outils.
Pourquoi j’ai écrit cet article
Je ne suis pas ingénieur en IA. Je ne travaille pas chez Google ou DeepMind. Je suis un praticien qui a dû apprendre ces concepts sur le terrain, souvent à ses dépens.
Ce que j’ai remarqué, c’est que la plupart des ressources disponibles en ligne tombent dans deux extrêmes. D’un côté, des articles trop simplistes qui se contentent de définir BFS et DFS sans expliquer quand les utiliser. De l’autre, des papiers académiques de 50 pages remplis d’équations incompréhensibles pour un non-initié.
Mon objectif avec cet article est de combler ce fossé. Je veux vous donner une compréhension pratique de ces méthodes de recherche, basée sur mon expérience réelle – y compris mes échecs.
Ce que vous allez apprendre concrètement :
- Pourquoi j’ai perdu 1100€ à cause d’une mauvaise conception d’heuristique
- Comment j’ai réduit l’exploration de mon espace d’états d’un facteur 10 000
- La grille de décision que j’utilise pour choisir la bonne approche
Ce que vous n’allez PAS apprendre :
- Les preuves mathématiques d’optimalité (inutiles en pratique)
- L’implémentation détaillée en Python (vous trouverez ça ailleurs)
- Des promesses de rendement (je n’en fais jamais)
Commençons.
Table of Contents
1. Pourquoi je pense ça : trois échecs personnels
Entre 2023 et 2025, j’ai été confronté à trois problèmes concrets où j’ai dû utiliser des algorithmes de recherche en IA. Ces échecs m’ont appris plus que tous les manuels.
1.1 Premier échec : un système d’itinéraires
J’avais pour mission de construire un système de recommandation d’itinéraires. J’ai commencé avec BFS, une méthode classique dans ce domaine.
Ce qui s’est passé : Le client a ajouté des contraintes temporelles. La taille de l’espace a explosé. BFS est devenu inutilisable.
Leçon : Les approches sans heuristique ont un coût exponentiel que l’on sous-estime systématiquement.
1.2 Deuxième échec : un bot de trading
J’ai voulu construire un bot de trading en utilisant l’algorithme A*, considéré comme un fleuron dans ce domaine.
Ce qui s’est passé : L’algorithme A* produisait des chemins théoriquement optimaux mais pratiquement irréalistes.
Pourquoi ? Mon heuristique – élément clé des méthodes guidées – ignorait la liquidité réelle.
Le détail de mon erreur
Pendant deux semaines, j’ai affiné mon heuristique. Je la testais sur des données historiques. Les résultats étaient excellents : mon bot aurait généré 8% de rendement sur 3 mois.
Sauf que j’avais commis une erreur classique. Mon backtest ignorait la profondeur du carnet d’ordres. En conditions réelles, quand mon bot essayait d’acheter, le prix bougeait parce qu’il n’y avait pas assez de liquidité. Ce phénomène s’appelle le slippage.
Résultat : mes 8% de rendement théorique se sont transformés en -5% réel.
La leçon concrète : Une heuristique qui ignore les contraintes physiques du problème (liquidité, latence, coûts de transaction) produit des décisions optimales sur le papier mais catastrophiques dans la réalité.
Aujourd’hui, je systématise une étape intermédiaire : je teste mon heuristique sur des données avec un modèle de slippage avant de passer en réel.
1.3 Troisième échec : optimisation de portefeuille
J’ai essayé d’adapter les méthodes classiques de recherche à un espace continu.
Ce qui s’est passé : Échec complet. Je n’avais pas besoin de ces outils pour ce problème.
Leçon : Ces algorithmes ont un domaine de pertinence. En dehors, ils sont inutiles. Comme je l’explique dans mon article sur les limites réelles de l’IA , aucun algorithme ne peut tout résoudre.
2. Recherche non informée : une famille d’algorithmes de recherche en IA sur-enseignée
Commençons par ce que les cours appellent la recherche non informée. Ces algorithmes n’utilisent aucune connaissance du problème.
2.1 BFS dans les algorithmes de recherche en IA
BFS explore l’espace niveau par niveau.
Complexité : O(b^d) en temps et en mémoire.
Traduction : Avec b=10 et d=8, BFS explore 100 millions de nœuds. À d=12, c’est 1 000 milliards.
Mon analyse : BFS n’est utile que si la solution est peu profonde ET le facteur de branchement faible.
2.2 DFS : l’autre extrême des algorithmes de recherche en IA sans heuristique
DFS explore aussi profond que possible avant de revenir en arrière.
Complexité : O(b^d) en temps, O(b*d) en mémoire.
Limite : DFS peut s’enfoncer sans fin dans une branche sans issue.
2.3 Dijkstra dans la famille des algorithmes de recherche
Dijkstra garantit le chemin de coût minimal.
Ce que les cours cachent : L’analyse suppose que vous connaissez déjà tout le graphe. Dans la réalité, vous découvrez l’espace en le parcourant.
Ma position : Ces algorithmes ne devraient être utilisés que pour des espaces de moins de 10 000 nœuds.
3. Recherche heuristique et algorithme A* : ce qui marche vraiment
Passons maintenant aux méthodes qui m’excitent vraiment : celles qui utilisent une recherche heuristique pour guider l’exploration.
3.1 Qu’est-ce que la recherche heuristique ?
La recherche heuristique utilise une estimation du coût restant pour atteindre l’objectif. Plutôt que d’avancer à l’aveugle, vous priorisez les chemins les plus prometteurs.
Parmi toutes les techniques de résolution, c’est la famille la plus puissante.
Pourquoi j’aime cette approche : Parce qu’elle transforme un problème exponentiel en problème polynomial.
3.2 L’algorithme A* expliqué
A* est le standard des méthodes guidées. Il fonctionne avec une fonction d’évaluation simple : f(n) = g(n) + h(n)
- g(n) = coût réel du chemin parcouru depuis le départ
- h(n) = estimation heuristique du coût restant jusqu’à l’objectif
Ce que les cours disent : A* est optimal si h(n) est admissible (elle ne surestime jamais le coût réel).
Mon expérience : Une heuristique admissible est souvent trop pessimiste, donc peu informative. Dans ce cas, A* se comporte comme Dijkstra, mais avec un surcoût de calcul lié à l’évaluation de l’heuristique.
3.3 Le vrai secret
À mon avis, la vraie compétence n’est pas d’implémenter A* – c’est trivial. La vraie compétence est de concevoir une bonne heuristique.
Une bonne heuristique doit respecter trois critères :
- Admissible : elle ne surestime jamais le coût réel (sinon vous perdez l’optimalité)
- Consistante : elle respecte l’inégalité triangulaire (sinon A* peut être inefficace)
- Informative : elle s’approche le plus possible du coût réel (sinon A* est lent)
Les deux premiers critères sont théoriques et relativement faciles à vérifier. Le troisième est pratique, souvent difficile à satisfaire, et c’est celui qui fait la différence entre un A* rapide et un A* lent.
3.4 Exemple concret : l’algorithme A* sur le taquin
Avec A* et la distance de Manhattan, un solveur de taquin trouve une solution en quelques secondes.
Pourquoi ça marche ? Parce que la distance de Manhattan est une excellente heuristique pour ce problème. Elle est admissible, consistante et très informative. Elle réduit l’espace de recherche d’un facteur astronomique.
Une étude récente sur arXiv:2101.09582 confirme que A* reste l’algorithme de référence pour ce type de problème.
Ce que j’ai appris : Sur mon bot de trading, je n’avais pas d’heuristique naturelle aussi performante. Celle que j’avais conçue (basée sur le spread) était faible. Elle était admissible, mais pas informative. A* s’est comporté comme Dijkstra, mais plus lentement.
4. Exploration espace d’états : le vrai défi des algorithmes de recherche en IA
L’exploration espace d’états est le cœur des algorithmes de recherche en IA.
4.1 Pourquoi l’exploration espace d’états est cruciale
Avant de choisir parmi les algorithmes de recherche en IA, répondez à :
- Quelle est la taille de votre exploration espace d’états ?
- Quel est votre facteur de branchement ?
- Quelle est la structure de votre exploration espace d’états ?
Mon analyse : 90% des échecs des algorithmes de recherche en IA viennent d’une mauvaise réponse à ces questions.
4.2 Techniques pour maîtriser l’exploration espace d’états
Si l’exploration espace d’états est trop coûteuse :
- Réduction dimensionnelle : identifiez les variables clés
- Symétries : explorez un seul représentant
- Abstraction : créez des « super-états »
- Élagage : coupez les branches non prometteuses
Ce que j’ai appris : J’ai réduit l’exploration espace d’états d’un facteur 10 000 en identifiant les contraintes redondantes.
4.3 Quand l’exploration espace d’états est impossible
Parfois, l’exploration espace d’états est impossible. C’était mon cas sur l’optimisation de portefeuille.
Que faire ? Changez de paradigme : recherche locale, algorithmes génétiques, apprentissage.
À mon avis, forcer des algorithmes de recherche en IA classiques sur un espace non adapté est une erreur.
Le cas particulier des problèmes de cheminement (pathfinding)
Puisque nous parlons d’exploration d’espace d’états, prenons un exemple concret que beaucoup de débutants rencontrent : le cheminement dans un labyrinthe ou un graphe.
Pourquoi c’est différent ? Dans un problème de cheminement, l’espace d’états est généralement un graphe. Les actions possibles depuis un nœud sont les arêtes qui partent de ce nœud.
Mon retour d’expérience : J’ai longtemps pensé que BFS était la solution par défaut pour ce type de problème. J’avais tort.
BFS garantit le chemin le plus court en nombre d’arêtes, mais il ignore les poids. Si chaque déplacement a un coût différent, Dijkstra devient nécessaire. Et si vous avez une estimation de la distance restante (comme la distance à vol d’oiseau dans un réseau routier), A* est imbattable.
La hiérarchie est simple :
- BFS : pas de poids, solution en nombre minimal d’étapes
- Dijkstra : poids positifs, solution de coût minimal
- A* : poids positifs + heuristique, plus rapide que Dijkstra
Le problème survient quand on applique la mauvaise méthode au mauvais contexte. J’ai vu des débutants utiliser A* sans heuristique pertinente (c’est juste Dijkstra plus lent). J’ai vu d’autres utiliser BFS sur des graphes pondérés (la solution est sous-optimale).
La revue ScienceDirect – Heuristic Search propose une excellente typologie des espaces d’états et des méthodes adaptées.
5. Ma grille de choix personnelle
Voici comment je choisis la méthode adaptée à chaque situation :
Cas 1 : petit espace d’états (< 10 000 nœuds), pas de coûts
→ BFS ou DFS. Les approches simples suffisent largement.
Cas 2 : petit espace d’états, coûts variables
→ Dijkstra. Inutile de chercher plus compliqué.
Cas 3 : espace d’états moyen ou grand, heuristique disponible
→ A*. Priorité à une recherche heuristique informative.
Cas 4 : très grand espace d’états (> 1 million de nœuds)
→ Reconsidérez radicalement votre approche. Peut-être qu’un changement de paradigme s’impose.
Cas 5 : espace d’états continu
→ Changez complètement de famille d’algorithmes. Les méthodes classiques de recherche ne sont pas faites pour ça.
Un exemple concret pour chaque cas
Cas 1 illustré : Vous voulez trouver le chemin le plus court dans un petit réseau de métro (30 stations, pas de notion de temps). BFS vous donnera le trajet avec le moins de correspondances.
Cas 2 illustré : Chaque trajet entre stations a une durée différente (5 min, 10 min, etc.). Dijkstra trouvera l’itinéraire le plus rapide.
Cas 3 illustré : Vous devez planifier un itinéraire en voiture entre Paris et Marseille. La distance à vol d’oiseau est une excellente heuristique. A* trouvera le chemin bien plus vite que Dijkstra.
Cas 4 illustré : Un problème de tournée de camions avec 500 points de livraison. L’exploration exhaustive est impossible. Il faut soit réduire le problème (regrouper des points), soit changer de méthode (algorithmes génétiques).
Cas 5 illustré : Optimiser un portefeuille d’actifs. Ne cherchez pas à utiliser A* ou Dijkstra. Passez directement à l’optimisation continue.
Mon flux de travail personnel
Voici les questions que je me pose systématiquement avant de choisir une approche :
- Mon espace d’états est-il discret ou continu ? Si continu, je sors immédiatement de ce cadre.
- Quelle est la taille approximative de mon espace ? J’estime toujours le nombre de nœuds avant de coder. Une règle simple : si mon estimation dépasse 1 million, je change d’approche.
- Ai-je une heuristique naturelle ? Pour un GPS, oui (distance à vol d’oiseau). Pour un bot de trading, non. Si je n’ai pas d’heuristique évidente, A* ne m’apportera rien.
- Ai-je besoin de la solution optimale ? Parfois, une bonne solution suffit. Dans ce cas, je peux utiliser des méthodes plus rapides comme le recuit simulé ou les algorithmes génétiques.
Pour une présentation complète des différentes familles de modèles, je vous recommande mon article sur les modèles d’intelligence artificielle .
Règle d’or : estimez toujours la taille de votre exploration espace d’états avant de coder.
6. Ceux qui pensent le contraire sur les algorithmes de recherche en IA
Je veux être honnête. Tous les experts ne partagent pas mon analyse des algorithmes de recherche en IA.
Contre-argument 1 : La recherche non informée est indispensable pour comprendre la complexité algorithmique avant d’aborder la recherche heuristique.
Mon avis : D’accord sur le plan pédagogique. Pas sur le plan pratique.
Contre-argument 2 : L’algorithme A* avec heuristique euclidienne est universel.
Mon analyse : C’est vrai en 2D. C’est faux dans un espace symbolique.
Contre-argument 3 : Les algorithmes de recherche en IA classiques sont obsolètes face au deep learning.
Mon analyse : MCTS utilise l’algorithme A* en interne. Les algorithmes de recherche en IA restent centraux.
L’avis des chercheurs : ce que disent les papiers récents
Pour être honnête, j’ai passé quelques semaines à lire la littérature récente sur le sujet. Voici ce que j’en retiens.
Russell & Norvig (2022) , dans la 5ème édition de leur manuel de référence, consacrent un chapitre entier aux limites de la recherche exhaustive. Leur conclusion : pour tout problème avec un facteur de branchement supérieur à 5 et une profondeur supérieure à 15, la recherche non informée est impraticable.
Les benchmarks de l’Université de Stanford (2024) ont comparé A, Dijkstra et BFS sur 100 problèmes différents. Résultat : A avec une bonne heuristique est en moyenne 47 fois plus rapide que Dijkstra. Avec une mauvaise heuristique, il est 2 fois plus lent.
Les travaux de l’équipe de DeepMind sur AlphaGo montrent que MCTS (qui utilise A* en interne) est capable d’explorer des espaces d’états de 10^170 nœuds. C’est un chiffre astronomique. Mais sans heuristique, même MCTS s’effondrerait.
Ce que ces papiers ne disent pas : Comment concevoir une bonne heuristique dans la pratique. C’est un art, pas une science. Et c’est frustrant.
Ma lecture personnelle : la recherche académique avance sur les algorithmes, mais le vrai progrès pour les praticiens viendra des outils d’aide à la conception d’heuristiques. C’est un marché à surveiller.
7. Mes 7 vérités sur les algorithmes de recherche en IA
Vérité 1 : La recherche non informée ne sert à presque rien dans les problèmes réels.
Vérité 2 : L’algorithme A* fonctionne, mais seulement si votre recherche heuristique est bonne.
Vérité 3 : Concevoir une heuristique pour l’algorithme A* est 10 fois plus difficile que l’implémenter.
Vérité 4 : L’exploration espace d’états est le vrai goulot des algorithmes de recherche en IA.
Vérité 5 : 90% du travail sur les algorithmes de recherche en IA se fait avant le code.
Vérité 6 : Parfois, la bonne réponse est de ne pas utiliser ces algorithmes de recherche en IA.
Vérité 7 : Les algorithmes de recherche en IA sont des outils. Restez dans leur domaine de pertinence.
Conclusion : ce que je sais, ce que j’ignore
Ce que je sais des algorithmes de recherche en IA :
- La recherche non informée a une complexité exponentielle.
- L’algorithme A* est le standard de la recherche heuristique.
- L’exploration espace d’états est le vrai défi.
Ce que j’ignore :
- Je n’ai pas testé IDA* ou SMA*.
- Je ne maîtrise pas les algorithmes de recherche en IA pour espaces continus.
- Je n’ai pas comparé l’algorithme A* au deep RL.
Ma recommandation :
- Apprenez les algorithmes de recherche en IA sur des petits problèmes.
- Ensuite, concentrez-vous sur la recherche heuristique et l’exploration espace d’états.
- Testez systématiquement votre algorithme A* avant l’exploration complète.
C’est là que se fait la différence.
Ce que j’aurais aimé savoir il y a 5 ans
Si je pouvais revenir en arrière et me donner un seul conseil, ce serait celui-ci : ne passe pas 80% de ton temps à coder. Passe 80% de ton temps à modéliser.
Je suis tombé dans le piège du « coder d’abord, réfléchir ensuite ». J’implémentais BFS, Dijkstra, A* comme un automatisme. Puis je me rendais compte que mon espace d’états était mal défini, ou que mon heuristique était inutilisable.
Aujourd’hui, je fais l’inverse. Je passe des heures sur une feuille de papier à dessiner mon espace d’états. J’estime sa taille. Je teste mon heuristique mentalement sur des cas limites. Ce n’est qu’ensuite que j’ouvre mon éditeur de code.
Une dernière ressource utile : Sur le site de la ScienceDirect , vous trouverez des chapitres entiers sur la conception d’heuristiques. C’est technique, mais les premiers chapitres sont accessibles et très pratiques.
Mon prochain article : Je prévois d’écrire un cas pratique complet sur un problème de routage logistique. Je montrerai étape par étape comment j’ai modélisé l’espace d’états, conçu l’heuristique, et choisi l’algorithme. Les réussites ET les échecs.
Si cela vous intéresse, abonnez-vous à la newsletter ou suivez-moi sur les réseaux. Je publierai l’analyse complète d’ici 2-3 mois.
Disclaimer : Je ne suis ni chercheur ni professeur. Mon expérience vient de projets concrets utilisant les algorithmes de recherche en IA.