Entraînement — Techniques de recherche (2/2)

Une heuristique est rapide et contextuelle. Elle ne remplace ni le test de but ni les contraintes du problème.

• État : positions des tuiles et du vide; mouvements légaux du vide, EI et but.
• h = nombre de tuiles mal placées hors vide; plus petit est meilleur.
• h classe approximativement les états, sans changer les opérations légales.
• Un calcul très coûteux peut annuler les économies de recherche.

Variantes : Autoévaluation explicite : accepter preuves, noms de variables, substitutions et formulations équivalentes si les étapes et hypothèses restent cohérentes.

Le sens dépend de la définition : bien placées → croissant; mal placées ou coût restant → décroissant.

Variantes : Une réponse exacte selon les données; aucune approximation ou convention implicite supplémentaire.

Le graphe est original et exhaustivement donné. L’ordre A,B,C est imposé; aucun départage supplémentaire n’est nécessaire ici.

• Simple choisit A, premier strictement meilleur, puis bloque car D est moins bon.
• Escarpé examine tous les enfants et choisit B, puis G.
• C égal au parent ne constitue pas une amélioration.
• Le blocage de la version simple n’implique pas absence de solution; ni version n’est complète en général.

Variantes : Autoévaluation explicite : accepter preuves, noms de variables, substitutions et formulations équivalentes si les étapes et hypothèses restent cohérentes.

Meilleur d’abord compare toute la frontière, et peut changer de branche. Il n’impose pas l’amélioration locale de Hill-Climbing.

• Après S : [A1,B2]; après A : [B2,C7].
• B est retiré, puis OUVERTS=[G0,C7]; G est but.
• Trace S,A,B,G; chemin S→B→G.
• C reste disponible même moins bon que A; la frontière conserve des alternatives.

Variantes : Autoévaluation explicite : accepter preuves, noms de variables, substitutions et formulations équivalentes si les étapes et hypothèses restent cohérentes.

f=g+h=10. g est parcouru, h estime le reste; les deux doivent employer une échelle compatible.

Variantes : Une réponse exacte selon les données; aucune approximation ou convention implicite supplémentaire.

La seule admissibilité ne suffit pas à justifier une variante qui ignore les fermés avec heuristique incohérente. Une politique de réouverture adaptée est alors nécessaire.

• Depuis S : A(g3,f5), B(g1,f4); retirer B.
• B améliore A en g2,f4 avec parent B; G est ouvert g9,f9.
• Retirer A; G amélioré g4,f4 avec parent A; retirer G.
• Chemin S→B→A→G, coût 4.
• h est cohérente sur chaque arc : h(u)≤c(u,v)+h(v); avec coûts positifs et h(G)=0, les fermés n’ont pas à être rouverts.

Variantes : Autoévaluation explicite : accepter preuves, noms de variables, substitutions et formulations équivalentes si les étapes et hypothèses restent cohérentes.

La mention orale 14 reste documentée comme résultat historique du maître. Le graphe PDF complet permet maintenant de la contredire par calcul. Séparer coût g, estimation h et priorité f évite de cumuler plusieurs fois les estimations.

• Après v0 : v1(g3,f5), v2(g4,f6), v3(g2,f7), tous de parent v0.
• Après v1 : v5(g10,f13,parent v1); pas f15. Après v2 : v4(g7,f9,parent v2); pas f11.
• Après v3 : v2 est fermé; v4 s’améliore en g3,f5,parent v3. Après v4 : v6(g7,f7,parent v4).
• Retraits v0,v1,v2,v3,v4,v6; solution v0→v3→v4→v6, coût 2+1+4=7.
• Le tableau historique réutilise f du parent au lieu de g dans les coûts suivants : 5+7+3=15, 6+3+2=11, 7+1+2=10, 10+4=14. C’est la cause arithmétique de 14; ce n’est pas le coût du chemin.
• h(v0)=9 dépasse la vraie distance 7; h n’est pas admissible sur tout le graphe et est incohérente, notamment sur v3→v4 : 5>1+2. L’optimalité de ce cas est vérifiée par Dijkstra, sans garantie générale pour cette variante.

Variantes : Autoévaluation explicite : accepter preuves, noms de variables, substitutions et formulations équivalentes si les étapes et hypothèses restent cohérentes.

w=0 donne g (Dijkstra), w=1 donne h (meilleur d’abord). Un facteur positif commun préserve l’ordre, pas la valeur numérique.

Variantes : Une réponse exacte selon les données; aucune approximation ou convention implicite supplémentaire.

Le coût mémoire et le coût de l’heuristique s’ajoutent aux critères d’exploration; le meilleur état dépend du sens de h.

• Hill-Climbing : seul choix local, premier ou meilleur enfant strictement améliorant; alternatives abandonnées.
• Meilleur d’abord : frontière globale triée sur h, alternatives conservées.
• A* : frontière triée sur g+h, amélioration des coûts et parents.
• Aucune garantie d’optimalité sans hypothèses : cohérence pour la variante sans réouverture, ou réouverture adéquate avec admissibilité.

Variantes : Autoévaluation explicite : accepter preuves, noms de variables, substitutions et formulations équivalentes si les étapes et hypothèses restent cohérentes.

Une feuille peut correspondre à un niveau MAX ou MIN dans un autre arbre; la perspective de l’évaluation reste MAX.

• Racine MAX, enfants MIN, feuilles à profondeur 2.
• Exemple : gauche a feuilles 3 et 5; droite a feuilles 2 et 9.
• Toutes les valeurs mesurent l’intérêt de MAX, quel que soit le joueur au niveau feuille.
• À coupure non terminale, l’évaluation est une estimation; après le coup réel, recalculer depuis le nouvel état.

Variantes : Autoévaluation explicite : accepter preuves, noms de variables, substitutions et formulations équivalentes si les étapes et hypothèses restent cohérentes.

B=min(3,5)=3; C=2; D=2. Racine=max(3,2,2)=3, choix B. MAX garantit 3 contre MIN rationnel; la feuille 8 ne peut pas être imposée à MIN.

Variantes : Une réponse exacte selon les données; aucune approximation ou convention implicite supplémentaire.

Le résultat est relatif au modèle, à l’évaluation et à l’adversaire rationnel. Il ne prédit pas toutes les parties contre un adversaire imparfait.

Variantes : Une réponse exacte selon les données; aucune approximation ou convention implicite supplémentaire.

MAX possède déjà B garantissant 3. C/D peuvent être limités à 2 par MIN, donc leurs autres feuilles n’améliorent pas le choix. Le PDF corrigé prime sur la vidéo pour la diapo 22 historique.

• Après B=3, α racine=3.
• Premier enfant de C=2 donne β=2≤α=3; couper sa feuille 8.
• Premier enfant de D=2 donne β=2≤3; couper sa feuille 5.
• Valeur racine 3 comme Minimax; α ne diminue pas, β n’augmente pas dans la propagation d’un même chemin.
• Couper quand α≥β; l’ordre change le travail, pas la valeur; au pire aucune coupure.

Variantes : Autoévaluation explicite : accepter preuves, noms de variables, substitutions et formulations équivalentes si les étapes et hypothèses restent cohérentes.

h est admissible : distances réelles S=5,A=3,B=4,G=0. Elle est incohérente sur B→A : 4>1+0. Ignorer l’amélioration de A laisse G à 6. Rouvrir A avec g=2 permet G à 5. Cet exemple précise la limite de la procédure du support.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

L’admissibilité exige h(n)≤d(n) partout. Le deuxième choix surestime A; le troisième surestime B. Ce tableau seul ne permet pas de vérifier la cohérence, qui dépend aussi des arcs.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

Les coefficients sélectionnent g ou h aux extrêmes. À w=0,5, on obtient (g+h)/2 : même ordre que A* si le départage est identique, mais valeurs divisées par deux.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

Le tri porte d’abord sur h, puis ici sur le nom. Il choisit A sans garantir un coût minimal si les arcs ont des coûts différents.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

Chez MAX, α devient au moins 6 et α≥β. La valeur exacte du sous-arbre peut rester inconnue, mais il ne sera pas préféré par l’ancêtre MIN disposant de 5.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

Une coupure peut fournir une borne plutôt que la valeur exacte de chaque nœud interne. La décision et la valeur racine Minimax sont conservées; le pire cas peut ne rien élaguer.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

Tous peuvent explorer A d’abord. Seul Hill-Climbing a abandonné l’alternative B. Meilleur d’abord conserve B par h; A* le conserve par g+h. L’heuristique donnée n’est pas admissible en S : aucune garantie générale supplémentaire n’est déduite de ce succès.

Variantes : Une réponse exacte sous les conventions de l’énoncé.

Les valeurs exactes calculées par Minimax et les bornes observées pendant Alpha-Bêta sont distinguées. Le second parcours n’a pas besoin de connaître A2=9 ni B2=8 pour conserver la décision racine.

• Valeurs exactes sans élagage : A1=5,A2=9,A=5; B1=4,B2=8,B=4; R=5, choisir A.
• A1 visite 3 puis 5, rend 5; A reçoit β=5. A2 reçoit β=5, visite 6 : α=6≥β=5, coupe la feuille 9.
• A rend exactement 5; R reçoit α=5. B1 visite 2 puis 4, rend 4. B a β=4≤α=5 : couper tout B2, donc feuilles 7 et 8.
• Feuilles visitées dans l’ordre : 3,5,6,2,4; trois feuilles évitées. R reste 5; A2 fournit seulement une borne ≥6 pendant Alpha-Bêta, sans prétendre calculer sa valeur exacte 9.
• Coupure chez MAX A2 à cause de β de A; coupure chez MIN B à cause de α de R.

Variantes : Les renommages uniformes et les démarches équivalentes justifiées sont acceptés.

Une estimation simple peut être utile sans résoudre tout le problème. Ici l’égalité à une borne inférieure certifie aussi le coût optimal du chemin proposé.

• h(x,y)=|2-x|+|1-y|, distance Manhattan ignorant les obstacles, à minimiser.
• Chaque déplacement change h d’au plus 1; h≤1+h(voisin), donc cohérence; aucun obstacle ignoré ne peut raccourcir sous Manhattan.
• Chemin (0,0)→(1,0)→(2,0)→(2,1), coût 3, égal à la borne initiale h=3.
• Calcul constant et rapide; moins informatif qu’une distance exacte tenant compte des murs. Représentation = cases/arcs; stratégie = ordre d’exploration.

Variantes : Les renommages uniformes et les démarches équivalentes justifiées sont acceptés.

La limite précédente confondait ce tableau avec BFS/DFS/Dijkstra. Le tableau de S04 contient bien les deux Hill-Climbing, meilleur d’abord, A*, Minimax et Alpha-Bêta.

• HC simple : premier enfant strictement meilleur dans l’ordre; alternatives abandonnées; ni complétude ni optimalité générales, même si le problème a une solution.
• HC escarpé : meilleur enfant strictement améliorant; alternatives abandonnées après choix; mêmes limites, malgré examen de tous les enfants locaux.
• Meilleur d’abord : meilleur h dans toute la frontière, alternatives conservées; exploration complète sur graphe fini avec traitement correct des doublons, mais coût optimal non garanti.
• A* : g+h, alternatives et parents conservés; coûts positifs, h cohérente pour fermés définitifs, ou politique adaptée de réouverture avec h admissible; optimalité sous ces hypothèses.
• Minimax : MAX prend max, MIN min des mêmes gains MAX; alternatives de coups explorées jusqu’aux feuilles/limite; valeur exacte de l’arbre fini évalué, pas garantie d’optimalité réelle au-delà d’une coupure heuristique.
• Alpha-Bêta : même valeur/décision que Minimax sur ce même arbre, bornes α/β et élagage; gain dépend de l’ordre, pire cas sans gain. Un parcours en profondeur peut libérer les sous-arbres : aucune obligation de conserver tout l’arbre en mémoire.
• Mémoire des alternatives n’est pas mémoire totale : états, fermés, parents et générations de voisins dépendent de l’implémentation. Ne pas donner un O(1) global parce que HC abandonne ses branches.

Variantes : Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Les quatre configurations et la fonction utilisée sont explicites. Aucun état initial n’est à deviner dans une figure absente.

• L1 h=1 : gauche → LF h=0. L2 h=1 : droite → LF h=0. L3 h=1 : bas → LF h=0.
• L4 h=2 : bas → [1,2,3,8,4,*,7,6,5], h=1; gauche → LF, h=0.
• À chaque état, calculer h de tous les voisins légaux, retenir le minimum strictement inférieur; hors grille = opération interdite.
• Les flèches décrivent le mouvement du vide. Si on préfère compter les tuiles bien placées, maximiser 8−h donne les mêmes choix.

Variantes : Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Le recalcul applique la définition précise de l’heuristique et de « plus à gauche ». Des départages globaux différents peuvent modifier la trace; le coût d’un chemin légal est vérifiable indépendamment.

• Trace sans doublon : VVBRR(4),VBVRR(5),VRVBR(4),VRBVR(2),BRVVR(3),RBVVR(3),VRRVB(3),VRRBV(3),VRVRB(4),VRBRV(2),BRVRV(3),RBVRV(3),RRVBV(2),RRBVV(0).
• Chemin par parents : VVBRR→VBVRR→VRVBR→VRVRB→VRBRV→BRVRV→RBVRV→RRVBV→RRBVV.
• Opérateurs du chemin : 1,4,2,3,3,2,4,1 (8 mouvements).
• La liste historique 1,4,1,3,3,4,1,2,3,2,3,2,4,1 n’est pas un chemin continu : après les quatre premiers, BRVVR ne permet pas l’opérateur 3 suivant.
• Elle suit des choix de branches dans l’illustration; l’illustration montre en plus VRRBV deux fois. La version du portail exclut ce doublon conformément à l’énoncé et distingue trace d’exploration/chemin.

Variantes : Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Ce sont les valeurs et liens du PDF, désormais tous fournis. Le résultat du maître est vérifié par une simulation déterministe.

• HC escarpé : P(10)→R(7), puis échec car V(10) et W(9) sont moins bons.
• Meilleur d’abord après P : [R7,S8,Q9]; après R : [S8,Q9,W9,V10] (égalité gauche→droite); après S : [Y0,X5,Q9,W9,V10].
• Retraits P,R,S,Y; succès. Parents de Y : Y←S←P, donc chemin P→S→Y, sans R.
• La frontière conserve Q/S quand R est choisi. HC abandonne ces alternatives et ne peut reprendre S.
• Avec les coûts unitaires ajoutés : A* retire aussi P,R,S,Y. Depuis P : R(g1,f8),S(g1,f9),Q(g1,f10); depuis S : Y(g2,f2),X(g2,f7). Chemin P→S→Y, coût2. h(P)=10>distance2 : l’heuristique de cet exercice de classement n’est pas admissible pour cette adaptation en coût.

Variantes : Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Le même dessin peut servir à une recherche ou à un jeu; la priorité h de cet exercice n’est pas une valeur Minimax.

• Retraits A9,C4,B5,D6,J4,W4 : succès car W est une feuille.
• Après A : C4,B5,D6. Après C : B5,D6,H8,G9. Après B : D6,F8,H8,E9,G9 (ordre spatial pour égalités).
• Après D, J4 est prioritaire; après J, W4 est prioritaire sur I5 et X5.
• Chemin A→D→J→W. P a h=0, mais il n’est pas retiré avant W; le test de but n’est pas ici « h=0 ».

Variantes : Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Les coordonnées et les cases interdites viennent du dessin PDF. L’expression numérique 3 horizontalement +2 verticalement est Manhattan, et non une distance euclidienne.

• Retraits Entrée,F,H,J,A,B,C,E,G,I,Sortie. Le départage f/h/ordre annoncé reproduit cet ordre; d’autres départages peuvent changer la trace sans changer le coût.
• F : g1,h4,f5; H : g2,h3,f5; J : g3,h4,f7. A reste ouvert g1,h6,f7; M est ajouté après J en g4,h5,f9.
• A→B→C donne g1,2,3; depuis C : E et D en g4,h3,f7. E→G→I donne g4,5,6 et h3,2,1.
• Depuis I : Sortie g7,h0,f7 et K g7,h2,f9; M reste ouvert, D aussi, J reste fermé.
• Chemin Entrée→A→B→C→E→G→I→Sortie, coût 7. Dijkstra confirme le minimum; Manhattan est admissible/cohérente sur les arcs unitaires.
• Le tableau du solutionnaire omet M dans les lignes ultérieures et réintroduit J déjà fermé. Le portail conserve la frontière complète et ne répète pas ces erreurs.

Variantes : Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

v0→v3→v4→v6 coûte 2+1+4=7. Le 14 du tableau est une accumulation erronée de priorités f; le coût g ne cumule que les arcs.

Variantes : Entier exact, unité et tolérance indiquées.

Les 32 valeurs ont été relues dans le tableau du PDF d’exercices. La décision « droite » du solutionnaire est confirmée, avec toutes les valeurs qui manquaient au maître.

• Profondeur 4, MAX, 16 valeurs gauche→droite : 5,3,4,6,−3,12,0,2,16,6,9,−15,17,2,7,2.
• Profondeur 3, MIN, 8 valeurs : 3,4,−3,0,6,−15,2,2.
• Profondeur 2, MAX, 4 valeurs : 4,0,6,2.
• Profondeur 1, MIN : gauche=0, droite=2. Racine profondeur 0 MAX : 2, choisir droite.
• Les feuilles sont à profondeur 5, niveau MIN dans cet arbre; leurs évaluations restent du point de vue de MAX. Ne pas inverser le signe des scores selon le joueur.

Variantes : Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.

Les vraies feuilles du PDF sont fournies. H et J sont élagués dans ce parcours précis; les valeurs exactes 8 et 5 sont issues du calcul Minimax complet, pas des feuilles lues par Alpha-Bêta.

• Valeurs MAX : E=max(3,2)=3,F=5,G=max(0,2)=2,H=max(7,8)=8,I=max(2,1)=2,J=max(4,5)=5.
• Valeurs MIN : B=min(3,5)=3,C=min(2,8)=2,D=min(2,5)=2. A=max(3,2,2)=3; choisir B.
• Alpha-Bêta visite K3,L2,M5 puis P0,Q2 : G rend 2, donc C coupe H (R7,S8) car β=2≤α=3.
• I visite T2,U1 et rend 2 : D coupe J (W4,X5) pour la même raison. Feuilles visitées K,L,M,P,Q,T,U : 7 sur 11.
• F ne possède qu’une feuille M; ne pas inventer un second enfant. Les minima et maxima restent alternés; la valeur racine 3 est inchangée.

Variantes : Renommages uniformes et démonstrations équivalentes acceptés si toutes les étapes demandées sont justifiées.