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

Constat

Search-3-Informed.ipynb enonce, cellule 38 :

Théorème : A* avec une heuristique admissible est optimal (trouve une solution de coût minimal).

et, cellule 39, dans la table admissible/consistante :

| Effet sur A* | Optimalité | Optimalité + pas de re-open |

Ces deux affirmations sont fausses pour l'implementation que le notebook fournit. Sa cellule 16 ferme definitivement les etats explores : un meilleur g arrivant plus tard sur un etat deja ferme est ignore.

        explored.add(current.state)
        ...
        for child in current.expand(problem, heuristic):
            if child.state not in explored:          # <-- jamais de re-ouverture
                old_g = g_scores.get(child.state, float('inf'))
                if child.path_cost < old_g:
                    ...

g_scores ne garde que la frontiere : il n'existe aucun chemin de code par lequel un etat ferme redevient extensible. Pour cette variante, la consistance n'est pas un bonus « en plus de l'optimalite » — c'est ce qui achete l'optimalite.

Le notebook se contredit lui-meme

La cellule 15 dit deja la bonne chose, et elle la dit bien :

| Optimalité | Oui | Si $h$ est admissible |
| Optimalité | Oui | Si $h$ est consistante (et Graph-Search) |

Théorème : Si $h$ est consistante, alors A* est optimal et n'explore jamais un nœud qui a déjà été visité (pas besoin de re-open).

Vingt-trois cellules plus loin, la distinction Tree-Search / Graph-Search est perdue et l'enonce est reduit a « admissible ⇒ optimal ». Ce n'est donc pas une notion absente du notebook : c'est une notion presente puis aplatie, et c'est la version aplatie qui est etiquetee « Théorème ».

Contre-exemple, execute avec les classes et la fonction du notebook, sur main courant

Cellules 2 / 4 / 6 / 16 chargees telles quelles (ast + exec, aucune reecriture) :

h(S)=3,5, h(A)=0, h(B)=2,5, h(G)=0.

admissible partout ? True   {'G': (0, 0), 'A': (0, 2), 'B': (2.5, 2.5), 'S': (3.5, 3.5)}
                             ^ (h, h*) par etat -- verification EXHAUSTIVE, pas un echantillon
arcs violant la consistance : [('S','A', c=2,   h(S)=3.5 > 2.0),
                               ('B','A', c=0.5, h(B)=2.5 > 0.5)]
A* du notebook  -> ['S', 'A', 'G'] 4

Optimum : S → B → A → G = 3,5. Le notebook rend 4.

L'heuristique est admissible partout — h(n) <= h*(n) verifie sur les quatre etats, pas seulement sur celui qui declenche le defaut. C'est le point : rien dans l'hypothese du « théorème » de la cellule 38 n'est viole, et la conclusion tombe quand meme.

Deux arcs violent la consistance, pas un : S → A autant que B → A.

La ligne « tuiles mal placées » (cellule 39)

• « Tuiles mal placées » est admissible mais pas nécessairement consistante

Dans la definition usuelle — les tuiles numerotees, case vide exclue — cette heuristique est consistante, et la demonstration tient en une ligne : un mouvement fait glisser une seule tuile numerotee, dont le statut « mal placee » passe de vrai a faux, de faux a vrai, ou reste inchange (jamais « bien placee → bien placee », les deux cases etant distinctes). Donc |h(n) − h(n')| <= 1 = c(n,n'), donc h(n) <= c(n,n') + h(n').

La reserve « pas necessairement » n'est vraie que si l'on compte la case vide, auquel cas un mouvement peut changer le compte de 2 — mais cette variante n'est deja plus admissible, ce que la table de la cellule 38 affirme pourtant (« Nombre de tuiles mal placées (8-puzzle) | Oui »). Les deux cellules ne parlent donc pas de la meme heuristique.

Autres sites portant la meme reduction

Ce que ce n'est pas — distinction d'avec #12465 (CLOSED, livree)

#12465 portait l'axe h non admissible → chemin sous-optimal, dont l'instance choisie ne declenchait jamais le defaut (« par chance, la solution non admissible est ici optimale »). Elle est fermee et livree : les cellules 60 et 62 exhibent desormais Grenoble→Marseille, sous-optimal de 105 km.

Le present constat est l'axe symetrique et toujours ouvert : h admissible, et pourtant sous-optimal — parce que la garantie annoncee ne vaut pas pour cette variante de Graph-Search. Le couple des deux contre-exemples est la lecon complete ; l'un ne remplace pas l'autre.

A noter : la livraison de #12465 a fait passer la table §8 de Optimal: Oui inconditionnel a Oui (h admissible). Le mouvement etait bon, la condition retenue est celle qui ne suffit pas ici.

Gate de sequencement — #14790

PR #14790 est OPEN et renomme ce fichier (Search-3-Informed.ipynb → Search-03-Informed.ipynb, et le jumeau C# de meme). Ne pas ouvrir de PR de contenu sur ce chemin avant qu'elle ne soit tranchee (elle porte un CHANGES_REQUESTED d'ai-01 du 2026-09-05T19:21:04Z) ; le fix se pose ensuite sur le chemin post-renommage.

Acceptance

1. La garantie enoncee et l'implementation fournie coincident, par l'une des deux voies : re-ouverture sur amelioration de g, ou enonce restreint aux heuristiques consistantes avec la variante nommee. La cellule 15 est deja correcte : elle sert de reference, elle n'est pas a reecrire.
2. Le graphe a quatre nœuds ci-dessus est conserve comme instance pedagogique, a cote du contre-exemple non-admissible de Search-3 — le contre-exemple 'heuristique non admissible -> chemin sous-optimal' n'est jamais exhibe : le run committe conclut 'par chance, optimale' #12465, et son cout est verifie contre l'optimum (3,5) — pas contre la presence du mot « admissible ». Une comparaison avec Dijkstra/UCS sur le meme graphe est le controle qui rougit si la garantie retombe.
3. Cellule 38 (« Théorème ») et cellule 39 (ligne « Effet sur A* ») corrigees ; c25, c54, c70 et Search-03d c0 reconcilies avec la formulation retenue.
4. La ligne « tuiles mal placées » est corrigee, ou porte explicitement la clause « case vide exclue » qui la rend consistante — et s'accorde avec la table de la cellule 38.
5. Le jumeau C# est traite dans le meme mouvement (meme defaut, meme ligne).
6. C.2 : notebook re-execute, sorties committees, execution_count non nul.

Verifie firsthand sur origin/main (reproduction executee, admissibilite balayee exhaustivement, cellule 16 lue, jumeau C# lu) — pas depuis le rapport d'origine.