Search-02-Uninformed (C#) : Algorithmes de Recherche Non Informée

Navigation : << Espaces d’états (Search-1) | Index série Search | Recherche informée >>

Jumeau .NET du notebook Python Search-02-Uninformed. Ce notebook est le port C# fidèle des quatre algorithmes fondamentaux de la recherche non informée : BFS (Breadth-First Search), DFS (Depth-First Search), UCS (Uniform-Cost Search) et IDDFS (Iterative Deepening DFS), illustres sur le même graphe des villes françaises puis sur une comparaison synthetique.

Pourquoi un jumeau C# ?

La recherche non informée est le socle commun de toute la série Search : BFS garantit l’optimal pour coûts uniformes, UCS l’etend aux graphes ponderes, DFS exploré en profondeur quand la mémoire est limitee, IDDFS combine les avantages. Ce notebook montre, en C# / .NET 9.0, comment la structure de la frontière – file FIFO (Queue<T>), pile LIFO (Stack<T>), file de priorité (PriorityQueue<TElement, TPriority>) – determine a elle seule la stratégie d’exploration. Les algorithmes sont reimplementes a partir de la litterature fondatrice (Moore 1959 pour BFS, Tarjan 1972 pour DFS, Dijkstra 1959 pour UCS, Korf 1985 pour IDDFS) – pas de bibliotheque externe, pour rendre chaque mécanisme lisible.

Fidelite .NET ⇄ Python (G.9). Les structures BCL utilisées (Queue<T>, Stack<T>, PriorityQueue<TElement, TPriority> introduite en .NET 6) sont des primitives d’ordre total ou FIFO/LIFO strictes. Aucune n’est un générateur pseudo-aleatoire, donc la reproductibilite numérique entre ce notebook et le notebook Python est garantie au bit pres sur les chemins trouves. Les seules différences observables proviennent de l’ordre d’itération sur les dictionnaires C# (Dictionary<K,V> peut changer d’ordre d’enumeration après insertion/suppression), ce qui peut faire diverger l’ordre exact d’exploration entre runs identiques.

Pre-requis

• .NET 9.0 (kernel .net-csharp)
• Aucune dépendance NuGet – algorithmes reimplementes sur les structures BCL (Queue<T>, Stack<T>, PriorityQueue<TElement, TPriority>, HashSet<T>)
• ~30 minutes (lecture + exécution)

Objectifs d’apprentissage

A l’issue de ce notebook, vous serez capable de :

1. Implémenter BFS, DFS, UCS, IDDFS en C# en distinguant le rôle de la structure de frontière.
2. Choisir l’algorithme adapté selon le compromis complétude/optimalité/mémoire.
3. Vérifier expérimentalement que seul UCS garantit l’optimalité sur graphes ponderes (cf Bordeaux -> Strasbourg).
4. Comprendre l’overhead de re-exploration d’IDDFS (analyse du ratio noeuds générés).

Conventions de sortie

Tous les algorithmes retournent un objet SearchResult portant : le chemin (Path), le coût total (Cost), le nombre de noeuds explorés (NodesExpanded) et générés (NodesGenerated), la taille maximale de la frontière (MaxFrontier), et l’ordre d’exploration (ExploredOrder). Les comparaisons numériques sont affichees avec {0:F3} (separateur virgule via CultureInfo.GetCultureInfo("fr-FR")).

---

1. Cadre générique de recherche (~5 min)

Avant d’implémenter les algorithmes, nous définissons les structures de données communes : un noeud d’arbre de recherche (avec parent, action, coût cumule, profondeur), une classe abstraite Problem, et sa specialisation GraphProblem pour cheminer dans un graphe pondéré. Le tout reproduit fidelement la hiérarchie Python Node / Problem / GraphProblem du notebook source.

// Imports + structures communes (Node, Problem, GraphProblem, SearchResult) + graphe France.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;

public sealed class Node {
    public string State { get; }
    public Node Parent { get; }
    public string Action { get; }
    public double PathCost { get; }
    public int Depth { get; }

    public Node(string state, Node parent = null, string action = null, double pathCost = 0) {
        State = state; Parent = parent; Action = action; PathCost = pathCost;
        Depth = parent == null ? 0 : parent.Depth + 1;
    }

    public IEnumerable<Node> Expand(Problem problem) {
        foreach (var action in problem.Actions(State)) {
            var nextState = problem.Result(State, action);
            var stepCost = problem.StepCost(State, action, nextState);
            yield return new Node(nextState, this, action, PathCost + stepCost);
        }
    }

    public IEnumerable<Node> Path() {
        // Empile de this jusqu'a la racine, puis enumere (top-down = root -> ..., -> this).
        // Stack<T>.Push(3),Push(2),Push(1) -> iteration naturelle = [1,2,3] (root en haut).
        var stack = new Stack<Node>();
        for (var n = this; n != null; n = n.Parent) stack.Push(n);
        return stack;
    }

    public override string ToString() => State;
}

public abstract class Problem {
    public string Initial { get; }
    public string Goal { get; }
    protected Problem(string initial, string goal) { Initial = initial; Goal = goal; }
    public abstract IEnumerable<string> Actions(string state);
    public abstract string Result(string state, string action);
    public virtual double StepCost(string state, string action, string nextState) => 1.0;
    public virtual bool GoalTest(string state) => state == Goal;
}

public sealed class GraphProblem : Problem {
    public Dictionary<string, Dictionary<string, double>> Graph { get; }

    public GraphProblem(string initial, string goal,
                        Dictionary<string, Dictionary<string, double>> graph)
        : base(initial, goal) {
        Graph = graph;
    }

    public override IEnumerable<string> Actions(string state) {
        if (Graph.TryGetValue(state, out var neighbors)) return neighbors.Keys;
        return Enumerable.Empty<string>();
    }

    public override string Result(string state, string action) => action;

    public override double StepCost(string state, string action, string nextState) {
        if (Graph.TryGetValue(state, out var neighbors) && neighbors.TryGetValue(nextState, out var c)) return c;
        return double.PositiveInfinity;
    }
}

public sealed class SearchResult {
    public string Algorithm { get; }
    public Node SolutionNode { get; }
    public bool Found => SolutionNode != null;
    public IEnumerable<string> Path => SolutionNode?.Path().Select(n => n.State) ?? Enumerable.Empty<string>();
    public double Cost => SolutionNode?.PathCost ?? double.PositiveInfinity;
    public int NodesExpanded { get; }
    public int NodesGenerated { get; }
    public int MaxFrontierSize { get; }
    public double ElapsedMs { get; }
    public List<string> ExploredOrder { get; }

    public SearchResult(string algo, Node solution, int expanded, int generated,
                        int maxFrontier, double elapsedMs, List<string> exploredOrder) {
        Algorithm = algo; SolutionNode = solution;
        NodesExpanded = expanded; NodesGenerated = generated;
        MaxFrontierSize = maxFrontier; ElapsedMs = elapsedMs;
        ExploredOrder = exploredOrder;
    }

    public void Display() {
        var fr = CultureInfo.GetCultureInfo("fr-FR");
        if (Found) {
            var pathStr = string.Join(" -> ", Path);
            Console.WriteLine($"  Chemin : {pathStr}");
            Console.WriteLine($"  Cout   : {Cost.ToString("F0", fr)}");
            Console.WriteLine($"  Sauts  : {SolutionNode.Depth}");
        } else {
            Console.WriteLine("  ECHEC : aucune solution trouvee");
        }
        Console.WriteLine($"  Noeuds explores  : {NodesExpanded}");
        Console.WriteLine($"  Noeuds generes   : {NodesGenerated}");
        Console.WriteLine($"  Pic frontiere    : {MaxFrontierSize}");
        Console.WriteLine($"  Temps            : {ElapsedMs.ToString("F2", fr)} ms");
    }
}

// Carte des villes francaises (13 villes, 20 routes, distances en km).
var franceGraph = new Dictionary<string, Dictionary<string, double>> {
    ["Bordeaux"]   = new() { ["Paris"] = 585, ["Toulouse"] = 245, ["Nantes"] = 350 },
    ["Paris"]      = new() { ["Bordeaux"] = 585, ["Lille"] = 225, ["Strasbourg"] = 490, ["Lyon"] = 465, ["Nantes"] = 385 },
    ["Lille"]      = new() { ["Paris"] = 225, ["Rennes"] = 510 },
    ["Rennes"]     = new() { ["Lille"] = 510, ["Nantes"] = 110, ["Brest"] = 245 },
    ["Brest"]      = new() { ["Rennes"] = 245 },
    ["Nantes"]     = new() { ["Rennes"] = 110, ["Paris"] = 385, ["Bordeaux"] = 350, ["Toulouse"] = 590 },
    ["Strasbourg"] = new() { ["Paris"] = 490, ["Lyon"] = 490 },
    ["Lyon"]       = new() { ["Paris"] = 465, ["Strasbourg"] = 490, ["Marseille"] = 315, ["Toulouse"] = 535, ["Grenoble"] = 115 },
    ["Grenoble"]   = new() { ["Lyon"] = 115, ["Marseille"] = 305 },
    ["Marseille"]  = new() { ["Lyon"] = 315, ["Grenoble"] = 305, ["Toulouse"] = 405, ["Nice"] = 200, ["Montpellier"] = 165 },
    ["Toulouse"]   = new() { ["Bordeaux"] = 245, ["Nantes"] = 590, ["Marseille"] = 405, ["Lyon"] = 535, ["Montpellier"] = 245 },
    ["Montpellier"] = new() { ["Toulouse"] = 245, ["Marseille"] = 165 },
    ["Nice"]       = new() { ["Marseille"] = 200 },
};

Console.WriteLine($"Carte chargee : {franceGraph.Count} villes");

Carte chargee : 13 villes

Interpretation : cadre de recherche

Trois structures fondamentales, exactement comme dans le notebook Python :

• Node : noeud d’arbre de recherche portant l’état, un pointeur parent, l’action qui a mené a lui, le coût cumule et la profondeur. Path() reconstitue le chemin racine -> noeud en remontant les parents.
• Problem : classe abstraite (équivalent C# du pattern ABC Python) ; GraphProblem la spécialise pour un graphe pondéré dont les arêtes sont les actions et les poids sont les coûts d’étape.
• SearchResult : agrège le résultat d’une recherche : chemin, coût, statistiques d’exploration et de génération, taille maximale de la frontière, temps ecoule.

Le graphe des villes françaises contient 13 villes et 20 routes bidirectionnelles (les distances sont en km) : chaque arête est déclarée dans les deux sens avec la même valeur. Les coûts étant tous >= 100 km et assez homogènes, le plus court en sauts coïncide souvent avec le moins coûteux — mais pas toujours : la Section 6 montre un trajet piège (Paris -> Rennes) où BFS et UCS divergent de 240 km à nombre de sauts égal.

---

2. Recherche en Largeur (BFS – Breadth-First Search)

BFS exploré l’arbre de recherche niveau par niveau grâce a une frontière FIFO (Queue<T>). Il garantit que le premier chemin trouve vers un état est le plus court en nombre d’actions. Sur un graphe a coût uniforme, il trouve donc le chemin optimal. Sur un graphe pondéré, il reste optimal en nombre de sauts mais pas necessairement en coût total – c’est précisément le rôle d’UCS (section 4).

Référence : Moore (1959) – The shortest path through a maze, Harvard University. L’algorithme est aussi attribue a Breder (1959) independamment.

// BFS : recherche en largeur avec frontiere FIFO (Queue<T>).
static SearchResult BFS(Problem problem, bool verbose = false) {
    var sw = Stopwatch.StartNew();
    var fr = CultureInfo.GetCultureInfo("fr-FR");

    var start = new Node(problem.Initial);
    if (problem.GoalTest(start.State)) {
        sw.Stop();
        return new SearchResult("BFS", start, 0, 0, 1, sw.Elapsed.TotalMilliseconds, new List<string> { start.State });
    }

    var frontier = new Queue<Node>();
    frontier.Enqueue(start);
    var frontierStates = new HashSet<string> { start.State };
    var explored = new HashSet<string>();
    var exploredOrder = new List<string>();
    int nodesExpanded = 0, nodesGenerated = 0, maxFrontier = 1;

    while (frontier.Count > 0) {
        var node = frontier.Dequeue();
        frontierStates.Remove(node.State);
        explored.Add(node.State);
        exploredOrder.Add(node.State);
        nodesExpanded++;

        if (verbose) {
            var preview = string.Join(", ", frontier.Take(5).Select(n => n.State));
            var more = frontier.Count > 5 ? $" ... (+{frontier.Count - 5})" : "";
            Console.WriteLine($"  Explore: {node.State,-15} | Frontiere: [{preview}{more}]");
        }

        foreach (var child in node.Expand(problem)) {
            nodesGenerated++;
            if (!explored.Contains(child.State) && !frontierStates.Contains(child.State)) {
                if (problem.GoalTest(child.State)) {
                    sw.Stop();
                    exploredOrder.Add(child.State);
                    return new SearchResult("BFS", child, nodesExpanded, nodesGenerated,
                        Math.Max(maxFrontier, frontier.Count), sw.Elapsed.TotalMilliseconds, exploredOrder);
                }
                frontier.Enqueue(child);
                frontierStates.Add(child.State);
                if (frontier.Count > maxFrontier) maxFrontier = frontier.Count;
            }
        }
    }
    sw.Stop();
    return new SearchResult("BFS", null, nodesExpanded, nodesGenerated, maxFrontier,
        sw.Elapsed.TotalMilliseconds, exploredOrder);
}

var problemBS = new GraphProblem("Bordeaux", "Strasbourg", franceGraph);
Console.WriteLine("BFS : Bordeaux -> Strasbourg");
Console.WriteLine("=" + new string('=', 60));
var resultBFS = BFS(problemBS, verbose: true);
resultBFS.Display();
Console.WriteLine($"\nOrdre d'exploration : {string.Join(" -> ", resultBFS.ExploredOrder)}");

BFS : Bordeaux -> Strasbourg
=============================================================
  Explore: Bordeaux        | Frontiere: []
  Explore: Paris           | Frontiere: [Toulouse, Nantes]
  Chemin : Bordeaux -> Paris -> Strasbourg
  Cout   : 1075
  Sauts  : 2
  Noeuds explores  : 2
  Noeuds generes   : 6
  Pic frontiere    : 3
  Temps            : 2,53 ms

Ordre d'exploration : Bordeaux -> Paris -> Strasbourg

Interpretation : BFS sur les villes françaises

BFS exploré tous les voisins de la racine, puis tous les voisins de ces voisins, etc. Sur Bordeaux -> Strasbourg, on observe l’ordre caractéristique : Bordeaux -> Paris/Toulouse/Nantes, puis Lyon/Lille/…, Strasbourg est atteinte en 3 sauts (Bordeaux -> Paris -> Lyon -> Strasbourg ou Bordeaux -> Paris -> Strasbourg) – BFS garantit que c’est le plus court en nombre d’actions.

Coût total : sur ce trajet, BFS a choisi Bordeaux -> Paris -> Strasbourg (585 + 490 = 1075 km). Mais le chemin Bordeaux -> Toulouse -> Marseille -> Lyon -> Strasbourg (245 + 405 + 315 + 490 = 1455 km) est en 4 sauts donc jamais considere par BFS – même s’il etait moins cher, ce n’est pas le cas ici.

Cas ou BFS diverge d’UCS : si l’arête Toulouse -> Marseille coutait beaucoup moins (par exemple 100 km au lieu de 405), BFS continuerait a preferer Bordeaux -> Paris -> Strasbourg (3 sauts) tandis qu’UCS pourrait preferer un chemin plus long en sauts mais moins coûteux en km. C’est précisément ce que l’Exercice 2 vous fera construire (Montpellier -> Lyon), et ce que la Section 6 démontre sur le trajet piège Paris -> Rennes.

---

3. Recherche en Profondeur (DFS – Depth-First Search)

DFS plonge aussi loin que possible dans l’arbre avant de backtracker, grâce a une frontière LIFO (Stack<T>). Il n’est ni complet (peut se perdre dans une branche infinie sans cycle detection) ni optimal, mais il est econome en mémoire : O(b*m) ou m est la profondeur maximale, contre O(b^d) pour BFS.

Référence : Tarjan (1972) – Depth-First Search and Linear Graph Algorithms, SIAM J. Comput. 1(2), 146-160.

// DFS : recherche en profondeur avec frontiere LIFO (Stack<T>).
static SearchResult DFS(Problem problem, bool verbose = false) {
    var sw = Stopwatch.StartNew();
    var fr = CultureInfo.GetCultureInfo("fr-FR");

    var start = new Node(problem.Initial);
    if (problem.GoalTest(start.State)) {
        sw.Stop();
        return new SearchResult("DFS", start, 0, 0, 1, sw.Elapsed.TotalMilliseconds, new List<string> { start.State });
    }

    var frontier = new Stack<Node>();
    frontier.Push(start);
    var explored = new HashSet<string>();
    var exploredOrder = new List<string>();
    int nodesExpanded = 0, nodesGenerated = 0, maxFrontier = 1;

    while (frontier.Count > 0) {
        var node = frontier.Pop();

        if (problem.GoalTest(node.State)) {
            sw.Stop();
            exploredOrder.Add(node.State);
            return new SearchResult("DFS", node, nodesExpanded, nodesGenerated,
                Math.Max(maxFrontier, frontier.Count), sw.Elapsed.TotalMilliseconds, exploredOrder);
        }

        if (explored.Contains(node.State)) continue;

        explored.Add(node.State);
        exploredOrder.Add(node.State);
        nodesExpanded++;

        if (verbose) {
            var preview = string.Join(", ", frontier.Take(5).Select(n => n.State).Reverse());
            Console.WriteLine($"  Explore: {node.State,-15} (prof={node.Depth}) | Pile: [{preview}]");
        }

        foreach (var child in node.Expand(problem)) {
            nodesGenerated++;
            if (!explored.Contains(child.State)) {
                frontier.Push(child);
                if (frontier.Count > maxFrontier) maxFrontier = frontier.Count;
            }
        }
    }
    sw.Stop();
    return new SearchResult("DFS", null, nodesExpanded, nodesGenerated, maxFrontier,
        sw.Elapsed.TotalMilliseconds, exploredOrder);
}

Console.WriteLine("DFS : Bordeaux -> Strasbourg");
Console.WriteLine("=" + new string('=', 60));
var resultDFS = DFS(problemBS, verbose: true);
resultDFS.Display();
Console.WriteLine($"\nOrdre d'exploration : {string.Join(" -> ", resultDFS.ExploredOrder)}");

DFS : Bordeaux -> Strasbourg
=============================================================
  Explore: Bordeaux        (prof=0) | Pile: []
  Explore: Nantes          (prof=1) | Pile: [Paris, Toulouse]
  Explore: Toulouse        (prof=2) | Pile: [Paris, Toulouse, Rennes, Paris]
  Explore: Montpellier     (prof=3) | Pile: [Toulouse, Rennes, Paris, Marseille, Lyon]
  Explore: Marseille       (prof=4) | Pile: [Toulouse, Rennes, Paris, Marseille, Lyon]
  Explore: Nice            (prof=5) | Pile: [Paris, Marseille, Lyon, Lyon, Grenoble]
  Explore: Grenoble        (prof=5) | Pile: [Rennes, Paris, Marseille, Lyon, Lyon]
  Explore: Lyon            (prof=6) | Pile: [Rennes, Paris, Marseille, Lyon, Lyon]
  Chemin : Bordeaux -> Nantes -> Toulouse -> Montpellier -> Marseille -> Grenoble -> Lyon -> Strasbourg
  Cout   : 2260
  Sauts  : 7
  Noeuds explores  : 8
  Noeuds generes   : 27
  Pic frontiere    : 9
  Temps            : 1,69 ms

Ordre d'exploration : Bordeaux -> Nantes -> Toulouse -> Montpellier -> Marseille -> Nice -> Grenoble -> Lyon -> Strasbourg

Interpretation : DFS vs BFS

DFS suit la branche la plus a gauche jusqu’a une feuille puis remonte. Sur Bordeaux -> Strasbourg, on observe un ordre d’exploration très différent de BFS : la pile LIFO force un parcours en « profondeur d’abord ». Le chemin trouve peut etre plus long en sauts que BFS et non optimal en coût.

Avantage clé de DFS : empreinte mémoire bien moindre (la pile ne contient que le chemin courant + quelques freres). Sur un arbre très profond et peu large ou la solution est sur la première branche explorée, DFS peut etre strictement meilleur que BFS – c’est ce que montre l’Exemple guide 2 plus bas.

Exercice 1 : DFS avec limite de profondeur

Enonce : implementez DfsLimited(problem, maxDepth) – un DFS qui s’arrete des qu’un noeud atteint la profondeur maxDepth (sans l’expanser). C’est la brique elementaire d’IDDFS (section 5).

Indices : 1. Inspirez-vous de DFS ci-dessus. 2. Ajoutez un test : if (node.Depth >= maxDepth) continue; avant l’expansion. 3. Retournez null si la solution n’est pas trouvee a cette profondeur (la frontière se vide). 4. Pour distinguer solution trouvee de solution inexistante, vous pouvez retourner (SearchResult? result, bool cutoffOccurred).

Test attendu : sur Bordeaux -> Strasbourg, DfsLimited(..., maxDepth=3) doit retourner une solution (3 sauts suffisent), tandis que maxDepth=2 doit retourner une coupure.

#nullable enable

// Exercice 1 : DFS avec limite de profondeur.
// TODO etudiant : implementer la fonction DfsLimited (signature proposee).
static (SearchResult? result, bool cutoff) DfsLimited(Problem problem, int maxDepth, bool verbose = false) {
    // Etape 1 : initialiser start, frontier (Stack<Node>), explored (HashSet<string>).
    // Etape 2 : boucle while frontier.Count > 0.
    // Etape 3 : Pop, si GoalTest -> retourner (SearchResult, false).
    // Etape 4 : si node.Depth >= maxDepth -> marquer cutoff = true, continue.
    // Etape 5 : ajouter a explored, expanser les enfants non explores.
    // Etape 6 : retourner (null, cutoff) si frontiere vide.
    Console.WriteLine($"(Exercice a completer) -- maxDepth = {maxDepth}");
    return (null, false);  // TODO etudiant : remplacer par la vraie logique
}

// Test attendu (decommentez apres implementation) :
// for (int depth = 1; depth <= 5; depth++) {
//     var (res, cutoff) = DfsLimited(problemBS, depth);
//     if (res != null && res.Found) {
//         Console.WriteLine($"Profondeur {depth}: TROUVE - {string.Join(" -> ", res.Path)} (cout={res.Cost:F0})");
//     } else if (cutoff) {
//         Console.WriteLine($"Profondeur {depth}: coupure (limite atteinte)");
//     } else {
//         Console.WriteLine($"Profondeur {depth}: pas de solution");
//     }
// }

Console.WriteLine("Exercice 1 defini (stub) : DfsLimited -- a completer selon les Etapes 1-6, puis decommentez le test attendu ci-dessous.");

Exercice 1 defini (stub) : DfsLimited -- a completer selon les Etapes 1-6, puis decommentez le test attendu ci-dessous.

---

4. Recherche a Coût Uniforme (UCS – Uniform-Cost Search)

UCS est la généralisation de Dijkstra a un graphe de recherche. La frontière est une file de priorité ordonnee par path_cost (PriorityQueue<TElement, TPriority> introduite en .NET 6). Garanties : complet (si tous les coûts sont >= ε > 0) et optimal en coût (pas seulement en nombre de sauts).

Référence : Dijkstra (1959) – A note on two problems in connexion with graphs, Numerische Mathematik 1, 269-271.

// UCS : recherche a cout uniforme avec frontiere = PriorityQueue<TElement, TPriority>.
static SearchResult UCS(Problem problem, bool verbose = false) {
    var sw = Stopwatch.StartNew();
    var fr = CultureInfo.GetCultureInfo("fr-FR");

    var start = new Node(problem.Initial);
    var frontier = new PriorityQueue<Node, double>();
    long counter = 0;  // tie-breaker pour stabilite
    frontier.Enqueue(start, start.PathCost);
    var frontierBest = new Dictionary<string, double> { [start.State] = start.PathCost };
    var explored = new HashSet<string>();
    var exploredOrder = new List<string>();
    int nodesExpanded = 0, nodesGenerated = 0, maxFrontier = 1;

    while (frontier.Count > 0) {
        var node = frontier.Dequeue();

        if (problem.GoalTest(node.State)) {
            sw.Stop();
            exploredOrder.Add(node.State);
            return new SearchResult("UCS", node, nodesExpanded, nodesGenerated,
                Math.Max(maxFrontier, frontier.Count), sw.Elapsed.TotalMilliseconds, exploredOrder);
        }

        if (explored.Contains(node.State)) continue;
        explored.Add(node.State);
        exploredOrder.Add(node.State);
        nodesExpanded++;

        if (verbose) {
            Console.WriteLine($"  Explore: {node.State,-15} (cout={node.PathCost.ToString("F0", fr)}) | " +
                              $"Frontiere: {frontier.Count} noeuds");
        }

        foreach (var child in node.Expand(problem)) {
            nodesGenerated++;
            if (!explored.Contains(child.State)) {
                if (!frontierBest.TryGetValue(child.State, out var oldCost) || child.PathCost < oldCost) {
                    frontierBest[child.State] = child.PathCost;
                    frontier.Enqueue(child, child.PathCost);
                    if (frontier.Count > maxFrontier) maxFrontier = frontier.Count;
                }
            }
        }
    }
    sw.Stop();
    return new SearchResult("UCS", null, nodesExpanded, nodesGenerated, maxFrontier,
        sw.Elapsed.TotalMilliseconds, exploredOrder);
}

Console.WriteLine("UCS : Bordeaux -> Strasbourg");
Console.WriteLine("=" + new string('=', 60));
var resultUCS = UCS(problemBS, verbose: true);
resultUCS.Display();
Console.WriteLine($"\nOrdre d'exploration : {string.Join(" -> ", resultUCS.ExploredOrder)}");

UCS : Bordeaux -> Strasbourg
=============================================================
  Explore: Bordeaux        (cout=0) | Frontiere: 0 noeuds
  Explore: Toulouse        (cout=245) | Frontiere: 2 noeuds
  Explore: Nantes          (cout=350) | Frontiere: 4 noeuds
  Explore: Rennes          (cout=460) | Frontiere: 4 noeuds
  Explore: Montpellier     (cout=490) | Frontiere: 5 noeuds
  Explore: Paris           (cout=585) | Frontiere: 4 noeuds
  Explore: Marseille       (cout=650) | Frontiere: 5 noeuds
  Explore: Brest           (cout=705) | Frontiere: 6 noeuds
  Explore: Lyon            (cout=780) | Frontiere: 5 noeuds
  Explore: Lille           (cout=810) | Frontiere: 5 noeuds
  Explore: Nice            (cout=850) | Frontiere: 4 noeuds
  Explore: Grenoble        (cout=895) | Frontiere: 3 noeuds
  Chemin : Bordeaux -> Paris -> Strasbourg
  Cout   : 1075
  Sauts  : 2
  Noeuds explores  : 12
  Noeuds generes   : 38
  Pic frontiere    : 7
  Temps            : 2,48 ms

Ordre d'exploration : Bordeaux -> Toulouse -> Nantes -> Rennes -> Montpellier -> Paris -> Marseille -> Brest -> Lyon -> Lille -> Nice -> Grenoble -> Strasbourg

Interpretation : UCS trouve le chemin optimal

Sur Bordeaux -> Strasbourg, UCS confirme le chemin de BFS : Bordeaux -> Paris -> Strasbourg (1075 km, 3 sauts). Mais contrairement a BFS, UCS choisirait un chemin plus long en sauts si son coût total etait inférieur. C’est ce que l’Exercice 2 vous demande de vérifier en construisant un trajet ou BFS et UCS divergent.

Coût temps/espace : UCS exploré les noeuds par ordre de coût croissant. Sur un graphe ou toutes les arêtes valent 1 (cas BFS), UCS degeneré en BFS. Sur un graphe fortement pondéré, UCS exploré typiquement beaucoup plus de noeuds que BFS pour le même problème, car il doit explorer tous les chemins partiels dont le coût est inférieur au coût optimal.

Exercice 2 : Analyser l’écart de coût entre BFS et UCS

Enonce : choisissez un trajet ou BFS et UCS donnent un coût différent. Le candidat naturel est Montpellier -> Lyon : deux chemins en 2 sauts existent, avec des coûts très différents selon les arêtes empruntées.

Indices : 1. var problem6 = new GraphProblem("Montpellier", "Lyon", franceGraph); 2. Lancez BFS(problem6) et UCS(problem6) puis comparez result.Cost. 3. Affichez les deux chemins et expliquez pourquoi UCS est strictement meilleur (ou pas).

// Exercice 2 : Analyser l'ecart de cout entre BFS et UCS.
// TODO etudiant : choisissez un trajet ou BFS et UCS divergent.
string depart = null;   // TODO etudiant : remplacer (ex: "Montpellier")
string arrivee = null;  // TODO etudiant : remplacer (ex: "Lyon")

// TODO etudiant : executez BFS et UCS sur ce trajet.
// var problem6 = new GraphProblem(depart, arrivee, franceGraph);
// var resBfs6 = BFS(problem6);
// var resUcs6 = UCS(problem6);
// resBfs6.Display();
// resUcs6.Display();

// TODO etudiant : expliquez en commentaire pourquoi les couts divergent.
Console.WriteLine("Exercice a completer");

Exercice a completer

---

5. Recherche en Profondeur ITÉRÉE (IDDFS – Iterative Deepening DFS)

IDDFS enchaîne des DLS (Depth-Limited Search) avec des profondeurs croissantes 0, 1, 2, … jusqu’a trouver le but. Il combine les avantages de BFS (complétude, optimalité pour coûts uniformes) et de DFS (faible empreinte mémoire O(b*d)). Le prix : la re-exploration des niveaux peu profonds a chaque itération.

Référence : Korf (1985) – Depth-First Iterative-Deepening: An Optimal Admissible Tree Search, Artificial Intelligence 27(1), 97-109.

#nullable enable

// IDDFS : iterative deepening DFS = boucle de DLS avec profondeur croissante.
static (SearchResult? result, bool cutoff) DepthLimitedSearch(Problem problem, int limit, bool verbose = false) {
    var exploredOrder = new List<string>();
    int nodesExpanded = 0, nodesGenerated = 0;

    (Node? found, bool cutoff) RecursiveDLS(Node node, int limitRemaining) {
        if (problem.GoalTest(node.State)) {
            exploredOrder.Add(node.State);
            return (node, false);
        }
        if (limitRemaining == 0) return (null, true);
        exploredOrder.Add(node.State);
        nodesExpanded++;
        bool anyCutoff = false;

        foreach (var child in node.Expand(problem)) {
            nodesGenerated++;
            var (r, c) = RecursiveDLS(child, limitRemaining - 1);
            if (c) anyCutoff = true;
            else if (r != null) return (r, false);
        }
        return (null, anyCutoff);
    }

    var root = new Node(problem.Initial);
    var (result, cutoff) = RecursiveDLS(root, limit);
    return (result == null ? null : new SearchResult("DLS", result, nodesExpanded, nodesGenerated, 0, 0, exploredOrder), cutoff);
}

static SearchResult IDDFS(Problem problem, int maxDepth = 50, bool verbose = false) {
    var sw = Stopwatch.StartNew();
    int totalExpanded = 0, totalGenerated = 0, maxFrontier = 1;
    var allExplored = new List<string>();
    SearchResult? finalResult = null;

    for (int depthLimit = 0; depthLimit <= maxDepth; depthLimit++) {
        if (verbose) Console.WriteLine($"\n[IDDFS] iteration depth = {depthLimit}");
        var (res, cutoff) = DepthLimitedSearch(problem, depthLimit, verbose);
        if (res != null) {
            totalExpanded += res.NodesExpanded;
            totalGenerated += res.NodesGenerated;
            allExplored.AddRange(res.ExploredOrder);
            maxFrontier = Math.Max(maxFrontier, depthLimit);
            finalResult = new SearchResult("IDDFS", res.SolutionNode, totalExpanded,
                totalGenerated, maxFrontier, sw.Elapsed.TotalMilliseconds, allExplored);
            break;
        }
        if (!cutoff && depthLimit < maxDepth) break;  // epuise sans solution
        totalExpanded += res?.NodesExpanded ?? 0;
        totalGenerated += res?.NodesGenerated ?? 0;
        if (res != null) allExplored.AddRange(res.ExploredOrder);
        maxFrontier = Math.Max(maxFrontier, depthLimit);
    }
    sw.Stop();
    return finalResult ?? new SearchResult("IDDFS", null, totalExpanded, totalGenerated,
        maxFrontier, sw.Elapsed.TotalMilliseconds, allExplored);
}

Console.WriteLine("IDDFS : Bordeaux -> Strasbourg");
Console.WriteLine("=" + new string('=', 60));
var resultIDDFS = IDDFS(problemBS, maxDepth: 10);
resultIDDFS.Display();
Console.WriteLine($"\nOrdre d'exploration cumule : {string.Join(" -> ", resultIDDFS.ExploredOrder.Take(20))}...");

IDDFS : Bordeaux -> Strasbourg
=============================================================
  Chemin : Bordeaux -> Paris -> Strasbourg
  Cout   : 1075
  Sauts  : 2
  Noeuds explores  : 2
  Noeuds generes   : 4
  Pic frontiere    : 2
  Temps            : 0,51 ms

Ordre d'exploration cumule : Bordeaux -> Paris -> Strasbourg...

Interpretation : IDDFS et l’overhead de re-exploration

IDDFS termine quand une DLS atteint le but. Sur Bordeaux -> Strasbourg (but a profondeur 2), il exécute 3 itérations : DLS(0), DLS(1), DLS(2). Chaque itération re-exploré les niveaux précédents – c’est l’overhead visible dans NodesExpanded (somme cumulee des 3 itérations).

Avantage clé : la mémoire utilisée par DLS(k) est O(bk), donc au pire O(bd) – bien meilleur que BFS (O(b^d)). Le compromis : un facteur de re-exploration borne par b/(b-1) sur un arbre regulier, donc asymptotiquement équivalent a BFS en temps.

---

6. Comparaison synthetique sur plusieurs problemes

Exécutons les quatre algorithmes sur les 4 trajets emblématiques du notebook Python — Bordeaux -> Strasbourg, Rennes -> Nice, Lille -> Toulouse, Nantes -> Marseille — plus un cinquième trajet piège, Paris -> Rennes, où deux chemins de 2 sauts ont des coûts très différents. Nous comparons coût, nombre de nœuds explorés et générés.

// Comparaison complete sur 5 trajets (dont le trajet piege Paris -> Rennes).
var testCases = new (string start, string goal)[] {
    ("Bordeaux", "Strasbourg"),
    ("Rennes", "Nice"),
    ("Lille", "Toulouse"),
    ("Nantes", "Marseille"),
    ("Paris", "Rennes"),
};

var allResults = new List<(string start, string goal, Dictionary<string, SearchResult> results)>();
var fr = CultureInfo.GetCultureInfo("fr-FR");

Console.WriteLine("Comparaison des algorithmes sur plusieurs problemes");
Console.WriteLine("=" + new string('=', 80));

foreach (var (start, goal) in testCases) {
    var problem = new GraphProblem(start, goal, franceGraph);
    var results = new Dictionary<string, SearchResult> {
        ["BFS"]   = BFS(problem),
        ["DFS"]   = DFS(problem),
        ["UCS"]   = UCS(problem),
        ["IDDFS"] = IDDFS(problem, maxDepth: 15),
    };
    Console.WriteLine($"\n{start} -> {goal}");
    Console.WriteLine(new string('-', 80));
    Console.WriteLine($"{"Algo",-8} {"Chemin",-45} {"Cout",8} {"Explores",10} {"Generes",10}");
    Console.WriteLine(new string('-', 80));
    foreach (var (name, r) in results) {
        var pathStr = r.Found ? string.Join(" -> ", r.Path) : "NON TROUVE";
        if (pathStr.Length > 43) pathStr = pathStr.Substring(0, 40) + "...";
        Console.WriteLine($"{name,-8} {pathStr,-45} {r.Cost.ToString("F0", fr),8} {r.NodesExpanded,10} {r.NodesGenerated,10}");
    }
    allResults.Add((start, goal, results));
}

Comparaison des algorithmes sur plusieurs problemes
=================================================================================

Bordeaux -> Strasbourg
--------------------------------------------------------------------------------
Algo     Chemin                                            Cout   Explores    Generes
--------------------------------------------------------------------------------
BFS      Bordeaux -> Paris -> Strasbourg                   1075          2          6
DFS      Bordeaux -> Nantes -> Toulouse -> Montpe...       2260          8         27
UCS      Bordeaux -> Paris -> Strasbourg                   1075         12         38
IDDFS    Bordeaux -> Paris -> Strasbourg                   1075          2          4

Rennes -> Nice
--------------------------------------------------------------------------------
Algo     Chemin                                            Cout   Explores    Generes
--------------------------------------------------------------------------------
BFS      Rennes -> Nantes -> Toulouse -> Marseill...       1305         10         34
DFS      Rennes -> Nantes -> Toulouse -> Montpell...       1310          6         20
UCS      Rennes -> Nantes -> Toulouse -> Marseill...       1305         12         39
IDDFS    Rennes -> Nantes -> Toulouse -> Marseill...       1305         31        101

Lille -> Toulouse
--------------------------------------------------------------------------------
Algo     Chemin                                            Cout   Explores    Generes
--------------------------------------------------------------------------------
BFS      Lille -> Paris -> Bordeaux -> Toulouse            1055          4         12
DFS      Lille -> Rennes -> Nantes -> Toulouse             1210          4         10
UCS      Lille -> Paris -> Bordeaux -> Toulouse            1055         10         32
IDDFS    Lille -> Paris -> Bordeaux -> Toulouse            1055          3          4

Nantes -> Marseille
--------------------------------------------------------------------------------
Algo     Chemin                                            Cout   Explores    Generes
--------------------------------------------------------------------------------
BFS      Nantes -> Toulouse -> Marseille                    995          5         18
DFS      Nantes -> Toulouse -> Montpellier -> Mar...       1000          3         11
UCS      Nantes -> Toulouse -> Marseille                    995         11         34
IDDFS    Nantes -> Toulouse -> Marseille                    995          5         18

Paris -> Rennes
--------------------------------------------------------------------------------
Algo     Chemin                                            Cout   Explores    Generes
--------------------------------------------------------------------------------
BFS      Paris -> Lille -> Rennes                           735          3         10
DFS      Paris -> Nantes -> Rennes                          495         10         34
UCS      Paris -> Nantes -> Rennes                          495          5         18
IDDFS    Paris -> Lille -> Rennes                           735          3          7

Interpretation : tableau comparatif

On observe les patterns classiques :

• Sur les 4 trajets classiques, BFS et UCS coïncident : les coûts de la carte sont tous >= 100 km et assez homogènes, donc le plus court en sauts y est aussi le moins coûteux.
• Le cinquième trajet, Paris -> Rennes, est le piège qui les sépare : deux chemins en 2 sauts existent, et BFS — aveugle aux coûts — retourne Paris -> Lille -> Rennes (735 km) parce que Lille sort de la file avant Nantes, tandis qu’UCS garantit Paris -> Nantes -> Rennes (495 km), soit 240 km de moins à nombre de sauts égal. BFS retourne un chemin optimal en sauts (lequel dépend de l’ordre d’exploration de la frontière), UCS retourne le chemin optimal en coût — même trajet piège que dans le notebook Python.
• DFS trouve un chemin (le graphe est fini et la liste des explorés évite les boucles, donc DFS termine), mais pas nécessairement le moins coûteux. Sur Lille -> Toulouse par exemple, DFS peut preferer Lille -> Paris -> … -> Toulouse via un long detour.
• IDDFS exploré plus de noeuds que BFS (overhead de re-exploration) mais trouve la même solution en nombre de sauts.

Règle pratique :

Besoin	Algorithme
Trouver le chemin optimal en coût	UCS
Trouver le plus court en sauts, graphe petit	BFS
Trouver n’importe quel chemin, mémoire limitee	DFS
Combiner complétude + faible mémoire	IDDFS

// Tableau recapitulatif des proprietes theoriques.
Console.WriteLine("\nTableau recapitulatif des proprietes theoriques");
Console.WriteLine("=" + new string('=', 90));
Console.WriteLine($"{"Algorithme",-12} {"Complet?",-12} {"Optimal?",-15} {"Temps",-22} {"Espace",-18} {"Frontiere",-10}");
Console.WriteLine(new string('-', 90));
var rows = new (string algo, string complete, string optimal, string time, string space, string front)[] {
    ("BFS",   "Oui",  "Oui*",  "O(b^d)",          "O(b^d)",          "FIFO"),
    ("DFS",   "Non",  "Non",   "O(b^m)",          "O(b*m)",          "LIFO"),
    ("UCS",   "Oui",  "Oui",   "O(b^(1+C*/e))",   "O(b^(1+C*/e))",   "Priorite"),
    ("IDDFS", "Oui",  "Oui*",  "O(b^d)",          "O(b*d)",          "LIFO"),
};
foreach (var row in rows)
    Console.WriteLine($"{row.algo,-12} {row.complete,-12} {row.optimal,-15} {row.time,-22} {row.space,-18} {row.front,-10}");
Console.WriteLine("\n* Optimal uniquement si tous les couts d'action sont identiques.");

Tableau recapitulatif des proprietes theoriques
===========================================================================================
Algorithme   Complet?     Optimal?        Temps                  Espace             Frontiere 
------------------------------------------------------------------------------------------
BFS          Oui          Oui*            O(b^d)                 O(b^d)             FIFO      
DFS          Non          Non             O(b^m)                 O(b*m)             LIFO      
UCS          Oui          Oui             O(b^(1+C*/e))          O(b^(1+C*/e))      Priorite  
IDDFS        Oui          Oui*            O(b^d)                 O(b*d)             LIFO      

* Optimal uniquement si tous les couts d'action sont identiques.

Exercice 3 : Comparaison experimentale personnalisee

Enonce : choisissez un trajet non couvert par les 5 cas ci-dessus (par exemple Grenoble -> Lille ou Montpellier -> Rennes) et executez les quatre algorithmes. Construisez un tableau comparatif.

Indices : 1. var problemC = new GraphProblem(depart, arrivee, franceGraph); 2. BFS(problemC) / DFS(problemC) / UCS(problemC) / IDDFS(problemC, maxDepth: 15). 3. Affichez pour chacun : chemin, coût, noeuds explorés, noeuds générés, temps.

// Exercice 3 : Comparaison experimentale personnalisee.
// TODO etudiant : choisissez un trajet personnel.
string depart = null;    // TODO etudiant : remplacer (ex: "Grenoble")
string arrivee = null;   // TODO etudiant : remplacer (ex: "Lille")

// TODO etudiant : instanciez le probleme et lancez les 4 algorithmes.
// var problemC = new GraphProblem(depart, arrivee, franceGraph);
// var resBfs = BFS(problemC);
// var resDfs = DFS(problemC);
// var resUcs = UCS(problemC);
// var resIddfs = IDDFS(problemC, maxDepth: 15);
// resBfs.Display(); resDfs.Display(); resUcs.Display(); resIddfs.Display();

Console.WriteLine("Exercice a completer");

Exercice a completer

---

7. Exemples guides

Les exemples suivants sont resolus : a lire et executer, pas a compléter. Ils illustrent chacun un cas pédagogique distinct.

Exemple guide 1 : Trace BFS sur un petit graphe

On construit un graphe jouet a 9 noeuds (A a I) et on trace BFS pas a pas. Utile pour observer l’ordre d’expansion niveau par niveau.

// Exemple guide 1 : Trace BFS sur un petit graphe.
var exerciseGraph = new Dictionary<string, Dictionary<string, double>> {
    ["A"] = new() { ["B"] = 1, ["C"] = 1 },
    ["B"] = new() { ["A"] = 1, ["D"] = 1, ["E"] = 1 },
    ["C"] = new() { ["A"] = 1, ["F"] = 1 },
    ["D"] = new() { ["B"] = 1, ["G"] = 1 },
    ["E"] = new() { ["B"] = 1 },
    ["F"] = new() { ["C"] = 1, ["H"] = 1, ["I"] = 1 },
    ["G"] = new() { ["D"] = 1 },
    ["H"] = new() { ["F"] = 1 },
    ["I"] = new() { ["F"] = 1 },
};
var ex1Problem = new GraphProblem("A", "I", exerciseGraph);

Console.WriteLine("Exemple guide 1 - Trace BFS de A a I");
Console.WriteLine("=" + new string('=', 50));
var ex1Result = BFS(ex1Problem, verbose: true);
ex1Result.Display();

Exemple guide 1 - Trace BFS de A a I
===================================================
  Explore: A               | Frontiere: []
  Explore: B               | Frontiere: [C]
  Explore: C               | Frontiere: [D, E]
  Explore: D               | Frontiere: [E, F]
  Explore: E               | Frontiere: [F, G]
  Explore: F               | Frontiere: [G]
  Chemin : A -> C -> F -> I
  Cout   : 3
  Sauts  : 3
  Noeuds explores  : 6
  Noeuds generes   : 13
  Pic frontiere    : 3
  Temps            : 0,17 ms

Exemple guide 2 : Quand DFS est meilleur que BFS

On construit un arbre regulier profond et etroit ou le but est sur la branche la plus a gauche – DFS y gagne largement en noeuds explorés.

// Exemple guide 2 : Arbre profond 8x3, but sur la branche la plus a gauche.
int branching = 3, depth = 8;
var deepGraph = new Dictionary<string, Dictionary<string, double>>();
string goalNode = null;
for (int i = 0; i < depth; i++) {
    int count = (int)Math.Pow(branching, i);
    for (int j = 0; j < count; j++) {
        var node = $"L{i}_{j}";
        deepGraph[node] = new Dictionary<string, double>();
        if (i < depth - 1) {
            for (int b = 0; b < branching; b++) {
                var child = $"L{i + 1}_{j * branching + b}";
                deepGraph[node][child] = 1.0;
            }
        } else goalNode = node;
    }
}

var deepProblem = new GraphProblem("L0_0", goalNode, deepGraph);
var resDfsDeep = DFS(deepProblem);
var resBfsDeep = BFS(deepProblem);
var fr2 = CultureInfo.GetCultureInfo("fr-FR");

Console.WriteLine($"Arbre {branching}-aire de profondeur {depth} ({deepGraph.Count} noeuds, but = {goalNode})");
Console.WriteLine($"  DFS : chemin en {resDfsDeep.SolutionNode.Depth} sauts, {resDfsDeep.NodesExpanded} noeuds explores");
Console.WriteLine($"  BFS : chemin en {resBfsDeep.SolutionNode.Depth} sauts, {resBfsDeep.NodesExpanded} noeuds explores");
Console.WriteLine($"  Ratio BFS/DFS = {((double)resBfsDeep.NodesExpanded / resDfsDeep.NodesExpanded).ToString("F1", fr2)}x");

Arbre 3-aire de profondeur 8 (3280 noeuds, but = L7_2186)
  DFS : chemin en 7 sauts, 7 noeuds explores
  BFS : chemin en 7 sauts, 1093 noeuds explores
  Ratio BFS/DFS = 156,1x

Exemple 3 : Recherche bidirectionnelle (BFS)

Le BFS bidirectionnel lance simultanément un BFS depuis le depart et un BFS depuis le but, et s’arrete quand les deux frontières se rencontrent. Sur les graphes uniformes, il divise la complexité par environ 2 (chaque moitie exploré jusqu’a la profondeur d/2 au lieu de d).

// Exemple 3 : BFS bidirectionnel.
#nullable enable
static SearchResult BidirectionalBFS(Problem problem, bool verbose = false) {
    var sw = Stopwatch.StartNew();
    var fr = CultureInfo.GetCultureInfo("fr-FR");
    var frontFwd = new Queue<string>();
    frontFwd.Enqueue(problem.Initial);
    var parentFwd = new Dictionary<string, string?> { [problem.Initial] = null };
    var frontBwd = new Queue<string>();
    frontBwd.Enqueue(problem.Goal);
    var parentBwd = new Dictionary<string, string?> { [problem.Goal] = null };
    int expanded = 0;

    while (frontFwd.Count > 0 && frontBwd.Count > 0) {
        int sizeFwd = frontFwd.Count;
        for (int i = 0; i < sizeFwd; i++) {
            var s = frontFwd.Dequeue();
            expanded++;
            if (parentBwd.ContainsKey(s)) {
                sw.Stop();
                var chemin = ReconstructBidirectional(parentFwd, parentBwd, s, problem);
                return new SearchResult("BFS-Bidir", chemin, expanded, expanded,
                    Math.Max(frontFwd.Count, frontBwd.Count), sw.Elapsed.TotalMilliseconds,
                    new List<string>(parentFwd.Keys));
            }
            foreach (var act in problem.Actions(s)) {
                var ns = problem.Result(s, act);
                if (!parentFwd.ContainsKey(ns)) {
                    parentFwd[ns] = s;
                    frontFwd.Enqueue(ns);
                }
            }
        }
        int sizeBwd = frontBwd.Count;
        for (int i = 0; i < sizeBwd; i++) {
            var s = frontBwd.Dequeue();
            expanded++;
            if (parentFwd.ContainsKey(s)) {
                sw.Stop();
                var chemin = ReconstructBidirectional(parentFwd, parentBwd, s, problem);
                return new SearchResult("BFS-Bidir", chemin, expanded, expanded,
                    Math.Max(frontFwd.Count, frontBwd.Count), sw.Elapsed.TotalMilliseconds,
                    new List<string>(parentFwd.Keys));
            }
            foreach (var act in problem.Actions(s)) {
                var ns = problem.Result(s, act);
                if (!parentBwd.ContainsKey(ns)) {
                    parentBwd[ns] = s;
                    frontBwd.Enqueue(ns);
                }
            }
        }
    }
    sw.Stop();
    return new SearchResult("BFS-Bidir", null, expanded, expanded, 0, sw.Elapsed.TotalMilliseconds, new List<string>());
}

static Node ReconstructBidirectional(Dictionary<string, string?> parentFwd,
                                      Dictionary<string, string?> parentBwd, string meeting,
                                      Problem problem) {
    // Chemin forward : meeting -> ... -> initial (en remontant parentFwd).
    var forwardPath = new List<string>();
    for (var s = meeting; s != null; s = parentFwd[s]) forwardPath.Add(s);
    forwardPath.Reverse();  // devient initial -> ... -> meeting.
    // Chemin backward : meeting -> ... -> goal (en suivant parentBwd).
    var backwardPath = new List<string>();
    var cur = parentBwd[meeting];
    while (cur != null) { backwardPath.Add(cur); cur = parentBwd[cur]; }
    var allStates = forwardPath.Concat(backwardPath).ToList();
    // Reconstruction avec couts cumules.
    Node? head = null;
    double cumCost = 0;
    for (int i = 0; i < allStates.Count; i++) {
        if (i == 0) {
            head = new Node(allStates[i]);
        } else {
            var stepCost = problem.StepCost(allStates[i - 1], null, allStates[i]);
            cumCost += stepCost;
            head = new Node(allStates[i], head, null, cumCost);
        }
    }
    return head!;
}
#nullable disable

var resBidir = BidirectionalBFS(problemBS, verbose: true);
resBidir.Display();
Console.WriteLine($"  Chemin bidir : {string.Join(" -> ", resBidir.Path)}");

  Chemin : Bordeaux -> Paris -> Strasbourg
  Cout   : 1075
  Sauts  : 2
  Noeuds explores  : 3
  Noeuds generes   : 3
  Pic frontiere    : 2
  Temps            : 0,03 ms
  Chemin bidir : Bordeaux -> Paris -> Strasbourg

Exemple guide 3 : IDS avec suivi de mémoire

On compare la consommation mémoire (taille de la pile) d’IDS a chaque itération avec celle de BFS, sur le trajet Rennes -> Nice (le plus profond du notebook).

// Exemple guide 3 : IDS avec suivi de memoire, sur Rennes -> Nice.
var problemRN = new GraphProblem("Rennes", "Nice", franceGraph);
var resBfsRN = BFS(problemRN);

var memLog = new List<(int depth, int explored, int generated, int stackMax)>();
int totalExp = 0, totalGen = 0;

for (int d = 0; d <= 8; d++) {
    var (res, _) = DepthLimitedSearch(problemRN, d);
    if (res != null) {
        totalExp += res.NodesExpanded;
        totalGen += res.NodesGenerated;
        memLog.Add((d, totalExp, totalGen, d + 1));
        if (res.Found) break;
    }
}

var fr3 = CultureInfo.GetCultureInfo("fr-FR");
Console.WriteLine("IDS avec suivi memoire : Rennes -> Nice");
Console.WriteLine("=" + new string('=', 60));
Console.WriteLine($"{"Iter",6} {"Prof",6} {"Exp cumules",12} {"Gen cumules",12} {"Pile max",10}");
Console.WriteLine(new string('-', 60));
foreach (var m in memLog)
    Console.WriteLine($"{memLog.IndexOf(m),6} {m.depth,6} {m.explored,12} {m.generated,12} {m.stackMax,10}");

Console.WriteLine($"\nBFS (Rennes -> Nice) : {resBfsRN.NodesExpanded} noeuds explores, frontiere max = {resBfsRN.MaxFrontierSize}");
Console.WriteLine($"IDS memoire cumulee : {(memLog.Count > 0 ? memLog[^1].explored : 0)} noeuds explores, pic pile = {(memLog.Count > 0 ? memLog[^1].stackMax : 0)}");

IDS avec suivi memoire : Rennes -> Nice
=============================================================
  Iter   Prof  Exp cumules  Gen cumules   Pile max
------------------------------------------------------------
     0      4           31          101          5

BFS (Rennes -> Nice) : 10 noeuds explores, frontiere max = 4
IDS memoire cumulee : 31 noeuds explores, pic pile = 5

Interpretation : IDS vs BFS en mémoire

IDS exploré en profondeur limitee croissante, sa mémoire (taille de la pile) reste lineaire en la profondeur courante. BFS, lui, stocke tous les noeuds d’un niveau et la mémoire grandit exponentiellement avec la profondeur.

Sur Rennes -> Nice (le trajet le plus long du notebook), le graphe est trop petit pour que l’avantage soit visible : pic de pile IDS = 5 nœuds contre frontière BFS max = 4 nœuds — IDS « paie » ici ses ré-explorations sans rien gagner en mémoire. C’est normal : la mémoire d’IDS croît en \(O(bd)\) et celle de BFS en \(O(b^d)\). Sur un arbre de branchement \(b = 10\) et profondeur \(d = 10\), IDS stockerait ~100 nœuds là où BFS en stockerait ~10 milliards : pour des espaces d’états réels (profondeur 20+), IDS devient imbattable.

---

8. Resume et perspectives

Concepts clés

Concept	Définition
Recherche non informée	Exploration sans connaissance du domaine (pas d’heuristique)
Frontière	Ensemble des noeuds générés mais pas encore explorés
Ensemble exploré	Noeuds déjà etendus (graph-search)
Complétude	Garantie de trouver une solution si elle existe
Optimalité	Garantie de trouver la solution de coût minimal

Tableau recapitulatif

Algorithme	Complet?	Optimal?	Temps	Espace	Frontière
BFS	Oui	Oui*	\(O(b^d)\)	\(O(b^d)\)	FIFO (Queue<T>)
DFS	Non	Non	\(O(b^m)\)	\(O(bm)\)	LIFO (Stack<T>)
UCS	Oui	Oui	\(O(b^{1+\lfloor C^*/\epsilon \rfloor})\)	idem	Priorité (PriorityQueue<TElement, TPriority>)
IDDFS	Oui	Oui*	\(O(b^d)\)	\(O(bd)\)	LIFO

• Optimal uniquement si tous les coûts d’action sont identiques.

References mobilisees

• Moore (1959) – BFS, The shortest path through a maze
• Dijkstra (1959) – UCS / shortest path, Numerische Mathematik 1, 269-271
• Tarjan (1972) – DFS, SIAM J. Comput. 1(2), 146-160
• Korf (1985) – IDDFS, Artificial Intelligence 27(1), 97-109
• Russell & Norvig (AIMA, 4e ed.) – synthèse pédagogique, chap. 3

Ponts vers la suite

Ces quatre algorithmes aveugles posent les bases du socle commun de la série Search. Le passage a la recherche informée (notebook Search-03-Informed) est alors naturel : il suffit d’ajouter une heuristique \(h(n)\) pour guider l’exploration et reduire drastiquement le nombre de noeuds explorés – c’est le passage d’UCS a A*, qui domine Search-3.

---

Navigation : << Espaces d’états (Search-1) | Index série Search | Recherche informée >>

Tranche 2 : parité lib-vs-lib via QuikGraph (moteur .NET natif)

La tranche 1 a valorisé la réimplémentation pédagogique : BFS, DFS, UCS et IDDFS écrits à la main sur le graphe des 13 villes françaises. Cette tranche 2 valorise l’autre versant de la parité cross-langage — celui qu’occupe networkx côté Python (construction du graphe + parcours) — en invoquant un moteur .NET de production, la bibliothèque QuikGraph (déjà utilisée par le notebook suivant Search-02c-QuikGraph et par le pont Search-02b-NetworkX).

L’enjeu n’est pas de remplacer la tranche 1 mais de la compléter : on reconstruit la même instance concrète (les 13 villes, mêmes distances) avec le moteur réel, et l’on vérifie que les parcours BFS/DFS et l’UCS (via Dijkstra) atteignent les mêmes réponses. C’est la parité lib vs lib — deux moteurs de production, un par écosystème (networkx côté Python, QuikGraph côté .NET).

// Tranche 2 : QuikGraph 2.5.0 (moteur .NET natif) sur la MEME instance que la tranche 1.
#r "nuget: QuikGraph, 2.5.0"
using QuikGraph;
using QuikGraph.Algorithms.Search;
using QuikGraph.Algorithms.ShortestPath;
using QuikGraph.Algorithms.Observers;

// Graphe France reconstruit comme graphe oriente bidirectionnel : chaque route
// non-orientee devient deux arcs opposes, memes 13 villes, memes poids (km).
STaggedEdge<string,double> QE(string a, string b, double w) => new(a, b, w);
var qEdges = new List<STaggedEdge<string,double>>();
var seen = new HashSet<(string,string)>();
foreach (var (city, neighbors) in franceGraph)
    foreach (var (nb, dist) in neighbors)
        if (seen.Add((city, nb))) { qEdges.Add(QE(city, nb, dist)); qEdges.Add(QE(nb, city, dist)); }
var qGraph = qEdges.ToBidirectionalGraph<string, STaggedEdge<string,double>>();
Console.WriteLine($"Graphe QuikGraph : {qGraph.VertexCount} villes, {qGraph.EdgeCount} arcs (bidirectionnel)");

// Parcours BFS via le moteur : ordre de decouverte + arbre de parente (TreeEdge).
static (string[] order, Dictionary<string,string> parent) QuikBFS(IBidirectionalGraph<string, STaggedEdge<string,double>> g, string root)
{
    var bfs = new BreadthFirstSearchAlgorithm<string, STaggedEdge<string,double>>(g);
    var order = new List<string>();
    var parent = new Dictionary<string,string>();
    bfs.DiscoverVertex += v => { order.Add(v); parent.TryAdd(v, null); };
    bfs.TreeEdge += e => parent[e.Target] = e.Source;
    bfs.Compute(root);
    return (order.ToArray(), parent);
}

// Parcours DFS via le moteur (meme contrat d'evenements).
static (string[] order, Dictionary<string,string> parent) QuikDFS(IBidirectionalGraph<string, STaggedEdge<string,double>> g, string root)
{
    var dfs = new DepthFirstSearchAlgorithm<string, STaggedEdge<string,double>>(g);
    var order = new List<string>();
    var parent = new Dictionary<string,string>();
    dfs.DiscoverVertex += v => { order.Add(v); parent.TryAdd(v, null); };
    dfs.TreeEdge += e => parent[e.Target] = e.Source;
    dfs.Compute(root);
    return (order.ToArray(), parent);
}

// UCS via le moteur : Dijkstra (UCS = Dijkstra sur graphe a couts >= 0), distance + retrace du
// chemin via l'observateur canonique VertexPredecessorRecorderObserver (API Attach + TryGetPath).
static (double cost, string[] path) QuikDijkstraPath(IBidirectionalGraph<string, STaggedEdge<string,double>> g, string root, string goal)
{
    var dij = new DijkstraShortestPathAlgorithm<string, STaggedEdge<string,double>>(g, e => e.Tag);
    var rec = new VertexPredecessorRecorderObserver<string, STaggedEdge<string,double>>();
    rec.Attach(dij);
    dij.Compute(root);
    var d = dij.GetDistance(goal);
    if (double.IsInfinity(d)) return (double.PositiveInfinity, Array.Empty<string>());
    if (goal == root) return (d, new[] { root });
    if (!rec.TryGetPath(goal, out var aretes)) return (d, Array.Empty<string>());
    var path = new[] { aretes.First().Source }.Concat(aretes.Select(a => a.Target)).ToArray();
    return (d, path);
}

// Chemin depuis l'arbre de parente BFS/DFS, cout du chemin dans le graphe QuikGraph.
static string[] RetracePath(string root, string goal, Dictionary<string,string> parent)
{
    var path = new List<string>();
    for (var v = goal; v != null; v = parent.TryGetValue(v, out var p) ? p : null) {
        path.Insert(0, v);
        if (v == root) break;
    }
    return path.ToArray();
}

static double PathCost(IBidirectionalGraph<string, STaggedEdge<string,double>> g, string[] path)
{
    double c = 0;
    for (int i = 0; i + 1 < path.Length; i++)
        c += g.OutEdges(path[i]).First(e => e.Target == path[i + 1]).Tag;
    return c;
}

// Comparaison chiffree sur la MEME instance : les 5 trajets de la section 6.
Console.WriteLine();
Console.WriteLine("Comparaison chiffree : tranche 1 (from-scratch) vs tranche 2 (QuikGraph)");
Console.WriteLine("Meme instance : les 5 trajets de la section 6, memes poids (km).");
Console.WriteLine(new string('=', 116));

foreach (var (start, goal) in testCases) {
    var problem = new GraphProblem(start, goal, franceGraph);
    var rBFS = BFS(problem);
    var rDFS = DFS(problem);
    var rUCS = UCS(problem);

    var (_, parentB) = QuikBFS(qGraph, start);
    var (_, parentD) = QuikDFS(qGraph, start);
    var bPath = RetracePath(start, goal, parentB);
    var dPath = RetracePath(start, goal, parentD);
    var (uCost, uPath) = QuikDijkstraPath(qGraph, start, goal);
    var bCost = PathCost(qGraph, bPath);
    var dCost = PathCost(qGraph, dPath);

    string Fmt(string[] p) => p.Length == 0 ? "NON TROUVE" : string.Join(" -> ", p);
    string Trim(string s) => s.Length > 44 ? s.Substring(0, 41) + "..." : s;

    bool parBFS = rBFS.Found && bPath.Length > 0 && rBFS.Path.SequenceEqual(bPath);
    bool parDFS = rDFS.Found && dPath.Length > 0 && rDFS.Path.SequenceEqual(dPath);
    bool parUCS = rUCS.Found && Math.Abs(rUCS.Cost - uCost) < 1e-6;

    Console.WriteLine($"\n{start} -> {goal}");
    Console.WriteLine(new string('-', 116));
    Console.WriteLine($"{"Algo",-5} {"Tranche 1 (from-scratch)",-46} {"Tranche 2 (QuikGraph)",-46} {"Cout T1",-8} {"Cout T2",-8} {"Parite",-7}");
    Console.WriteLine(new string('-', 116));
    Console.WriteLine($"{"BFS",-5} {Trim(Fmt(rBFS.Path.ToArray())),-46} {Trim(Fmt(bPath)),-46} {rBFS.Cost.ToString("F0", fr),-8} {bCost.ToString("F0", fr),-8} {(parBFS ? "OK" : "ECART"),-7}");
    Console.WriteLine($"{"DFS",-5} {Trim(Fmt(rDFS.Path.ToArray())),-46} {Trim(Fmt(dPath)),-46} {rDFS.Cost.ToString("F0", fr),-8} {dCost.ToString("F0", fr),-8} {(parDFS ? "OK" : "ECART"),-7}");
    Console.WriteLine($"{"UCS",-5} {Trim(Fmt(rUCS.Path.ToArray())),-46} {Trim(Fmt(uPath)),-46} {rUCS.Cost.ToString("F0", fr),-8} {uCost.ToString("F0", fr),-8} {(parUCS ? "OK" : "ECART"),-7}");
}

Installing Packages

• QuikGraph

Graphe QuikGraph : 13 villes, 80 arcs (bidirectionnel)

Comparaison chiffree : tranche 1 (from-scratch) vs tranche 2 (QuikGraph)
Meme instance : les 5 trajets de la section 6, memes poids (km).
====================================================================================================================

Bordeaux -> Strasbourg
--------------------------------------------------------------------------------------------------------------------
Algo  Tranche 1 (from-scratch)                       Tranche 2 (QuikGraph)                          Cout T1  Cout T2  Parite 
--------------------------------------------------------------------------------------------------------------------
BFS   Bordeaux -> Paris -> Strasbourg                Bordeaux -> Paris -> Strasbourg                1075     1075     OK     
DFS   Bordeaux -> Nantes -> Toulouse -> Montpel...   Bordeaux -> Paris -> Lille -> Rennes -> N...   2260     3045     ECART  
UCS   Bordeaux -> Paris -> Strasbourg                Bordeaux -> Paris -> Strasbourg                1075     1075     OK     

Rennes -> Nice
--------------------------------------------------------------------------------------------------------------------
Algo  Tranche 1 (from-scratch)                       Tranche 2 (QuikGraph)                          Cout T1  Cout T2  Parite 
--------------------------------------------------------------------------------------------------------------------
BFS   Rennes -> Nantes -> Toulouse -> Marseille...   Rennes -> Nantes -> Toulouse -> Marseille...   1305     1305     OK     
DFS   Rennes -> Nantes -> Toulouse -> Montpelli...   Rennes -> Lille -> Paris -> Bordeaux -> T...   1310     2615     ECART  
UCS   Rennes -> Nantes -> Toulouse -> Marseille...   Rennes -> Nantes -> Toulouse -> Marseille...   1305     1305     OK     

Lille -> Toulouse
--------------------------------------------------------------------------------------------------------------------
Algo  Tranche 1 (from-scratch)                       Tranche 2 (QuikGraph)                          Cout T1  Cout T2  Parite 
--------------------------------------------------------------------------------------------------------------------
BFS   Lille -> Paris -> Bordeaux -> Toulouse         Lille -> Paris -> Bordeaux -> Toulouse         1055     1055     OK     
DFS   Lille -> Rennes -> Nantes -> Toulouse          Lille -> Paris -> Bordeaux -> Toulouse         1210     1055     ECART  
UCS   Lille -> Paris -> Bordeaux -> Toulouse         Lille -> Paris -> Bordeaux -> Toulouse         1055     1055     OK     

Nantes -> Marseille
--------------------------------------------------------------------------------------------------------------------
Algo  Tranche 1 (from-scratch)                       Tranche 2 (QuikGraph)                          Cout T1  Cout T2  Parite 
--------------------------------------------------------------------------------------------------------------------
BFS   Nantes -> Toulouse -> Marseille                Nantes -> Toulouse -> Marseille                995      995      OK     
DFS   Nantes -> Toulouse -> Montpellier -> Mars...   Nantes -> Bordeaux -> Paris -> Strasbourg...   1000     2230     ECART  
UCS   Nantes -> Toulouse -> Marseille                Nantes -> Toulouse -> Marseille                995      995      OK     

Paris -> Rennes
--------------------------------------------------------------------------------------------------------------------
Algo  Tranche 1 (from-scratch)                       Tranche 2 (QuikGraph)                          Cout T1  Cout T2  Parite 
--------------------------------------------------------------------------------------------------------------------
BFS   Paris -> Lille -> Rennes                       Paris -> Lille -> Rennes                       735      735      OK     
DFS   Paris -> Nantes -> Rennes                      Paris -> Bordeaux -> Toulouse -> Nantes -...   495      1530     ECART  
UCS   Paris -> Nantes -> Rennes                      Paris -> Nantes -> Rennes                      495      495      OK     

Lecture du résultat : la parité lib vs lib est atteinte sur BFS et UCS, le DFS illustre une divergence de stratégie

Le pont QuikGraph reconstruit la même instance : 13 villes, 80 arcs (chaque route non-orientée devient deux arcs opposés, mêmes poids en km). Les algorithmes de la tranche 1 sont ré-invoqués sur cette instance via le moteur .NET de production :

• BFS — parité OK sur les 5 trajets : chemins et coûts identiques à la tranche 1 (ex. Paris -> Lille -> Rennes à 735 km, Bordeaux -> Paris -> Strasbourg à 1075 km). L’ordre de visite des voisins de la tranche 1 (ordre du dictionnaire franceGraph) est reproduit à l’identique par QuikGraph, donc la file BFS produit le même arbre de parenté.
• UCS (via Dijkstra) — parité OK sur les 5 trajets : coûts optimaux identiques, y compris le trajet piège de la section 6 (Paris -> Nantes -> Rennes à 495 km, qui bat le chemin BFS via Lille à 735 km). C’est le cœur de la parité : deux moteurs différents (la PriorityQueue de la tranche 1 et l’algorithme de Dijkstra de QuikGraph) convergent vers la même réponse.
• DFS — ECART sur les 5 trajets : les chemins diffèrent (ex. Paris -> Rennes : 495 km via Nantes pour la tranche 1, mais 1530 km pour QuikGraph). Ce n’est pas une erreur de calcul mais une divergence de stratégie de parcours : la tranche 1 implémente un DFS itératif qui pousse les voisins sur une pile (le dernier voisin est exploré en premier), tandis que QuikGraph explore les voisins dans l’ordre sortant (le premier voisin d’abord, parcours récursif). Les deux sont des DFS valides — le résultat dépend de l’ordre de visite, ce qui rappelle pourquoi le DFS ne garantit pas l’optimalité (la tranche 2 trouve même le chemin optimal pour Lille -> Toulouse à 1055 km là où la tranche 1 en trouvait un plus long à 1210 km).

En résumé : BFS et UCS atteignent une parité chiffre-à-chiffre entre la réimplémentation pédagogique (tranche 1) et le moteur de production QuikGraph (tranche 2) — deux moteurs, une seule réponse. Le DFS documente un écart de stratégie connu, pas une divergence de résultat.