Mini-test — Techniques de recherche (1/2)

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.

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.

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 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.

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.

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.