Search - Algorithmes de Recherche et Programmation par Contraintes

← Notebooks | ↑ .. | → SymbolicAI

Tout problème d’IA, du plus simple jeu de plateau à la planification logistique industrielle, se réduit à un même défi : explorer un espace de solutions possibles pour trouver la meilleure. Cette série vous apprend à maîtriser cette exploration, depuis les algorithmes classiques (BFS, A*, Minimax) jusqu’aux techniques avancées (CSP, métaheuristiques, hybridation LLM). Le fil rouge est la réduction de l’espace de recherche : comment passer d’une exploration aveugle exponentielle à une résolution intelligemment guidée.

Le parcours couvre quatre grands piliers. Les fondements formalisent les espaces d’états et couvrent les algorithmes de recherche non informée, informée, locale, génétique, adversariale et MCTS. La programmation par contraintes (CSP) introduit un changement de paradigme : au lieu d’explorer, on réduit les domaines par propagation. Les applications (20 cas réels, chacun décliné en binôme Python ⇄ C#) illustrent chaque concept sur des problèmes adaptés de projets étudiants. Enfin, les métaheuristiques et l’hybridation relient la recherche à l’optimisation continue et aux LLMs.

À qui s’adresse cette série : étudiants en informatique (L3-M2), ingénieurs logiciel confrontés à des problèmes d’optimisation, et candidats à des entretiens techniques. Les notebooks Python ne nécessitent que Python 3.10+ avec ortools et deap. Les notebooks C# — jumeaux de parité de chaque notebook Python (marathon EPIC #4956) et la Partie 4 — métaheuristiques composables au-dessus de GeneticSharp — requièrent .NET 9.0 + dotnet-interactive. Aucun prérequis en algorithmique avancée : les concepts sont introduits depuis les espaces d’états.

Pourquoi cette série

La recherche et l’optimisation sont au coeur de l’informatique : tout problème, du plus simple jeu de plateau à la planification logistique industrielle, se réduit à explorer un espace de solutions. Cette série couvre l’intégralité du spectre algorithmique — de la recherche aveugle (BFS) à l’hybridation LLM+CSP — en construisant une compréhension progressive des compromis fondamentaux.

Cette série repose sur une double approche, délibérément juxtaposée :

  • Exploration systématique (recherche classique) : BFS, DFS, A*, Minimax — des algorithmes qui garantissent de trouver une solution optimale si elle existe, mais dont le coût peut être exponentiel. C’est le domaine des espaces d’états, des heuristiques admissibles, de la complétude.
  • Réduction de l’espace (programmation par contraintes) : au lieu d’explorer bêtement, on élague les domaines impossibles par propagation (AC-3, Forward Checking, CP-SAT). C’est un changement de paradigme : on ne cherche plus, on contraint. Avantage : résolution de problèmes industriels (ordonnancement, emploi du temps) en quelques millisecondes. Limite : la modélisation est un art.

Avoir les deux approches permet de comprendre quand explorer, quand contraindre, et quand les combiner — une compétence cruciale pour tout ingénieur confronté à des problèmes combinatoires.

Au-delà de la méthodologie, cette série couvre des applications réelles adaptées de projets étudiants : planification d’infirmiers (CHU), ordonnancement d’atelier (industrie), optimisation de portefeuille (finance), TSP/VRP (logistique), démineur (CSP + probabilités), Picross (couverture exacte). Chaque application est une brique construite sur les concepts précédents.

Qu’est-ce que la recherche en IA ?

Aspect Exploration systématique Programmation par contraintes Métaheuristiques
Philosophie Énumérer méthodiquement Réduire les domaines impossibles S’inspirer de la nature
Garantie Solution optimale (si temps) Solution optimale (si modélisable) Aucune garantie
Modélisation Espace d’états (S, A, T, G) Variables, domaines, contraintes Fonction objectif, voisinage
Complexité Exponentielle (mais heuristiques) Exponentielle (mais propagation) Polynomiale par itération
Quand l’utiliser Problèmes bien définis, heuristique connue Contraintes claires, domaine discret Grands espaces, approximation acceptable

Objectifs d’apprentissage

À l’issue de cette série, vous serez capable de :

  1. Formaliser un problème réel en espace d’états (S, s0, A, T, G) et choisir l’algorithme de recherche adapté
  2. Comparer recherche systématique (A*), contraintes (CSP) et métaheuristiques (GA, SA) sur un même problème
  3. Modéliser un problème industriel en CSP (ordonnancement, routing, emploi du temps) avec OR-Tools CP-SAT
  4. Évaluer les compromis garantie vs performance vs généralisation pour choisir une stratégie algorithmique
  5. Combiner approches complémentaires (CP+SAT, LLM+CSP, MCTS+DQN) pour des problèmes complexes

Parcours d’apprentissage

Phase 1 : Fondements de la recherche (Part 1, notebooks 1-7, ~7h)

Le parcours commence par Search-1 (StateSpace) qui formalise les problèmes sous forme (S, s0, A, T, G) et Search-2 (Uninformed) qui couvre BFS, DFS, UCS et IDDFS. Search-3 (Informed) introduit les heuristiques et A*, le cœur de la recherche guidée. Search-4 (LocalSearch) pivote vers l’optimisation locale (Hill Climbing, Simulated Annealing, Tabu Search), et Search-5 (GeneticAlgorithms) généralise avec les algorithmes évolutionnaires. Search-6 (AdversarialSearch) explore la recherche dans les jeux (Minimax, Alpha-Beta), et Search-7 (MCTS) va jusqu’à Monte Carlo Tree Search et les approches AlphaGo. À l’issue de cette phase, vous maîtrisez les trois grands paradigmes : exploration systématique, optimisation locale, et recherche dans les jeux.

Phase 2 : Programmation par contraintes (Part 2, CSP 1-6, ~6h)

La Phase 2 change de paradigme : au lieu d’explorer un espace, on le réduit. CSP-1 (Fundamentals) introduit le modèle (X, D, C) et le backtracking. CSP-2 (Consistency) couvre la propagation de contraintes (AC-3, Forward Checking, MAC). CSP-3 à CSP-6 montent en complexité : contraintes globales (AllDifferent, Cumulative), ordonnancement (Job-Shop, RCPSP), optimisation (Bin Packing, Knapsack), et hybridation (LCG, CP+SAT, CP+ML, LLM+CSP). Cette phase présuppose les bases de la Phase 1 (formalisation, backtracking = DFS) et constitue le cœur pratique de la série.

Phase 3 : Applications et frontières (Applications + notebooks avancés, ~18h)

Les 20 applications (chacune en binôme Python ⇄ C#) illustrent chaque concept sur des cas réels : planification d’infirmiers (CSP-4), ordonnancement d’atelier (CSP-4), optimisation de portefeuille (métaheuristiques), TSP et VRP (routing), démineur et Wordle (CSP + théorie de l’information), Picross (couverture exacte). Les notebooks avancés de la Part 1 (programmation linéaire Search-9, automates symboliques Search-10, métaheuristiques Search-11) et de la Part 2 (contraintes souples CSP-7, temporelles CSP-8, distribuées CSP-9) complètent le panorama. L’ensemble est enrichi par des ponts vers les autres séries : Sudoku (DLX, automates), SymbolicAI (Z3, planification), GameTheory (Minimax, MCTS), et RL (MCTS + DQN).

flowchart LR
    P1["<b>Phase 1 — Fondements</b> (~7h)<br/>Search-1 … Search-7<br/><i>Trois paradigmes :</i><br/>• exploration systématique<br/>&nbsp;&nbsp;(BFS, UCS, A*)<br/>• optimisation locale<br/>&nbsp;&nbsp;(SA, Tabu, GA)<br/>• recherche dans les jeux<br/>&nbsp;&nbsp;(Minimax, MCTS)"]
    P2["<b>Phase 2 — Programmation<br/>par contraintes</b> (~6h)<br/>CSP-1 … CSP-6<br/><i>Réduire l'espace<br/>plutôt que l'explorer</i><br/>backtracking → AC-3<br/>→ contraintes globales<br/>→ ordonnancement<br/>→ CP + SAT / ML / LLM"]
    P3["<b>Phase 3 — Applications<br/>&amp; frontières</b> (~18h)<br/>20 cas réels × 2 langues :<br/>TSP, VRP, RCPSP,<br/>Bin Packing, Wordle, Picross…<br/>+ notebooks avancés<br/>(LP, automates,<br/>souples, temporelles)"]
    BR["<b>Séries connexes</b><br/>Sudoku (DLX)<br/>SymbolicAI (Z3)<br/>GameTheory (Minimax/MCTS)<br/>RL (MCTS + DQN)"]
    P4["<b>Side-track .NET 9</b><br/>Part 4 — Métaheuristiques<br/>composables<br/>MGS-1 … MGS-19<br/><i>reconstruire &amp; composer<br/>au-dessus de GeneticSharp</i>"]
    P1 -->|"backtracking = DFS"| P2
    P2 -->|"modélisation industrielle"| P3
    P3 -.->|"ponts"| BR
    P1 -.->|"side-track .NET"| P4

Side-track avancé : métaheuristiques composables (Part 4, C# .NET 9)

En parallèle du parcours Python, la Partie 4 — MetaGeneticSharp propose un side-track .NET 9 de 22 notebooks (MGS-1 à MGS-19 plus la trilogie MGS-7b/7c/7d de projection N-D des paysages) qui reconstruit et compose les métaheuristiques au-dessus de GeneticSharp plutôt que d’importer une boîte noire. Il prolonge Search-5 (GeneticAlgorithms) et Search-11 (Métaheuristiques) et se lit en quatre temps : MGS-1 à 7 bâtissent le moteur et la grammaire de composition (jusqu’au TSP) ; MGS-7b, MGS-8 à 14 visualisent les paysages de fitness (MGS-7b projette les benchmarks en dimension N≥5) et mesurent la robustesse aux biais des bancs CEC (décalage, rotation, synergie d’îles) ; MGS-15 à 18 referment la série sur l’analyse quantitative de paysage et la méta-stratégie (No-Free-Lunch, contrôle de paramètres) ; MGS-19 démonte le recuit simulé pour éprouver l’opérateur de Metropolis seul. Optionnel pour qui vise le cœur Python, central pour qui veut construire ses métaheuristiques en .NET.

Ce que chaque notebook apporte

Chaque notebook introduit un concept ou algorithme spécifique. Le tableau ci-dessous résume en une ligne l’apport pédagogique de chacun.

Partie 1 : Search Fondamental

# Notebook Apport pédagogique
1 StateSpace Formaliser un problème en espace d’états (S, s0, A, T, G)
2 Uninformed BFS vs DFS : comment l’ordre d’exploration change la complexité
3 Informed Heuristiques admissibles et A* : guider la recherche vers la solution
4 LocalSearch Abandonner la garantie pour l’efficacité : paysages de fitness et optima locaux
5 GeneticAlgorithms Populations, crossover, mutation : l’évolution comme métaheuristique — piège déceptif Goldberg k-trap (k=4, L=20) [#6849] : hill-climber bloqué 17/20, AG 20/20 via croisement
6 AdversarialSearch Minimax, Alpha-Beta : chercher dans les jeux à deux joueurs
7 MCTS-And-Beyond Monte Carlo Tree Search et la révolution AlphaGo (MCTS + DQN)
8 DancingLinks Couverture exacte de Knuth : une structure de données transforme un algorithme
9 LinearProgramming Programmation linéaire (PuLP) : relaxer les contraintes entières
10 SymbolicAutomata Automates finis + Z3 : raisonner sur des alphabets infinis
11 Métaheuristiques PSO, ABC, BRO avec MEALPy : comparer 160+ algorithmes

Partie 2 : Programmation par Contraintes

# Notebook Apport pédagogique
1 CSP Fundamentals Modèle (X, D, C) : déclarer le problème plutôt que l’algorithme
2 CSP Consistency AC-3, Forward Checking : réduire l’espace par propagation avant la recherche
3 CSP Advanced Contraintes globales (AllDifferent, Cumulative, Circuit)
4 CSP Scheduling Job-Shop, RCPSP, Nurse : l’ordonnancement industriel par contraintes
5 CSP Optimization Bin Packing, Knapsack, Portfolio : optimiser sous contraintes
6 CSP Hybridization LCG, CP+SAT, CP+ML, LLM+CSP : combiner les paradigmes
7 CSP Soft Contraintes souples, Fuzzy CSP : quand toutes les contraintes ne sont pas égales
8 CSP Temporal Allen’s Interval Algebra, STP : raisonner sur le temps
9 CSP Distributed ABT, AWC : résoudre des CSP répartis entre agents

#—

Applications (Applications/)

Problèmes du monde réel adaptés de projets étudiants. Chaque application est un binôme Python ⇄ C# (parité complète depuis le marathon #4956) ; les jumeaux C# suivent la convention App-Nb-...-CSharp.ipynb.

Applications Search (Applications/Search/)

# Notebook Durée Contenu Source
1 App-14b-ConnectFour ~50 min Puissance 4 : 5 IA au tournoi (Random, Glouton, Minimax α-β d=4/d=6, MCTS) + framework AIMA Projet étudiant
1b App-14c-ConnectFour-CSharp ~45 min Jumeau C# — Minimax + Alpha-Beta + MCTS (UCB1) + glouton + iterative deepening from-scratch, heuristique de fenêtres + tournoi round-robin, parité #4956 Jumeau .NET
2 App-14-ConnectFour-Adversarial ~45 min Benchmark adversarial : Minimax, Alpha-Beta, MCTS Projet étudiant
2b App-14-ConnectFour-Adversarial-CSharp ~40 min Jumeau C# — Minimax + Alpha-Beta (élagage) + MCTS (UCB1) from-scratch, benchmark nœuds + tournoi round-robin, parité #4956 Jumeau .NET

Applications CSP (Applications/CSP/)

# Notebook Durée Contenu Source
1 App-1-NQueens ~30 min Benchmark classique CSP : backtracking, min-conflicts, OR-Tools Classique
2 App-2-GraphColoring ~45 min Coloration de cartes : Greedy, DSATUR, CP-SAT, départements français Projet étudiant
3 App-3-NurseScheduling ~60 min Planning infirmiers : contraintes hard/soft, OR-Tools CP-SAT Projet étudiant
4 App-4-JobShopScheduling ~60 min Ordonnancement industriel : intervalles, précédences, makespan Projet étudiant
5 App-5-Timetabling ~50 min Emploi du temps universitaire : MiniZinc + OR-Tools Projet étudiant
6 App-6-Minesweeper ~50 min Démineur CSP : propagation, probabilités, hybride CSP+LLM Projet étudiant
7 App-7-Wordle ~45 min Solveur Wordle : filtrage CSP + théorie de l’information Projet étudiant
8 App-8-MiniZinc ~50 min Modélisation déclarative : syntaxe MiniZinc, contraintes globales Nouveau
9 App-11-Picross ~40 min Nonogrammes : speedup 27Mx CP-SAT vs naïve Projet étudiant
10 App-15-SportsScheduling ~55 min Calendrier sportif : contraintes TV, équité, déplacements Projet étudiant
11 App-16-Crossword-CSP ~45 min Mots croisés : backtracking, OR-Tools, génération Projet étudiant
12 App-19-ProceduralGeneration-WFC ~45 min Génération procédurale : Wave Function Collapse via CP-SAT Projet étudiant
12 (C#) App-19-ProceduralGeneration-WFC-CSharp ~45 min Twin C# du 12 : WFC from-scratch (entropie de Shannon + propagation AC-3 + backtracking) (See #4956) Marathon
13 App-20-SudokuBenchmark-Python ~50 min Benchmark 4 solveurs Sudoku (backtracking naïf → optimisé → contraintes) sur banc Easy/Medium/Hard : dénombrement du travail Synthèse série
13 (C#) App-20b-SudokuBenchmark-CSharp ~50 min Twin C# du 13 : mêmes solveurs from-scratch en .NET, comparaison des écosystèmes Jumeau .NET
16 App-26-CoveringArrays-Guarantee-Audit ~55 min Covering Arrays : oracle constraint-aware, set cover CP-SAT exact, bornes et baselines IPOG/AETG-like — distillation PrCon H4 (Valérian Pichot) Projet étudiant (PrCon PR #58)

Les autres jumeaux C# de la sous-série CSP (N-Queens, GraphColoring, NurseScheduling, JobShop, Timetabling, Minesweeper, Wordle, MiniZinc, Picross, SportsScheduling) suivent le même principe : ré-implémentation .NET du notebook Python de référence, solveurs from-scratch ou OR-Tools natif selon le sujet (marathon #4956).

Applications Hybrides / Métaheuristiques (Applications/Hybrid/)

# Notebook Durée Contenu Source
1 App-9-EdgeDetection ~40 min Détection de bords par GA : PyGAD, filtres de convolution Existant (refonte)
2 App-9b-EdgeDetection-CSharp ~35 min Side track C# : GeneticSharp pour detection de bords Existant
3 App-10-Portfolio ~40 min Optimisation de portefeuille : frontière de Pareto, multi-objectif Existant (refonte)
4 App-10b-Portfolio-CSharp ~30 min Side track C# : GeneticSharp pour portefeuille Existant
5 App-13-TSP-Metaheuristics ~50 min TSP : SA, GA, ACO, OR-Tools routing Classique
6 App-13b-TSP-Metaheuristics-CSharp ~45 min Jumeau C# — SA, GA, ACO from-scratch sur le même TSP, parité #4956 Jumeau .NET
7 App-17-VRP-Logistics ~60 min Vehicle Routing : SA, GA, ACO, CP-SAT Projet étudiant
8 App-17b-VRP-Logistics-CSharp ~55 min Jumeau C# — VRP métaheuristiques .NET, parité #4956 Jumeau .NET
8b App-17b-VRP-Logistics-Python ~45 min Twin Python du b — VRP métaheuristiques from-scratch (numpy) + vérification OR-Tools, parité #4956 Jumeau Python
9 App-18-HyperparameterTuning ~40 min Optimisation ML : Bayésienne, GA, PSO, Optuna Nouveau
10 App-18b-HyperparameterTuning-CSharp ~35 min Jumeau C# — tuning GA/PSO from-scratch .NET, parité #4956 Jumeau .NET
11 App-18b-HyperparameterTuning-Python ~35 min Jumeau Python from-scratch — GP+EI, GA, PSO numpy + pont Optuna, parité #4956 Jumeau Python
12 App-22-AlgorithmSelection-Python ~45 min Sélection empirique d’algorithmes : 3 jeux, 13 familles conceptuelles / 14 étiquettes mesurées, non-commensurabilité + Pareto + choix sous préférences — hommage PR IS #42 (Théodore Deguest) Projet étudiant (IS PR #42)

Parité .NET ⇄ Python

Cette série est née Python d’abord pour son cœur pédagogique (recherche, CSP, applications), avec la Partie 4 — métaheuristiques composables comme territoire .NET natif (au-dessus de MetaGeneticSharp). Le marathon parité EPIC #4956 (juin–juillet 2026) a ensuite généralisé le binôme Python ⇄ C# à l’ensemble du cœur curriculaire : jumeaux C# des fondements (Part 1), de la programmation par contraintes (Part 2), de la recherche heuristique avancée et de 20 cas d’application. Depuis, des compagnons et audits App-21 à App-31 ont porté le dossier Applications à 57 notebooks ; le tableau distingue donc le cœur en binômes de l’inventaire actuel.

Couverture actuelle

Sous-série Cœur pédagogique Langage Correspondance dans l’autre langage
Part1-Foundations 23 (Search-1 à Search-11, Search-2b, Search-2c, Search-03b à Search-03e, Search-09b à Search-09c, Search-11c, Search-11d, Search-12a, Search-13a) Python (22) + C# natif (Search-2c QuikGraph) 15 jumeaux C# (Search-1 à 11, 2b, 03b/03c/03d) + déclinaison deep-dive Search-11b (Métaheuristiques, 4 volets)
Discrepancy 2 (Discrepancy-01 Beck–Fiala, Discrepancy-02 Komlós) Python + Lean 4 (kernel lean4-wsl) Compagnons formels du lake discrepancy_lean
Part2-CSP 9 (CSP-1 à CSP-9) Python + .NET 9 binômes complets — marathon achevé, voir bilan final
Part4-Metaheuristics 35 (25 à la racine + 10 dans MGS-vs-mealpy/) C# / .NET (natif) Prolonge Search-5 / Search-11 (Python) sous l’angle ingénierie
Applications 20 cas cœur (App-1 à App-20), 57 notebooks actuels Python + .NET 20 binômes complets + compagnons et audits App-21 à App-31
Racine 0 — (aucun — voir _archive/ pour les anciens notebooks racine)

La série a atteint la parité Python ⇄ C# complète en juillet 2026 : le marathon EPIC #4956 a livré les jumeaux des trois parties curriculaires et des 20 applications, tous mergés sur main. Seule la Partie 4 reste mono-langage — par conception, puisqu’elle démontre l’ingénierie .NET native au-dessus de GeneticSharp.

Leviers .NET utilisés par le portage

Le levier .NET retenu a dépendu de la dépendance sous-jacente de chaque notebook :

Cible Dépendance Python Levier .NET retenu Remarque
CSP-1 à CSP-9 (modélisation par contraintes) ortools (CSP-3 à CSP-8) Choco-solver via IKVM (CSP-1/2/3/4/5/7) ; Google.OrTools NuGet natif (CSP-6/8) ; from-scratch Yokoo DisCSP (CSP-9) Précédent fondateur : Sudoku-11-Choco-CSharp (Choco via IKVM) et son binôme Sudoku-11-Choco-Python
Search-9 Linear Programming pulp Google.OrTools (NuGet natif, GLOP / PDLP) Port direct, sans IKVM
Recherche d’états et jeux (Search-1 à Search-8) aucune dépendance lourde .NET Interactive pur, structures from-scratch BFS/DFS/A*, Minimax/MCTS, DLX directement portés
Applications (App-1 à App-20) ortools, pygad, stdlib Mix from-scratch / OR-Tools natif / GeneticSharp selon le sujet 20 binômes complets

Le portage s’est fait au fil de l’eau, une tranche par contribution — un notebook .NET exécuté de bout en bout avec ses exercices, jamais une passe monolithique. Le suivi d’ensemble est assuré par l’issue #4956.

Marathon EPIC #4956 — bilan final : parité 9/9 (2026-07-07)

La parité .NET ⇄ Python de la Partie 2 CSP a été portée par un marathon structuré autour de l’EPIC #4956 (mandat user 2026-07-03 : équilibre Choco ⇔ OR-Tools ⇔ from-scratch). Bilan final — 9 binômes C# sur 9, tous mergés sur main :

Notebook PR Cycle Solver C# verdict SOTA Sortie noteworthy
CSP-1-Fundamentals-CSharp #5270 14 (2026-07-03) IKVM 8.15 + Choco-solver 4.10.17 (DLL 12 MB) SOTA-OK Coloration de l’Australie 71 ms ; 8-Reines 102 ms
CSP-2-Consistency-CSharp #5274 15 (2026-07-04) IKVM 8.15 + Choco-solver 4.10.17 SOTA-OK AC-3 custom C# + Choco AC-3 builtin ; audit table Choco ⇔ OR-Tools
CSP-3-Csharp PRs antérieurs antérieur IKVM 8.15 + Choco 4.10.17 MERGED (palette reine / équidistance, base historique)
CSP-4-Scheduling-CSharp #5067 tranche 1 cherry IKVM 8.15 + Choco 4.10.17 (+ audit croisé OR-Tools) SOTA-OK Job-Shop / Nurse Scheduling en Choco IntVar / Task
CSP-5-Optimization-CSharp #5018 → #5133 (rebase) antérieur IKVM 8.15 + Choco 4.10.17 SOTA-OK Bin Packing / Knapsack / cardinalité en Choco
CSP-6-Hybridization-CSharp #5275 16 (2026-07-04) Google.OrTools 9.15.6755 NuGet SOTA-OK CP + ML 50 instances (98 % faisables) ; Portfolio multi-stratégies
CSP-7-Csharp PRs antérieurs antérieur IKVM 8.15 + Choco 4.10.17 MERGED (global-cardinality, symétrie, base historique)
CSP-8-Temporal-CSharp #5276 17 (2026-07-04) Google.OrTools 9.15.6755 SOTA-OK Allen 13 relations + STP Floyd-Warshall + TCSP ; CP-SAT optimal 0,0065 s
CSP-9-Distributed-CSharp #5277 18 (2026-07-04) Algo distribué Yokoo 1992 from-scratch (DisCSP) SOTA-OK AWC 62,0 msgs vs ABT 159,4 msgs à densité 0,5 (2,5× plus efficace) ; -58 % de fuite privacy

Les 9 binômes sont tous mergés sur main (vérifié disque au 2026-07-07 : Part2-CSP/CSP-1-Csharp à CSP-9-Csharp présents et gît-trackés). Le verdict SOTA-OK est documenté dans les PRs du marathon (règle EPIC #3801 — vrai outil, pas workaround dégradé) ; les 2 PRs les plus anciennes (CSP-3, CSP-7) ont été livrées avant la formalisation de la règle et n’ont pas de verdict écrit. Équilibre solvers final : 6 Choco via IKVM (CSP-1/2/3/4/5/7), 2 OR-Tools CP-SAT natif .NET (CSP-6/8), 1 from-scratch (CSP-9, algorithme distribué Yokoo 1992).

Au-delà de la Partie 2, le même marathon a livré les jumeaux C# de la Partie 1 (Search-1 à 11, 2b), de la Partie 3 (Search-03b/03c/03d) et des 20 applications (dont App-20-SudokuBenchmark, créé directement en binôme) — la parité est complète sur tout le périmètre curriculaire de la série.

Concepts clés

Concept Description
Espace d’états Formalisation (S, s0, A, T, G) d’un problème de recherche
BFS/DFS/A* Algorithmes de recherche non informée et informée
Heuristique Fonction h(n) estimant le coût restant (f = g + h pour A*)
Recherche locale Hill Climbing, Simulated Annealing, Tabu Search
Recherche adversariale Minimax, Alpha-Beta pruning, Null-window search
MCTS Monte Carlo Tree Search : Sélection, Expansion, Simulation, Backpropagation
Métaheuristiques PSO, ABC, SA, BRO - optimisation sans dérivées
CSP Constraint Satisfaction Problem : (X, D, C)
Backtracking Exploration systématique avec retour arrière
MRV/LCV Heuristiques de choix de variable/valeur
Arc Consistency Réduction des domaines par propagation (AC-3)
Algorithme Génétique Évolution de population : sélection, crossover, mutation
Dancing Links (DLX) Algorithme X avec listes doublement liées pour couverture exacte
Programmation Linéaire Optimisation linéaire avec contraintes (PuLP, simplex)
Automates Symboliques Prédicats Z3 pour alphabets infinis
OR-Tools CP-SAT Solveur de programmation par contraintes de Google

Ressources

Livres de référence

Bibliothèques

Projets étudiants sources

Les applications sont adaptées de projets étudiants. Les références spécifiques sont indiquées dans chaque notebook d’application.

Structure des fichiers

Search/
├── README.md                              # Ce fichier
├── requirements.txt                       # Dependances Python
├── search_helpers.py                      # Utilitaires partages
├── Part1-Foundations/                     # Search Fondamental — jumeaux directs -Csharp Search-1..11/2b/03b..03d + Search-2c QuikGraph natif + déclinaison Métaheuristiques Search-11b en 4 volets + Search-09b/09c discrépance + Search-03e optimalité A* + Search-11c/11d sélection empirique & descente sous budget + Search-12a Composer-Regards + Search-13a Traverser-Murs-Certifies
│   ├── Search-01-StateSpace.ipynb
│   ├── Search-02-Uninformed.ipynb
│   ├── Search-02b-NetworkX.ipynb
│   ├── Search-02b-NetworkX-CSharp.ipynb   # Twin C# graphes from-scratch (BFS/DFS, Dijkstra, centralités, Ford-Fulkerson) (See #4956)
│   ├── Search-02c-QuikGraph.ipynb
│   ├── Search-03-Informed.ipynb
│   ├── Search-04-LocalSearch.ipynb
│   ├── Search-05-GeneticAlgorithms.ipynb
│   ├── Search-06-AdversarialSearch.ipynb
│   ├── Search-07-MCTS-And-Beyond.ipynb
│   ├── Search-08-DancingLinks.ipynb
│   ├── Search-09-LinearProgramming.ipynb
│   ├── Search-09b-SpuriousMinima.ipynb
│   ├── Search-09c-CombinatorialDiscrepancy.ipynb
│   ├── Search-10-SymbolicAutomata.ipynb
│   ├── Search-11-Metaheuristics.ipynb
│   ├── Search-11c-Empirical-Algorithm-Selection.ipynb
│   ├── Search-11d-Descente-Sous-Budget.ipynb   # Descente gloutonne sous plafond d'évaluations : loi Descent.lean (hstrict/hbarrier) exercée, hnostall réfuté (See #12204)
│   ├── Search-03b-PatternDatabases.ipynb
│   ├── Search-03c-LimitedDiscrepancySearch.ipynb
│   ├── Search-03d-WeightedAstar.ipynb
│   ├── Search-12a-Composer-Regards.ipynb       # Composer des regards : play forward x coplay backward, corridor optimal f*=g+d (op 12 #12204)
│   └── Search-13a-Traverser-Murs-Certifies.ipynb   # Traverser un mur : chemin minimal certifié (potentiels, 0-1 BFS, flot max/coupure min) sur pavage hexagonal (op 13 #12204)
├── Discrepancy/                           # Sous-série formelle (ouverte par #17816, arbitrage Search #17802) : compagnons Lean du lake discrepancy_lean
│   ├── Discrepancy-01-BeckFiala-Lean-Python.ipynb   # Beck–Fiala : pont Python vers le lake, sans Lean au runtime
│   └── Discrepancy-02-Komlos-Lean.ipynb             # Compagnon formel : lake discrepancy_lean via kernel lean4-wsl (#13868)
│
├── Part2-CSP/                             # Programmation par Contraintes (18 notebooks : 9 Python + 9 jumeaux C#)
│   ├── CSP-1-Fundamentals.ipynb
│   ├── CSP-2-Consistency.ipynb
│   ├── CSP-3-Advanced.ipynb
│   ├── CSP-4-Scheduling.ipynb
│   ├── CSP-5-Optimization.ipynb
│   ├── CSP-6-Hybridization.ipynb
│   ├── CSP-7-Soft.ipynb
│   ├── CSP-8-Temporal.ipynb
│   └── CSP-9-Distributed.ipynb
│
├── Applications/
│   ├── Search/                            # Applications Search (4 notebooks)
│   │   ├── App-14b-ConnectFour.ipynb
│   │   ├── App-14c-ConnectFour-CSharp.ipynb
│   │   ├── App-14-ConnectFour-Adversarial.ipynb
│   │   └── App-14-ConnectFour-Adversarial-CSharp.ipynb
│   │
│   ├── CSP/                               # Applications CSP (31 notebooks : sélection ci-dessous, 18 Python + 13 C#)
│   │   ├── App-1-NQueens.ipynb
│   │   ├── App-2-GraphColoring.ipynb
│   │   ├── App-3-NurseScheduling.ipynb
│   │   ├── App-4-JobShopScheduling.ipynb
│   │   ├── App-5-Timetabling.ipynb
│   │   ├── App-6-Minesweeper.ipynb
│   │   ├── App-6-Minesweeper-CSharp.ipynb
│   │   ├── App-7-Wordle.ipynb
│   │   ├── App-8-MiniZinc.ipynb
│   │   ├── App-11-Picross.ipynb
│   │   ├── App-15-SportsScheduling.ipynb
│   │   ├── App-16-Crossword-CSP.ipynb
│   │   ├── App-16-Crossword-CSP-CSharp.ipynb   # Twin C# backtracking + forward-checking from-scratch (marathon #4956, Prong B)
│   │   ├── App-19-ProceduralGeneration-WFC.ipynb
│   │   ├── App-19-ProceduralGeneration-WFC-CSharp.ipynb
│   │   ├── App-20-SudokuBenchmark-Python.ipynb   # Benchmark 4 solveurs Sudoku, synthèse de la série
│   │   ├── App-20b-SudokuBenchmark-CSharp.ipynb
│   │   └── (+ autres notebooks et jumeaux C# App-1b/2b/3b/4b/7b/11b/15b et App-5/8-CSharp, marathon #4956)
│   │
│   └── Hybrid/                            # Métaheuristiques (22 notebooks : sélection ci-dessous, 17 Python + 5 C#)
│       ├── App-9-EdgeDetection.ipynb
│       ├── App-9b-EdgeDetection-CSharp.ipynb
│       ├── App-10-Portfolio.ipynb
│       ├── App-10b-Portfolio-CSharp.ipynb
│       ├── App-13-TSP-Metaheuristics.ipynb
│       ├── App-13b-TSP-Metaheuristics-CSharp.ipynb
│       ├── App-17-VRP-Logistics.ipynb
│       ├── App-17b-VRP-Logistics-CSharp.ipynb
│       ├── App-17b-VRP-Logistics-Python.ipynb      # Twin Python du b — VRP métaheuristiques from-scratch (numpy) + vérification OR-Tools
│       ├── App-18-HyperparameterTuning.ipynb
│       ├── App-18b-HyperparameterTuning-CSharp.ipynb
│       ├── App-18b-HyperparameterTuning-Python.ipynb
│       └── App-22-AlgorithmSelection-Python.ipynb  # Sélection empirique : 3 jeux, 13 familles / 14 étiquettes, Pareto + préférences (PR IS #42)
│
├── MetaGeneticSharp/                      # Sous-module : metaheuristiques composables sur GeneticSharp (jsboige/MetaGeneticSharp)
├── Part4-Metaheuristics/                  # Partie 4 (35 notebooks C# .NET 9 : 25 à la racine + 10 sous MGS-vs-mealpy/) ; consomme le sous-module MetaGeneticSharp
│
└── _archive/                               # Notebooks racine archivés (C209 tranche 8/8 #5081) — voir _archive/README.md
    ├── README.md
    ├── CSPs_Intro.ipynb                                  # Remplacé par Part2-CSP/CSP-1-Fundamentals.ipynb
    └── Exploration_non_informée_et_informée_intro.ipynb # Remplacé par Part1-Foundations/Search-{2,3}-...

Progression recommandée

Le parcours détaillé avec prérequis et enchaînements logiques est décrit dans la section Parcours d’apprentissage ci-dessus.

FAQ / Troubleshooting

OR-Tools ne s’installe pas

OR-Tools nécessite une version Python compatible. Sur Windows : - Vérifiez votre version Python : python --version (3.10-3.12 recommandé) - Installez avec : pip install ortools (les wheels précompilés sont disponibles pour la plupart des plateformes) - Si échec : essayez conda install -c conda-forge ortools-python

MiniZinc ne trouve pas son solveur

Le notebook App-8 utilise MiniZinc qui requiert l’installation de l’IDE : - Téléchargez depuis minizinc.org - Le solveur Gecode est inclus par défaut - Vérifiez : minizinc --version dans un terminal

Les notebooks C# (.NET Interactive) ne s’exécutent pas

  • Vérifiez que .NET SDK 9.0+ est installé : dotnet --version
  • Installez le kernel : dotnet tool install -g Microsoft.dotnet-interactive && dotnet interactive jupyter install
  • Vérifiez : jupyter kernelspec list doit afficher .net-csharp
  • Les jumeaux C# hybrides (App-9b, App-10b) utilisent GeneticSharp et SkiaSharp ; les autres notebooks C# installent leurs packages (Google.OrTools, IKVM + Choco…) via #r nuget dans les cellules

DEAP ou PyGAD provoquent des erreurs d’import

  • DEAP : pip install deap — compatible Python 3.8+
  • PyGAD : pip install pygad — requiert numpy. Si conflit : pip install --upgrade numpy pygad
  • MEALPy (Search-11) : pip install mealpy — dépendances nombreuses, préférez un env dédié

Les solveurs CP-SAT sont lents sur mon problème

  • Vérifiez que vous utilisez model.parameters.max_time_in_seconds pour limiter le temps
  • Les contraintes globales (AllDifferent, Cumulative) sont beaucoup plus efficaces que des contraintes binaires équivalentes
  • Activez la parallélisation : solver.parameters.num_workers = 8
  • Consultez le CP-SAT Primer pour les bonnes pratiques

Comment choisir entre A*, CSP et métaheuristiques ?

  • Espace d’états petit, solution optimale requise : A* avec heuristique admissible
  • Contraintes complexes, domaine discret : CP-SAT (OR-Tools)
  • Grands espaces, approximation acceptable : Métaheuristiques (GA, SA, PSO)
  • Problème de jeux, deux adversaires : Minimax / Alpha-Beta / MCTS
  • Problème NP-difficile, temps limite : LNS (Large Neighborhood Search) dans CP-SAT

Quel parcours choisir ?

Si vous découvrez la recherche en IA

Commencez par Search-1 (StateSpace) et Search-2 (Uninformed) pour comprendre la formalisation des problèmes et les algorithmes fondamentaux (BFS, DFS). Puis Search-3 (Informed) pour découvrir A* et les heuristiques. C’est le socle commun à toute la série.

Si vous venez de la programmation par contraintes

Commencez par CSP-1 (Fundamentals) et CSP-2 (Consistency) si vous connaissez déjà les espaces d’états. Puis montez en complexité avec CSP-3-6 et les applications industrielles (App-3 NurseScheduling, App-4 JobShop).

Si vous préparez un entretien technique

Concentrez-vous sur Search-1 à Search-3 (espaces d’états, BFS/DFS, A*), Search-6 (AdversarialSearch) (Minimax) et CSP-1-2 (backtracking, propagation). Ce sont les algorithmes les plus fréquemment demandés.

Si vous voulez résoudre un problème industriel

Allez directement aux applications qui correspondent à votre domaine : App-3/App-4 (ordonnancement), App-13/App-17 (routing/logistique), App-5 (emploi du temps), ou App-10 (optimisation portefeuille). Chaque application est autonome avec les prérequis indiqués.

Statistiques catalogue à jour (audit fichier-entier §E, 2026-09-16)

Audit disque ↔︎ CATALOG-STATUS ↔︎ prose vérifié firsthand via git ls-files MyIA.AI.Notebooks/Search | grep -E '\.ipynb$' + comptage disque par sous-dossier. Référence canonique = fichiers gît-tracked (les _output.ipynb sont des artéfacts non-trackés par .gitignore — exclus du compte ; MetaGeneticSharp/ et search_lean/ ne contiennent aucun .ipynb). La répartition de maturité (PRODUCTION/BETA) est portée par le marqueur CATALOG-STATUS en tête de fichier, régénéré quotidiennement par l’automatisation (son compte peut traîner d’un jour — le compte ci-dessous fait foi au 2026-09-16).

Sous-série Fichiers .ipynb gît-tracked Langages Algorithmes représentatifs
Part 1 — Fondements (Part1-Foundations/) 43 (23 notebooks Python + Lean : Search-1 → Search-11, Search-2b, Search-03b/03c/03d/03e (ex-Partie 3 + optimalité A*), Search-09b, Search-09c, Search-11c, Search-11d, Search-12a (Composer-Regards, op 12 #12204), Search-13a (Traverser-Murs-Certifies, op 13 #12204) + compagnon Lean Search-09d (kernel lean4-wsl, lake discrepancy_lean) + 20 C# : jumeaux -Csharp (Search-1 à 11, 2b et 03b/03c/03d) + Search-2c QuikGraph natif + déclinaison deep-dive Search-11b Métaheuristiques en 4 volets C# natif, marathon #4956) Python + Lean 4 + .NET (C#) StateSpace, BFS/DFS/UCS/IDDFS, A, Local Search (SA/Tabu), GA, Minimax/Alpha-Beta, MCTS, DLX, LP, Symbolic Automata, métaheuristiques (PSO/ABC/BRO + 160+ MEALPy), NetworkX, QuikGraph, Pattern Databases, Limited Discrepancy Search, Weighted A, minima fallacieux SDP (Burer–Monteiro), discrépance combinatoire (Beck–Fiala, Bansal–Jiang 2025) et sa formalisation Lean 4 (conjecture de Komlós), sélection empirique d’algorithme, descente gloutonne sous plafond d’évaluations (loi Descent.lean)
Part 2 — Programmation par Contraintes (Part2-CSP/) 18 (9 Python : CSP-1 → CSP-9 + 9 jumeaux C#, marathon #4956 achevé) Python + .NET (C#) CSP Fundamentals (backtracking), AC-3/FC/MAC, CSP Advanced (AllDifferent/Cumulative/Circuit), Scheduling (Job-Shop/RCPSP/Nurse), Optimization (Bin Packing/Knapsack), Hybridization (LCG/CP+SAT/CP+ML/LLM+CSP), Soft, Temporal (Allen’s Interval Algebra), Distributed (Yokoo 1992)
Part 4 — Métaheuristiques composables (Part4-Metaheuristics/, C# .NET 9, MetaGeneticSharp) 35 (MGS-1 → MGS-31 : cœur MGS-1..19, trilogie MGS-7b/7c/7d de projection N-D des paysages, MGS-17b sélection empirique, MGS-21 représentation vs algorithme ; le volet comparatif vs MEALPY (10 notebooks MGS-22..31) vit dans la sous-série Part4-Metaheuristics/MGS-vs-mealpy/ — duels PSO/DE/SA/WOA/EO/FBI/BBPSO/GA/ScatterSearch vs Mealpy + synthèse croisée ; tous C# .NET au-dessus de GeneticSharp vendored) C# / .NET Composition, Eukaryote, Islands, Compound Metaheuristics, TSP, projection N-D des paysages, Landscape Explorer, Center Bias, Island Synergy, Axis Alignment, Landscape Debias, Island Synergy Found, Landscape Analysis (FDC), Algorithm Selection (No-Free-Lunch), Parameter Control, CEC Banc, Metropolis Reinsertion, représentation vs algorithme, campagne comparative MGS vs mealpy
Applications (Applications/) 57 (37 Python + 20 C# — 20 binômes Python ⇄ C# App-1 à App-20, plus compagnons statistical-validity, jumeaux Python et notebooks d’audit App-23 à App-31) 37 Python + 20 C# N-Queens, Graph Coloring, Nurse/Job-Shop/Timetabling Scheduling, Minesweeper, Wordle, MiniZinc, Picross (27M× speedup), Sports/Crossword/WFC CSP, SudokuBenchmark, Portfolio/TSP/VRP/Hyperparameter Tuning, Edge Detection, ConnectFour (Minimax/MCTS), Covering Arrays, Algorithm Selection
**_archive** (_archive/) 2 (CSPs_Intro, Exploration_non_informée_et_informée_intro, historiques pré-tranche 8/8 #5081) Python Notebooks historiques, remplacés par Part2-CSP/CSP-1-Fundamentals et Part1-Foundations/Search-{2,3}
Total 153 (43 + 18 + 35 + 57 = 153 pédagogiques, Search-09d inclus + 2 archive = 155) Python + Lean 4 + C# 4 piliers + archive, voir « Structure des fichiers » pour l’arborescence complète

Note de maturité : la validation end-to-end (Python 3.10+ stdlib + ortools + deap + networkx + mealpy + pygad ; C# = .NET 9.0 + Microsoft.dotnet-interactive) est documentée PR par PR dans l’EPIC #4956 pour les jumeaux C#, et dans les PRs po-2025:CoursIA-2 pour la série landscape-bias MGS-10 → MGS-19 (analyse comparative NFL/WOA encore en cours, cf EPIC #3975).

  • Maturité : la répartition autoritative est celle du bloc CATALOG-STATUS automatisé en tête de fichier ; elle n’est pas dupliquée manuellement ici.

Compagnon Lean formel : la série dispose d’un lake phare search_lean (#4048) qui démontre la correction d’A* (admissibilité de l’heuristique ⟹ optimalité, P1), la consistance (P2) et les bornes (P4/P5) en Lean 4 sur des graphes à coût uniforme puis généralisées au cas pondéré. Voir la section « Pont vers les Preuves Formelles (Lean 4) — différenciant CoursIA » l. 640+ pour la cartographie inter-familles focalisée Search (10+ lakes formels du dépôt) et le Mermaid flowchart simulation ↔︎ preuve. Cette section ne duplique pas cette cartographie, elle ancre les chiffres ; la cartographie elle-même reste l. 640+.

Conformité C.1 (stubs sans raise NotImplementedError) : tous les notebooks pédagogiques s’exécutent end-to-end (cellules # Solution/# Exemple résolu démonstratives conservées, cellules # Exercice stubées via pass/return None/print("Exercice à compléter")). Convention trois exercices par notebook respectée pour la majorité des notebooks récents (cf .claude/rules/three-exercises-per-notebook.md).

Dépendances (requirements.txt) : numpy, matplotlib, ortools, z3-solver, deap, pygad, mealpy, simanneal, networkx, python-constraint, minizinc, choco-solver (Java bridge via JPype), openai (LLM+CSP), semantic-kernel, pulp (LP relaxation Part 1). C# : .NET 9.0 + Microsoft.dotnet-interactive (kernel .net-csharp enregistré via dotnet interactive jupyter install) + GeneticSharp vendored (MetaGeneticSharp/) + IKVM 8.15 (CSP-1/3/4/5/7 C# twin bridge).

Parité .NET ⇄ Python (EPIC #4956 marathon achevé) : la parité Python ⇄ C# est désormais complète sur tout le périmètre curriculaire — Part 1 (Search-1 à 11, 2b), Part 2 (CSP-1 à CSP-9, 9 binômes sur 9, tous mergés sur main, vérifié disque 2026-07-07), Part 3 (Search-03b/03c/03d) et les 20 applications. Le détail par solver (6 Choco via IKVM, 2 OR-Tools CP-SAT natif .NET, 1 from-scratch Yokoo 1992) et les verdicts SOTA-OK figurent dans le bilan final du marathon ci-dessus. Seule la Partie 4 reste mono-langage, par conception (ingénierie .NET native au-dessus de GeneticSharp).

Prérequis

Python

# Creer un environnement
python -m venv venv
# Ou: conda create -n search python=3.10

# Installer les dependances
pip install -r requirements.txt

C# (.NET Interactive) - pour side tracks uniquement

# .NET 9.0 requis
dotnet --version

# Les packages NuGet sont installes dans les notebooks :
# - GeneticSharp
# - SkiaSharp (visualisation)

MiniZinc (optionnel, pour App-8)

# Installer MiniZinc IDE depuis https://www.minizinc.org/
# Puis: pip install minizinc

Activités associées

L’activité Exploration : cannibales et missionnaires met la modélisation d’états et l’arbre d’exploration de cette série en situation de jeu d’équipe.

Conclusion / Prochaines étapes

Ce que vous avez appris

Cette série vous a fait traverser l’une des idées les plus fécondes de l’informatique : tout problème, du jeu de plateau à la planification logistique, se réduit à explorer un espace de solutions — et l’art de l’ingénieur est de réduire cette exploration d’une aveugle croissance exponentielle à une résolution intelligemment guidée. L’arc pédagogique :

  • Le geste fondateur — formaliser un problème en espace d’états (S, s₀, A, T, G) plutôt que de le traiter cas par cas. Cette abstraction est le socle commun : sans elle, pas de BFS, pas d’A*, pas de backtracking, pas de Minimax. La série part de là (Search-1) pour reconstruire tout l’édifice algorithmique sur des fondations propres.
  • La double approche, délibérément juxtaposée — d’un côté l’exploration systématique (BFS, DFS, A, Minimax), qui garantit* la solution optimale si on lui laisse le temps mais paie ce coût en explosion combinatoire ; de l’autre la réduction par contraintes (AC-3, Forward Checking, CP-SAT), un véritable changement de paradigme où l’on ne cherche plus mais où l’on contraint les domaines jusqu’à ce que la solution émerge. Comprendre les deux, c’est comprendre quand explorer, quand contraindre, et quand les combiner.
  • L’instrument — les outils qui opérationnalisent la théorie : OR-Tools CP-SAT pour la programmation par contraintes industrielle, A* et ses heuristiques admissibles pour la recherche guidée, Minimax et MCTS pour les jeux, et toute la famille des métaheuristiques (GA, SA, PSO) pour les grands espaces où l’on troque la garantie contre l’efficacité. MiniZinc pour la modélisation déclarative, Z3 pour raisonner sur des alphabets infinis.
  • La finesse — que la modélisation CSP est un art autant qu’une technique (un bon modèle se résout en millisecondes, un mauvais jamais), que les applications réelles (planification d’infirmiers au CHU, ordonnancement d’atelier, optimisation de portefeuille, TSP/VRP logistique, démineur, Picross et son speedup 27M×) sont autant de briques où chaque concept trouve sa justification, et que les frontières les plus excitantes sont les hybridations (LCG, CP+SAT, CP+ML, et surtout LLM+CSP).

La thèse est puissante et honnêtement présentée : il n’existe pas d’algorithme universel de recherche, mais un spectre de stratégies aux compromis clairement cartographiés — garantie vs performance, exploration vs réduction, optimalité vs approximation — et la compétence de l’ingénieur est de savoir choisir dans ce spectre, voire de combiner plusieurs points.

Prochaines étapes

  • Approfondir l’IA symbolique : SymbolicAI (Z3/SMT, planification PDDL/HTN, logique formelle Tweety) est le prolongement naturel de la Partie 2 — les CSP y deviennent du satisfiability solving et la modélisation par contraintes se généralise en raisonnement logique. Plusieurs ponts explicites sont tracés (CSP-3 → Z3, CSP-4 → Planners, CSP-6 → LLM+CSP).
  • Élargir aux jeux et à l’apprentissage par renforcement : GameTheory (Minimax, MCTS, choix social) et les notebooks RL (MCTS + DQN, AlphaGo) reprennent la recherche adversariale sous l’angle de l’apprentissage — où la valeur des positions n’est plus calculée mais apprise.
  • Pratiquer sur la couverture exacte : Sudoku (DLX, automates symboliques) applique Dancing Links et les techniques de cette série à une famille de puzzles combinatoires concrets.
  • Construire plutôt qu’utiliser : la Partie 4 — métaheuristiques composables (C# .NET 9, MetaGeneticSharp) prolonge Search-5/Search-11 sous l’angle de l’ingénierie — au lieu d’importer WOA ou EO, on les reconstruit depuis des primitives composables (Match, Container, grammaire fluente) au-dessus de GeneticSharp, et l’on assemble des configurations qu’aucune bibliothèque monolithique n’offre (sous-populations spécialisées, îles migratoires).
  • Pour la pratique : reprenez CSP-6-Hybridization et expérimentez le pont LLM+CSP — comment un modèle de langage peut-il amorçer un solveur par contraintes, et où cette hybridation gagne-t-elle (ou perd-elle) par rapport au CP-SAT pur ?

Le fil rouge

La recherche en IA propose un changement de regard sur la résolution de problèmes : ne plus demander « quel algorithme appliquer ? » mais « comment réduire l’espace des possibilités jusqu’à ce que la solution devienne inévitable ? ». La série vous a donné le formalisme (espaces d’états, modèle (X, D, C)), les algorithmes (de BFS à MCTS, du backtracking à CP-SAT), et l’intuition des compromis pour transformer un problème combinatoire apparemment intractable en une résolution guidée, contrainte, ou hybridée — en gardant à l’esprit qu’aucune stratégie ne domine partout, et que c’est précisément ce pluralisme qui fait la richesse (et la difficulté) du domaine.

Pont vers les Preuves Formelles (Lean 4) — différenciant CoursIA

Le hub Search alignait une riche prose sur la double approche exploration systématique / réduction par contraintes, mais ne posait pas de cartographie Lean 4 inter-familles formalisée. Le search algorithmique a pourtant un lake phare : search_lean (#4048), où la correction d’A* (admissibilité de l’heuristique ⟹ optimalité), la consistance de l’heuristique (P2) et les bornes sur la complexité (P4/P5) sont démontrées en Lean 4 sur des graphes à coût uniforme puis généralisées au cas pondéré.

grep -E "cartographie|inter-familles" dans le hub Search = 0 occurrence avant cette PR. La même section livrée c.194-c.196 sur les hubs GameTheory (#5050), Probas (#5053) et ML (#5054) reçoit une table focalisée + un Mermaid flowchart ; le hub Search doit donc renvoyer la balle avec une vue locale focalisée Search/search_lean, pas un copier-coller.

Famille Lake phare Théorème / brique Branchement notebook
Search / Part 1 search_lean (#4048) A* admissibilité → optimalité (P1) Search-03-Informed (A*, heuristique admissible)
Search / Part 1 search_lean A* consistance d’heuristique (P2) + relaxation pondérée Search-03d-WeightedAstar (Weighted A*, Pohl 1970)
Search / Part 1 search_lean Pattern DB additives (Korf & Felner 2002) Search-03b-PatternDatabases
ML learning_theory_lean (#5054) Novikoff perceptron 0 sorry #4140 Perceptron.lean (lake, pas notebook pédagogique)
Probas decision_theory_lean (#5053) Concentration uniforme + Hoeffding (PAC iter-2) Infer-3-Factor-Graphs (factor graphs + PAC)
QC kelly_lean (#5047) Kelly criterion + mean-variance bound QC-Py-10-Risk-Portfolio-Management (Kelly sizing)
GameTheory game_theory_lean/SocialChoice (lakes standalone social_choice_lean #5050 + cooperative_games_lean absorbés post-#4365, contenue dans game_theory_lean/) Arrow + Sen voting GameTheory-15-CooperativeGames-Python
GameTheory game_theory_lean/CooperativeGames/Shapley.lean (lake cooperative_games_lean supprimé post-#4365, contenu absorbé) Bondareva-Shapley 0 sorry #3954 GameTheory-13-ImperfectInfo-CFR-Python
SymbolicAI argumentation_lean (#5043 MERGED) Tweety Preferred extensions + Dung framework Tweety-3-Dung-Csharp (Dung Preferred semantics) 
flowchart LR
    subgraph SIM["Simulation (notebooks)"]
        S3["Search-3<br/>A* + heuristique<br/>admissible"]
        S14["Search-14<br/>Weighted A*<br/>Pohl 1970"]
        S12["Search-12<br/>Pattern DB<br/>additives"]
        S6["Search-6<br/>Minimax / Alpha-Beta"]
        S7["Search-7<br/>MCTS + UCB1"]
    end
    subgraph LEAN["Preuves formelles (Lean 4)"]
        LA["search_lean<br/>A* admissibilité<br/>P1/P2/P4/P5"]
        LM["learning_theory_lean<br/>Novikoff perceptron<br/>0 sorry #4140"]
        LP["decision_theory_lean<br/>PAC iter-2<br/>uniform concentration"]
        LK["kelly_lean<br/>Kelly + MV bound"]
        LG["game_theory_lean/SocialChoice<br/>Arrow + Sen<br/>(lakes #4365 absorbés)"]
        LB["game_theory_lean/CooperativeGames<br/>Bondareva-Shapley<br/>0 sorry #3954"]
    end
    S3 -.->|"admissibilité ⟹<br/>optimalité"| LA
    S14 -.->|"pondération W<br/>bornée par"| LA
    S12 -.->|"PDB additives<br/>(Korf 2002)"| LA
    S6 -.->|"valeur de position<br/>+ élagage"| LG
    S7 -.->|"UCB1 + borne<br/>regret cumulé"| LP
    SIM -.->|"simulation<br/>ML.NET / Python"| LEAN
    LEAN -.->|"garantie<br/>formelle"| SIM
    classDef lean fill:#e8f5e9,stroke:#1b5e20,color:#1b5e20
    class LA,LM,LP,LK,LG,LB lean

La double culture simulation + preuve formelle est précisément ce que la cartographie AIMA 3-level du hub central P0 (#5045 MERGED) articule : « instinct algorithmique ↔︎ méta-analyse ↔︎ preuve formelle ». Le hub Search ancre le premier niveau (instinct) par ses notebooks Python/C# git-tracked (parité complète #4956, marqueur CATALOG-STATUS faisant foi — le compte exact vit dans pedagogical_count, régénéré par le cron) et le deuxième niveau (méta-analyse) par les benchmarks comparatifs (App-13 TSP, App-18 hyperparameter tuning, MGS-16 No-Free-Lunch) ; le troisième niveau (preuve formelle) arrive ici via search_lean, qui démontre ce que les simulations Search-3/Search-14 ne peuvent que suggérer empiriquement : qu’une heuristique admissible garantit l’optimalité d’A*, et qu’une heuristique consistente (P2) garantit que le premier chemin trouvé est déjà optimal (sans réouverture).

Sans cette section, le chainage vers ML (perceptron 0 sorry comme borne duale de la convergence A* sur graphes pondérés), QC (Kelly, borné inférieurement par l’arbitrage risque/rendement), GameTheory (Arrow, posant les conditions sur les procédures de vote), Probas (PAC iter-2, formalisant pourquoi un échantillon suffit) et SymbolicAI (argumentation, formalisant la sémantique preferred) restait invisible depuis Search.

Note sur les références notebooks : six références historiques de cette section ont suivi les renumérotations du dépôt (cf issue #5065) : ML-2.3-Perceptron → Perceptron.lean (lake, pas de notebook pédagogique correspondant), Infer-3-ProbabilisticReasoning → Infer-3-Factor-Graphs, QC-Py-10 → QC-Py-10-Risk-Portfolio-Management, GT-15 SocialChoice ↔︎ CooperativeGames et GT-13 CooperativeGames ↔︎ ImperfectInfo-CFR (inversions), Tweety-3-PreferredSemantics → Tweety-3-Dung-Csharp.

Liens : EPIC #4038 (Roadmap Lean) · cross-refs hubs QC (#5047) · central P0 (#5049) · GameTheory (#5050) · Probas (#5053) · ML (#5054) · SymbolicAI Lean (#5043 MERGED).

Licence

Voir la licence du repository principal.

Version 1.3.0 — Juillet 2026 — parité .NET ⇄ Python complète : Part 1/2/3 + 20 applications en binômes (EPIC #4956 marathon achevé, 2026-07-07).

Retour au sommet