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

La formalisation définit tous les états et mouvements, pas seulement le chemin 0→1. Ce petit exemple original est autonome.

• État i entier entre 0 et 4, différent de 2.
• EI=0; test de but i=1; opérations gauche/droite de ±1.
• Précondition : destination dans le domaine et non bloquée; effet : nouvelle position.
• Invariant : toujours une case valide; la stratégie choisit l’ordre d’exploration des successeurs.

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

Un même état peut avoir plusieurs occurrences dans l’arbre déroulé. Une chaîne de parents appartient à cet arbre, alors qu’un chemin valide appartient au graphe d’états.

• N={S,A,B,G}; A contient les quatre arcs indiqués; ensemble de départ {S}, GD={G}.
• S→A→G est un chemin solution; A→B→A est un cycle.
• Le graphe n’est pas un arbre : cycle A/B; il faut distinguer graphe d’états et arbre de recherche.
• Dans l’arbre déroulé, racine S, parent de la première occurrence de A = S, enfants B et G.

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

La représentation implicite économise la construction préalable, sans supprimer l’explosion combinatoire ni choisir la stratégie.

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

Alternance et arrêt après victoire contraignent les états et parties. Le calcul simplifié illustre surtout la croissance combinatoire.

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

Aucune graduation ne permet de prélever un volume arbitraire. EI=(0,0), but v4=2; le chemin du maître est une solution, pas la définition du problème.

• État (v4,v3), bornes 0≤v4≤4 et 0≤v3≤3, volumes entiers.
• Précondition v4>0 et v3<3; t=min(v4,3-v3).
• Effet (v4-t,v3+t); depuis (3,2), t=1, donc (2,3).
• Conserver les bornes et le volume pendant le transvidage; remplissage/vidage ont d’autres effets.

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

Un chemin valide transporte lapin, retour seul, chien, retour lapin, salade, retour seul, lapin. La sécurité fait partie de la représentation.

• Sans fermier, lapin et salade restent ensemble : état dangereux.
• Le fermier doit être sur la rive de son passager; bateau : fermier seul ou un passager.
• Les retours permettent de transporter les autres et parfois ramener le lapin.
• Chaque objet appartient exactement à une rive; contrôler les deux rives après chaque traversée.

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

Les quatre règles sont VB→BV, BR→RB, VRB→BRV et BVR→RVB. Chaque transition conserve deux V, deux R et un B dans la séquence totale.

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

L’arithmétique 3+4=7 ne suffit pas à satisfaire la précondition physique.

• Non : les deux chaînes doivent être ouvertes.
• Ouvrir (4,F) en (4,O), attacher en (7,O), puis fermer si voulu.
• La somme totale des longueurs reste 12 dans le problème complet; le nombre de chaînes peut varier.
• Ouvrir/fermer change l’état, pas la longueur.

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

Ne pas généraliser une propriété sans préciser domaine, doublons, coûts et structure mémorisée.

• Avant : depuis EI; arrière : depuis le but avec prédécesseurs; bidirectionnelle : rencontre des frontières.
• Exactitude : solution légale; complétude : trouver si existe sous hypothèses; optimalité : coût minimal défini.
• Temps : travail; espace : structures conservées.
• Espace fini et détection des cycles suffisent au parcours exhaustif; un espace infini exige d’autres conditions.

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

Le parent est fixé à la découverte pour ces deux politiques sans doublon. G est découvert depuis A avant le développement de C. La distinction porte sur les parents mémorisés, pas sur la validité des arcs S→A→C→G.

• Largeur : retraits S,A,B,C,G; parents A←S,B←S,C←A,G←A; solution S→A→G, coût 9.
• Profondeur avec insertion simultanée précisée : retraits S,A,C,G; C ne remplace pas G déjà ouvert; solution mémorisée S→A→G, coût 9.
• S→A→C→G est bien un chemin valide du graphe, de coût 6; ce n’est pas la solution reconstruite par les parents de cette exécution.
• La trace de retrait n’est pas automatiquement le chemin reconstruit.

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

Distances : B=1,A=2; B donne C=2; A est traité avant C à égalité et propose G=9; C remplace G par 4. Chemin S→B→C→G; retraits S,B,A,C,G.

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

Les traces L1/L2/L3 du maître sont des résultats documentés; les figures absentes ne permettent pas une reconstruction fidèle de toutes leurs transitions.

• Non : avec le même premier opérateur, les deux stratégies peuvent partager ce préfixe.
• Il faut connaître les autres successeurs, leur ordre, la politique de doublons et les retraits suivants.
• La compatibilité d’une trace n’est pas une preuve de l’algorithme effectivement employé.

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

Les conventions du maître restent visibles, mais une comparaison doit préciser la structure effectivement conservée; O(n) sur graphe explicite ne supprime pas une croissance exponentielle avec la profondeur.

• Le cours décrit temps O(n) pour chaque nœud visité une fois; n est le nombre de nœuds du graphe parcouru.
• O(w) décrit la frontière; mémoriser tous les fermés et parents peut ajouter O(n).
• Largeur minimise le nombre d’arcs à coûts uniformes; à coûts variables, ce n’est pas le coût minimal.
• Les heuristiques visent à réduire l’exploration, avec leurs propres coûts et garanties.

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

Développer S donne [A,B]; retirer A laisse [B], puis ajouter C en queue donne [B,C]. [C,B] correspondrait à une insertion en tête; les nœuds retirés ne restent pas ouverts.

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

Après S : [A,B]. Retirer A puis insérer C en tête donne [C,B]. Le parent A n’est plus dans la frontière.

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

Le nouveau coût est g(B)+c(B,A)=2+3=5<7. La relaxation met à jour ensemble distance et parent. Le coût de l’arc seul ne vaut pas le coût depuis le départ.

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

BFS minimise le nombre d’arcs sous ses hypothèses de complétude, pas leur coût pondéré. Dijkstra compare les coûts cumulés non négatifs et améliore le parent de G.

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

Une recherche arrière remonte les arcs entrants. Réutiliser seulement les arcs sortants du but peut explorer une zone sans lien avec le départ; bidirectionnelle suppose aussi une rencontre testable.

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

La croissance combinatoire rend l’exploration exhaustive coûteuse. Une heuristique guide l’effort sans garantir à elle seule optimalité, complétude ou absence d’explosion.

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

Exactitude des solutions produites, découverte éventuelle d’une solution et minimalité du coût sont trois propriétés distinctes. La mémoire et le temps sont encore d’autres critères.

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

Les arcs ne sont pas des rotations dans les deux sens. La borne inférieure de trois mouvements prouve la minimalité; choisir une stratégie ne remplace pas la définition des états et opérations.

• N={0,1,2}², 9 états; S={(0,0)}, GD={(1,2)}. A relie chaque état aux deux rotations autorisées.
• Opération i applicable à tout état valide; seul le composant i devient (xi+1) mod 3; l’autre est inchangé.
• Invariant : deux composantes dans {0,1,2}; une seule roue change par arc.
• Exemple minimal (0,0)→(1,0)→(1,1)→(1,2), coût 3. Une rotation sur la première et deux sur la seconde sont nécessaires.
• Le générateur calcule exactement les deux successeurs à la demande; BFS avec mémorisation des états évite les cycles.

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

Le coût et la reconstruction sont tous deux demandés. La trace de cette petite exécution coïncide avec le chemin, ce qui n’est pas une propriété générale.

• Après S : Q(g=1,parent=S),P(g=4,parent=S).
• Après Q : améliorer P(g=2,parent=Q); créer T(g=10,parent=Q).
• Après P : améliorer T(g=5,parent=P). Retirer T : but.
• Retraits S,Q,P,T; parents finaux Q←S,P←Q,T←P; chemin S→Q→P→T, coût 5.
• Chaque relaxation compare g(parent)+coût à la meilleure distance; aucun fermé ne nécessite de réouverture avec Dijkstra sur coûts positifs.

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

La fin de partie est le test de but de cette modélisation. Un autre objectif (gagner pour X) demanderait un autre ensemble GD, sans changer les coups légaux.

• État : tableau 3×3 sur {vide,X,O}; N = grilles atteignables depuis la grille vide en respectant alternance et arrêt dès fin.
• S={grille vide}; GD = grilles terminales atteignables avec alignement de trois marques identiques ou grille pleine.
• Opération placer(joueur,case) : état non terminal, case vide, joueur déterminé par les comptes (#X=#O : X; #X=#O+1 : O). Effet : seule cette case reçoit sa marque.
• Invariants : #X=#O ou #X=#O+1; alternance, aucune case écrasée, aucune transition sortant d’un terminal. Les seuls comptes ne suffisent pas à exclure tous les états illégaux : la définition par atteignabilité impose aussi l’arrêt à la victoire.
• A est l’ensemble de ces transitions légales. La représentation génère les options; Minimax est un choix de stratégie, pas une partie de N.

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

Le but fixe seulement x=2. Une liste de mouvements ne remplace pas les règles capables de générer toutes les transitions.

• N={(x,y) : x entier 0..4,y entier 0..3}; S={(0,0)}; GD={(2,y) : y=0..3}.
• Remplir 4 : x<4, (x,y)→(4,y). Vider 4 : x>0, (x,y)→(0,y).
• Remplir 3 : y<3, (x,y)→(x,3). Vider 3 : y>0, (x,y)→(x,0).
• 4→3 : x>0,y<3; t=min(x,3−y); effet (x−t,y+t). 3→4 : y>0,x<4; t=min(y,4−x); effet (x+t,y−t).
• A contient exactement ces transitions. Invariants : intégralité et bornes; le volume total se conserve pendant un transvasement, pas pendant remplissage/vidage.
• Exemple légal : (0,0)→(0,3)→(3,0)→(3,3)→(4,2)→(0,2)→(2,0). Pas de prélèvement arbitraire dans un bidon non gradué.

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

Le retour avec le lapin est une opération nécessaire. Interdire tous les retours supprimerait des transitions indispensables à la solution.

• N⊆{0,1}⁴ : si C=L alors F=L; si L=S alors F=L. Ces conditions interdisent chaque paire dangereuse sans fermier sur les deux rives.
• Départ {(0,0,0,0)}, but {(1,1,1,1)}.
• Le fermier traverse seul, ou avec un seul objet p∈{C,L,S} placé sur sa rive. Effet : inverser F et, si choisi, p; laisser les autres positions inchangées.
• Préconditions supplémentaires : l’état résultant doit appartenir à N. Les mêmes règles couvrent les deux sens.
• Invariants : chaque identifiant sur une seule rive, bateau avec F et au plus un passager, sécurité maintenue.
• Suite de passagers : lapin, seul, chien, lapin au retour, salade, seul, lapin. Vérifier chaque état et les deux rives.

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

L’espace des configurations valides contient aussi des états non atteignables depuis le départ; le générateur détermine la partie effectivement accessible.

• N = mots de longueur 5 sur {V,R,B}, contenant exactement 2V,2R,1B (30 mots). S={VVBRR}, GD={RRBVV}.
• Op1 : VB→BV; op2 : BR→RB; op3 : VRB→BRV; op4 : BVR→RVB.
• Chaque précondition est la présence du motif contigu de gauche. Remplacer cette occurrence par le motif de droite en conservant le contexte; un seul B rend son emplacement non ambigu.
• A contient toutes et seulement ces substitutions applicables. Longueur et multiplicité des couleurs sont invariantes.
• Un remplacement de mêmes lettres mais dans le mauvais ordre peut respecter le comptage tout en violant l’opérateur. La stratégie décide quel mot généré développer.

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

Le mot « ensemble » du maître est précisé ici comme collection avec multiplicité. Cette précision corrige une ambiguïté formelle sans changer le modèle d’opérations du cours.

• État = MULTIENSEMBLE de couples (n,e), n entier positif,e∈{O,F}; somme des n = 12. Un ensemble mathématique ordinaire ferait disparaître les quatre occurrences identiques du départ.
• S={multiensemble [(3,O),(3,O),(3,O),(3,O)]}; GD={[(12,F)]}.
• Attacher deux occurrences distinctes (i,O),(j,O), toutes deux présentes : les retirer et insérer (i+j,O). Deux occurrences identiques exigent une multiplicité au moins 2.
• Ouvrir : remplacer une occurrence (i,F) par (i,O). Fermer : remplacer (i,O) par (i,F). Les autres occurrences sont inchangées.
• A est l’ensemble de ces transitions. Invariants : somme 12, longueurs positives, multiplicité préservée sauf fusion de deux chaînes en une.
• [(3,O)×4]→[(6,O),(3,O)×2]→[(9,O),(3,O)]→[(12,O)]→[(12,F)]. Le nombre de chaînes varie, pas le nombre total de maillons.

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

Les deux traces du maître sont maintenant recalculables : la liste complète des arcs, l’ordre, le test de but et la politique des doublons sont fournis.

• DFS : A,C,H,Q,R,P,I,G,D,J,S,T,U,K,E,M,L,X.
• BFS : A,C,D,E,B,H,I,G,J,K,M,L,F,Q,R,P,S,T,U,X.
• Dans les deux exécutions : parent(E)=A, parent(L)=E, parent(X)=L; solution A→E→L→X.
• DFS développe C/H, D/J avant de reprendre E. BFS génère les enfants par niveaux. Les états déjà présents dans OUVERTS sont aussi exclus; il ne suffit pas de tester FERMÉS.
• Les arcs numérotés sont des ordres d’opérations, pas des coûts pondérés.

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