Station MinuitPortail personnel de révision

IFT-2003 — Intelligence artificielle IAutomne 2026

Semaine 3 — Techniques de recherche (1/2)

4. Rechercher dans un espace d’états

LECTURE 05 / 124 repèresSynthèse avec omissions acceptées
Sommaire de cet article
  1. 4. Rechercher dans un espace d’états
  2. 4.1 Directions possibles
  3. 4.2 Cinq critères d’évaluation
  4. 4.3 Cadre générer-tester
Autres lectures de cette unité
  1. Couverture, dates et plan
  2. 1. Finalité et progression
  3. 2. Représenter un problème par un espace d’états
  4. 3. Exemples de modélisation
  5. 4. Rechercher dans un espace d’états
  6. 5. Profondeur, largeur et Dijkstra
  7. 6. Exercices et corrigés
  8. 7. Comparaisons, limites et erreurs fréquentes
  9. 8. Résultats d’apprentissage
  10. 9. Actions personnelles
  11. 10. Carte des sources
  12. 11. Preuve de couverture
Couverture et sources

4. Rechercher dans un espace d’états

4.1 Directions possibles

Une recherche peut partir des données, donc de l’état initial, reculer depuis le but, ou progresser dans les deux directions. Les exemples de la semaine utilisent une recherche avant, de EI vers EF.

Une recherche est dite non informée, aveugle ou exhaustive lorsqu’elle n’a aucune estimation de la proximité du but. Elle connaît uniquement les successeurs légaux et le test de but.

4.2 Cinq critères d’évaluation

  • Exactitude : toute solution retournée satisfait réellement le but.
  • Complétude : une solution est trouvée lorsqu’elle existe et l’absence de solution peut être établie.
  • Optimalité : la solution retournée est la meilleure selon le coût retenu.
  • Complexité temporelle : nombre d’états ou d’opérations nécessaires.
  • Complexité spatiale : mémoire nécessaire pour conserver les états utiles à la recherche.

Ces propriétés dépendent des hypothèses : espace fini ou infini, détection des cycles, coût uniforme ou pondéré, ordre des successeurs et structure effectivement mémorisée.

4.3 Cadre générer-tester

Deux collections structurent l’algorithme :

  • OUVERTS contient les états générés mais non encore développés;
  • FERMÉS contient les états déjà testés et développés.

Procédure générale :

  1. initialiser OUVERTS avec EI et FERMÉS à vide;
  2. retirer le premier état e de OUVERTS;
  3. si e satisfait le but, retourner la solution;
  4. générer les enfants de e au moyen des opérations applicables;
  5. éliminer les enfants déjà dans OUVERTS ou FERMÉS;
  6. déplacer e dans FERMÉS;
  7. insérer les nouveaux enfants dans OUVERTS selon la stratégie;
  8. recommencer tant que OUVERTS n’est pas vide.

La conservation des parents ou d’une information équivalente permet de reconstruire le chemin solution. La détection des doublons évite les cycles et les développements répétés.

Un graphe original pour séparer trace et cheminArcs dirigés uniquement : S→A(2), S→B(1), A→C(2), A→G(7), B→C(1), C→G(2). Aucun autre arc. Départ S, but G; coûts positifs; égalités alphabétiques et but testé au retrait. Les flèches indiquent exactement les arcs, et non leur réciproque.SABCG2 →1 →7 →2 ↓1 →2 ↑Flèches : arcs; nombres : coûts.Dijkstra : S→B→C→G, coût 4.
Un graphe original pour séparer trace et chemin

Arcs dirigés uniquement : S→A(2), S→B(1), A→C(2), A→G(7), B→C(1), C→G(2). Aucun autre arc. Départ S, but G; coûts positifs; égalités alphabétiques et but testé au retrait. Les flèches indiquent exactement les arcs, et non leur réciproque.

Source : Schéma original créé pour le portail le 16 octobre 2026; aucun graphe source incomplet reconstitué. · S03 §4.3–5.3; questions de parcours et Dijkstra

Pile et file : le même état, deux frontièresArcs dirigés S→A,S→B,A→C,B→D; ordre alphabétique. Après développement de S, frontière [A,B]. Retirer A laisse [B]. BFS ajoute C en queue : [B,C]; DFS insère C en tête : [C,B]. Les boîtes ne contiennent que les nœuds encore ouverts; les parents restent A←S,B←S,C←A.Après S : [A, B]Retirer A : [B]BFS : [B, C]DFS : [C, B]Ajout en queueInsertion en tête
Pile et file : le même état, deux frontières

Arcs dirigés S→A,S→B,A→C,B→D; ordre alphabétique. Après développement de S, frontière [A,B]. Retirer A laisse [B]. BFS ajoute C en queue : [B,C]; DFS insère C en tête : [C,B]. Les boîtes ne contiennent que les nœuds encore ouverts; les parents restent A←S,B←S,C←A.

Source : Schéma original du portail, données autonomes; consolidation du 16 octobre 2026. · Maître S03 : 4.3 Cadre générer-tester

Retour au sommaire de l’unitéHaut de page
Récupérer manuellement les données locales

Copier séparément les données ci-dessous dans des fichiers texte avant de fermer la page ou de modifier le stockage. Une valeur illisible ou incompatible reste en place. Aucun effacement ni rétablissement écrasant n’est effectué automatiquement. L’export/import JSON est disponible sur la page Progression du cours. Cette récupération séparée reste utile pour une valeur brute ou un conflit.

Clé de ce cours : . Format v1 porté par cette clé; dates UTC et identifiants durables.

Si l’accès est refusé, la valeur persistée peut rester inaccessible. Réautoriser le stockage dans le navigateur puis rouvrir ce cours permet de la relire. Une réinitialisation exige une décision explicite après récupération; aucune commande de suppression n’est proposée ici. Les données restent sur cette origine et cet appareil, sans transfert automatique.