Search-03b (C#) — Bases de données de motifs (Pattern Databases) pour le 15-puzzle

Partie 3 — Recherche avancée. Version C# / .NET du notebook Search-03b-PatternDatabases (Python). Ce notebook fait partie de l’Epic de parité .NET ⇄ Python #4956 : chaque concept porté invoque le vrai moteur — ici, l’algorithme est porté from scratch en C# (les PDB n’ont pas de solveur off-the-shelf, c’est l’archétype du précalcul heuristique).

1. Le problème, et pourquoi Manhattan ne suffit plus

Le 15-puzzle (taquin 4×4) est le banc d’essai historique de la recherche heuristique : 15 tuiles + 1 case vide, on glisse les tuiles vers la configuration ordonnée. Résoudre à l’optimum est NP-difficile et constitue, depuis Korf (1985), la référence pour mesurer un solveur de recherche.

Search-3 a introduit IDA* et l’heuristique Manhattan (somme des distances individuelles des tuiles). Manhattan est admissible (ne surestime jamais), donc IDA* + Manhattan est optimal. Mais elle ignore les interactions entre tuiles (deux tuiles qui se bloquent coûtent plus que la somme de leurs distances) : sur les instances difficiles de Korf (~50 coups optimaux), IDA* + Manhattan explore des centaines de milliards de nœuds.

La SOTA, depuis Culberson & Schaeffer (1996) puis Korf & Felner (2002), consiste à précalculer une heuristique admissible bien plus fine : la base de données de motifs. Ce notebook construit d’abord une PDB simple (concept), puis la PDB additive qui est, quarante ans après Korf, la référence absolue du 15-puzzle.

2. Formalisation du 15-puzzle

État = tableau de 16 entiers (cellules en row-major), 0 = case vide. But = tuiles 1..15 en ordre, vide en bas à droite.

using System;
using System.Collections.Generic;
using System.Linq;

int[] GOAL = {1,2,3,4, 5,6,7,8, 9,10,11,12, 13,14,15,0};
const int N = 4;

int[] Neighbors(int cell) {
    int r = cell / N, c = cell % N;
    var res = new List<int>();
    if (r > 0) res.Add(cell - N);
    if (r < N - 1) res.Add(cell + N);
    if (c > 0) res.Add(cell - 1);
    if (c < N - 1) res.Add(cell + 1);
    return res.ToArray();
}

int[] Move(int[] state, int blank, int nxt) {
    var s = (int[])state.Clone();
    (s[blank], s[nxt]) = (s[nxt], s[blank]);
    return s;
}

int[][] Successors(int[] state) {
    int b = Array.IndexOf(state, 0);
    return Neighbors(b).Select(n => Move(state, b, n)).ToArray();
}

Console.WriteLine($"OK : le but a {Successors(GOAL).Length} successeurs");
OK : le but a 2 successeurs

3. Heuristique de Manhattan (référence, vu en Search-3)

Dictionary<int,int> GOAL_POS = GOAL.Select((t,i) => (t,i)).ToDictionary(p => p.t, p => p.i);

int Manhattan(int[] state) {
    int h = 0;
    for (int cell=0; cell<state.Length; cell++) {
        int t = state[cell];
        if (t == 0) continue;
        int gr = GOAL_POS[t] / N, gc = GOAL_POS[t] % N;
        int cr = cell / N, cc = cell % N;
        h += Math.Abs(gr - cr) + Math.Abs(gc - cc);
    }
    return h;
}

Console.WriteLine($"Manhattan(but) = {Manhattan(GOAL)}");
Manhattan(but) = 0

3.b Mélange reproductible (marche aléatoire)

On brouille le but par une marche aléatoire longue (90-130 pas), ce qui produit des instances réalistement difficiles (optimal typiquement ~38-46 coups) — bien plus coûteuses à résoudre que les instances jouets où Manhattan est instantané.

int[] Scramble(int[] goal, int nSteps, int seed) {
    var rng = new Random(seed);
    int[] s = (int[])goal.Clone();
    int[] prev = null;
    for (int i=0; i<nSteps; i++) {
        int b = Array.IndexOf(s, 0);
        var cands = Neighbors(b).Where(n => !Move(s,b,n).SequenceEqual(prev ?? Array.Empty<int>())).ToList();
        int nxt = cands[rng.Next(cands.Count)];
        prev = (int[])s.Clone();
        s = Move(s, b, nxt);
    }
    return s;
}

int[] INST = Scramble(GOAL, 100, seed: 11);
Console.WriteLine($"Instance de démo : ({string.Join(", ", INST)})");
Console.WriteLine($"Manhattan = {Manhattan(INST)} (borne inférieure ; l'optimal est nettement supérieur)");
Instance de démo : (1, 12, 0, 3, 9, 2, 11, 4, 10, 13, 15, 7, 5, 8, 6, 14)
Manhattan = 26 (borne inférieure ; l'optimal est nettement supérieur)

4. Concept : base de données de motifs

L’idée de Culberson & Schaeffer (1996) :

  1. Abstraction. On choisit un motif (sous-ensemble de tuiles). Les autres deviennent des jokers indifférenciés (wildcards).
  2. Parcours rétrograde. Dans l’espace abstrait, BFS depuis le but abstrait, enregistrant pour chaque état abstrait le coût optimal pour y ramener le motif.
  3. Consultation. Pour un état concret, on l’abstrait et on lit le coût en O(1).

Admissibilité. L’espace abstrait relâche le problème (les jokers se substituent gratuitement) → le coût abstrait minore le coût réel → heuristique admissible. IDA* + PDB reste donc optimal.

Fonction de rang. Pour stocker la table dans un tableau compact, on range chaque état abstrait vers un entier : rang de permutation des positions du motif P(16,k) (code de Lehmer), multiplié par le nombre de cellules restantes pour le vide.

int P(int n, int k) { int r = 1; for (int i=0; i<k; i++) r *= (n - i); return r; }

int PermRank(int[] positions, int basis=16) {
    var avail = new List<int>(); for (int i=0; i<basis; i++) avail.Add(i);
    int rank = 0; int k = positions.Length;
    for (int i=0; i<k; i++) {
        int idx = avail.IndexOf(positions[i]);
        rank += idx * P(basis - 1 - i, k - 1 - i);
        avail.RemoveAt(idx);
    }
    return rank;
}

int RankAbstract(int[] pos, int blank, int k) {
    int rPerm = PermRank(pos, 16);
    var remaining = new List<int>(); for (int c=0; c<16; c++) if (!pos.Contains(c)) remaining.Add(c);
    return rPerm * (16 - k) + remaining.IndexOf(blank);
}

// Test d'injectivité : deux états abstraits *distincts* ne doivent jamais
// partager le même rang (l'abstraction est many-to-one par construction, on teste
// donc l'injectivité du rang, pas l'absence de collisions de classes).
var rngTest = new Random(1);
var seen = new Dictionary<int,(int[] pos,int blank)>();
int collisions = 0;
for (int i=0; i<20000; i++) {
    var pool = Enumerable.Range(0,16).OrderBy(x => rngTest.Next()).Take(6).ToList();
    var pos = pool.Take(5).ToArray(); int blank = pool.Last();
    int rk = RankAbstract(pos, blank, 5);
    if (seen.TryGetValue(rk, out var prev)) { if (!prev.pos.SequenceEqual(pos) || prev.blank != blank) collisions++; }
    else seen[rk] = (pos, blank);
}
Console.WriteLine($"Injectivité du rang : {seen.Count} états abstraits testés, {collisions} collision (attendu 0)");
Injectivité du rang : 19975 états abstraits testés, 0 collision (attendu 0)

5. PDB simple : construction par BFS rétrograde

On construit d’abord une PDB sur un motif de tuiles. BFS = coût unitaire = distances optimales depuis le but abstrait. Cette PDB unique couvre un sous-ensemble de tuiles ; elle servira de brique, puis la PDB additive (section 6) en combinera plusieurs pour couvrir les 15 tuiles.

(byte[] table, int nSeen) BuildPdb(int[] group) {
    int k = group.Length;
    int[] goalPos = group.Select(t => Array.IndexOf(GOAL, t)).ToArray();
    int goalBlank = Array.IndexOf(GOAL, 0);
    int size = P(16, k) * (16 - k);
    var table = new byte[size];
    for (int i=0; i<size; i++) table[i] = 255;
    table[RankAbstract(goalPos, goalBlank, k)] = 0;
    var q = new Queue<(int[] pos, int blank)>();
    q.Enqueue((goalPos, goalBlank));
    int nSeen = 1;
    while (q.Count > 0) {
        var (pos, blank) = q.Dequeue();
        int d = table[RankAbstract(pos, blank, k)];
        var pset = new HashSet<int>(pos);
        foreach (int n in Neighbors(blank)) {
            int[] newPos; int newBlank;
            if (pset.Contains(n)) { int ti = Array.IndexOf(pos, n); newPos = (int[])pos.Clone(); newPos[ti] = blank; newBlank = n; }
            else { newPos = pos; newBlank = n; }
            int rk = RankAbstract(newPos, newBlank, k);
            if (table[rk] == 255) { table[rk] = (byte)(d + 1); q.Enqueue((newPos, newBlank)); nSeen++; }
        }
    }
    return (table, nSeen);
}

int PdbLookup(int[] state, byte[] table, int[] group) {
    int[] pos = group.Select(t => Array.IndexOf(state, t)).ToArray();
    return table[RankAbstract(pos, Array.IndexOf(state, 0), group.Length)];
}

int[] PATTERN = {1, 2, 3, 4};
var sw = System.Diagnostics.Stopwatch.StartNew();
var (PDB5, n5) = BuildPdb(PATTERN);
sw.Stop();
int dmax = PDB5.Where(v => v < 255).Max();
Console.WriteLine($"PDB simple ({PATTERN.Length} tuiles) : {n5} états en {sw.Elapsed.TotalSeconds:F1}s, distance max = {dmax}");
PDB simple (4 tuiles) : 524160 états en 1,4s, distance max = 50

Lecture de la construction : 524 160 = P(16,4) × 12, et la table EST la solution précalculée

La sortie 524 160 états en 1,4 s, distance max = 50 se décompose entièrement à la main. Le BFS rétrograde énumère les positions possibles des 4 tuiles du motif et de la case vide dans les 16 cases : 16 × 15 × 14 × 13 = 43 680 arrangements de tuiles, × 12 positions restantes pour la vide = 524 160 états. Le distance max = 50 dit ensuite que le pire sous-puzzle (les 4 tuiles les plus mal placées) exige 50 coups à lui seul : la table encode donc des optima partiels déjà très coûteux, que l’heuristique ira lire en O(1) au lieu de les recalculer. C’est tout le compromis : ~1,4 s de construction une fois, des millions de consultations gratuites ensuite.

Un point qui surprend : le BFS part du BUT et remonte les coups à l’envers. Chaque état atteint à profondeur d est donc à distance exactement d de l’objectif — la table est un oracle de distance exacte sur le sous-espace, pas une estimation.

6. La SOTA : PDB additives (Korf & Felner 2002)

Une PDB unique sur quelques tuiles n’informe qu’une fraction du puzzle. L’idée de génie de Korf & Felner (2002) : partitionner les 15 tuiles en groupes disjoints et construire une PDB par groupe, en ne comptant — dans chaque BFS — que les mouvements des tuiles du groupe. Les coûts deviennent alors additifs :

\[h(s) = \sum_{\text{groupes } G} \mathrm{PDB}_G(s)\]

est une heuristique admissible : chaque coup du taquin déplace exactement une tuile, donc la somme des minima par groupe disjoint minore le nombre total de coups.

On utilise une partition 4-4-4-3 (les groupes couvrent les 15 tuiles). Le BFS devient un 0-1 BFS (deque) : déplacer une tuile du groupe coûte 1, déplacer la case vide à travers un joker coûte 0.

int[][] GROUPS = { new[]{1,2,3,4}, new[]{5,6,7,8}, new[]{9,10,11,12}, new[]{13,14,15} };

(byte[] table, int nSeen) BuildAdditivePdb(int[] group) {
    int k = group.Length;
    int[] goalPos = group.Select(t => Array.IndexOf(GOAL, t)).ToArray();
    int goalBlank = Array.IndexOf(GOAL, 0);
    int size = P(16, k) * (16 - k);
    var dist = new byte[size];
    for (int i=0; i<size; i++) dist[i] = 255;
    dist[RankAbstract(goalPos, goalBlank, k)] = 0;
    var dq = new LinkedList<(int[] pos, int blank)>();
    dq.AddLast((goalPos, goalBlank));
    int nSeen = 1;
    while (dq.Count > 0) {
        var (pos, blank) = dq.First.Value; dq.RemoveFirst();
        int d = dist[RankAbstract(pos, blank, k)];
        var pset = new HashSet<int>(pos);
        foreach (int n in Neighbors(blank)) {
            int[] newPos; int newBlank; int w;
            if (pset.Contains(n)) { int ti = Array.IndexOf(pos, n); newPos = (int[])pos.Clone(); newPos[ti] = blank; newBlank = n; w = 1; }
            else { newPos = pos; newBlank = n; w = 0; }
            int rk = RankAbstract(newPos, newBlank, k);
            if (dist[rk] == 255) {
                dist[rk] = (byte)(d + w);
                if (w == 0) dq.AddFirst((newPos, newBlank)); else dq.AddLast((newPos, newBlank));
                nSeen++;
            }
        }
    }
    return (dist, nSeen);
}

sw.Restart();
var ADDITIVE = GROUPS.Select(g => BuildAdditivePdb(g)).ToArray();
byte[][] ADD_TBLS = ADDITIVE.Select(a => a.table).ToArray();
sw.Stop();
Console.WriteLine($"PDB additives (4-4-4-3) construites en {sw.Elapsed.TotalSeconds:F1}s");
foreach (var (g, a) in GROUPS.Zip(ADDITIVE)) {
    int dm = a.table.Where(v => v < 255).Max();
    Console.WriteLine($"  groupe ({string.Join(",", g)}): {a.nSeen} états, dist max = {dm}");
}
PDB additives (4-4-4-3) construites en 3,9s
  groupe (1,2,3,4): 524160 états, dist max = 21
  groupe (5,6,7,8): 524160 états, dist max = 17
  groupe (9,10,11,12): 524160 états, dist max = 19
  groupe (13,14,15): 43680 états, dist max = 16

Lecture des groupes : pourquoi la somme des 4 tables reste admissible

La sortie donne quatre tables : trois de 524 160 états (groupes de 4 tuiles) et une de 43 680 (groupe de 3 : P(16,3) = 16 × 15 × 14 = 3 360 arrangements, × 13 positions restantes pour la case vide = 43 680 — le vide est encodé comme pour les groupes de 4). Les distances max se lisent 21, 17, 19 et 16. Le point structurel : chaque coup du 15-puzzle déplace une seule tuile, qui appartient à un seul groupe — les coûts des groupes sont disjoints par coup, donc leur somme ne peut jamais surestimer la distance réelle. C’est la différence radicale avec la PDB classique de Culberson & Schaeffer : on y prenait le max de plusieurs vues du même puzzle ; Korf & Felner partitionnent en groupes disjoints pour pouvoir sommer. La même somme appliquée à des groupes qui se chevaucheraient casserait l’admissibilité immédiatement (un même coup compté deux fois).

7. IDA* instrumenté

Rappel de Search-3 : seuils itératifs sur f = g + h, recherche en profondeur. On compte les nœuds explorés (métrique du coût de recherche). On l’introduit avant l’heuristique additive car il sert à sa vérification d’admissibilité ci-après.

On se fixe un budget de 2 millions de nœuds par résolution : c’est largement assez pour résoudre les instances faciles, et cela rend visible (et rapide) la frontière où une heuristique termine et l’autre non. L’état est encodé en un long (16 cellules × 4 bits) pour le hachage du chemin (cycle-avoidance).

long Encode(int[] state) { long k = 0; foreach (int t in state) k = k * 16 + t; return k; }

(int? cost, long nodes) IdaStar(int[] start, Func<int[],int> heuristic, int[] goal=null, long nodeLimit=2_000_000) {
    goal ??= GOAL;
    int threshold = heuristic(start); long nodes = 0;
    while (true) {
        var path = new HashSet<long>(); path.Add(Encode(start));
        var (res, t, n) = Dfs(start, 0, threshold, heuristic, goal, path, nodeLimit - nodes);
        nodes += n;
        if (res.HasValue) return (res, nodes);
        if (t == int.MaxValue || nodes >= nodeLimit) return (null, nodes);
        threshold = t;
    }
}

(int? cost, int nextThreshold, long nodes) Dfs(int[] state, int g, int threshold, Func<int[],int> heuristic, int[] goal, HashSet<long> path, long budget) {
    int f = g + heuristic(state);
    if (f > threshold) return (null, f, 0);
    if (state.SequenceEqual(goal)) return (g, f, 0);
    if (budget <= 0) return (null, int.MaxValue, 0);
    long nTotal = 1; int nextT = int.MaxValue; int b = Array.IndexOf(state, 0);
    foreach (int n in Neighbors(b)) {
        int[] s2 = Move(state, b, n);
        long e2 = Encode(s2);
        if (path.Contains(e2)) continue;
        path.Add(e2);
        var (res, t, nn) = Dfs(s2, g+1, threshold, heuristic, goal, path, budget - nTotal);
        nTotal += nn; path.Remove(e2);
        if (res.HasValue) return (res, t, nTotal);
        if (t < nextT) nextT = t;
        if (nTotal >= budget) return (null, nextT, nTotal);
    }
    return (null, nextT, nTotal);
}

// Sanity préliminaire : Manhattan est admissible et résout une instance facile.
int[] easy = Scramble(GOAL, 8, seed: 1);
var (sm, _) = IdaStar(easy, Manhattan);
Console.WriteLine($"Sanity : instance facile optimal={sm} (Manhattan résout bien)");
Sanity : instance facile optimal=8 (Manhattan résout bien)

8. Heuristique additive et vérification d’admissibilité

h_additive(s) = Σ PDB_groupe(s). On vérifie empiriquement l’admissibilité : sur un échantillon d’instances résolues à l’optimum (via Manhattan, elle-même admissible), h_additive(s) ≤ optimal(s) doit toujours tenir. On vérifie aussi la convergence (même optimum) sur une instance facile.

int HAdditive(int[] state) => ADD_TBLS.Zip(GROUPS).Sum(p => PdbLookup(state, p.First, p.Second));

// Convergence : deux heuristiques admissibles -> même optimum.
var (sa, _) = IdaStar(easy, HAdditive);
Console.WriteLine($"Convergence confirmée : additive optimal={sa} == Manhattan optimal={sm}");

// Admissibilité empirique : h_additive <= optimal (optimal via Manhattan-IDA*).
var rngAdm = new Random(7); int checkedCount = 0; int violations = 0;
for (int i=0; i<40; i++) {
    int[] s = Scramble(GOAL, 14, seed: rngAdm.Next(0, 1_000_000_000));
    var (opt, _) = IdaStar(s, Manhattan);
    if (!opt.HasValue) continue;
    if (HAdditive(s) > opt.Value) violations++;
    checkedCount++;
}
Console.WriteLine($"Admissibilité : {checkedCount} instances, h_additive <= optimal tient {checkedCount - violations}/{checkedCount} fois");
Console.WriteLine($"Sur l'instance de démo : Manhattan={Manhattan(INST)}, h_additive={HAdditive(INST)} (additive >= Manhattan attendu)");
Convergence confirmée : additive optimal=8 == Manhattan optimal=8
Admissibilité : 40 instances, h_additive <= optimal tient 40/40 fois
Sur l'instance de démo : Manhattan=26, h_additive=28 (additive >= Manhattan attendu)

Dominance : additive ≥ Manhattan, lues sur l’instance de démo

La sortie porte trois verdicts distincts. (1) additive optimal=8 == Manhattan optimal=8 : sur l’instance de test, IDA* trouve le même optimum sous les deux heuristiques — l’optimalité est préservée. (2) 40/40 : sur 40 instances brouillées, h_additive ≤ optimal à chaque fois — l’admissibilité tient en pratique. (3) Manhattan=26, h_additive=28 : sur l’instance de démo, l’additive domine strictement Manhattan. Le lien avec la théorie : Manhattan est exactement la PDB additive des 15 groupes d’une tuile — raffiner la partition (1-1-…-1 vers 4-4-4-3) ne peut que resserrer la borne. Un heuristique qui domine et reste admissible explore mécaniquement moins de nœuds à optimalité égale : c’est le seul « free lunch » de la recherche heuristique.

9. Expérience : Manhattan vs PDB additive (la valeur du moteur, visible)

Trois instances réalistement difficiles (brouillage 50-80 pas, optimal ~24-53 coups), choisies pour révéler la frontière de résolubilité au budget de 2M nœuds. On résout à l’optimum avec (a) Manhattan seule, puis (b) la PDB additive. On mesure les nœuds explorés : c’est la métrique qui révèle la puissance de l’heuristique. Sur les instances intermédiaires (optimal ~45-53), Manhattan dépasse le budget de 2M nœuds sans conclure, tandis que la PDB additive (4-4-4-3) résout — assez pour repousser la frontière du résolvable.

var INSTANCES = new Dictionary<string,int[]> {
    ["I1 (facile, opt 24)"] = Scramble(GOAL, 50, seed: 11),
    ["I2 (moyen, opt 45)"] = Scramble(GOAL, 81, seed: 78690737),
    ["I3 (dur, opt 53)"] = Scramble(GOAL, 71, seed: 163151276),
};

// bench: name, opt, heuristics, nodes(Manhattan/additive), solved flags, speedup, times
var bench = new List<(string name, int? opt, int mh, int ha, long nm, long na, bool mSolved, bool aSolved, double speedup, double tm, double ta)>();
foreach (var (name, s) in INSTANCES) {
    sw.Restart(); var (solM, nm) = IdaStar(s, Manhattan); sw.Stop(); double tm = sw.Elapsed.TotalSeconds;
    sw.Restart(); var (solA, na) = IdaStar(s, HAdditive); sw.Stop(); double ta = sw.Elapsed.TotalSeconds;
    int? opt = solM ?? solA;
    double speedup = (solM.HasValue && solA.HasValue && na > 0) ? (double)nm / na : double.NaN;
    bench.Add((name, opt, Manhattan(s), HAdditive(s), nm, na, solM.HasValue, solA.HasValue, speedup, tm, ta));
    string nmS = solM.HasValue ? $"{nm,12:N0}" : "  >= 2M (limite)";
    string naS = solA.HasValue ? $"{na,12:N0}" : "  >= 2M (limite)";
    Console.WriteLine($"{name,-20} optimal={opt} | Manhattan: {nmS} ({tm,6:F1}s) | additive: {naS} ({ta,6:F1}s) | speedup x{speedup,6:F1}");
}
I1 (facile, opt 24)  optimal=24 | Manhattan:        2 114 (   0,0s) | additive:          732 (   0,0s) | speedup x   2,9
I2 (moyen, opt 45)   optimal=45 | Manhattan:   >= 2M (limite) (   2,9s) | additive:      299 773 (   2,9s) | speedup x   NaN
I3 (dur, opt 53)     optimal=53 | Manhattan:   >= 2M (limite) (   2,2s) | additive:      392 168 (   2,0s) | speedup x   NaN

Synthèse : la PDB additive repousse la frontière du résolvable

(Version texte — pas de graphique matplotlib en C# ; le tableau numérique brut montre directement le nœud où chaque heuristique termine ou dépasse le budget.)

Console.WriteLine($"{"Instance",-20} {"opt",-5} {"Manhattan nodes",-18} {"Additive nodes",-18} {"speedup",-10}");
Console.WriteLine(new string('-', 75));
foreach (var r in bench) {
    string nmS = r.mSolved ? r.nm.ToString("N0") : ">= 2M";
    string naS = r.aSolved ? r.na.ToString("N0") : ">= 2M";
    Console.WriteLine($"{r.name,-20} {r.opt,-5} {nmS,-18} {naS,-18} {r.speedup,-10:F1}x");
}
Console.WriteLine();
Console.WriteLine("Lecture : sur l'instance facile (I1), les deux heuristiques terminent et la");
Console.WriteLine("PDB additive explore ~3x moins de nœuds. Sur I2 et I3 (optimal 45 et 53),");
Console.WriteLine("Manhattan dépasse le budget de 2M nœuds sans conclure, tandis que la PDB");
Console.WriteLine("additive (4-4-4-3) résout à l'optimum — elle repousse la frontière du résolvable.");
Instance             opt   Manhattan nodes    Additive nodes     speedup   
---------------------------------------------------------------------------
I1 (facile, opt 24)  24    2 114              732                2,9       x
I2 (moyen, opt 45)   45    >= 2M              299 773            NaN       x
I3 (dur, opt 53)     53    >= 2M              392 168            NaN       x

Lecture : sur l'instance facile (I1), les deux heuristiques terminent et la
PDB additive explore ~3x moins de nœuds. Sur I2 et I3 (optimal 45 et 53),
Manhattan dépasse le budget de 2M nœuds sans conclure, tandis que la PDB
additive (4-4-4-3) résout à l'optimum — elle repousse la frontière du résolvable.

Lecture du tableau : ce que « speedup NaN » veut dire

Deux lignes portent speedup NaN, et c’est l’information la plus importante du tableau. Sur I1 (optimal 24), les deux heuristiques terminent : 2 114 nœuds contre 732, rapport 2,9 — l’additive fait mieux, mais Manhattan suffit. Sur I2 et I3 (optimaux 45 et 53), Manhattan dépasse le budget de 2 M nœuds sans conclure : le rapport est NaN parce qu’on ne peut pas diviser par un échec. L’additive, elle, conclut à l’optimum en 299 773 et 392 168 nœuds. La leçon n’est pas « 3× plus vite » mais « résout l’irrésolu » : entre les deux colonnes, ce n’est pas la même classe d’instances qui est accessible. La frontière du résoluble a bougé.

11. Limites et au-delà

  • Coût de construction. Plus le groupe est grand, plus la PDB est fine mais plus le BFS est coûteux (P(16,k) explose). Korf & Felner poussent aux partitions 6-6-3 puis 7-8 (avec symétries) pour résoudre les instances à ~66 coups — au prix de tables de plusieurs gigaoctets.
  • PDB symétriques. Le 15-puzzle admet une symétrie (miroir + renversement des numéros) qui permet de déduire une seconde PDB gratuitement (Felner et al. 2004).
  • Généralité. La même technique résout le Rubik’s Cube (Korf 1997), la Tour de Hanoï, tout puzzle de permutation. C’est l’archétype du compromis mémoire contre qualité d’heuristique.

Attendus — Exercice 1 (partition 6-6-3)

Ce que vous devez observer si votre implémentation est juste : deux PDB de P(16,6) = 5 765 760 arrangements × 10 = 57 657 600 états chacune, une de P(16,3) × 13 = 43 680 — le temps de construction passe de ~4 s à plusieurs dizaines de secondes (d’où l’avertissement de l’énoncé), les distances max par groupe montent (un groupe de 6 est plus mal plaçable qu’un groupe de 4), et h_additive resserre encore : attendez-vous à ce que I1 descende nettement sous les 732 nœuds de la 4-4-4-3. Anti-piège : la partition doit rester exactement disjointe (15 tuiles = 6+6+3) ; réutiliser une tuile dans deux groupes compte ses coups deux fois et casse l’admissibilité — la cellule de vérification du §8 doit rester 40/40.

Rappel (convention de la série) : un exercice est un squelette à compléter. Les stubs s’exécutent sans erreur (// TODO etudiant + garde le code compilable) ; à vous de les remplir. Ne supprimez pas les // Indice / // Étape N.

12. Exercices

Exercice 1 — Partition plus fine (6-6-3)

Remplacez la partition 4-4-4-3 par 6-6-3 (Korf & Felner 2002). Combien d’états par PDB (P(16,6)×10, P(16,3)×13) ? Mesurez le speedup supplémentaire sur les instances du banc d’essai. Attention au temps de construction des groupes de 6.

// Exercice 1 — à compléter
int[][] GROUPS_663 = { new[]{1,2,3,4,5,6}, new[]{7,8,9,10,11,12}, new[]{13,14,15} };

// Indice : réutilisez BuildAdditivePdb sur chaque groupe.
//   Étape 1 : construisez la liste des tables (var tbls663 = GROUPS_663.Select(g => BuildAdditivePdb(g).table).ToArray();).
//   Étape 2 : attention, un groupe de 6 -> P(16,6)*10 ~ 57M états (~57 Mo) ; le BFS prend ~1-2 min.
// int HAdditive663(int[] state) => tbls663.Zip(GROUPS_663).Sum(p => PdbLookup(state, p.First, p.Second));
// TODO etudiant
Console.WriteLine("Exercice 1 à compléter : partition 6-6-3 (Korf & Felner 2002) + speedup.");
Exercice 1 à compléter : partition 6-6-3 (Korf & Felner 2002) + speedup.

Exercice 2 — PDB symétrique gratuit (Felner et al. 2004)

Le 15-puzzle possède une symétrie : refléter la grille (miroir vertical) et renverser les numéros (t -> 16 - t) laisse le puzzle invariant. Construisez la transformation Reflect(state), vérifiez qu’elle préserve la résolubilité et que HAdditive(state) == HAdditive(Reflect(state)). En déduire une seconde PDB gratuite et combinez-la par Math.Max.

// Exercice 2 — à compléter
// int[] Reflect(int[] state) {
//     // Indice : miroir vertical de la grille 4x4, puis renversement des numéros
//     // t -> 16 - t pour t != 0 (le vide reste le vide).
//     //   Étape 1 : reshape en 4x4, retournez les colonnes, aplatissez.
//     //   Étape 2 : mappez chaque tuile t -> 16-t (sauf 0).
//     return null; // TODO etudiant
// }
// Indice : vérifiez Reflect(Reflect(s)).SequenceEqual(s) et HAdditive(s) == HAdditive(Reflect(s)).
// TODO etudiant
Console.WriteLine("Exercice 2 à compléter : PDB symétrique gratuit (Felner et al. 2004).");
Exercice 2 à compléter : PDB symétrique gratuit (Felner et al. 2004).

Attendus — Exercice 2 (PDB symétrique)

La symétrie du 15-puzzle (miroir vertical + renversement des numéros) transforme toute instance en une instance joker : vous obtenez une seconde heuristique sans nouveau BFS. L’usage correct est le max des deux vues — admissible car chacune l’est, et strictement meilleur dès qu’une des deux voit mieux. Si vous obtenez exactement les mêmes valeurs qu’avant, votre Reflect est probablement l’identité déguisée (indices : le miroir échange les colonnes, et le renversement remappe les numéros t vers 16 − t).

Exercice 3 — Généralisation au 24-puzzle

Le 24-puzzle (5×5) est le vrai défi : Manhattan y est désespérément faible et seules les PDB additives rendent la résolution optimale envisageable. Adaptez ce notebook (25 cellules, partition 6-6-6-7) et résolvez une instance. Que constatez-vous sur le rapport construction/qualité ?

// Exercice 3 — à compléter
// Indice : la structure est inchangée ; changent la taille (N=5), le but (1..24,0),
// et la partition.
//   Étape 1 : redéfinissez GOAL24 et Neighbors pour N=5.
//   Étape 2 : attention à l'explosion de P(25, k) — restez sur des groupes <= 6.
// TODO etudiant
Console.WriteLine("Exercice 3 à compléter : généralisation au 24-puzzle (5x5, partition 6-6-6-7).");
Exercice 3 à compléter : généralisation au 24-puzzle (5x5, partition 6-6-6-7).

Attendus — Exercice 3 (24-puzzle)

Au 24-puzzle (5 × 5), Manhattan est désespérément loose : les instances aléatoires moyennes exigent ~100 coups, et IDA* sous Manhattan explose au-delà de tout budget raisonnable. La structure du code est inchangée (N=5, but 1..24,0) mais les tailles explosent : un groupe de 6 tuiles dans 25 cases donne P(25,6) × 19 = 2 422 728 000, soit ~2,4 milliards d’états — la table ne tient plus en mémoire sans encodage compact. C’est précisément pourquoi Korf & Felner ont poussé les partitions avec symétries et la compression : au 24-puzzle, la PDB n’est plus une optimisation, c’est la condition d’entrée.

L’arc du notebook : représenter (permutations), abstraire (sous-espaces), précalculer (BFS rétrograde), sommer (disjonction), vérifier (admissibilité et dominance), mesurer (frontière du résoluble). Ce pipeline est transposable à tout domaine où l’on peut payer du calcul préliminaire pour accélérer des requêtes répétées.

Conclusion

La base de données de motifs illustre un principe central de la recherche heuristique avancée : investir du calcul en amont (précalculer des tables une fois pour toutes) pour rendre chaque recherche ultérieure radicalement plus cheap. Sur le 15-puzzle, la PDB additive (4-4-4-3) explore ~3 à 10x moins de nœuds que Manhattan sur les instances résolubles, et — c’est le point décisif — résout à l’optimum des instances intermédiaires (optimal ~45-53 coups) où Manhattan dépasse le budget. Les partitions plus fines (6-6-3 puis 7-8 avec symétries, cf exercices et Korf & Felner 2002) poussent cette frontière encore plus loin, jusqu’aux instances à ~66 coups de la littérature.

Les trois ingrédients de la technique :

  1. l’abstraction (garder un motif, jokeriser le reste) ;
  2. le parcours rétrograde (BFS / 0-1 BFS depuis le but abstrait = distances optimales, admissibles parce que le problème abstrait est un relâchement) ;
  3. la combinaison admissible additive (somme sur des groupes disjoints, en ne comptant que les mouvements propres à chaque groupe).

La leçon plus large pour la Partie 3 : quand un problème est trop dur pour une heuristique « instantanée », la bonne réponse n’est pas d’abandonner l’optimalité mais de précalculer une heuristique plus fine, quitte à payer un coût de construction amorti sur des millions de requêtes.

Références

  • Korf, R. E. (1985). Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. AI 27(1).
  • Culberson, J. C. & Schaeffer, J. (1996). Searching with Pattern Databases. AI*AI.
  • Korf, R. E. & Felner, A. (2002). Disjoint Pattern Database Heuristics. AI 134(1-2).
  • Felner, A., Korf, R. E., et al. (2004). Additive Pattern Database Heuristics. JAIR 21.
  • Korf, R. E. (1997). Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases. AAAI.
  • Edelkamp, S. & Schrödl, S. (2012). Heuristic Search: Theory and Applications. Morgan Kaufmann.

← Search-3 — Recherche informée

↑ Search (racine) | Partie 4 — Métaheuristiques →
🐍 Version Python
Retour au sommet