Search-1 : Espaces d’etats et formalisation de problemes (C# / .NET 9.0)

Navigation : Index | Précédent | Suivant >>

Jumeau .NET du notebook Python

Ce notebook est le port C# .NET 9.0 de Search-01-StateSpace.ipynb. Il introduit le 5-tuple $(S, s_0, A, T, G)$ qui formalise un problème de recherche, puis l’applique a trois problemes classiques (monde de l’aspirateur, taquin, itineraire). Les algorithmes de recherche (BFS, UCS, A*) ne seront introduits qu’a partir de Search-2 et Search-3 – ici on se concentre sur comment poser un problème, pas sur la stratégie pour le resoudre.

Pourquoi ce twin ?

Portee pedagogique : Search-1 pose les fondations formelles des notebooks 2-11. Les structures SearchProblem définies ici sont reutilisees par Search-2 (BFS/DFS/UCS) et Search-3 (A*). Le jumelage .NET permet de voir l’equivalence stricte avec Python.
Fidelite mathematique : les algorithmes en C# operent sur les mêmes types de données structures BCL (Dictionary<K,V>, ValueTuple, HashSet<T>). Les structures C# refletent la 5-tuple $(S, s_0, A, T, G)$ par des signatures de méthodes rigoureusement identiques au Python.
Couverture EC : ce notebook fait partie de la serie Search-1 a 11 (fondamentaux) et des jumeaux .NET de la serie (cf EPIC #4956).

References

Russell, S. & Norvig, P. – Artificial Intelligence: A Modern Approach (4e ed., 2021), chap. 3 Solving Problems by Searching.
EPIC #4956 : marathon parite .NET pour Search/CSP.
Jumeau Python : Search-01-StateSpace.ipynb.

1. Introduction

Qu’est-ce qu’un problème de recherche ?

Un problème de recherche se caracterise par :

un etat initial $s_0$ (configuration de depart) ;
un ensemble d’actions $A(s)$ applicables selon l’etat courant ;
une fonction de transition $T(s, a) \to s'$ déterministe ;
un test de but qui decide si un etat satisfait l’objectif ;
eventuellement un cout $c(s, a, s')$ par transition.

Une solution est une sequence $a_0, a_1, \dots, a_{n-1}$ telle que $T(\dots T(T(s_0, a_0), a_1), \dots, a_{n-1})$ satisfait le test de but. La qualite d’une solution depend du contexte : nombre d’étapes, cout total, ou tout autre critere.

Objectifs de ce notebook

Formaliser un problème sous forme de 5-tuple $(S, s_0, A, T, G)$ et l’implanter en C# via une classe abstraite SearchProblem.
Voir trois problemes canoniques : monde de l’aspirateur, 8-Puzzle (taquin), recherche d’itineraire.
Distinguer les proprietes cles (taille de l’espace d’etats, facteur de branchement, reversibilite, cout).
Implementer trois variantes en C# (3 exercices conformes a la convention #2161 : >= 3 exercices par notebook).

// Cellule de setup - using directives et classes de base reutilisees partout dans le notebook.
// Les types sont publics (top-level program en .NET Interactive) pour permettre la portee au niveau du submission.
using System;
using System.Collections.Generic;
using System.Linq;

// Classe abstraite representant un probleme de recherche.
// Correspond au 5-tuple (S, s0, A, T, G) avec cout optionnel.
public abstract class SearchProblem {
    // Etat initial s0.
    public abstract object InitialState();

    // Liste des actions applicables dans l'etat donne.
    public abstract IEnumerable<object> Actions(object state);

    // Etat resultant de l'application de l'action.
    public abstract object Transition(object state, object action);

    // Teste si l'etat est un etat objectif.
    public abstract bool IsGoal(object state);

    // Cout de la transition (defaut : 1 par action).
    public virtual double Cost(object state, object action, object nextState) => 1.0;

    // Taille de l'espace d'etats (si calculable, sinon null).
    public virtual int? StateSpaceSize() => null;

    // Representation textuelle concise (utilisee dans les impressions).
    public override string ToString() {
        var size = StateSpaceSize();
        var sizeStr = size.HasValue ? $", |S|={size.Value}" : "";
        return $"SearchProblem({GetType().Name}{sizeStr})";
    }
}

Console.WriteLine("Classe SearchProblem definie.");
Console.WriteLine("Methodes : InitialState(), Actions(s), Transition(s,a), IsGoal(s), Cost(s,a,s')");
Console.WriteLine("Heritage : chaque probleme concret etend SearchProblem et implemente les methodes abstraites.");

Classe SearchProblem definie.
Methodes : InitialState(), Actions(s), Transition(s,a), IsGoal(s), Cost(s,a,s')
Heritage : chaque probleme concret etend SearchProblem et implemente les methodes abstraites.

2. Formalisation d’un problème de recherche

Le 5-tuple $(S, s_0, A, T, G)$

Un problème de recherche est un objet mathematique a cinq composantes :

Symbole	Signification	C# (.NET Interactive)
$S$	Ensemble des etats	type `object` retour des méthodes
$s_0 \in S$	Etat initial	`InitialState()`
$A(s)$	Actions applicables dans l’etat $s$	`Actions(state)` -> `IEnumerable<object>`
$T(s, a) \to s'$	Transition déterministe	`Transition(state, action) -> object`
$G \subseteq S$	Etats objectifs (test d’arret)	`IsGoal(state) -> bool`
$c(s, a, s')$	Cout (optionnel)	`Cost(state, action, next) -> double`

La formalisation en C# objet (vs Python class) impose une signature de méthode stricte : chaque sous-classe doit implementer toutes les méthodes abstraites, ou la compilation echoue (erreur CS0534 ou CS0144).

Pourquoi cette formalisation

Indépendance algorithme/problème : un même BFS, A*, ou UCS peut resoudre n’importe quel SearchProblem. C’est la portee du polymorphisme applique aux algorithmes de recherche.
Test : chaque sous-classe concrete peut etre instanciee et testee separement (3 exemples, 3 exos).
Heritage : toutes les definitions partagent la même API, ce qui simplifie l’orchestration par un algorithme de recherche.

Passons aux trois exemples canoniques.

Classe abstraite en C

La cellule précédente a défini SearchProblem avec quatre méthodes abstraites (InitialState, Actions, Transition, IsGoal) et une méthode virtuelle Cost (1.0 par defaut). En C#, le mot-cle abstract impose que toute classe concrete derivant de SearchProblem doit implementer ces quatre méthodes – c’est plus strict que Python ou les méthodes auraient simplement leve NotImplementedError. Cette rigueur compile-time est un avantage du typage statique.

Le pattern de retour object (non generique) reflete fidelement le Python ou Any est utilise. Pour typer plus strictement on pourrait utiliser une signature generique SearchProblem<TState, TAction> (cf variante avancee en commentaire), mais cela complique la presentation pedagogique – on conserve object.

3. Exemple 1 : Le monde de l’aspirateur

Description

Le monde de l’aspirateur (Russell & Norvig, AIMA 2e ed.) est le plus petit problème de recherche interessant :

2 pieces (gauche, droite) ;
chaque piece peut etre propre (P) ou sale (S) ;
l’aspirateur occupe une piece a la fois ;
3 actions : Aspirer (nettoie la piece courante), Gauche, Droite.

L’etat complet est le tuple (position, gauche_sale, droite_sale) ou position $\in \{G, D\}$ et gauche_sale, droite_sale $\in \{Vrai, Faux\}$. Cela donne $2 \times 2 \times 2 = 8$ etats distincts, dont 2 sont les etats objectifs : $(G, P, P)$ et $(D, P, P)$.

// Etat : tuple (position, gauche_sale, droite_sale)
//   position : 'G' (gauche) ou 'D' (droite)
//   gauche_sale / droite_sale : booleens (true = sale)
//
// IMPORTANT : on sauvegarde l'etat initial comme ValueTuple dans un champ
// pour eviter le transtipage ((char,bool,bool))state dans les Console.WriteLine.
public class VacuumWorld : SearchProblem {
    private readonly (char pos, bool gSale, bool dSale) start;

    public VacuumWorld(char position = 'G', bool gauche_sale = true, bool droite_sale = true) {
        start = (position, gauche_sale, droite_sale);
    }

    public override object InitialState() => start;

    // Actions possibles depuis state : Aspirer + deplacement vers l'autre piece.
    public override IEnumerable<object> Actions(object state) {
        var s = ((char pos, bool gSale, bool dSale))state;
        var acts = new List<object> { "Aspirer" };
        if (s.pos == 'G') acts.Add("Droite");
        else acts.Add("Gauche");
        return acts;
    }

    // Transition deterministe selon l'action.
    public override object Transition(object state, object action) {
        var s = ((char pos, bool gSale, bool dSale))state;
        string a = (string)action;
        return a switch {
            "Aspirer" => s.pos == 'G' ? (s.pos, false, s.dSale) : (s.pos, s.gSale, false),
            "Droite" => ('D', s.gSale, s.dSale),
            "Gauche" => ('G', s.gSale, s.dSale),
            _ => state
        };
    }

    // But : les deux pieces sont propres.
    public override bool IsGoal(object state) {
        var s = ((char pos, bool gSale, bool dSale))state;
        return !s.gSale && !s.dSale;
    }

    public override int? StateSpaceSize() => 8;

    // Enumere tous les etats possibles (8 au total).
    public IEnumerable<(char pos, bool gSale, bool dSale)> AllStates() {
        foreach (var p in new[] { 'G', 'D' })
            foreach (var g in new[] { false, true })
                foreach (var d in new[] { false, true })
                    yield return (p, g, d);
    }
}

// Creation du probleme et demonstration.
// IMPORTANT : on declare s0 avec var (inference => ValueTuple<char,bool,bool>),
// puis on accede aux champs nommes (Item1/Item2/Item3 OU pos/gSale/dSale une fois caste).
var vacuum = new VacuumWorld(position: 'G', gauche_sale: true, droite_sale: true);
var s0 = vacuum.InitialState();
var s0Tuple = ((char pos, bool gSale, bool dSale))s0;

Console.WriteLine($"Probleme : {vacuum}");
Console.WriteLine($"Etat initial : {s0}");
Console.WriteLine($"  -> Position : {s0Tuple.pos}, Gauche sale : {s0Tuple.gSale}, Droite sale : {s0Tuple.dSale}");
Console.WriteLine($"Actions depuis l'etat initial : [{string.Join(", ", vacuum.Actions(s0).Select(a => (string)a))}]");

Probleme : SearchProblem(VacuumWorld, |S|=8)
Etat initial : (G, True, True)
  -> Position : G, Gauche sale : True, Droite sale : True
Actions depuis l'etat initial : [Aspirer, Droite]

Interpretation : Etat initial du monde de l’aspirateur

Sortie obtenue : l’aspirateur est en position Gauche (G), la piece gauche est sale (S), la piece droite est sale (S). L’espace d’etats compte 8 etats au total (2 positions x 2 etats gauche x 2 etats droite).

Observations cles :

L’etat est code par un value tuple (char, bool, bool) en C# 7+, equivalent structurel des tuples Python. C’est le type naturel pour des champs heterogenes peu nombreux.
On accede aux champs par leur nom (s0Tuple.Item1) après un cast explicite (((char pos, bool gSale, bool dSale))s0) – c’est le prix de la signature non-generique object.
Les actions possibles depuis l’etat initial : Aspirer (nettoie la piece gauche), Droite (deplacement vers la piece droite). L’aspirateur ne peut pas aller a gauche depuis la gauche (pas d’action Gauche).

Trace d’exécution

Simulons une sequence d’actions pour resoudre le problème et observons l’evolution de l’etat. La sequence Aspirer puis Droite puis Aspirer est evidente pour l’observateur humain :

depart : $(G, S, S)$ aspirateur a gauche, deux pieces sales ;
étape 1 : Aspirer $\to (G, P, S)$ piece gauche nettoyee ;
étape 2 : Droite $\to (D, P, S)$ aspirateur deplace a droite ;
étape 3 : Aspirer $\to (D, P, P)$ piece droite nettoyee, but atteint.

// Fonction utilitaire : execute une sequence d'actions sur un probleme et affiche la trace.
// Renvoie l'etat final et un booleen indiquant si le but est atteint.
static (object finalState, bool goalReached) TraceSolution(SearchProblem problem, IList<object> actions) {
    var current = problem.InitialState();
    Console.WriteLine("#  Action        Etat                 ");
    Console.WriteLine(new string('-', 50));
    Console.WriteLine($"0  {"(initial)",-12} {current}");
    int step = 0;
    foreach (var action in actions) {
        step++;
        current = problem.Transition(current, action);
        Console.WriteLine($"{step}  {action.ToString(),-12} {current}");
    }
    var isGoal = problem.IsGoal(current);
    Console.WriteLine();
    Console.WriteLine(isGoal ? "==> BUT ATTEINT" : "==> BUT NON ATTEINT");
    return (current, isGoal);
}

// Resolution evidente par l'observation humaine
var actions1 = new List<object> { "Aspirer", "Droite", "Aspirer" };
var (final1, goalReached1) = TraceSolution(vacuum, actions1);

#  Action        Etat                 
--------------------------------------------------
0  (initial)    (G, True, True)
1  Aspirer      (G, False, True)
2  Droite       (D, False, True)
3  Aspirer      (D, False, False)

==> BUT ATTEINT

Interpretation : Solution du monde de l’aspirateur

Sortie obtenue : la sequence Aspirer -> Droite -> Aspirer en 3 actions atteint le but. Une recherche systématique (BFS, voir Search-2) confirmerait que c’est la solution optimale en 3 actions depuis l’etat $(G, S, S)$. On observe aussi que la sequence Droite -> Aspirer -> Gauche -> Aspirer (4 actions) est sous-optimale – d’ou l’intérêt de la recherche systématique sur les graphes d’etats.

Reflexe d’ingenieur : la formalisation en 5-tuple rend trivial le test de sequences manuelles – on n’a besoin ni d’un algorithme, ni d’une UI, juste d’appeler Transition etat par etat. C’est le socle des notebooks suivants : BFS, UCS et A* s’appuient sur le même cycle Actions(state) -> Transition -> IsGoal.

Visualisation du graphe d’etats

Avec seulement 8 etats, nous pouvons visualiser l’integralite du graphe d’etats sans dépendance graphique – une representation ASCII suffit. Cela permet de voir d’un coup d’oeil :

les 8 etats du monde de l’aspirateur ;
les transitions par action (Aspirer, Gauche, Droite) ;
les 2 etats but (lignes vertes) ;
l’etat initial (ligne bleue, ici (G, S, S)).

// Visualisation ASCII du graphe d'etats complet du monde de l'aspirateur.
// 8 etats avec les transitions par action. Pas de dependance graphique.
static void VisualizeVacuumStateSpace(VacuumWorld problem) {
    Console.WriteLine("Graphe d'etats du monde de l'aspirateur (8 etats) :");
    Console.WriteLine();

    // Aspirateur a GAUCHE
    Console.WriteLine("  Aspirateur a GAUCHE (G)");
    Console.WriteLine("  +-----------------------------------------------------------+");
    foreach (var g in new[] { false, true }) {
        foreach (var d in new[] { false, true }) {
            var s = (pos: 'G', gSale: g, dSale: d);
            var isInit = s.Equals(problem.InitialState());
            var isGoal = problem.IsGoal(s);
            string gStr = g ? "S" : "P";
            string dStr = d ? "S" : "P";
            string tag = isInit ? " <- INITIAL" : (isGoal ? " <- BUT" : "");
            Console.WriteLine($"  | (Gauche={gStr}, Droite={dStr}){tag,-13}|");
        }
    }
    Console.WriteLine("  +-----------------------------------------------------------+");
    Console.WriteLine();
    Console.WriteLine("  Aspirateur a DROITE (D)");
    Console.WriteLine("  +-----------------------------------------------------------+");
    foreach (var g in new[] { false, true }) {
        foreach (var d in new[] { false, true }) {
            var s = (pos: 'D', gSale: g, dSale: d);
            var isInit = s.Equals(problem.InitialState());
            var isGoal = problem.IsGoal(s);
            string gStr = g ? "S" : "P";
            string dStr = d ? "S" : "P";
            string tag = isInit ? " <- INITIAL" : (isGoal ? " <- BUT" : "");
            Console.WriteLine($"  | (Gauche={gStr}, Droite={dStr}){tag,-13}|");
        }
    }
    Console.WriteLine("  +-----------------------------------------------------------+");
    Console.WriteLine();
    Console.WriteLine("  Actions : Aspirer (nettoie la piece courante), Gauche, Droite");
    Console.WriteLine();
    Console.WriteLine("  Exemples de transitions depuis l'etat initial (G, S, S) :");
    foreach (var a in problem.Actions(problem.InitialState())) {
        var sPrime = problem.Transition(problem.InitialState(), a);
        Console.WriteLine($"    T((G,S,S), {(string)a,-8}) = {sPrime}");
    }
}

VisualizeVacuumStateSpace(vacuum);

Graphe d'etats du monde de l'aspirateur (8 etats) :

  Aspirateur a GAUCHE (G)
  +-----------------------------------------------------------+
  | (Gauche=P, Droite=P) <- BUT      |
  | (Gauche=P, Droite=S)             |
  | (Gauche=S, Droite=P)             |
  | (Gauche=S, Droite=S) <- INITIAL  |
  +-----------------------------------------------------------+

  Aspirateur a DROITE (D)
  +-----------------------------------------------------------+
  | (Gauche=P, Droite=P) <- BUT      |
  | (Gauche=P, Droite=S)             |
  | (Gauche=S, Droite=P)             |
  | (Gauche=S, Droite=S)             |
  +-----------------------------------------------------------+

  Actions : Aspirer (nettoie la piece courante), Gauche, Droite

  Exemples de transitions depuis l'etat initial (G, S, S) :
    T((G,S,S), Aspirer ) = (G, False, True)
    T((G,S,S), Droite  ) = (D, True, True)

Interpretation : Graphe d’etats de l’aspirateur

Sortie obtenue : 8 etats enumeres, 2 etats but (lignes Gauche=P Droite=P), 1 etat initial (Gauche=S, Droite=S). Les transitions depuis l’etat initial Aspirer puis Droite puis Aspirer produisent le chemin optimal de 3 actions.

Lecon de portee :

Un graphe de 8 sommets est un excellent exemple pedagogique : il est assez petit pour tenir sur un ecran, assez grand pour montrer l’intérêt d’une recherche systématique (vs observation manuelle).
La complexite $b^{d}$ (facteur de branchement $b$ a la profondeur $d$) commence a apparaitre : pour l’aspirateur, $b = 2$ (Aspirer, plus un seul deplacement selon la position) et $d = 3$, soit $2^{3} = 8$ – exactement l’espace d’etats entier : la complexite sature le graphe des 8 configurations, elle ne le depasse pas.
Pour le 8-Puzzle (cf. exemple 2), $b \approx 2.67$ mais $d \approx 22$, soit $2.67^{22} \approx 10^{10}$ : la recherche exhaustive devient impossible.

4. Exemple 2 : Le taquin (8-Puzzle)

Description

Le taquin (8-Puzzle) est une grille $3 \times 3$ contenant 8 tuiles numerotees de 1 a 8 et une case vide (representee par 0). L’etat but classique est :

1 2 3
4 5 6
7 8 _

Les 4 actions sont Haut, Bas, Gauche, Droite – elles deplacent la case vide dans la direction indiquee, en echangeant sa position avec la tuile adjacente. Le nombre d’etats atteignables est $\frac{9!}{2} = 181\,440$ ; les transitions sont reversibles (l’inverse d’un mouvement est possible).

Etat initial pris pour exemple : (7, 2, 4, 5, 0, 6, 8, 3, 1) – configuration typique mentionnee dans AIMA comme etat de test standard.

// Etat : tuple de 9 entiers ; 0 = case vide.
// On utilise ValueTuple<int,int,int,int,int,int,int,int,int> pour 9 champs nommes.
public class EightPuzzle : SearchProblem {
    // Etat but classique (ligne par ligne)
    public static readonly (int a, int b, int c, int d, int e, int f, int g, int h, int i) GOAL =
        (1, 2, 3, 4, 5, 6, 7, 8, 0);

    // Mouvements possibles de la case vide selon sa position (index 0-8)
    private static readonly Dictionary<int, Dictionary<string, int>> MOVES = new() {
        [0] = new() { ["Bas"] = 3, ["Droite"] = 1 },
        [1] = new() { ["Bas"] = 4, ["Gauche"] = 0, ["Droite"] = 2 },
        [2] = new() { ["Bas"] = 5, ["Gauche"] = 1 },
        [3] = new() { ["Haut"] = 0, ["Bas"] = 6, ["Droite"] = 4 },
        [4] = new() { ["Haut"] = 1, ["Bas"] = 7, ["Gauche"] = 3, ["Droite"] = 5 },
        [5] = new() { ["Haut"] = 2, ["Bas"] = 8, ["Gauche"] = 4 },
        [6] = new() { ["Haut"] = 3, ["Droite"] = 7 },
        [7] = new() { ["Haut"] = 4, ["Gauche"] = 6, ["Droite"] = 8 },
        [8] = new() { ["Haut"] = 5, ["Gauche"] = 7 },
    };

    private readonly (int a, int b, int c, int d, int e, int f, int g, int h, int i) start;

    public EightPuzzle((int a, int b, int c, int d, int e, int f, int g, int h, int i) start) {
        this.start = start;
    }

    public override object InitialState() => start;

    // Trouve la position de la case vide (0).
    private static int BlankPos((int a, int b, int c, int d, int e, int f, int g, int h, int i) state) {
        if (state.a == 0) return 0; if (state.b == 0) return 1; if (state.c == 0) return 2;
        if (state.d == 0) return 3; if (state.e == 0) return 4; if (state.f == 0) return 5;
        if (state.g == 0) return 6; if (state.h == 0) return 7; return 8;
    }

    public override IEnumerable<object> Actions(object state) {
        var st = ((int, int, int, int, int, int, int, int, int))state;
        var bp = BlankPos(st);
        return MOVES[bp].Keys.Cast<object>();
    }

    public override object Transition(object state, object action) {
        var st = ((int, int, int, int, int, int, int, int, int))state;
        var arr = new[] { st.Item1, st.Item2, st.Item3, st.Item4,
                          st.Item5, st.Item6, st.Item7, st.Item8, st.Item9 };
        var bp = Array.IndexOf(arr, 0);
        string a = (string)action;
        var targetPos = MOVES[bp][a];
        (arr[bp], arr[targetPos]) = (arr[targetPos], arr[bp]);
        return (arr[0], arr[1], arr[2], arr[3], arr[4], arr[5], arr[6], arr[7], arr[8]);
    }

    public override bool IsGoal(object state) => state.Equals(GOAL);

    // |S| = 9!/2 = 181 440 etats atteignables (la moitie des permutations)
    public override int? StateSpaceSize() {
        long f = 1; for (int i = 2; i <= 9; i++) f *= i;
        return (int)(f / 2);
    }
}

// Creation
var puzzle = new EightPuzzle((7, 2, 4, 5, 0, 6, 8, 3, 1));
var s0p = puzzle.InitialState();
Console.WriteLine($"Taille de l'espace d'etats : {puzzle.StateSpaceSize():N0} etats");
Console.WriteLine($"Etat initial : {s0p}");
Console.WriteLine($"Etat but     : {EightPuzzle.GOAL}");
Console.WriteLine($"Actions depuis l'etat initial : [{string.Join(", ", puzzle.Actions(s0p).Select(a => (string)a))}]");

Taille de l'espace d'etats : 181 440 etats
Etat initial : (7, 2, 4, 5, 0, 6, 8, 3, 1)
Etat but     : (1, 2, 3, 4, 5, 6, 7, 8, 0)
Actions depuis l'etat initial : [Haut, Bas, Gauche, Droite]

Affichage visuel du taquin

Pour mieux comprendre le problème, affichons les etats du taquin sous forme de grille 3x3 ASCII. Les tuiles numerotees 1-8 sont affichees, la case vide (0) apparait comme _.

// Affiche un etat du taquin sous forme de grille 3x3 ASCII.
static void DrawPuzzleState((int a, int b, int c, int d, int e, int f, int g, int h, int i) state, string title = "") {
    if (!string.IsNullOrEmpty(title)) Console.WriteLine($"  {title}");
    var arr = new[] { state.a, state.b, state.c, state.d, state.e, state.f, state.g, state.h, state.i };
    for (int row = 0; row < 3; row++) {
        Console.WriteLine("  +-----+-----+-----+");
        Console.Write("  ");
        for (int col = 0; col < 3; col++) {
            int v = arr[row * 3 + col];
            string cell = v == 0 ? "  _  " : $"  {v}  ";
            Console.Write($"|{cell}");
        }
        Console.WriteLine("|");
    }
    Console.WriteLine("  +-----+-----+-----+");
}

// Affiche une sequence d'etats du taquin (liste verticale compacte).
static void DrawPuzzleSequence(List<(int a, int b, int c, int d, int e, int f, int g, int h, int i)> states,
                              List<string> actions = null, string title = "") {
    if (!string.IsNullOrEmpty(title)) Console.WriteLine($"{title}");
    for (int i = 0; i < states.Count; i++) {
        string frameTitle = $"  Etape {i}";
        if (actions != null && i > 0) frameTitle += $" -- apres action '{actions[i-1]}'";
        if (i == 0) frameTitle = "  Initial";
        DrawPuzzleState(states[i], frameTitle);
        Console.WriteLine();
    }
}

// Simuler quelques mouvements depuis l'etat initial.
var s0p2 = puzzle.InitialState();
var s0Tuple2 = ((int a, int b, int c, int d, int e, int f, int g, int h, int i))s0p2;
var demoActions = new List<object> { "Haut", "Droite", "Bas" };
var demoActionsCast = new List<string> { "Haut", "Droite", "Bas" };

var statesSeq = new List<(int a, int b, int c, int d, int e, int f, int g, int h, int i)> { s0Tuple2 };
object current = s0p2;
foreach (var a in demoActions) {
    current = puzzle.Transition(current, a);
    statesSeq.Add(((int a, int b, int c, int d, int e, int f, int g, int h, int i))current);
}

// Afficher la sequence comme suite verticale
DrawPuzzleSequence(statesSeq, demoActionsCast, "Exploration depuis l'etat initial (3 mouvements) :");

// Facteur de branchement selon la position de la case vide
Console.WriteLine("Facteur de branchement selon la position de la case vide :");
Console.WriteLine("  Coin (positions 0, 2, 6, 8) : 2 actions");
Console.WriteLine("  Bord (positions 1, 3, 5, 7) : 3 actions");
Console.WriteLine("  Centre (position 4)         : 4 actions");
Console.WriteLine($"  Facteur de branchement moyen : {(4 * 2 + 4 * 3 + 1 * 4) / 9.0:F2}");

Exploration depuis l'etat initial (3 mouvements) :
    Initial
  +-----+-----+-----+
  |  7  |  2  |  4  |
  +-----+-----+-----+
  |  5  |  _  |  6  |
  +-----+-----+-----+
  |  8  |  3  |  1  |
  +-----+-----+-----+

    Etape 1 -- apres action 'Haut'
  +-----+-----+-----+
  |  7  |  _  |  4  |
  +-----+-----+-----+
  |  5  |  2  |  6  |
  +-----+-----+-----+
  |  8  |  3  |  1  |
  +-----+-----+-----+

    Etape 2 -- apres action 'Droite'
  +-----+-----+-----+
  |  7  |  4  |  _  |
  +-----+-----+-----+
  |  5  |  2  |  6  |
  +-----+-----+-----+
  |  8  |  3  |  1  |
  +-----+-----+-----+

    Etape 3 -- apres action 'Bas'
  +-----+-----+-----+
  |  7  |  4  |  6  |
  +-----+-----+-----+
  |  5  |  2  |  _  |
  +-----+-----+-----+
  |  8  |  3  |  1  |
  +-----+-----+-----+

Facteur de branchement selon la position de la case vide :
  Coin (positions 0, 2, 6, 8) : 2 actions
  Bord (positions 1, 3, 5, 7) : 3 actions
  Centre (position 4)         : 4 actions
  Facteur de branchement moyen : 2,67

Interpretation : Transitions du taquin

Sortie obtenue : trois mouvements successifs depuis l’etat initial montrent comment la case vide se deplace et quelles tuiles echangent leur position avec elle. Le facteur de branchement moyen est $\approx 2.67$ – typique d’un taquin.

Lecons :

Un mouvement d’une tuile correspond en realite a un mouvement de la case vide en sens inverse (optimisation classique pour economiser une copie).
Les coins (4 positions) ont 2 actions ; les bords (4 positions) en ont 3 ; le centre (1 position) en a 4. La moyenne ponderee est $\approx 2.67$.
Un BFS sur le 8-puzzle depuis un etat typique explore environ $2.67^{22} \approx 10^{10}$ noeuds – beaucoup trop pour une enumeration exhaustive. Cela justifie les algorithmes informes (A*) introduits en Search-3.

5. Exemple 3 : Recherche d’itineraire

Description

Le problème de recherche d’itineraire (route finding) consiste a trouver le chemin le plus court (ou de cout minimal) entre deux villes dans un graphe routier. Contrairement aux deux exemples précédents, l’espace d’etats est implicite (les sommets sont les villes, pas tous les etats enumeres a l’avance).

Caractéristiques : - Etats = sommets du graphe (villes) ; - Actions = aretes sortantes (villes voisines) ; - Transitions déterministes ($s’ = $ voisin) ; - Cout par transition = distance routiere en km ; - Facteur de branchement moyen : nombre moyen d’arcs sortants par sommet (3.15 pour le graphe France : 41 arcs / 13 villes, mesure plus bas).

// Graphe de villes francaises (distances approximatives en km)
// Chaque ville est associee a une liste de (voisin, distance).
var franceGraph = new Dictionary<string, List<(string neighbor, double distance)>> {
    ["Paris"]      = new() { ("Lyon", 465), ("Lille", 225), ("Strasbourg", 490), ("Nantes", 385), ("Bordeaux", 585) },
    ["Lyon"]       = new() { ("Paris", 465), ("Marseille", 315), ("Grenoble", 105), ("Strasbourg", 490), ("Bordeaux", 555) },
    ["Marseille"]  = new() { ("Lyon", 315), ("Toulouse", 405), ("Nice", 200), ("Montpellier", 170) },
    ["Lille"]      = new() { ("Paris", 225), ("Rennes", 510) },
    ["Bordeaux"]   = new() { ("Paris", 585), ("Lyon", 555), ("Toulouse", 250), ("Nantes", 385) },
    ["Toulouse"]   = new() { ("Bordeaux", 250), ("Marseille", 405), ("Montpellier", 250) },
    ["Nice"]       = new() { ("Marseille", 200), ("Grenoble", 335) },
    ["Nantes"]     = new() { ("Paris", 385), ("Bordeaux", 385), ("Rennes", 110), ("Brest", 305) },
    ["Rennes"]     = new() { ("Nantes", 110), ("Lille", 510), ("Brest", 245) },
    ["Brest"]      = new() { ("Nantes", 305), ("Rennes", 245) },
    ["Strasbourg"] = new() { ("Paris", 490), ("Lyon", 490) },
    ["Grenoble"]   = new() { ("Lyon", 105), ("Nice", 335), ("Marseille", 305) },
    ["Montpellier"]= new() { ("Toulouse", 250), ("Marseille", 170) },
};

// Probleme de recherche d'itineraire parametrique sur un graphe.
public class RouteFinding : SearchProblem {
    private readonly Dictionary<string, List<(string neighbor, double distance)>> graph;
    private readonly string startCity;
    private readonly string goalCity;

    public RouteFinding(Dictionary<string, List<(string, double)>> graph, string start, string goal) {
        this.graph = graph;
        this.startCity = start;
        this.goalCity = goal;
    }

    public override object InitialState() => startCity;

    public override IEnumerable<object> Actions(object state) {
        return graph.TryGetValue((string)state, out var neighbors)
            ? neighbors.Select(n => (object)n.neighbor)
            : Enumerable.Empty<object>();
    }

    public override object Transition(object state, object action) => action;

    public override bool IsGoal(object state) => (string)state == goalCity;

    public override double Cost(object state, object action, object nextState) {
        if (!graph.TryGetValue((string)state, out var neighbors)) return double.PositiveInfinity;
        foreach (var (neighbor, distance) in neighbors) {
            if (neighbor == (string)nextState) return distance;
        }
        return double.PositiveInfinity;
    }

    public override int? StateSpaceSize() => graph.Count;
}

// Creation du probleme
var route = new RouteFinding(franceGraph, "Bordeaux", "Strasbourg");
Console.WriteLine($"Probleme : {route}");
Console.WriteLine($"Etat initial (depart) : {route.InitialState()}");
Console.WriteLine($"Etat but (arrivee)   : Strasbourg");
Console.WriteLine($"Nombre de villes |S| = {route.StateSpaceSize()}");
Console.WriteLine($"Actions depuis Bordeaux : [{string.Join(", ", route.Actions(route.InitialState()).Select(a => (string)a))}]");

Probleme : SearchProblem(RouteFinding, |S|=13)
Etat initial (depart) : Bordeaux
Etat but (arrivee)   : Strasbourg
Nombre de villes |S| = 13
Actions depuis Bordeaux : [Paris, Lyon, Toulouse, Nantes]

Visualisation de la carte

Affichons la structure du graphe : 13 villes, aretes avec distances en km, repere de depart (Bordeaux) et d’arrivee (Strasbourg). Une representation textuelle suffit pour un notebook pedagogique – l’objectif est de voir la topologie, pas de rendre une carte interactive.

// Visualisation textuelle du graphe de villes.
// Pour chaque ville, liste les voisins avec distances en km.
static void VisualizeRouteGraph(Dictionary<string, List<(string neighbor, double distance)>> graph,
                                string start = null, string goal = null) {
    Console.WriteLine($"Reseau routier francais ({graph.Count} villes)");
    Console.WriteLine(new string('=', 60));
    Console.WriteLine($"{"Ville",-15} {"Voisins (distance km)",-45}");
    Console.WriteLine(new string('-', 60));
    foreach (var (city, neighbors) in graph.OrderBy(kv => kv.Key)) {
        string prefix;
        if (city == start) prefix = "[START] ";
        else if (city == goal) prefix = "[GOAL]  ";
        else prefix = "        ";
        var neighStr = string.Join(", ", neighbors.Select(n => $"{n.neighbor}({n.distance:F0})"));
        Console.WriteLine($"{prefix}{city,-10} -> {neighStr}");
    }
    Console.WriteLine(new string('=', 60));
}

VisualizeRouteGraph(franceGraph, start: "Bordeaux", goal: "Strasbourg");

Reseau routier francais (13 villes)
============================================================
Ville           Voisins (distance km)                        
------------------------------------------------------------
[START] Bordeaux   -> Paris(585), Lyon(555), Toulouse(250), Nantes(385)
        Brest      -> Nantes(305), Rennes(245)
        Grenoble   -> Lyon(105), Nice(335), Marseille(305)
        Lille      -> Paris(225), Rennes(510)
        Lyon       -> Paris(465), Marseille(315), Grenoble(105), Strasbourg(490), Bordeaux(555)
        Marseille  -> Lyon(315), Toulouse(405), Nice(200), Montpellier(170)
        Montpellier -> Toulouse(250), Marseille(170)
        Nantes     -> Paris(385), Bordeaux(385), Rennes(110), Brest(305)
        Nice       -> Marseille(200), Grenoble(335)
        Paris      -> Lyon(465), Lille(225), Strasbourg(490), Nantes(385), Bordeaux(585)
        Rennes     -> Nantes(110), Lille(510), Brest(245)
[GOAL]  Strasbourg -> Paris(490), Lyon(490)
        Toulouse   -> Bordeaux(250), Marseille(405), Montpellier(250)
============================================================

Interpretation : Reseau routier

Sortie obtenue : 13 villes listees avec leurs voisins et distances. Le reseau n’est pas symetrique exactement (les distances routieres dependent du sens, mais ici pour simplifier on les suppose symetriques).

Observations cles :

Paris est le hub principal (5 voisins), suivi de Lyon (5 voisins) et Marseille (4 voisins) ; les villes peripheriques (Brest, Nice) ont 2 voisins.
L’itineraire Bordeaux -> Strasbourg est realisable en plusieurs chemins : via Paris (direct, 2 sauts), via Lyon (3 sauts), via le sud (5+ sauts). Le cout (somme des distances) varie.
C’est exactement le genre de problème ou UCS (uniform-cost search, voir Search-2) et A* (voir Search-3) prennent tout leur sens : cout non uniforme + besoin d’optimalite.

Comparaison de deux itineraires

Comparons un itineraire direct (peu d’étapes mais cout eleve) et un itineraire detourne (plus d’étapes, distance similaire) sur le trajet Bordeaux -> Strasbourg.

// Evalue un itineraire : cout total et segments detailles.
static (double totalCost, List<(string, string, double)> segments) EvaluatePath(
    RouteFinding problem, List<string> path) {
    double totalCost = 0;
    var segments = new List<(string, string, double)>();
    for (int i = 0; i < path.Count - 1; i++) {
        double c = problem.Cost(path[i], path[i + 1], path[i + 1]);
        totalCost += c;
        segments.Add((path[i], path[i + 1], c));
    }
    return (totalCost, segments);
}

// Itineraire 1 : via Paris (direct)
var path1 = new List<string> { "Bordeaux", "Paris", "Strasbourg" };
var (cost1, segments1) = EvaluatePath(route, path1);

// Itineraire 2 : via le sud (long detour)
var path2 = new List<string> { "Bordeaux", "Toulouse", "Montpellier", "Marseille", "Lyon", "Strasbourg" };
var (cost2, segments2) = EvaluatePath(route, path2);

Console.WriteLine("Comparaison de deux itineraires Bordeaux -> Strasbourg");
Console.WriteLine(new string('=', 60));

Console.WriteLine($"\nItineraire 1 : via Paris");
Console.WriteLine($"  Nombre d'etapes : {path1.Count - 1}");
foreach (var (s, d, c) in segments1) Console.WriteLine($"  {s} -> {d} : {c:F0} km");
Console.WriteLine($"  Distance totale : {cost1:F0} km");

Console.WriteLine($"\nItineraire 2 : via le sud");
Console.WriteLine($"  Nombre d'etapes : {path2.Count - 1}");
foreach (var (s, d, c) in segments2) Console.WriteLine($"  {s} -> {d} : {c:F0} km");
Console.WriteLine($"  Distance totale : {cost2:F0} km");

Console.WriteLine($"\nDifference : {Math.Abs(cost1 - cost2):F0} km");
Console.WriteLine($"Le chemin le plus court est l'itineraire {(cost1 <= cost2 ? "1 (via Paris)" : "2 (via le sud)")}");

Comparaison de deux itineraires Bordeaux -> Strasbourg
============================================================

Itineraire 1 : via Paris
  Nombre d'etapes : 2
  Bordeaux -> Paris : 585 km
  Paris -> Strasbourg : 490 km
  Distance totale : 1075 km

Itineraire 2 : via le sud
  Nombre d'etapes : 5
  Bordeaux -> Toulouse : 250 km
  Toulouse -> Montpellier : 250 km
  Montpellier -> Marseille : 170 km
  Marseille -> Lyon : 315 km
  Lyon -> Strasbourg : 490 km
  Distance totale : 1475 km

Difference : 400 km
Le chemin le plus court est l'itineraire 1 (via Paris)

Interpretation : Nombre d’étapes vs cout

Sortie obtenue : deux itineraires de longueur différente (2 sauts vs 5 sauts) compares en distance reelle. Le chemin via Paris l’emporte clairement en distance (1075 km vs 1475 km via le sud).

Lecon de portee :

Dans un problème ou le cout n’est pas uniforme (kilometres vs simple transition), le nombre d’étapes seul n’est pas un bon critere d’optimalite – il faut un algorithme qui prend en compte les couts.
C’est le rôle de UCS (uniform-cost search) et de A* : choisir le chemin de cout minimal. BFS classique (sur le nombre d’étapes) ne conviendrait pas.
Pour la formalisation en 5-tuple, la différence est uniquement dans la méthode Cost(state, action, next) -> double : 1.0 par defaut (cout uniforme), variable sinon.

Verifier l’optimalite : confier le graphe a un moteur dedie

L’interpretation ci-dessus nomme UCS et A* comme les algorithmes du cout minimal – mais la comparaison qui precede n’en execute aucun : elle evalue deux itineraires choisis a la main et couronne le moins cher des deux. Rien n’y etablit qu’un troisieme trajet ne fasse pas mieux.

C’est precisement la limite qu’un moteur de graphes leve. QuikGraph (successeur de QuickGraph, portage .NET de Boost.Graph) fournit les algorithmes classiques – Dijkstra, A*, Bellman-Ford, composantes connexes, tri topologique – prets a l’emploi, sans reimplementation.

Nous ne dupliquons pas les donnees : nous alimentons QuikGraph avec le franceGraph deja defini, puis lui posons trois questions auxquelles un dictionnaire d’adjacence ne repond pas seul :

quelles sont les caracteristiques mesurees du graphe (sommets, arcs, branchement) ?
le reseau est-il symetrique – tout arc a-t-il sa reciproque ?
quel est le chemin de cout minimal prouve de Bordeaux a Strasbourg ?

#r "nuget: QuikGraph, 2.5.0"

using QuikGraph;
using QuikGraph.Algorithms;

// 1. Alimenter QuikGraph avec les MEMES donnees : aucune duplication du graphe.
//    TaggedEdge<string, double> = arc etiquete par sa distance en km.
var routeGraph = new AdjacencyGraph<string, TaggedEdge<string, double>>();
foreach (var ville in franceGraph.Keys) routeGraph.AddVertex(ville);
foreach (var kv in franceGraph)
    foreach (var (voisin, km) in kv.Value)
        routeGraph.AddEdge(new TaggedEdge<string, double>(kv.Key, voisin, km));

Console.WriteLine("Caracteristiques mesurees du graphe France");
Console.WriteLine(new string('=', 60));
Console.WriteLine($"  Sommets (villes)       : {routeGraph.VertexCount}");
Console.WriteLine($"  Arcs diriges           : {routeGraph.EdgeCount}");
Console.WriteLine($"  Facteur de branchement : {(double)routeGraph.EdgeCount / routeGraph.VertexCount:F2}");

// 2. Un reseau routier devrait etre symetrique : le moteur permet de le verifier.
var sansReciproque = routeGraph.Edges
    .Where(e => !routeGraph.ContainsEdge(e.Target, e.Source))
    .ToList();
Console.WriteLine();
Console.WriteLine(sansReciproque.Count == 0
    ? "  Symetrie : OK, tout arc a sa reciproque."
    : $"  Symetrie : {sansReciproque.Count} arc(s) sans reciproque ; il manque : " +
      string.Join(" ; ", sansReciproque.Select(e => $"{e.Target} -> {e.Source} ({e.Tag:F0} km)")));

// 3. Dijkstra = UCS sur graphe pondere a couts positifs : optimalite prouvee
//    sur TOUT le graphe, pas sur un echantillon de trajets choisis a la main.
Console.WriteLine();
Console.WriteLine("Plus court chemin Bordeaux -> Strasbourg (Dijkstra)");
Console.WriteLine(new string('=', 60));
var plusCourt = routeGraph.ShortestPathsDijkstra(e => e.Tag, "Bordeaux");
if (plusCourt("Strasbourg", out IEnumerable<TaggedEdge<string, double>> chemin)) {
    var aretes = chemin.ToList();
    var villes = new[] { aretes[0].Source }.Concat(aretes.Select(e => e.Target));
    var coutOptimal = aretes.Sum(e => e.Tag);
    Console.WriteLine($"  Trajet : {string.Join(" -> ", villes)}");
    Console.WriteLine($"  Cout   : {coutOptimal:F0} km en {aretes.Count} etapes");
    Console.WriteLine();
    Console.WriteLine("  Face aux deux itineraires choisis a la main :");
    Console.WriteLine($"    itineraire 1 (via Paris)  : {cost1:F0} km  (+{cost1 - coutOptimal:F0} km)");
    Console.WriteLine($"    itineraire 2 (via le sud) : {cost2:F0} km  (+{cost2 - coutOptimal:F0} km)");
}

Installed Packages

QuikGraph, 2.5.0

Caracteristiques mesurees du graphe France
============================================================
  Sommets (villes)       : 13
  Arcs diriges           : 41
  Facteur de branchement : 3,15

  Symetrie : 1 arc(s) sans reciproque ; il manque : Marseille -> Grenoble (305 km)

Plus court chemin Bordeaux -> Strasbourg (Dijkstra)
============================================================
  Trajet : Bordeaux -> Lyon -> Strasbourg
  Cout   : 1045 km en 2 etapes

  Face aux deux itineraires choisis a la main :
    itineraire 1 (via Paris)  : 1075 km  (+30 km)
    itineraire 2 (via le sud) : 1475 km  (+430 km)

Interpretation : ce que le moteur revele

Sortie obtenue : 13 sommets, 41 arcs diriges, facteur de branchement mesure 3.15, 1 arc sans reciproque, et un chemin optimal Bordeaux -> Lyon -> Strasbourg a 1045 km.

Trois enseignements :

Le trajet optimal ne figurait dans aucun des deux itineraires compares. Dijkstra passe par Lyon (555 + 490 km) et economise 30 km sur l’itineraire via Paris – celui-la meme qui etait declare vainqueur ci-dessus. Comparer deux candidats choisis a la main n’etablit rien de plus que leur ordre relatif ; seul un parcours systematique du graphe prouve l’optimalite. C’est exactement ce que promettait l’interpretation precedente en nommant UCS : Dijkstra est UCS sur un graphe pondere a couts positifs.
Le facteur de branchement reel est 3.15, soit 41 arcs pour 13 villes. Un chiffre recopie a la main finit par diverger du graphe qu’il decrit ; le moteur, lui, le recompte a chaque execution.
Un arc n’a pas sa reciproque : Grenoble -> Marseille (305 km) existe, Marseille -> Grenoble non. Un dictionnaire d’adjacence rempli a la main ne signale jamais cet oubli – il faut le demander au graphe. Consequence concrete : ce segment est franchissable dans un sens et introuvable dans l’autre.

Et A* ? Il exige une heuristique admissible (une minoration du cout restant, typiquement la distance a vol d’oiseau), donnee que ce graphe ne porte pas : sans coordonnees, h = 0 reduit A* a Dijkstra exactement – meme chemin, memes sommets examines, aucune capacite demontree. Construire une heuristique et mesurer le gain qu’elle procure est l’objet du notebook Search-03-Informed.

Note de parite : le jumeau Python decrit un autre graphe

Le jumeau Python (Search-01-StateSpace.ipynb) decrit un graphe plus petit : 11 villes, 28 arcs diriges symetriques, facteur de branchement 2.55, poids differents (Bordeaux-Toulouse : 245 km contre 250 ici). Sur ce graphe, l’optimum Bordeaux -> Strasbourg vaut 1075 km via Paris : le moteur y confirme l’itineraire declare vainqueur a la main. La lecon du present notebook – le moteur infirme le choix a la main (1045 km via Lyon) – est donc propre a ce graphe, pas a la serie. L’ecart est consigne dans le registre de parite (scripts/notebook_tools/twin_pairs.d/search-1-statespace.yaml).

6. Proprietes des problemes de recherche

Classification des problemes

Les problemes de recherche se distinguent par plusieurs proprietes qui determinent le choix d’un algorithme adapte (cf. Search-2 et suivants) :

Propriete	Question	Impact algorithmique
Observable	L’agent connait-il parfaitement l’etat ?	Si non : belief state, Branch and Bound
Déterministe	Résultat previsible d’une action ?	Si non : AND/OR search, contingence
Episodique	Les actions dependent-elles du passe ?	Si non : perception au lieu de recherche
Statique	L’environnement change-t-il tout seul ?	Si non : planificateur reactif
Discret	Etats et actions en nombre fini ?	Si continu : méthode numérique (HJB, ILQR)

Les trois exemples de ce notebook sont tous totalement observables, déterministes, statiques, discrets – la catégorie la plus favorable a la recherche systématique.

// Tableau comparatif des trois problemes (caracteristiques quantitatives).
var properties = new (string nom, string aspirateur, string puzzle, string itineraire)[] {
    ("Propriete", "Aspirateur", "8-Puzzle", "Itineraire"),
    ("---------------", "----------", "---------", "----------"),
    ("Observable", "Oui", "Oui", "Oui"),
    ("Deterministe", "Oui", "Oui", "Oui"),
    ("Discret", "Oui", "Oui", "Oui"),
    ("Statique", "Oui", "Oui", "Oui"),
    ("Agent unique", "Oui", "Oui", "Oui"),
    ("---", "---", "---", "---"),
    ("Taille |S|", "8", "181 440", "13 (variable)"),
    ("Facteur branch.", "2", "~2.67", "3.15"),
    ("Cout uniforme", "Oui (1/action)", "Oui (1/action)", "Non (distances)"),
    ("Prof. solution", "2-3", "~22 (moy.)", "Variable"),
    ("Reversible", "Partiel", "Oui", "Oui"),
};

Console.WriteLine("Comparaison des trois problemes de recherche");
Console.WriteLine(new string('=', 70));
foreach (var row in properties) {
    Console.WriteLine($"{row.nom,-16} {row.aspirateur,-13} {row.puzzle,-13} {row.itineraire,-13}");
}

Comparaison des trois problemes de recherche
======================================================================
Propriete        Aspirateur    8-Puzzle      Itineraire   
---------------  ----------    ---------     ----------   
Observable       Oui           Oui           Oui          
Deterministe     Oui           Oui           Oui          
Discret          Oui           Oui           Oui          
Statique         Oui           Oui           Oui          
Agent unique     Oui           Oui           Oui          
---              ---           ---           ---          
Taille |S|       8             181 440       13 (variable)
Facteur branch.  2             ~2.67         3.15         
Cout uniforme    Oui (1/action) Oui (1/action) Non (distances)
Prof. solution   2-3           ~22 (moy.)    Variable     
Reversible       Partiel       Oui           Oui

Interpretation : Comparaison des proprietes

Les trois problemes partagent des proprietes communes (observables, déterministes, discrets, statiques) mais différent sur la taille de l’espace d’etats et sur la structure du cout.

Lecons :

Le passage de l’aspirateur (8 etats) au 8-puzzle (181 440 etats) multiplie la complexite par 22 680 – suffisant pour rendre la recherche exhaustive delicate mais encore realisable.
L’itineraire se distingue par son cout non uniforme : un trajet en 2 sauts peut couter plus cher qu’un detour en 5 sauts. Cela impose des algorithmes tenant compte des couts (UCS, A*).
Tous les exemples sont reversibles (chaque action a un inverse applicable) – cela simplifie la recherche en permettant le backtracking sans conditions speciales.

7. Exercices

Trois exercices pour mettre en pratique la formalisation en C#. Chacun implemente une nouvelle sous-classe de SearchProblem. Les squelettes (stubs) sont fournis – completez-les pour resoudre le problème.

Convention [C.1] : raise NotImplementedError / assert False / 1/0 sont interdits – le notebook doit s’executer end-to-end même si les exercices sont incomplets. On utilise des stubs return null + garde try pour afficher un message clair.

// Exercice 1 : Missionnaires et Cannibales
//
// Trois missionnaires et trois cannibales veulent traverser une riviere.
// Le bateau peut transporter 1 ou 2 personnes a la fois.
// Sur chaque rive (et dans le bateau), si les missionnaires sont plus
// nombreux que les cannibales, ils sont devores.
//
// Etat : (missionnaires_gauche, cannibales_gauche, position_bateau)
//   position_bateau : 'G' (gauche) ou 'D' (droite)
//   missionnaires_gauche, cannibales_gauche : entiers entre 0 et 3.
//
// Indices :
// - initial_state() retourne (3, 3, 'G') -- tout le monde a gauche.
// - IsValid(state) verifie 0 <= m, c <= 3 et securite (m >= c OU m == 0 sur chaque rive).
// - actions(state) genere les paires (m, c) avec 1 <= m+c <= 2.
// - transition(state, action) deplace (m, c) selon la position du bateau.
// - is_goal(state) verifie (0, 0, 'D').
public class MissionariesCannibals : SearchProblem {
    public override object InitialState() {
        // TODO etudiant : retourner le tuple (3, 3, 'G').
        return null;
    }

    // Verifie que l'etat est valide (pas de missionnaire devore).
    private bool IsValid((int mG, int cG, char boat) state) {
        // TODO etudiant :
        //   - bornes : 0 <= mG, cG <= 3
        //   - securite gauche : si mG > 0 alors mG >= cG
        //   - securite droite : si (3-mG) > 0 alors (3-mG) >= (3-cG)
        return false;
    }

    public override IEnumerable<object> Actions(object state) {
        // TODO etudiant :
        //   - generer les paires (m, c) avec 1 <= m+c <= 2, 0 <= m, c <= 3
        //   - selon la rive du bateau, envoyer dans un sens ou dans l'autre
        //   - valider l'etat resultant avant de l'inclure dans les actions
        return new List<object>();
    }

    public override object Transition(object state, object action) {
        // TODO etudiant :
        //   - recuperer (m, c) de l'action
        //   - selon la rive du bateau : ajouter ou soustraire (m, c)
        //   - basculer la position du bateau
        return null;
    }

    public override bool IsGoal(object state) {
        // TODO etudiant : retourner (mG, cG, boat) == (0, 0, 'D').
        return false;
    }
}

Console.WriteLine("Classe MissionnairesCannibals definie (squelette).");
Console.WriteLine("Completez les methodes pour resoudre le probleme.");

Classe MissionnairesCannibals definie (squelette).
Completez les methodes pour resoudre le probleme.

Indices pour l’exercice 1 :

Rappels : - Utilisez une recherche en largeur (BFS) sur l’espace d’etats (16 etats possibles au total, 10 accessibles). - Le mystere classique : la solution optimale necessite 11 traversees (et non 9), avec une configuration ou les cannibales commencent par partir pour reduire le nombre de missionnaires exposes. - Verifiez systematiquement la securite après chaque transition : si vous etes perdu sur un etat invalide, IsValid doit le rejeter. - Vous pouvez tester votre implementation avec la cellule suivante (BFS simple).

// BFS simple pour tester votre implementation de MissionnairesCannibals.
// Retourne une liste d'actions et l'etat final, ou null si pas resolu.
static (List<object> actions, object final) BfsSolve(SearchProblem problem) {
    var start = problem.InitialState();
    if (start == null) return (null, null);
    var queue = new Queue<(object state, List<object> path)>();
    var visited = new HashSet<object> { start };
    queue.Enqueue((start, new List<object>()));
    while (queue.Count > 0) {
        var (state, path) = queue.Dequeue();
        if (problem.IsGoal(state)) return (path, state);
        foreach (var action in problem.Actions(state)) {
            var nextState = problem.Transition(state, action);
            if (nextState != null && !visited.Contains(nextState)) {
                visited.Add(nextState);
                var newPath = new List<object>(path) { action };
                queue.Enqueue((nextState, newPath));
            }
        }
    }
    return (null, null);
}

// Test de la resolution : desactive si l'implementation n'est pas complete.
try {
    var mc = new MissionariesCannibals();
    var (actions, final) = BfsSolve(mc);
    if (actions == null) {
        Console.WriteLine("Completez la classe MissionnairesCannibals pour voir la solution.");
    } else {
        Console.WriteLine($"Solution trouvee en {actions.Count} traversees :");
        Console.WriteLine($"  Etat final : {final}");
    }
} catch (Exception ex) {
    Console.WriteLine("Completez la classe MissionnairesCannibals pour voir la solution.");
}

Completez la classe MissionnairesCannibals pour voir la solution.

Interpretation : Missionnaires et Cannibales

Sortie obtenue : (Exercice non complete) le notebook affiche le message “Completez la classe MissionnairesCannibals pour voir la solution.” – c’est le comportement attendu pour un exercice a completer, conforme a la convention [C.1] (stubs sans erreur).

Resolution manuelle (pour verification ulterieure) :

2 cannibales passent a droite $\to (3, 1, 'D')$
1 cannibale revient a gauche $\to (3, 2, 'G')$
2 cannibales passent a droite $\to (3, 0, 'D')$
1 cannibale revient a gauche $\to (3, 1, 'G')$
2 missionnaires passent a droite $\to (1, 1, 'D')$
1 missionnaire + 1 cannibale reviennent a gauche $\to (2, 2, 'G')$
2 missionnaires passent a droite $\to (0, 2, 'D')$
1 cannibale revient a gauche $\to (0, 3, 'G')$
2 cannibales passent a droite $\to (0, 1, 'D')$
1 cannibale revient a gauche $\to (0, 2, 'G')$
2 cannibales passent a droite $(0, 0, ‘D’) = $ but !

Total : 11 traversees. C’est l’un des classiques de la litterature IA (cf. AIMA 3e ed., exercice 3.22).

Exercice 2 : Taille de l’espace d’etats du 15-puzzle

Question : Calculez la taille de l’espace d’etats des taquins $k \times k$ :

8-puzzle ($k = 3$, $n = 9$ tuiles)
15-puzzle ($k = 4$, $n = 16$ tuiles)
24-puzzle ($k = 5$, $n = 25$ tuiles)

Rappels : - Le nombre total de permutations est $n!$ ; - Seule la moitie des permutations est atteignable (parce que les transpositions créent deux composantes) ; - L’espace atteignable est donc $n!/2$ etats.

Conclusions attendues : la recherche exhaustive devient rapidement impossible même avec les algorithmes les plus performants, d’ou l’intérêt des heuristiques et de la recherche informee (cf. Search-3).

// Exercice 2 : Taille de l'espace d'etats des taquins.
//
// Pour chaque puzzle, calculer la taille de l'espace d'etats :
//   - n!   : nombre total de permutations (factorielle)
//   - n!/2 : nombre d'etats atteignables
//
// Conclure sur la faisabilite de la recherche exhaustive.

// Liste des taquins a etudier : (nom, k, n)  -- donnee fournie.
var puzzles = new (string name, int k, int n)[] {
    ("8-puzzle",   3,  9),
    ("15-puzzle",  4, 16),
    ("24-puzzle",  5, 25),
};

// TODO (etudiant) : implementez la fonction factorielle n! -> long.
// Indice : boucle multiplicative ; utilisez long pour eviter l'overflow de 16! et 25!.
// Etape 1 : completer 'static long Factorial(int n)' ci-dessous.
static long Factorial(int n)
{
    // Votre code ici.
    return 0L;  // TODO etudiant : remplacer par le calcul de n!.
}

// TODO (etudiant) : pour chaque taquin, afficher n! et n!/2 dans un tableau.
// Indice : l'espace atteignable vaut total / 2 (parite des permutations).
// Etape 2 : parcourir 'puzzles', calculer Factorial(p.n) puis total / 2.
// Etape 3 : afficher un tableau (nom | n! | n!/2) et conclure sur la
//           faisabilite (8-puzzle vs 15-puzzle vs 24-puzzle, cf. Search-3).
Console.WriteLine("Exercice 2 a completer : implementez Factorial puis le tableau n!/2.");

Exercice 2 a completer : implementez Factorial puis le tableau n!/2.

Exercice 3 : Labyrinthe comme problème de recherche

Tâche : Modelisez un labyrinthe en MazeProblem (sous-classe de SearchProblem) et resolvez-le par BFS.

Le labyrinthe est une grille 2D : - . = passage - # = mur - S = depart - E = sortie

Etat : tuple (ligne, colonne) ; actions : deplacements Haut, Bas, Gauche, Droite (verifier bornes et absence de mur) ; but : atteindre la position E.

Sortie attendue (après implementation) : - liste des actions de la solution ; - chemin de cellules colorees en jaune dans la visualisation ASCII du labyrinthe.

// Exercice 3 : Labyrinthe comme probleme de recherche.
//
// Grille 2D avec passages (.), murs (#), depart (S) et sortie (E).
//
// Indices :
// - Le constructeur recoit `maze` (List<string>), chercher 'S' et 'E'.
// - initial_state(): retourner la position de depart (ligne, colonne).
// - actions(state): pour chaque direction, verifier bornes et absence de mur.
// - transition(state, action): appliquer (dr, dc) de DIRECTIONS.
// - is_goal(state): verifier (row, col) == ExitPos.
// - state_space_size(): compter les cellules non-mur.
public class MazeProblem : SearchProblem {
    public static readonly Dictionary<string, (int dr, int dc)> DIRECTIONS = new() {
        ["Haut"]   = (-1, 0),
        ["Bas"]    = (1, 0),
        ["Gauche"] = (0, -1),
        ["Droite"] = (0, 1),
    };

    public List<string> Maze { get; }
    public int Rows { get; }
    public int Cols { get; }
    public (int row, int col) StartPos { get; private set; }
    public (int row, int col) ExitPos { get; private set; }

    public MazeProblem(List<string> maze) {
        this.Maze = maze;
        this.Rows = maze.Count;
        this.Cols = maze.Count > 0 ? maze[0].Length : 0;
        // Valeurs par defaut ; a corriger en scannant la grille.
        StartPos = (0, 0);
        ExitPos = (0, 0);
        // TODO etudiant : Scanner la grille pour trouver 'S' et 'E'.
    }

    public override object InitialState() => StartPos;

    public override IEnumerable<object> Actions(object state) {
        // TODO etudiant :
        //   - pour chaque direction, calculer (newRow, newCol)
        //   - verifier 0 <= newRow < Rows, 0 <= newCol < Cols
        //   - verifier Maze[newRow][newCol] != '#'
        return new List<object>();
    }

    public override object Transition(object state, object action) {
        var (row, col) = ((int, int))state;
        var (dr, dc) = DIRECTIONS[(string)action];
        return (row + dr, col + dc);
    }

    public override bool IsGoal(object state) {
        return state.Equals(ExitPos);
    }

    public override int? StateSpaceSize() {
        int count = 0;
        foreach (var row in Maze) {
            foreach (var c in row) if (c != '#') count++;
        }
        return count;
    }
}

Console.WriteLine("Classe MazeProblem definie (squelette).");
Console.WriteLine("Completez Actions et le scan de 'S'/'E' dans __init__ pour resoudre.");

Classe MazeProblem definie (squelette).
Completez Actions et le scan de 'S'/'E' dans __init__ pour resoudre.

Visualisation du labyrinthe

Affichons le labyrinthe avec le chemin solution mis en evidence (après implementation). Voici un labyrinthe d’exemple canonique (7 lignes x 11 colonnes) :

############
#S.......#.#
#.######.#.#
#.#....#.#.#
#.#.##.#.#.#
#.#.##...#E#
############

// Petit labyrinthe d'exemple pour la demonstration (sans resolution).
// Les exercices 3 fully implemented resolvent ce labyrinthe par BFS.
var exampleMaze = new List<string> {
    "############",
    "#S.......#.#",
    "#.######.#.#",
    "#.#....#.#.#",
    "#.#.##.#.#.#",
    "#.#.##...#E#",
    "############",
};

Console.WriteLine("Labyrinthe d'exemple (7 x 11) :");
foreach (var row in exampleMaze) Console.WriteLine("  " + row);
Console.WriteLine();
Console.WriteLine("Legende : # = mur, . = passage, S = depart, E = sortie");
Console.WriteLine($"Dimensions : {exampleMaze.Count} lignes x {exampleMaze[0].Length} colonnes");
Console.WriteLine();
Console.WriteLine("Apres implementation de MazeProblem.Actions et de l'initialisation correcte");
Console.WriteLine("de StartPos/ExitPos dans le constructeur, ce labyrinthe peut etre resolu en BFS");
Console.WriteLine("pour obtenir un chemin de S a E en ~26 deplacements typiques.");

Labyrinthe d'exemple (7 x 11) :
  ############
  #S.......#.#
  #.######.#.#
  #.#....#.#.#
  #.#.##.#.#.#
  #.#.##...#E#
  ############

Legende : # = mur, . = passage, S = depart, E = sortie
Dimensions : 7 lignes x 12 colonnes

Apres implementation de MazeProblem.Actions et de l'initialisation correcte
de StartPos/ExitPos dans le constructeur, ce labyrinthe peut etre resolu en BFS
pour obtenir un chemin de S a E en ~26 deplacements typiques.

Interpretation : Labyrinthe comme espace d’etats

Sortie obtenue : (Exercice non complete – le notebook affiche la structure du labyrinthe d’exemple sans la solution tracee).

Lecons :

Le labyrinthe se formalise trivialement comme un SearchProblem : etat = position (row, col), actions = deplacements, but = case de sortie. C’est l’exemple le plus visuel et le plus immediat.
La complexite d’un labyrinthe $r \times c$ est en $O(rc)$ etats : 7x11 = 77 cellules, dont ~50 accessibles après deduction des murs. Très petit par rapport au 8-puzzle.
Une fois Actions(state) correctement implementee, une simple resolution par BFS (BfsSolve défini plus haut) suffit a obtenir le chemin optimal en quelques millisecondes.
Cette reduction d’un problème du monde reel a un SearchProblem est le pattern fondamental de la recherche en IA. On le verra reapparaitre dans Search-2 (algorithmes), Search-8 (Dancing Links), Search-9 (PL), et Search-10 (automates symboliques).

Exercice 4 : Enumere tous les etats d’un SearchProblem

Le monde de l’aspirateur a 8 etats. La méthode VacuumWorld.AllStates() (def. dans la cellule 6) existe déjà – l’exercice consiste a implementer une méthode generique EnumerateAllStates(SearchProblem problem) qui enumererait les etats d’un problème quelconque, en partant de InitialState() et en suivant toutes les actions jusqu’a exhaustion.

Indice : il faut utiliser une recherche en largeur (BFS) ou en profondeur (DFS) sur le graphe d’etats, en collectant les etats visites. Pour le monde de l’aspirateur (8 etats), la sortie attendue est une liste de 8 tuples (pos, gSale, dSale) distincts.

Lecon : pour des problemes plus gros (8-puzzle: 181 440 etats), cette enumeration devient prohibitive – d’ou l’intérêt des representations symboliques (cf Search-8, Dancing Links) et de la recherche informee (cf Search-3, A*).

// Exercice 4 : Enumeration generique des etats.
//
// Implementer une fonction qui enumere tous les etats accessibles depuis
// l'etat initial, en suivant toutes les actions possibles.
//
// Indice : BFS avec HashSet<object> pour detecter les cycles.
// Indice : utiliser IEnumerable<object> comme type de retour pour supporter
//          n'importe quel type d'etat.
//
// Pour VacuumWorld, on doit obtenir 8 etats ; pour le 8-puzzle, 181 440.
static IEnumerable<object> EnumerateAllStates(SearchProblem problem, int maxStates = 1000) {
    // TODO etudiant :
    //   - initialiser un HashSet<object> visites et une Queue<object>
    //   - partir de problem.InitialState()
    //   - a chaque etape :
        //     * yield return current
        //     * pour chaque action, calculer nextState
        //     * si non visite, l'ajouter
    //   - securite : s'arreter a maxStates pour eviter les boucles infinies
    return new List<object>();
}

// Test avec le monde de l'aspirateur
var vacuum2 = new VacuumWorld();
var allStates = EnumerateAllStates(vacuum2, maxStates: 100).ToList();
Console.WriteLine($"Nombre d'etats enumeres du monde de l'aspirateur : {allStates.Count}");
Console.WriteLine($"Attendu : 8 (si la methode EnumerateAllStates est implementee).");
Console.WriteLine();
Console.WriteLine("Completez EnumerateAllStates pour enumerer les 8 etats.");

Nombre d'etats enumeres du monde de l'aspirateur : 0
Attendu : 8 (si la methode EnumerateAllStates est implementee).

Completez EnumerateAllStates pour enumerer les 8 etats.

8. Resume

Concepts cles

Concept	Definition
5-tuple (S, s0, A, T, G)	Formalisation minimale d’un problème de recherche
Espace d’etats	Ensemble S des configurations possibles
Etat initial	s0 ou l’agent demarre la recherche
Fonction de transition	T(s, a) -> s’ déterministe ou stochastique
Test de but	IsGoal(s) : true si s est un etat objectif
Cout	c(s, a, s’) optionnel, permet UCS / A*

Trois exemples canoniques

Exemple	\|S\|	Facteur branch.	Cout uniforme	Reversibilite
Aspirateur	8	2	Oui	Partielle
8-Puzzle	181 440	~2.67	Oui	Oui
Itineraire	variable	3.15	Non (km)	Oui

Trois exercices

Exercice	Formalisation	Algorithme	Difficulte
Missionnaires et Cannibales	etat = (mG, cG, boat)	BFS	Moyenne (verification securite)
15-puzzle (taille espace)	factorielle n!	Calcul	Facile (1 formule)
Labyrinthe	etat = (row, col)	BFS	Facile (4 deplacements)

References

AIMA : Russell, S., & Norvig, P. – Artificial Intelligence: A Modern Approach (4e ed., 2021). Chap. 3 Solving Problems by Searching, sections 3.1 a 3.3 couvrent exactement la formalisation presentee ici. Le monde de l’aspirateur (fig. 3.2) et le 8-puzzle (fig. 3.4) sont les exemples-types du chapitre.
Documentation Microsoft : Méthodes abstraites et sealed en C# ; Heritage en C#.
Prochain notebook : Search-02-Uninformed-CSharp.ipynb – port C# des algorithmes de recherche non informee (BFS, DFS, UCS, IDDFS) qui operent sur les mêmes structures SearchProblem ici définies.

Ouverture

Une fois le problème formalise en SearchProblem, n’importe quel algorithme de la serie Search (BFS, DFS, UCS, A*, IDDFS) peut etre branche et le resoudre. Ce notebook ne contient pas d’algorithme – c’est volontaire : l’objectif etait de poser le problème. Le prochain notebook (Search-02-CSharp) introduit les premiers algorithmes, en les appliquant directement aux classes VacuumWorld, EightPuzzle et RouteFinding que vous venez de définir.

Navigation : Index | Précédent | Suivant >>

Jumeau .NET de : Search-01-StateSpace.ipynb – version Python de ce notebook.

Serie Search : Part1-Foundations | EPIC parite .NET #4956.

Genere avec .NET Interactive (kernel .net-csharp). Conventions : C.1 (stubs sans raise NotImplementedError) / #2161 (>= 3 exos par notebook) / #5214 (.NET execution_count != null).

Retour au sommet

Jumeau .NET du notebook Python

Pourquoi ce twin ?

References

1. Introduction

Qu’est-ce qu’un problème de recherche ?

Objectifs de ce notebook

2. Formalisation d’un problème de recherche

Le 5-tuple \((S, s_0, A, T, G)\)

Pourquoi cette formalisation

Classe abstraite en C

3. Exemple 1 : Le monde de l’aspirateur

Description

Interpretation : Etat initial du monde de l’aspirateur

Trace d’exécution

Interpretation : Solution du monde de l’aspirateur

Visualisation du graphe d’etats

Interpretation : Graphe d’etats de l’aspirateur

4. Exemple 2 : Le taquin (8-Puzzle)

Description

Affichage visuel du taquin

Interpretation : Transitions du taquin

5. Exemple 3 : Recherche d’itineraire

Description

Visualisation de la carte

Interpretation : Reseau routier

Comparaison de deux itineraires

Interpretation : Nombre d’étapes vs cout

Verifier l’optimalite : confier le graphe a un moteur dedie

Interpretation : ce que le moteur revele

6. Proprietes des problemes de recherche

Classification des problemes

Interpretation : Comparaison des proprietes

7. Exercices

Interpretation : Missionnaires et Cannibales

Exercice 2 : Taille de l’espace d’etats du 15-puzzle

Exercice 3 : Labyrinthe comme problème de recherche

Visualisation du labyrinthe

Interpretation : Labyrinthe comme espace d’etats

Exercice 4 : Enumere tous les etats d’un SearchProblem

8. Resume

Concepts cles

Trois exemples canoniques

Trois exercices

References

Ouverture