Search-03c (C#) — Recherche à écart limité (Limited Discrepancy Search)
Partie 3 — Recherche avancée. Ce notebook est le jumeau .NET du notebook Search-03c — Limited Discrepancy Search (Python). Il implémente en C# le même algorithme — LDS de Harvey & Ginsberg (1995) — sur le même banc d’essai (sac à dos 0/1), pour montrer comment la technique se transpose à une recherche arborescente typée.
Prérequis : avoir vu les fondations de la recherche heuristique en Partie 1 — Search-3 (Informed) (A*, heuristiques admissibles).
2. Le problème-banc d’essai : le sac à dos 0/1
Le sac à dos binaire (0/1 knapsack) est NP-difficile et se prête naturellement à une recherche arborescente. On dispose de \(n\) objets, chacun avec un poids \(w_i\) et une valeur \(v_i\), et d’une capacité \(C\). On veut maximiser la valeur totale sans dépasser la capacité.
L’heuristique gloutonne consistant à prendre les objets par ratio valeur/poids décroissant est naturelle mais myope : elle peut rater l’optimum en se bloquant trop tôt. C’est précisément le défaut que LDS corrige.
// Le sac à dos 0/1 : liste d'objets (nom, poids, valeur), ordonnés par RATIO valeur/poids décroissant// (c'est l'ordre où l'heuristique gloutonne les considère).// Item: nom, poids, valeur — record C# immuable (équivalent du tuple nommé Python).public record Item(string Name,int Weight,int Value);Item[] items =new Item[]{new("A",6,8),// ratio 1.33 <-- top ratio, MAIS poids 6 bloque la paire B+C (valeur 12 > 10)new("B",5,6),// ratio 1.20new("C",5,6),// ratio 1.20new("D",4,2),// ratio 0.50new("E",3,1),// ratio 0.33};int capacity =10;Console.WriteLine($"Objets (ordre heuristique, ratio valeur/poids décroissant) :");foreach(var it in items) Console.WriteLine($" {it.Name}: poids={it.Weight}, valeur={it.Value}, ratio={it.Value / (double)it.Weight:F2}");Console.WriteLine($"Capacité du sac : {capacity}");
Lecture du banc d’essai : ce que l’ordre des objets encode
La sortie classe A (ratio 1,33) > B = C (1,20) > D (0,50) > E (0,33) pour une capacité de 10. Deux choses se lisent déjà. D’abord, l’ordre du tableau est l’heuristique : LDS parlera de « suivre la recommandation » = prendre les objets dans cet ordre tant que le poids le permet. Ensuite, l’égalité parfaite B = C (mêmes poids 5, valeur 6) fabrique une indifférence : l’heuristique ne peut pas les départager, et c’est exactement là que les écarts paieront — la solution optimale [B, C] consiste à refuser A (le mieux classé !) pour loger la paire que la capacité (10 = 5 + 5) accueille exactement.
Stratégie gloutonne (k = 0)
Suivre aveuglément l’heuristique : prendre chaque objet s’il rentre.
// Stratégie GLOUTONNE (k=0) : suivre l'heuristique aveuglement — prendre chaque objet s'il rentre.(int Value, List<string> Selection,int Nodes)GreedyKnapsack(Item[] items,int capacity){var sel =new List<string>();int totalW =0, totalV =0, nodes =0;foreach(var it in items){ nodes++;if(totalW + it.Weight<= capacity)// heuristique : prendre si ça rentre{ sel.Add(it.Name); totalW += it.Weight; totalV += it.Value;}}return(totalV, sel, nodes);}var(greedyV, greedySel, greedyNodes)=GreedyKnapsack(items, capacity);Console.WriteLine($"Greedy (k=0) : valeur={greedyV}, sélection=[{string.Join(",", greedySel)}], nœuds={greedyNodes}");
Pourquoi le glouton échoue ici (et pourquoi c’est instructif)
valeur=10, sélection=[A, D], nœuds=5 : le glouton prend A (ratio max, poids 6), ne peut plus loger ni B ni C (6+5 > 10), recolle D (poids 4, valeur 2) et s’arrête à 10. La solution optimale est [B, C] = 12 — deux objets mieux notés en volume dont la somme (10) remplit le sac exactement. L’échec n’est pas un accident du banc : il est structurel (le glouton 0/1 n’a pas de ratio d’approximation borné en général). Les 5 nœuds disent aussi son prix : un parcours linéaire. La question que LDS pose est : peut-on réparer quelques décisions du glouton sans payer le 2ⁿ de l’énumération ?
3. Le concept d’écart, et l’algorithme LDS(k)
À chaque nœud, l’heuristique recommande une action (prendre l’objet s’il rentre, sinon le laisser). Choisir l’autre action coûte un écart :
Objet prenable : rang 0 = prendre (recommandé), rang 1 = laisser (1 écart).
Objet non prenable : rang 0 = laisser (recommandé), rang 1 = impossible (capacité dépassée).
LDS(k) explore tous les chemins de l’arbre qui s’écartent au plus \(k\) fois de l’heuristique. Pour \(k = 0\) on retrouve le glouton ; pour \(k \to \infty\) on retrouve la DFS exhaustive. L’intuition de Harvey & Ginsberg : si l’heuristique est bonne, l’optimum est un proche voisin du chemin glouton, donc un petit \(k\) suffit souvent.
// LDS(k) sur le sac à dos 0/1 — version récursive bornée par le nombre d'écarts.// items : tableau ordonné par ordre heuristique (meilleur ratio d'abord).// Renvoie (meilleure valeur, meilleure sélection, nombre de nœuds explorés).(int Value, List<string>? Selection,int Nodes)LdsKnapsack(Item[] items,int capacity,int kMax){int n = items.Length;int bestValue =-1; List<string>? bestSel =null;int nodes =0;voidRec(int i,int remCap,int valSoFar, List<string> sel,int discLeft){ nodes++;if(i == n){if(valSoFar > bestValue){ bestValue = valSoFar; bestSel =new List<string>(sel);}return;}var it = items[i];bool canTake = it.Weight<= remCap;// Recommandation de l'heuristique à ce nœud :// - si l'objet rentre : prendre (rang 0)// - sinon : laisser (rang 0)// L'autre choix consomme 1 écart (si possible).if(canTake){// rang 0 (recommandé) : prendre sel.Add(it.Name);Rec(i +1, remCap - it.Weight, valSoFar + it.Value, sel, discLeft); sel.RemoveAt(sel.Count-1);// rang 1 (écart) : laisserif(discLeft >0)Rec(i +1, remCap, valSoFar, sel, discLeft -1);}else{// rang 0 (recommandé) : laisser (impossible de prendre)Rec(i +1, remCap, valSoFar, sel, discLeft);// rang 1 (écart) : prendre — impossible (capacité), branche tronquée}}Rec(0, capacity,0,new List<string>(), kMax);return(bestValue, bestSel, nodes);}// Balayage k = 0..n : montre la convergence vers l'optimum.Console.WriteLine(string.Format("{0,3}{1,8}{2,10} sélection","k","valeur","nœuds"));for(int k =0; k <= items.Length; k++){var(v, sel, nd)=LdsKnapsack(items, capacity, k); Console.WriteLine(string.Format("{0,3}{1,8}{2,10} [{3}]", k, v, nd,string.Join(", ", sel ??new List<string>())));}
Lecture du tableau LDS : l’optimum est à k=1, le coût croît régulièrement
Trois lectures. (1) La colonne valeur saute de 10 (k=0) à 12 (k=1) puis ne bouge plus : un seul écart au glouton — refuser A — suffit à atteindre l’optimum. (2) Les nœuds montent 6, 13, 21, 28, 33, 34 : à k fixé, LDS explore les chemins à au plus k écarts ; k=5 = n couvre tout l’arbre (34 s’approche des 32 feuilles plus les nœuds internes revisités). (3) La sélection [B, C] est stable dès k=1 : LDS ne « change pas d’avis » en explorant plus, il confirme. Les deux warnings CS8632 de la sortie sont bénins : des annotations de nullabilité ? utilisées hors contexte #nullable (le gabarit interactif compile sans le flag) — ils n’affectent ni l’exécution ni les résultats.
4. Référence : l’optimum par énumération exhaustive
Pour prouver que LDS atteint bien le vrai optimum (et non une borne locale), on calcule la solution optimale par énumération exhaustive de l’arbre binaire complet (\(2^n\) feuilles). LDS devra converger vers cette même valeur pour \(k\) assez grand.
// Optimum exact par énumération exhaustive (2^n) — référence de vérité.(int Value, List<string> Selection,int Nodes)ExhaustiveKnapsack(Item[] items,int capacity){int n = items.Length;int bestV =-1, nodes =0; List<string> bestSel =new();long total =1L<< n;// 2^n combinaisonsfor(long mask =0; mask < total; mask++){ nodes++;int w =0, v =0;var sel =new List<string>();for(int i =0; i < n; i++){if(((mask >> i)&1L)==1L){ w += items[i].Weight; v += items[i].Value; sel.Add(items[i].Name);}}if(w <= capacity && v > bestV){ bestV = v; bestSel = sel;}}return(bestV, bestSel, nodes);}var(optV, optSel, exNodes)=ExhaustiveKnapsack(items, capacity);Console.WriteLine($"Exhaustif : valeur optimale={optV}, sélection=[{string.Join(",", optSel)}], nœuds={exNodes}");
La colonne « % exhaustif » : où LDS cesse d’être une bonne affaire
La dernière colonne est la plus parlante : LDS(1) atteint l’optimum pour 40,6 % du coût de l’énumération (13 nœuds contre 32). Mais la ligne LDS(4) franchit 103,1 % et LDS(5) 106,2 % : passé un certain k, LDS explore plus que l’énumération exhaustive — le décompte par écarts revisite des chemins déjà vus et ajoute du travail. La niche de LDS est donc exactement : une heuristique assez bonne pour que l’optimal soit à petit k. Quand l’heuristique est mauvaise (exercice 3), le k optimal monte, la combinatoire gonfle, et LDS dégénère — sans jamais perdre la garantie de complétude à k = n.
Lecture du résultat
Le greedy (k=0) est sous-optimal : il prend A au ratio le plus élevé (1,33), qui remplit 6 des 10 unités de capacité et ne laisse de la place que pour D — ratant la paire B+C dont la valeur (12) est supérieure. Dès k=1, LDS explore le chemin « laisser A » et découvre l’optimum {B, C, …}, en n’explorant qu’une fraction de l’arbre exhaustif. C’est tout l’intérêt de LDS : saisir l’optimum à coût sous-exponentiel quand l’heuristique est bonne.
Implémentez ILDS : exécutez LDS pour k=0, 1, 2, … en vous arrêtant dès que la valeur stagne (deux incréments consécutifs sans amélioration) ou que k atteint n. Comparez le nombre total de nœuds explorés par ILDS à l’énumération exhaustive sur cette instance. - Indice : le critère d’arrêt « valeur qui stagne » évite de gaspiller des nœuds pour des k qui n’apportent plus rien. Accumulez les nœuds de chaque appel LdsKnapsack(k).
// Exercice 1 à compléter// Conseil : bouclez k = 0..n, accumulez les nœuds, arrêtez quand la valeur cesse de croître.// Comparez le total accumulé à exNodes (l'exhaustif calculé ci-dessus).int totalNodesIlds =0;Console.WriteLine("Exercice 1 à compléter");
Exercice 1 à compléter
Attendus — Exercice 1 (ILDS)
Le tableau attendu : k = 0..n en boucle, nœuds cumulés ; la valeur stagne à 12 dès k=1, donc ILDS s’arrête à k=2 si votre critère est « deux tours sans amélioration ». Anti-piège : n’interrompez pas au premier k sans amélioration — sur d’autres instances l’optimum peut réapparaître à k+1 après un plateau ; c’est le compromis arrêt-anticipé classique.
Exercice 2 : passage à l’échelle — LDS vs exhaustif
Construisez une instance plus grande (par ex. n=18 objets aléatoires, capacité ~50% du poids total) où le greedy est sous-optimal. Mesurez : 1. Le plus petit k pour lequel LDS atteint l’optimum (vérifié via DP ou exhaustif si n petit). 2. Le ratio de nœuds LDS(k*) / exhaustif (\(2^{18} = 262\,144\) feuilles). - Indice : tirez des (poids, valeur) aléatoires avec une graine fixée (new Random(42)), calculez l’optimum exhaustif, puis balayez k jusqu’à l’atteindre.
// Exercice 2 à compléter// Conseil : générez n=18 objets aléatoires (poids, valeur), calculez l'optimum exhaustif,// puis balayez k jusqu'à l'atteindre. Affichez le ratio LDS(k*)/2**18.Console.WriteLine("Exercice 2 à compléter");
Exercice 2 à compléter
Attendus — Exercice 2 (passage à l’échelle)
À n=18 : l’énumération = 2¹⁸ = 262 144 feuilles ; LDS à k≤3 explore de l’ordre de la somme des binomiaux C(18, i) pour i ≤ 3, soit ~1 000 nœuds — le ratio se creuse avec n tant que l’optimum reste à petit k. Observez le basculement : si vous générez des ratios « adverses » (l’optimal exige de refuser les 4 premiers objets), LDS(3) ne suffit plus et la courbe nœuds(k) croise la ligne 2ⁿ.
Exercice 3 : sensibilité à la qualité de l’heuristique
LDS suppose une heuristique bonne. Refaites le balayage k=0..n mais en perturbant l’ordre des objets : (a) ordre aléatoire, (b) ordre par valeur absolue décroissante (au lieu du ratio). Pour chaque heuristique, notez le k minimum pour atteindre l’optimum. - Indice : plus l’heuristique est mauvaise, plus k* grandit — LDS perd tout son intérêt si l’heuristique est essentiellement aléatoire. Permutez le tableau items et réutilisez LdsKnapsack.
// Exercice 3 à compléter// Conseil : permutez `items` selon différents ordres, et pour chacun cherchez le k min.// Perturbation : utilisez new Random(123) pour un ordre aléatoire reproductible.Console.WriteLine("Exercice 3 à compléter");
Exercice 3 à compléter
Attendus — Exercice 3 (sensibilité à l’heuristique)
Avec un ordre aléatoire des objets, le k optimal grimpe vers n/2 et le coût LDS rejoint l’énumération — LDS n’a pas de magie intrinsèque, il emprunte la qualité de l’heuristique. La courbe à tracer : k* (l’écart de l’optimal au classement) en fonction du nombre d’inversions de l’ordre testé. Elle doit être grossièrement croissante.
Conclusion
Limited Discrepancy Search occupe une niche précise dans le spectre de la recherche heuristique. À une extrémité, le greedy est instantané mais myope ; à l’autre, la DFS exhaustive est exacte mais exponentielle. LDS exploite l’idée que si l’heuristique est bonne, l’optimum est un proche voisin du greedy : en bornant le nombre d’écarts \(k\), on obtient un compromis réglable entre qualité et coût.
Comparaison C# vs Python (jumeau)
Le port C# met en évidence : - le typage statique des record Item (sécurité compile-time vs tuples dynamiques Python) ; - la récursion avec closure (void Rec(...) { ... } capturant bestValue, nodes) vs la fermeture Python def rec(...) avec nonlocal ; - la manipulation de bits pour l’exhaustif (1L << n, (mask >> i) & 1L) plus explicite en C# qu’avec itertools.product.
L’algorithmique, elle, est identique — LDS est language-agnostic. Voir le jumeau Python pour la version dynamique.
Référence : Harvey, W. D., & Ginsberg, M. L. (1995). Limited Discrepancy Search. Proceedings of IJCAI 1995.