[Search-03] Greedy graph-search complete sur graphe fini (tableau dit Non) + IDA* passe iterations au slot max_frontier_size #21193

Constat : MyIA.AI.Notebooks/Search/Part1-Foundations/Search-03-Informed.ipynb présente deux défauts techniques vérifiables dans son code et son tableau récapitulatif, plus une note méthodologique sur la portée des benchmarks. Le notebook a aussi un défaut pédagogique connu (A* admissibilité vs consistance) déjà tracké par #14824 (CLOSED 2026-09-05) — cette issue-ci ne le rouvre pas et s'en tient aux deux défauts techniques encore ouverts.

Preuves (lecture directe du notebook, commit courant sur main) :

Défaut 1 — Greedy graph-search est complet sur graphe fini, le tableau dit « Non »

Code (cellule id="exemple-greedy", lignes ~22-30) :

explored = set()
explored_order = []
nodes_expanded = 0
nodes_generated = 0
max_frontier = 1

while frontier:
    h_val, _, current = heapq.heappop(frontier)

    # Ignorer si on a trouve un meilleur chemin vers cet etat
    if current.state in explored:
        continue

    if problem.goal_test(current.state):
        # ...
        return SearchResult('Greedy', current, ...)

    explored.add(current.state)
    explored_order.append(current.state)

L'implémentation est un graph search avec closed set (explored), pas un tree search.

Tableau récapitulatif (cellule id="exemple-tab", markdown) :
| Algorithme | Complet | Optimal | ...
| Greedy | Non | Non | Par $h(n)$ | Oui |

Pourquoi c'est un défaut : la complétude d'un algorithme de recherche dépend de la variante d'implémentation :

• Tree search sans détection des cycles (visite plusieurs fois le même état dans la pile de récursion) : peut boucler indéfiniment sur un graphe à cycles, donc non complet.
• Graph search avec closed set (l'implémentation ici) : sur un graphe fini avec un nombre fini de successeurs par état, l'algorithme termine toujours — soit en trouvant le but, soit en concluant qu'aucun chemin n'existe. Il est complet (sous l'hypothèse standard : $\forall s$, $A(s)$ fini, graphe fini).

L'audit a raison : dire « Greedy = Non complet » sans qualifier la variante est incorrect pour cette implémentation. La nuance est exactement la même que celle que le notebook applique ailleurs pour A* (tableau cell 57 : « optimal avec heuristique consistante, variante Graph-Search sans ré-ouverture, contre-exemple §7 »).

Correction proposée : mettre à jour le tableau en distinguant les deux variantes. Soit :

• Greedy (tree) : Non / Non
• Greedy (graph-search, closed set) : Oui / Non

Et ajouter une note : « La complétude vaut pour les graphes finis avec successeurs finis. Sur des graphes infinis ou des espaces d'états non bornés, Greedy n'est pas complet. »

Défaut 2 — ida_star_search passe iterations au slot max_frontier_size de SearchResult

Code (cellule id="exemple-ida", lignes ~80-86 et ~95-100) :

return SearchResult('IDA*', result, total_expanded,
                    total_generated, iterations,    # <-- 5ème argument
                    elapsed, explored_order,
                    heuristic.__name__)

Le 5ème argument positionnel de SearchResult est max_frontier_size (la taille maximale de la frontière). Vérification croisée par les autres algorithmes du même notebook :

• Greedy (cellule 10) : SearchResult('Greedy', current, nodes_expanded, nodes_generated, max_frontier, ...) — 5ème slot = max_frontier
• A* (cellule 16) : SearchResult('A*', current, nodes_expanded, nodes_generated, max_frontier, ...) — 5ème slot = max_frontier
• BFS (cellule 56) : SearchResult('BFS', child, nodes_expanded, nodes_generated, max_frontier, ...) — 5ème slot = max_frontier

IDA* passe donc iterations dans le slot max_frontier_size. La statistique de mémoire affichée (« frontière maximale de 4 » pour 4 itérations) n'est pas une mesure valide de la mémoire consommée par IDA*.

Pourquoi c'est un défaut : le notebook utilise ensuite cette statistique pour comparer la mémoire d'IDA* à celle d'A*. L'argument pédagogique d'IDA* (« mémoire $O(bd)$ au lieu de $O(b^d)$ pour A* ») est démontrablement vrai dans la littérature, mais la mesure affichée par ce notebook n'est pas une mesure — c'est un compteur d'itérations. Un étudiant qui regarde la table récapitulative et voit « IDA* : frontière max = 4 » peut croire qu'IDA* a tenu en mémoire 4 nœuds, ce qui est plus restrictif que la réalité ($bd$ nœuds, pas 4).

Correction proposée :

• Dans ida_star_search, ajouter un compteur max_recursion_depth incrémenté/décrémenté autour de l'appel récursif search(child, ...), et le passer au 5ème argument de SearchResult au lieu de iterations.
• Ajouter un compteur iterations à part (ex. attribut result.iterations ou dans un dataclass séparé) et l'afficher séparément.
• Si la classe SearchResult n'a pas d'attribut iterations, l'ajouter ou utiliser un dataclass(IDAStarResult) séparé.

Défaut 3 — Note méthodologique (portée des benchmarks) — NON un défaut

L'audit lui-même qualifie ce point en gravité faible : « Il s'agit surtout d'une question d'interprétation des résultats, et non d'un défaut majeur de l'expérience. » Le notebook reconnaît d'ailleurs certaines de ces limites (« la solution non optimale n'apparaît pas sur tous les trajets »).

Ce point n'appelle pas de correction de code. C'est une saine prudence d'interprétation, déjà portée par la prose du notebook. Pas de demande d'action sur ce point dans cette issue.

Doublon — Défaut « A* admissibilité vs consistance »

L'audit a aussi relevé la contradiction pédagogique sur la garantie d'optimalité d'A* (« A* garantit une solution optimale si $h$ est admissible » vs « exige $h$ consistante pour la variante graph-search »). Ce défaut est déjà tracké et résolu :

• Search-3 : le « théorème » admissible ⇒ optimal (c38/c39) est réfuté par l'implémentation du notebook lui-même — sa cellule 15 énonce pourtant la bonne condition #14824 (CLOSED 2026-09-05) — « Search-3 : le « théorème » admissible ⇒ optimal (c38/c39) est réfuté par l'implémentation du notebook lui-même — sa cellule 15 énonce pourtant la bonne condition ».

Le tableau récapitulatif actuel (cellule 57) dit déjà « A* : optimal avec heuristique consistante (variante Graph-Search sans ré-ouverture, contre-exemple §7) ; IDA* : optimal avec heuristique admissible (pas d'ensemble fermé). » La correction est en place. Cette issue-ci ne le rouvre pas.

Distinction avec des simplifications pédagogiques

Pas un B.0 HARD : les algorithmes sont corrects, les exemples calculés sont justes, le contre-exemple A* est une réussite pédagogique. Les deux défauts sont des problèmes de qualification/mesure sur des points périphériques à l'argument central.

Demande

1. Pour Greedy : mettre à jour le tableau de la cellule 57 pour distinguer Greedy (tree) et Greedy (graph-search, closed set), avec mention explicite que la 2e variante est complète sur graphe fini.
2. Pour IDA* : modifier ida_star_search pour mesurer effectivement la profondeur récursive maximale (ou la taille de pile), passer cette mesure au 5ème argument de SearchResult, et exposer iterations séparément (via un nouvel attribut, ou un SearchResult spécialisé, ou un affichage direct).
3. Ré-exécuter le carnet via Papermill (C.2) et joindre le log frais au body de la PR.
4. Vérifier que les notebooks jumeaux Search-03-Informed-CSharp.ipynb, Search-03b-PatternDatabases-Python.ipynb, Search-03d-WeightedAstar-Python.ipynb n'ont pas les mêmes défauts — si oui, factoriser la correction ou ouvrir une issue sœur par carnet.

Travaux existants liés

• Search-3 : le « théorème » admissible ⇒ optimal (c38/c39) est réfuté par l'implémentation du notebook lui-même — sa cellule 15 énonce pourtant la bonne condition #14824 (CLOSED 2026-09-05) — Doublon : A* admissibilité vs consistance (résolu).
• Audit critique au long cours des 1343 notebooks -- campagne Hermes + NanoClaw, decouverte de classes et organes #17073 (OPEN) — EPIC « Audit critique au long cours des 1343 notebooks ».
• [Audit #17073] Série Search — partition NanoClaw #18244 (CLOSED 2026-09-28) — Audit Search partition NanoClaw.
• epic(audit): arc narratif des carnets compliques -- lecture simple d'abord, approfondissements en annexes (generalisation du pilote Lean-31) #18703 (OPEN) — Epic « arc narratif des carnets compliques -- lecture simple d'abord ».
• [ML-Pipeline][L4] train_rl_dt.py : RTG leakage a l'evaluation OOS -- separation entrainement/inference + clarification 'OOS 2027 holdout' #21187 (OPEN) — autre audit du même cycle (DT RTG leakage).
• [Planners-10] generate_plan_tot = wrapper trivial sur generate_plan_direct (ToT non implemente) + CoT raisonnement non transmis au plan + config API conditionnee par HAS_DOTENV #21189 + [Planners-10] Suivi #21189 : etendre validate_pddl_advanced (4 etapes) + rendre visible la nature qualitative du tableau de synthese #21190 (OPEN) — Planners-10 audits.
• [GameTheory-02] find_dominant_strategy ambiguë (>= strict+faible mêlés) + IESDS affiche issue predite sans vérifier taille 1x1 #21192 (OPEN) — GameTheory-02 audit.