10. Exercices et résultats
La vidéo d’accompagnement confirme que les bons énoncés et corrigés ont remplacé des fichiers initialement dupliqués. Les six PDF conservés localement correspondent aux versions affichées le 25 septembre. Pour toute question, la présentation renvoie au courriel, au forum ou à une prise de rendez-vous avec l’équipe d’encadrement.
10.1 Recherche heuristique
Exercice 1 — Taquin, Hill-Climbing escarpé
L1 → LF : ←L2 → LF : →L3 → LF : ↓L4 → LF : ↓, ←
L’ordre imposé des opérations est gauche, haut, droite, bas.
Exercice 2 — Cinq billes
État initial VVBRR, but RRBVV, heuristique égale au nombre de billes mal placées, sans revisite. La séquence d’opérateurs du corrigé est :
1, 4, 1, 3, 3, 4, 1, 2, 3, 2, 3, 2, 4, 1
En cas d’égalité, choisir le nœud le plus à gauche.
Exercice 3 — Comparaison
- Hill-Climbing escarpé :
P, R, puis échec; aucun enfant deRn’améliore l’heuristique. - Meilleur d’abord :
P, R, S, Y, succès avech(Y)=0.
Exercice 4 — Meilleur d’abord
Trace : A, C, B, D, J, W, succès.
Exercice 5 — A dans le labyrinthe*
Chaque déplacement orthogonal coûte 1; h estime la distance jusqu’à la sortie sans tenir compte des murs. La trace corrigée développe notamment F, H, J, A, B, C, E, G, I, puis la sortie. Il faut conserver les parents pour distinguer cette trace du chemin final.
10.2 Jeux avec adversaires
Exercice 1
Après propagation Minimax dans l’arbre de profondeur 5, MAX doit jouer à droite pour garantir le meilleur gain.
Exercice 2
- Niveau MAX intermédiaire :
E=3,F=5,G=2,H=8,I=2,J=5. - Niveau MIN :
B=3,C=2,D=2. - Racine MAX :
A=3. - Choix : MAX joue B.
10.3 Erreurs fréquentes
- Choisir le maximum sans vérifier si l’heuristique est croissante ou décroissante.
- En Hill-Climbing simple, examiner tous les enfants au lieu de prendre le premier strictement meilleur.
- En Hill-Climbing escarpé, accepter un enfant égal au parent.
- En meilleur d’abord, rejeter un enfant uniquement parce qu’il est moins bon que son parent.
- Confondre trace d’expansion et chemin solution.
- Dans A*, oublier
g(n), ne pas remplacer une entrée ouverte par un meilleur chemin ou perdre les parents. - Dans Minimax, évaluer les feuilles du point de vue du joueur dont c’est le tour plutôt que du point de vue de MAX.
- Alterner incorrectement les niveaux MAX et MIN.
- Choisir une feuille très avantageuse sans considérer que MIN peut l’éviter.
- Croire qu’Alpha-Bêta modifie la valeur Minimax plutôt que seulement le travail nécessaire.
P→Q,R,S; Q→T,U; R→V,W; S→X,Y; T→Z,A; U→B; V→C; W→D. h : P=10, Q=9, R=7, S=8, T=8, U=7, V=10, W=9, X=5, Y=0, Z=6, A=7, B=0, C=5, D=7. HC escarpé : P,R,échec; meilleur d’abord : P,R,S,Y, chemin P→S→Y. Chaque boîte donne le nom et h.
Source : PDF locaux officiels Exercices_Heuristique.pdf p.1–4 et Solutions_Heuristique.pdf p.1–2; figures contrôlées le 16 octobre 2026. · 10. Exercices et résultats
A→B,C,D; B→E,F; C→G,H; D→I,J; E→K,L; F→M; G→P,Q; H→R,S; I→T,U; J→W,X. Les autres nœuds sont des feuilles. Heuristiques : A=9, B=5, C=4, D=6, E=9, F=8, G=9, H=8, I=5, J=4, K=3, L=2, M=5, P=0, Q=2, R=7, S=8, T=2, U=1, W=4, X=5. But : première feuille retirée, pas h=0. Trace A,C,B,D,J,W; chemin A→D→J→W.
Source : PDF locaux officiels Exercices_Heuristique.pdf p.1–4 et Solutions_Heuristique.pdf p.1–2; figures contrôlées le 16 octobre 2026. · 10. Exercices et résultats
A→B,C,D; B→E,F; C→G,H; D→I,J; E→K,L; F→M; G→P,Q; H→R,S; I→T,U; J→W,X. Les autres nœuds sont des feuilles. Gains des feuilles puis valeurs propagées affichés. A MAX, B/C/D MIN, E..J MAX. F a seulement M comme feuille. Racine 3, choix B. Alpha-Bêta coupe H et J après G=2 puis I=2.
Source : PDF locaux officiels Exercices_Jeux.pdf p.1–2, Solutions_Jeux.pdf p.1; valeurs contrôlées le 16 octobre 2026. · 10.2 Jeux avec adversaires
Grille de 4 colonnes et 6 lignes. MUR est interdit; N nomme la case sans lettre du PDF. Entrée (0,1), sortie (3,3). Chemin Entrée→A→B→C→E→G→I→Sortie, coût 7; déplacements orthogonaux unitaires, Manhattan comme h. La branche F→H→J ne fait pas partie du chemin final.
Source : PDF locaux officiels Exercices_Heuristique.pdf p.1–4 et Solutions_Heuristique.pdf p.1–2; figures contrôlées le 16 octobre 2026. · 10.1 Recherche heuristique
Les 31 boîtes représentent les nœuds internes aux profondeurs 0..4, alternance MAX/MIN/MAX/MIN/MAX. Chaque boîte du dernier rang prend le maximum de la paire de feuilles correspondante, de gauche à droite. Les 32 feuilles à profondeur5 sont fournies intégralement dans Q30 et la note : a=4, b=5, c=3, d=2, e=3, f=4, g=4, h=6, i=-9, j=-3, k=4, l=12, m=-8, n=0, o=1, p=2, q=15, r=16, s=-12, t=6, u=9, v=1, w=-17, x=-15, y=8, z=17, a1=2, b1=-1, c1=3, d1=7, e1=-5, f1=2. Racine2, sous-arbres gauche0/droite2 : choisir droite. Ce dessin condense les feuilles terminales dans le tableau au lieu de leur attribuer un niveau supplémentaire fictif.
Source : PDF locaux officiels Exercices_Jeux.pdf p.1–2, Solutions_Jeux.pdf p.1; valeurs contrôlées le 16 octobre 2026. · 10.2 Jeux avec adversaires