Partie 1 : Search Fondamental

↑ Série Search | Partie 2 : CSP →

Comment passer d’une énumération exhaustive à une exploration intelligemment guidée d’un espace d’états ? Cette première partie couvre les trois grands paradigmes de la recherche en IA : systématique (BFS, A*), locale (Hill Climbing, recuit simulé) et évolutive (algorithmes génétiques, PSO). Le fil rouge est la réduction progressive de l’espace de recherche, depuis la formalisation du problème jusqu’aux métaheuristiques comparées sur des benchmarks.

Le parcours s’ouvre sur une idée simple et étonnamment puissante : avant de résoudre un problème, il faut le poser. Search-1 montre qu’un taquin, un aspirateur-robot et une recherche d’itinéraire sont un seul et même objet mathématique — un espace d’états (S, A, T, G) — et que cette formalisation suffit à rendre le problème calculable. Search-2 lance alors l’exploration à l’aveugle : BFS garantit l’optimal mais explose en mémoire, DFS file droit mais peut se perdre, et leurs variantes (UCS, IDDFS) négocient chacune un compromis différent entre garantie et coût. Search-3 apporte la réponse classique à cette explosion : une heuristique — une estimation du chemin restant — et l’algorithme A*, dont l’optimalité tient à une propriété fine, l’admissibilité, que le notebook prend le temps d’éprouver plutôt que de la postuler.

Cette formalisation se voit : le monde de l’aspirateur (Search-1) se ramène à un espace d’états de huit nœuds — la position de l’aspirateur croisée à la propreté des deux pièces — reliés par des transitions colorées selon l’action exécutée (aspirer, aller à gauche, aller à droite). C’est ce graphe qu’explorent ensuite tous les algorithmes de la partie.

Espace d’états du monde de l’aspirateur : 8 états en grille, transitions colorées par action

La suite change deux fois de point de vue. Quand seule la destination compte — pas le chemin —, la recherche locale (Search-4) abandonne l’arbre d’exploration pour naviguer de voisin en voisin dans un paysage de fitness, quitte à accepter temporairement de moins bonnes solutions pour s’échapper des optima locaux (recuit simulé, recherche tabou). Les algorithmes génétiques (Search-5) généralisent le procédé : une population entière explore en parallèle, sélection et croisement faisant émerger les bonnes solutions. Et quand l’environnement riposte — un adversaire joue contre vous —, la recherche devient un jeu : Minimax et l’élagage Alpha-Beta (Search-6), puis Monte Carlo Tree Search (Search-7), qui remplace l’évaluation experte par la simulation statistique et mène jusqu’à l’architecture d’AlphaGo.

Trois extensions complètent le panorama. La couverture exacte et les Dancing Links de Knuth (Search-8), structure de données spectaculaire qui résout Sudoku, N-Queens et Pentominoes par simple manipulation de pointeurs. La programmation linéaire (Search-9), qui troque le discret pour le continu et résout en quelques lignes de PuLP des problèmes de transport et de régime alimentaire. Les automates symboliques (Search-10), où les transitions deviennent des prédicats Z3 — premier pont vers l’IA symbolique. Search-11 referme la partie en confrontant les métaheuristiques (PSO, ABC, recuit) sur des benchmarks communs : l’occasion de constater qu’aucune ne domine partout, et d’apprendre à choisir.

Pourquoi cette partie

Cette partie est l’alphabet de toute la série : la formalisation en espace d’états, le backtracking et les heuristiques qu’on y construit sont réutilisés tels quels par la programmation par contraintes (Partie 2) et par les 40 notebooks d’application. Mais son véritable enseignement est un réflexe d’ingénieur : chaque algorithme y est présenté comme un compromis — complétude contre mémoire, garantie contre temps de calcul, exploration contre exploitation — et jamais comme une recette. C’est ce réflexe, plus que tel ou tel algorithme, qui distingue celui qui applique une bibliothèque de celui qui choisit une stratégie.

Objectifs d’apprentissage

À l’issue de cette partie, vous serez capable de :

  1. Formaliser un problème sous forme d’espace d’états (S, A, T, G) et l’implémenter en Python
  2. Choisir l’algorithme de recherche adapté au problème : systématique (BFS, A*), locale (SA, Tabu), ou évolutive (GA, PSO)
  3. Concevoir et évaluer des heuristiques admissibles et consistantes pour guider la recherche
  4. Appliquer la recherche adversariale (Minimax, Alpha-Beta, MCTS) aux jeux à deux joueurs
  5. Comparer les métaheuristiques sur des benchmarks réels et justifier le choix d’un algorithme

Notebooks

# Notebook Kernel Contenu Durée
1 Search-01-StateSpace Python 3 Espaces d’états, formalisation (S, A, T, G), taquin, aspirateur, recherche d’itinéraire ~40 min
1 (.NET) Search-01-StateSpace (C#) .NET (C#) Jumeau .NET : formalisation (S, A, T, G) en C# 9.0 (SearchProblem abstrait, object comme etat generique), VacuumWorld (8 etats, parcours complet), 8-Puzzle (181 440 etats), RouteFinding — port C# fidèle avec Dictionary<TKey,TValue>, tuples nommes ((char pos, bool gSale, bool dSale)) ~40 min
2 Search-02-Uninformed Python 3 BFS, DFS, UCS, IDDFS : comparaison des algorithmes non informés ~50 min
2 (.NET) Search-02-Uninformed (C#) .NET (C#) Jumeau .NET : BFS (Queue), DFS (Stack), UCS (PriorityQueue<TElement, TPriority>), IDDFS — port C# fidèle sur le graphe des villes françaises + arbre profond 8x3 (ratio BFS/DFS = 156,1×) + BFS bidirectionnel avec reconstruction de coût ~50 min
2b Search-02b-NetworkX Python 3 Boîte à outils de graphes networkx : Graph/DiGraph, DFS/BFS, Dijkstra, Bellman-Ford, centralités de degré, composantes connexes, MST, Floyd-Warshall, parité structurelle avec QuikGraph (Search-2c) — matière optionnelle, utile dès la fin de Search-2 ~1h
2b (.NET) Search-02b-NetworkX (C#) .NET (C#) Jumeau .NET : théorie des graphes from-scratch (Dictionary / adjacency list pondérée) — parcours BFS/DFS, plus courts chemins (Dijkstra), centralités, flot maximum (Ford-Fulkerson), exercices (détection de cycles DFS 3 couleurs, A* avec heuristique, communautés Louvain) + tranche 2 QuikGraph (parité lib-vs-lib sur la même instance) — port C# fidèle du notebook Python NetworkX, distinct de Search-2c (QuikGraph, approche library) — parité #4956 ~1h
2c Search-02c-QuikGraph .NET (C#) Bibliothèque de graphes QuikGraph 2.5.0 (NuGet) : AdjacencyGraph / BidirectionalGraph / UndirectedGraph, DFS/BFS, Dijkstra, Bellman-Ford, centralités de degré, composantes connexes, Edmonds-Karp (flot max), parité avec NetworkX ~1h
3 Search-03-Informed Python 3 A, Greedy, IDA, heuristiques admissibles et consistantes ~50 min
3 (.NET) Search-03-Informed (C#) .NET (C#) Jumeau .NET : Greedy Best-First, A* (PriorityQueue), IDA* (iterative deepening, f-limit 791→1055 sur 5 itérations) — port C# fidèle sur le graphe des villes françaises (A* coût 1055 optimal vs Greedy 1210, surcoût 14,7 %, 3 nœuds explorés) + étude admissibilité/consistance sur 8-puzzle ~50 min
3b Search-03b-PatternDatabases Python 3 Pattern Databases (Culberson & Schaeffer 1996), PDB additives (Korf & Felner 2002), 15-puzzle, IDA* — heuristique précalculée admissible ; section 12 « quotienter / fibrer » (op 3 du chantier ICT, #12204) : le fondement informationnel des PDB, mesuré sur un espace énuméré exhaustivement — règle de chaîne exacte, témoin I(X_A;X_B | S_B) = 0 contre 2,071 bits marginaux, contre-témoin du quotient trop grossier, dette Ruzsa (accrétion de Search-3) ~2h
3b (.NET) Search-03b-PatternDatabases (C#) .NET (C#) Jumeau .NET : PDB + additives sur 15-puzzle, port C# from-scratch (BFS rétrograde, 0-1 BFS deque, rang de Lehmer) — parité stricte (accrétion de Search-3) ~1h30
3c Search-03c-LimitedDiscrepancySearch Python 3 Limited Discrepancy Search (Harvey & Ginsberg 1995), sac à dos 0/1, greedy vs LDS(k) vs exhaustif — toujours optimal (accrétion de Search-3) ~45min
3c (.NET) Search-03c-LimitedDiscrepancySearch (C#) .NET (C#) Jumeau .NET : même LDS sur sac à dos 0/1, port C# (record Item, récursion, bits) — parité stricte (accrétion de Search-3) ~45min
3d Search-03d-WeightedAstar Python 3 Weighted A* (Pohl 1970), sous-optimalité bornée f=g+W·h, terrain pondéré — optimalité relâchée de façon contrôlée (accrétion de Search-3) ~50min
3d (.NET) Search-03d-WeightedAstar (C#) .NET (C#) Jumeau .NET : même Weighted A*, balayage de W — port C# (PriorityQueue, value types), coût <= W fois l’optimal (accrétion de Search-3) ~50min
3e Search-03e-AStar-Optimality Python 3 (+WSL lean) Compagnon formel : l’admissibilité comme condition exacte de l’optimalité d’A* — preuves du lake search_lean visitées depuis Python (subprocess → WSL lean), pont vers Lean-6 (accrétion de Search-3) ~45min
3f Search-03f-Reparer-Localement-Sous-Garantie Python 3 Réparer localement sous garantie (op 6 du chantier ICT, #12204) : recherche incrémentale LPA* (Koenig & Likhachev 2002) — g/rhs et file d’incohérences, repair après blocage d’une cellule du plan optimal : optimalité transportée (34 = 34) au prix de 12 expansions contre 273 au A* from scratch (23×), séquence de 8 changements 8/8 concordante (9 vs 2258 expansions cumulées), contre-témoins mesurés — repair naïf dette +2 ; sans propagation, g(goal) affirme 34 pour un optimum réel de 36 sur un monde à goulet, où le changement structurel annule l’avantage (269 vs 276) — 2e attestation, substrat indépendant de GT-13b/13c ; section « recoller » (op 5 du chantier ICT) : tables locales de trois fenêtres chevauchantes recollées — compatibilité par paires vérifiée, composition sur le triple violée puis réparée, témoin exploitable exécuté pas à pas (accrétion de Search-3) ~1h45
4 Search-04-LocalSearch Python 3 Hill Climbing, Simulated Annealing, Tabu Search, paysages de fitness ~45 min
4 (.NET) Search-04-LocalSearch (C#) .NET (C#) Jumeau .NET : Hill Climbing (steepest-ascent), Random-Restart, recuit simulé (critère de Metropolis, programmes de refroidissement), recherche tabou (liste tabou) — port C# fidèle sur paysage 1D multimodal puis N-Reines (benchmark taux de succès) ~45 min
5 Search-05-GeneticAlgorithms Python 3 Sélection, crossover, mutation, DEAP/PyGAD, théorie unifiée ~50 min
5 (.NET) Search-05-GeneticAlgorithms (C#) .NET (C#) Jumeau .NET : algorithme générique from-scratch GeneticAlgorithm<T> (sélection roulette/tournoi, crossover 1-point/arithmétique, mutation bit-flip/gaussienne), élitisme, taux de mutation adaptatif — port C# fidèle validé sur OneMax (convergence 20/20, GA-easy), piège déceptif Goldberg k-trap (k=4, L=20) : hill-climber bloqué 17/20 (gradient trompeur), AG atteint 20/20 via croisement qui recombine les blocs tout-1 [#6849] + Rastrigin (f(x)≈1.3, optimum local évité) ~1h
6 Search-06-AdversarialSearch Python 3 Minimax, Alpha-Beta pruning, Null-window search, tables de transposition ~1h
6 (.NET) Search-06-AdversarialSearch (C#) .NET (C#) Jumeau .NET : Minimax, Alpha-Beta (speedup 31,9×), heuristique + profondeur limitée, iterative deepening, table de transposition — port C# fidèle sur Tic-Tac-Toe (valeur du jeu = 0) ~1h
7 Search-07-MCTS-And-Beyond Python 3 Monte Carlo Tree Search, UCB1, OpenSpiel, architecture AlphaGo (DQN+MCTS) ~1h30
7 (.NET) Search-07-MCTS-And-Beyond (C#) .NET (C#) Jumeau .NET : MCTS générique (IJeuSommeNulle<T> + UCB1, sélection/expansion/rollout/backprop en convention UCT « moved-into »), Minimax, convergence Tic-Tac-Toe, benchmark paramètre c (c=√2 optimal → 100 %), Nim (découvre l’action optimale 3) — port C# fidèle, tables texte au lieu de matplotlib ~1h30
8 Search-08-DancingLinks Python 3 Algorithme X de Knuth, Dancing Links (DLX), couverture exacte (Sudoku, N-Queens, Pentominoes) ~1h30
8 (.NET) Search-08-DancingLinks (C#) .NET (C#) Jumeau .NET : Algorithme X naïf (réduction de matrice) + structure Dancing Links from-scratch (DlxNode toroïdal, Cover/Uncover O(1), heuristique S de Knuth), couverture exacte canonique [S2,S4,S6], pavage de polyominos (triominos I/L sur grille 2×3), comparaison perf DLX vs backtracking (DLX ~27× plus rapide sur pavage 3×3) — port C# fidèle Prong A, tables texte au lieu de matplotlib ~1h30
9 Search-09-LinearProgramming Python 3 Programmation linéaire avec PuLP, simplex, problème du transport, diet problem, PLNE ~2h
9 (.NET) Search-09-LinearProgramming (C#) .NET (C#) Jumeau .NET : programmation linéaire avec Google OrTools (LinearSolver, solveurs GLOP/CBC) — problème de production, diet problem, analyse de sensibilité et dualité (shadow prices), PLNE (sac à dos binaire), exercices (set cover, optimisation multi-objectif) — port C# fidèle du notebook Python (PuLP) — parité #4956 ~1h
9b Search-09b-SpuriousMinima Python 3 Relaxation SDP de MaxCut (Goemans–Williamson, résolue exactement par cvxpy/CLARABEL) et sa factorisation de Burer–Monteiro \(Y = XX^T\) : recensement borné des minima fallacieux par rang (40 départs × 3 instances C6/K8/G10, graines fixes, référence brute-force \(2^{n-1}\)) — à \(r=1\) le paysage dégénère en MaxCut discret (40/40 fallacieux), les pièges se raréfient aux rangs intermédiaires, et aucun piège à/au-dessus du seuil \(r(r+1)/2 > m\) (Burer–Monteiro 2005, Barvinok–Pataki) — le point d’arrivée « certification » du fil paysages (suite directe de Search-9, écho de MGS-15) ~1h15
9c Search-09c-CombinatorialDiscrepancy Python 3 Discrépance combinatoire (Beck–Fiala 1981, frontière 2025 Bansal–Jiang arXiv:2508.03961) : colorier ±1 sans déséquilibrer, borne inf √k (Chernoff), arrondi flottant 2k−1 implémenté, CP-SAT en oracle exact — fil relaxation/arrondi/optimisation combinatoire (accrétion de Search-9) ~45min
9d Discrepancy-02-Komlos-Lean lean4-wsl Compagnon formel de Search-09c : le lake discrepancy_lean exécuté depuis le kernel Lean 4 — #check des conjectures (Komlós ∃C universel, Beck–Fiala 2k−1, régimes Bansal–Jiang 2025), témoins coloriés ±1 énumérés exhaustivement sur des instances jouet (Hadamard ½n en particulier), exercices ancrés sur les énoncés du lake ~45min
10 Search-10-SymbolicAutomata Python 3 Automates finis (DFA/NFA) avec automata-lib, prédicats Z3, automates symboliques ~2h
10 (.NET) Search-10-SymbolicAutomata (C#) .NET (C#) Jumeau .NET (tranches 1+2) : automates finis classiques (DFA/NFA hand-rolled, opérations ensemblistes par produit cartésien) + automates symboliques avec Microsoft.Z3 (NuGet 4.12.2) — classe SymbolicAutomaton (transitions = prédicats Z3, décision via solveur SMT), intervalle [10,100], parité, multiples de 5, opérations symboliques (union/intersection/complément via MkAnd/MkOr/MkNot vérifiées exactes) — port C# fidèle §1-4 — parité #4956 ~1h30
11 Search-11-Metaheuristics Python 3 PSO, ABC, SA, BRO avec MEALPy, benchmark comparatif de métaheuristiques ~1h30
11 (.NET) Search-11-Metaheuristics (C#) .NET (C#) Jumeau .NET : PSO (inertie décroissante + clamp velocity), recuit simulé (acceptation Metropolis, pas proportionnel à √(T/T₀)), algorithme génétique (tournoi, croisement arithmétique, mutation gaussienne, élitisme) from-scratch, fonctions de benchmark (Sphere/Rastrigin/Rosenbrock/Ackley), convergence gbest monotone, benchmark comparatif PSO/SA/GA, optimisation de profit (retrouve l’optimum analytique x≈17.14, y≈15.71), TSP par recuit 2-opt — parité #4956, tables texte au lieu de matplotlib ~1h30
11b (.NET) Search-11b-Metaheuristiques-Deep (+ T2 PSO, T3 ABC, T4 Benchmark) .NET (C#) Déclinaison deep-dive en 4 volets — un algorithme from-scratch approfondi par tranche : recuit simulé (T1), Particle Swarm Optimization (T2), Artificial Bee Colony (T3), benchmark comparatif capstone (T4). Complète le jumeau 11 (.NET) (survol PSO/SA/GA) par un traitement détaillé algorithme par algorithme ~4×45 min
11c Search-11c-Empirical-Algorithm-Selection Python 3 Distillation du projet L4 EPITA SCIA 2026 (Th. Deguest, PR source #42) : sélection empirique d’algorithmes sous protocole commun (timeout 5 s, budget nœuds explicite, métriques uniformes) sur deux terrains — Sudoku (BT naïf/MRV, DLX, CP-SAT, Z3, GA, recuit simulé ; tranche 1) et Puissance 4 (random, minimax, alpha-beta, MCTS ; round-robin double, tranche 2) — front de Pareto qualité-coût, sweep de budget qui inverse la sélection, carte problème × paradigme : No Free Lunch mesuré (Rice 1976, Wolpert 1996), écho App-14 ~1h30
12a Search-12a-Composer-Regards Python 3 Composer des regards (op 12 du chantier ICT, #12204) : play forward (g, Dijkstra depuis le départ) × coplay backward (d, Dijkstra depuis l’arrivée) sur un gridworld pondéré 10×14 déterministe — corridor optimal isolé par f* = g + d (19/140 nœuds), associativité de la composition à relais (toujours vraie comme opérateur), exactitude conditionnelle (écart 0 sur route, +2 hors route : inégalité triangulaire), paire de lectures incompatibles exhibée (coût × pas : divergence dès le pas 1, route à +32 de coût ; A* 24 vs 75 expansions) — 2e attestation directe, substrat indépendant de GT-21 (#12245) ~1h
13a Search-13a-Traverser-Murs-Certifies Python 3 Traverser un mur (op 13 du chantier ICT, #12204) : pavage hexagonal de 61 salles (coordonnées axiales), deux chambres séparées par une double chaîne de murs (8+9 cellules de coût 3 contre sol à 1) fermant l’anneau de bout en bout, six swaps générateurs (les six directions hexagonales) — chemin minimal certifié par quatre organes indépendants (Dijkstra L=12, audit de potentiels : 312 arêtes, 0 violation, égalités serrées le long du chemin ; 0-1 BFS : épaisseur m_path=2 ; flot max Edmonds-Karp par nœuds fendus : largeur m=8 = coupure minimale, certificat de coupe par BFS) — distinction épaisseur (murs sur un chemin) vs largeur (murs à démolir, Menger), test négatif de l’opération : percement Δ=−2 et certificat rejeté (pas un morphisme) contre swap silencieux de feuille Δ=0 et certificat préservé (morphisme), balayage du coût c_w qui bascule le point de passage (3 → 2 murs franchis) — 2e attestation directe, substrat indépendant de GT-24 (#12364) ~1h

Accrétions avancées de Search-3 (ex-Partie 3)

Cette partie absorbe le contenu durable de l’ancienne Partie 3, centrée sur la recherche heuristique avancée. Le fil rouge reste le 15-puzzle — le banc d’essai historique de la recherche heuristique depuis Korf (1985). L’enjeu central est la mémoire comme ressource algorithmique : jusqu’où peut-on précalculer, et comment décomposer un problème pour que ce précalcul reste abordable ?

Les notebooks absorbés forment un triptyque aux stratégies complémentaires : renforcer l’heuristique (Pattern Databases précalculées), borner les écarts à l’heuristique dont on dispose (Limited Discrepancy Search), et relâcher l’optimalité de façon contrôlée (Weighted A*). Ces accrétions répondent à la même question — « l’heuristique ne suffit pas à résoudre à l’optimum » — et illustrent comment la qualité de l’estimation se paie en précalcul retourné sans jamais violer l’admissibilité.

Progression

Les trois premiers notebooks forment le socle commun — on y apprend à poser un problème, puis à l’explorer systématiquement — et tout le reste s’y greffe. Au-delà, le parcours n’est pas linéaire : cinq branches indépendantes s’ouvrent, à prendre dans l’ordre de vos curiosités :

  • Recherche locale et évolutive : Search-4 (LocalSearch) puis Search-5 (GeneticAlgorithms) puis Search-11 (Metaheuristics)
  • Recherche dans les jeux : Search-3 puis Search-6 (AdversarialSearch) puis Search-7 (MCTS)
  • Couverture exacte : Search-2 puis Search-8 (DancingLinks)
  • Boîte à outils de graphes : Search-2 puis Search-2b (NetworkX, ou son jumeau C#) puis Search-2c (QuikGraph)
  • Indépendants : Search-9 (LinearProgramming, algèbre linéaire requise), Search-09b (SpuriousMinima, sa suite semidéfinie : Search-9 recommandé au préalable), Search-09c (CombinatorialDiscrepancy, relaxation/arrondi — écho du fil optimisation) suivi de son compagnon formel Discrepancy-02 (Lean, kernel lean4-wsl : Search-09c recommandé au préalable), Search-11c (Empirical-Algorithm-Selection, distillation benchmark cross-paradigmes : aucun prérequis, écho App-14), Search-12a (Composer-Regards, lecture avant/arrière d’un même terrain : Search-3 recommandé au préalable, op 12 du chantier ICT #12204), Search-13a (Traverser-Murs-Certifies, chemin minimal certifié à travers une bande de cellules coûteuses : Search-2 recommandé au préalable, op 13 du chantier ICT #12204), Search-03f (Reparer-Localement-Sous-Garantie, repair incrémental LPA* avec garantie d’optimalité transportée : Search-3 recommandé au préalable, op 6 du chantier ICT #12204) et Search-10 (SymbolicAutomata, liens avec SymbolicAI/SMT/Z3-Linq2Z3)
flowchart LR
    SOCLE["<b>Socle commun</b><br/>Search-1 — StateSpace<br/>(formalisation S, A, T, G)<br/>Search-2 — Uninformed<br/>(BFS, DFS, UCS, IDDFS)<br/>Search-3 — Informed<br/>(A*, heuristiques)"]
    B1["<b>Recherche locale &amp; évolutive</b><br/>Search-4 — LocalSearch<br/>Search-5 — GeneticAlgorithms<br/>Search-11 — Metaheuristics"]
    B2["<b>Recherche dans les jeux</b><br/>Search-6 — AdversarialSearch<br/>(Minimax, Alpha-Beta)<br/>Search-7 — MCTS (AlphaGo)"]
    B3["<b>Couverture exacte</b><br/>Search-8 — Dancing Links (Knuth)"]
    B4["<b>Indépendants</b><br/>Search-9 — LinearProgramming<br/>Search-10 — SymbolicAutomata"]
    B5["<b>Boîte à outils de graphes</b><br/>Search-2b — NetworkX<br/>Search-2c — QuikGraph"]
    SOCLE --> B1
    SOCLE --> B2
    SOCLE --> B3
    SOCLE --> B4
    SOCLE --> B5

Les fondamentaux de cette partie (formalisation, backtracking, heuristiques) sont le prérequis de la Partie 2 (CSP).

Prérequis & environnement

Besoin Détail
Python 3.10+, environnement virtuel recommandé
ortools Search-9 (Linear Programming), Search-11c (CP-SAT)
deap Search-5 (Genetic Algorithms)
mealpy Search-11 (Métaheuristiques)
z3-solver Search-10 (Symbolic Automata), Search-11c (SMT)
OpenSpiel Search-7 (MCTS) : requiert WSL ou Linux
cvxpy Search-09b (relaxation SDP, solveur CLARABEL embarqué)
Kernel lean4-wsl Discrepancy-02 : kernel Jupyter Lean 4 + miroir local du lake discrepancy_lean (Mathlib 4 via les packages du dépôt) — cf. docs/reference/wsl-kernels-detail.md
QuikGraph 2.5.0 (NuGet) Search-2c (parité C#) : nécessite .NET Interactive, installable via dotnet tool install --global Microsoft.dotnet-interactive

Pour le setup complet, voir le README de la série Search.

Bibliothèques : parité Python networkx ↔︎ .NET QuikGraph

Le notebook Search-2c-QuikGraph ferme la boucle côté .NET Interactive : il offre l’équivalent C# du notebook Python Search-2b-NetworkX, avec une table de parité structurelle entre les deux écosystèmes. Le notebook Python modélise par exemple un réseau routier 5×5 : les arêtes sont colorées par poids (du jaune au rouge) et le plus court chemin — identique pour Dijkstra et A* — y est tracé en rouge entre la source (en vert) et la destination (en rouge).

Réseau routier 5×5 : arêtes pondérées colorées, plus court chemin Dijkstra en rouge

La règle pratique : QuikGraph 2.5.0 (fork KeRNeLith, NuGet) couvre les algorithmes classiques (DFS, BFS, Dijkstra, Bellman-Ford, A*, Edmonds-Karp, Tarjan, MST, Floyd-Warshall) et suffit pour tous les notebooks Search 1-11 si l’on travaille en C# — son verdict honnête est qu’il ne fournit pas les centralités élaborées (betweenness, closeness, PageRank) ni la détection de communautés (Louvain), qu’il faut alors implémenter à la main ou brancher une autre bibliothèque.

Note de numérotation. La plage 1-11 porte les algorithmes fondamentaux, les numéros 03b à 03f désignent les accrétions de Search-3 (heuristiques avancées : Pattern Databases, Limited Discrepancy Search, Weighted A*, compagnon formel de l’optimalité, repair incrémental LPA*). Les suffixes b/c rattachent une accrétion au numéro de base : Search-2b-NetworkX et Search-2c-QuikGraph prolongent Search-2 (la boîte à outils de graphes vient se greffer sur la recherche non informée), Search-11b-Metaheuristiques-Deep (4 volets) approfondit Search-11. Un suffixe b peut désigner une déclinaison approfondie (11b) ou un compagnon de même niveau (2b) — le jumeau C# canonique porte toujours le numéro nu. Chaque numéro (suffixe compris) désigne un notebook unique. La plage 12 s’ouvre sur une accrétion sans numéro de base : Search-12a-Composer-Regards (op 12 du chantier ICT #12204) — le suffixe a marque une ligne nouvelle dont les futurs notebooks partageront le sujet (composer des lectures d’un même problème). La plage 13 suit le même geste : Search-13a-Traverser-Murs-Certifies (op 13 du chantier ICT #12204) — traverser une frontière coûteuse et certifier le chemin minimal.

Ponts vers les autres séries

Cette partie irrigue le reste du dépôt : les Dancing Links de Search-8 sont à l’œuvre dans la série Sudoku, Minimax et MCTS (Search-6/7) se prolongent dans GameTheory avec OpenSpiel puis dans RL côté politiques apprises, et les prédicats Z3 de Search-10 ouvrent sur SymbolicAI.

Références

Couverture par notebook des sources fondatrices mobilisées dans cette partie :

Notebook(s) Référence
Search-1 à 7, 9 Russell, S., & Norvig, P. — Artificial Intelligence: A Modern Approach (4e éd., 2021). La référence pour la formalisation en espace d’états, les algorithmes informés/non informés et la recherche dans les jeux.
Search-3 (Informed) Hart, P. E., Nilsson, N. J., & Raphael, B. (1968) — « A Formal Basis for the Heuristic Determination of Minimum Cost Paths », IEEE Trans. on Systems Science and Cybernetics 4(2). L’article fondateur d’A*.
Search-5 (GeneticAlgorithms) Holland, J. H. (1975) — Adaptation in Natural and Artificial Systems. University of Michigan Press. Origine des algorithmes génétiques.
Search-7 (MCTS) Browne, C. B., Powley, E., et al. (2012) — « A Survey of Monte Carlo Tree Search Methods », IEEE Trans. on Computational Intelligence and AI in Games 4(1).
Search-8 (DancingLinks) Knuth, D. E. (2000) — « Dancing Links », dans Millennial Perspectives in Computer Science (Springer).
Discrepancy-02 (conjecture de Komlós) Matoušek, J. (1999) — Geometric Discrepancy: An Illustrated Guide, Springer. Contexte classique de la conjecture de Komlós (disc ≤ C pour colonnes unitaires) ; les énoncés KomlosConjecture / BansalJiangLargeDegree / KomlosBansalJiangWeak formalisés dans discrepancy_lean/Komlos.lean suivent les régimes de Bansal & Jiang (2025, arXiv:2508.03961 — cf. Search-09c).
Search-11 (Metaheuristics) Kennedy, J., & Eberhart, R. (1995) — « Particle Swarm Optimization », Proc. IEEE Int. Conf. on Neural Networks. Origine du PSO.

FAQ

Problème Solution
A* trop lent sur les grands graphes Vérifier que l’heuristique est admissible ET consistante ; essayer IDA* (Search-3), qui consomme moins de mémoire
GA stagne sans amélioration Augmenter le taux de mutation ou la taille de la population ; comparer avec les métaheuristiques de Search-11

Conclusion / Prochaines étapes

Ce que vous avez appris

Cette première partie a posé l’alphabet de la recherche en IA. L’arc pédagogique part d’un seul objet mathématique — l’espace d’états (S, A, T, G) formalisé en Search-1 — et en fait le dénominateur commun d’une grande famille d’algorithmes :

  • La recherche systématique (Search-2, Search-3) — de l’énumération à l’aveugle (BFS, DFS, UCS, IDDFS) jusqu’à l’exploration informée par une heuristique (A, Greedy, IDA). Le moment clé est l’épreuve de l’admissibilité : l’optimalité d’A* ne se postule pas, elle se démontre, et la frontière entre une heuristique qui guide et une heuristique qui ment est fine.
  • La recherche locale et évolutive (Search-4, Search-5, Search-11) — abandonner l’arbre d’exploration pour naviguer de voisin en voisin dans un paysage de fitness, accepter temporairement de dégrader (recuit simulé, tabou), puis laisser une population entière explorer en parallèle (génétiques, PSO, ABC). Le benchmark comparatif de Search-11 enseigne le no-free-lunch : aucune métaheuristique ne domine partout.
  • La recherche dans les jeux (Search-6, Search-7) — quand l’environnement riposte, la recherche devient adversariale : Minimax et l’élagage Alpha-Beta, puis Monte Carlo Tree Search, qui remplace l’évaluation experte par la simulation statistique et mène jusqu’à l’architecture d’AlphaGo.
  • Trois extensions (Search-8, Search-9, Search-10) — les Dancing Links de Knuth pour la couverture exacte, la programmation linéaire (du discret au continu via PuLP), et les automates symboliques où les transitions deviennent des prédicats Z3 — premier pont vers l’IA symbolique.

Deux de ces familles se donnent à voir dans les figures extraites des notebooks. La recherche systématique oppose d’abord les stratégies à l’aveugle : sur un même arbre binaire, l’écart d’expansion entre BFS (par niveaux) et DFS (en profondeur) saute aux yeux dès qu’on numérote les nœuds par ordre d’exploration.

BFS vs DFS : deux arbres binaires, nœuds numérotés par ordre d’exploration

Dès qu’une heuristique est disponible, A* exploite ce savoir pour prioriser les états prometteurs : sur le 8-puzzle, chaque état développé est annoté de ses coûts g (déjà parcouru), h (estimé par distance de Manhattan) et f = g + h, et l’optimum est atteint en explorant peu de nœuds.

Progression d’A* sur le 8-puzzle : états successifs annotés g/h/f

Côté recherche locale et évolutive, le benchmark comparatif de Search-11 confirme le no-free-lunch : aucune métaheuristique ne domine partout, que ce soit en fitness atteinte (échelle log) ou en temps de calcul.

Comparaison des métaheuristiques : fitness (log) et temps, par algorithme et fonction

L’étude du paramètre clé, la taille de population PSO, quantifie alors l’arbitrage entre qualité de la solution et coût de calcul.

Impact de la taille de population PSO : fitness et temps

Le véritable enseignement, au-delà du catalogue d’algorithmes, est un réflexe d’ingénieur : chaque méthode y est présentée comme un compromis — complétude contre mémoire, garantie contre temps de calcul, exploration contre exploitation — et jamais comme une recette universelle.

Prochaines étapes

  • La programmation par contraintes : la suite naturelle est la Partie 2 (CSP), qui réutilise le backtracking et les heuristiques de cette partie pour propager des contraintes plutôt que d’énumérer — la réduction de l’espace de recherche y devient systématique plutôt qu’heuristique.
  • Les applications : les 40 notebooks d’application (détection de contours, TSP, VRP, optimisation de portefeuille, hyperparameter tuning) mobilisent directement les métaheuristiques et la recherche locale vues ici sur des problèmes réels.
  • Les ponts vers les autres séries : les Dancing Links irriguent Sudoku, Minimax et MCTS se prolongent dans GameTheory (OpenSpiel) puis RL (politiques apprises), et les prédicats Z3 de Search-10 ouvrent sur SymbolicAI. Reprendre un de ces ponts après avoir posé les fondations de la recherche donne aux primitives une nouvelle profondeur.
  • La série dans son ensemble : le sommaire Search cartographie les quatre parties et les applications — celle-ci est le socle commun.

Le fil rouge

La recherche en IA propose un changement de regard sur la résolution de problèmes : ne plus voir chaque algorithme comme une recette à appliquer, mais comprendre qu’ils sont tous des négociations d’un même compromis fondamental — entre la garantie de trouver l’optimal et le coût pour l’atteindre, entre explorer l’inconnu et exploiter l’acquis, entre la complétude et la mémoire disponible. BFS garantit l’optimal mais explose en mémoire ; DFS file droit mais peut se perdre ; A* négocie les deux via une heuristique dont l’honnêteté (l’admissibilité) conditionne la justesse du résultat ; le recuit simulé accepte de remonter la pente pour s’échapper d’un optimum local ; MCTS remplace l’expertise par la statistique. Comprendre la recherche, c’est comprendre qu’il n’existe pas de « bon » algorithme dans l’absolu, mais une famille de stratégies dont le choix dépend du compromis qu’on est prêt à accepter — et que ce compromis, loin d’être une limitation, est précisément ce qui rend la recherche applicable à tout problème formalisable en espace d’états.

Retour au sommet