Search-03c — Recherche à écart limité (Limited Discrepancy Search)

Partie 3 — Recherche avancée. Ce notebook prolonge la Partie 3 : techniques de recherche heuristique avancées, au-delà des fondations de la Partie 1 (A\, IDA\, heuristiques admissibles). Là où Search-03b fabriquait une heuristique assez informée pour résoudre à l’optimum par précalcul, ici nous partons d’une heuristique déjà bonne mais imparfaite et demandons : comment trouver l’optimum sans explorer tout l’arbre ?

1. L’idée : une bonne heuristique se trompe peu

La recherche exhaustive (DFS sur tout l’arbre) trouve l’optimum mais coûte \(2^n\) feuilles — prohibitif. La stratégie greedy (suivre aveuglément la recommandation de l’heuristique) est instantanée mais myope : elle se contente du premier chemin, parfois sous-optimal. Entre ces deux extrêmes, Limited Discrepancy Search (Harvey & Ginsberg, 1995) exploite une intuition forte :

Si l’heuristique est bonne, la solution optimale s’écarte de peu de ses recommandations.

Un écart (discrepancy) est, à un nœud, le choix d’un enfant que l’heuristique ne recommande pas en premier (rang > 0). LDS(k) énumère exactement les chemins comportant au plus k écarts : à k=0 c’est le greedy ; à k croissant on élargit progressivement le voisinage du chemin greedy, sans jamais payer le coût exponentiel de la DFS complète. C’est l’incarnation algorithmique du principe « l’optimum est un voisin du greedy ».

2. Le problème-banc d’essai : le sac à dos 0/1

Le sac à dos binaire (0/1 knapsack) est NP-diff 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 \(C\) — en décidant, pour chaque objet, de le prendre ou de le laisser. C’est un arbre de décision binaire de profondeur \(n\).

L’heuristique gloutonne canonique ordonne les objets par ratio valeur/poids décroissant et, à chaque nœud, recommande de prendre l’objet courant s’il rentre. Cette heuristique est bonne (les objets à fort ratio sont rarement un mauvais choix) mais imparfaite : un objet à ratio élevé peut en bloquer deux de ratio moyen dont la somme dépasse sa valeur — auquel cas le greedy se trompe.

# Le sac a dos 0/1 : liste d'objets (nom, poids, valeur), ordonnes par RATIO valeur/poids decroissant
# (c'est l'ordre ou l'heuristique gloutonne les considere).
items = [
    ("A", 6, 8),   # ratio 1.33  <-- top ratio, MAIS poids 6 bloque la paire B+C (valeur 12 > 10)
    ("B", 5, 6),   # ratio 1.20
    ("C", 5, 6),   # ratio 1.20
    ("D", 4, 2),   # ratio 0.50
    ("E", 3, 1),   # ratio 0.33
    ("F", 2, 0),   # ratio 0.00  (objet de valeur nulle -- piege pour le greedy s'il reste de la place)
    ("G", 1, 0),   # ratio 0.00  (objet de valeur nulle -- piege pour le greedy)
]
CAPACITY = 10

# Verifions l'ordre par ratio (l'heuristique suppose cet ordre).
ratios = [(name, v / w if w > 0 else float("inf")) for name, w, v in items]
print("Objets dans l'ordre heuristique (ratio v/w decroissant) :")
for name, r in ratios:
    print(f"  {name}: ratio = {r:.3f}")
print(f"Capacite C = {CAPACITY}")

Objets dans l'ordre heuristique (ratio v/w decroissant) :
  A: ratio = 1.333
  B: ratio = 1.200
  C: ratio = 1.200
  D: ratio = 0.500
  E: ratio = 0.333
  F: ratio = 0.000
  G: ratio = 0.000
Capacite C = 10

# StratEGIE GLOUTONNE (k=0) : suivre l'heuristique aveuglement -- prendre chaque objet s'il rentre.
def greedy_knapsack(items, capacity):
    selection, total_w, total_v = [], 0, 0
    for name, w, v in items:
        if total_w + w <= capacity:        # heuristique : prendre si ca rentre
            selection.append(name)
            total_w += w
            total_v += v
    return total_v, selection, "greedy"

gv, gsel, _ = greedy_knapsack(items, CAPACITY)
print(f"Greedy (k=0) : valeur = {gv}, selection = {gsel}")
print("--> Le greedy prend A (poids 6, valeur 8), puis il ne reste que 4 de capacite :")
print("    seul D (poids 4) y rentre. Greedy = {A, D} = 10. La paire B+C (valeur 12) est bloquee par A.")

Greedy (k=0) : valeur = 10, selection = ['A', 'D']
--> Le greedy prend A (poids 6, valeur 8), puis il ne reste que 4 de capacite :
    seul D (poids 4) y rentre. Greedy = {A, D} = 10. La paire B+C (valeur 12) est bloquee par A.

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 (recommande), rang 1 = laisser (1 ecart).
Objet non prenable (trop lourd) : rang 0 = laisser (seule option realisable).

LDS(k) descend en privilégiant l’action recommandée, et n’emprunte une branche « contraire » que si le budget d’écarts k n’est pas épuisé. Elle énumère ainsi tous les chemins à au plus k écarts, et retient la meilleure valeur rencontrée.

def lds_knapsack(items, capacity, k_max):
    # LDS(k_max) sur le sac a dos 0/1.
    # items : liste (nom, poids, valeur), ordre heuristique (meilleur ratio d'abord).
    # Renvoie (meilleure valeur, meilleure selection, nombre de noeuds explores).
    n = len(items)
    best = {"value": -1, "sel": None}
    nodes = [0]

    def rec(i, rem_cap, val_so_far, sel, disc):
        nodes[0] += 1
        if i == n:                                   # feuille : on enregistre une solution
            if val_so_far > best["value"]:
                best["value"] = val_so_far
                best["sel"] = list(sel)
            return
        name, w, v = items[i]
        can_take = w <= rem_cap
        if can_take:
            # Rang 0 (recommande) : PRENDRE -- n'epargne aucun ecart.
            sel.append(name)
            rec(i + 1, rem_cap - w, val_so_far + v, sel, disc)
            sel.pop()
            # Rang 1 (contraire) : LAISSER -- coute 1 ecart, si budget reste.
            if disc < k_max:
                rec(i + 1, rem_cap, val_so_far, sel, disc + 1)
        else:
            # Objet trop lourd : seule action realisable = laisser (rang 0, sans ecart).
            rec(i + 1, rem_cap, val_so_far, sel, disc)

    rec(0, capacity, 0, [], 0)
    return best["value"], best["sel"], nodes[0]


# Balayage k = 0, 1, 2, ... : a chaque increment on elargit le voisinage du greedy.
print("k | valeur | selection        | nœuds explores")
print("--|--------|-----------------|----------------")
for k in range(len(items) + 1):
    val, sel, nd = lds_knapsack(items, CAPACITY, k)
    print(f"{k} | {val:6d} | {str(sel):15s} | {nd}")

k | valeur | selection        | nœuds explores
--|--------|-----------------|----------------
0 |     10 | ['A', 'D']      | 8
1 |     12 | ['B', 'C']      | 19
2 |     12 | ['B', 'C']      | 34
3 |     12 | ['B', 'C']      | 52
4 |     12 | ['B', 'C']      | 73
5 |     12 | ['B', 'C']      | 91
6 |     12 | ['B', 'C']      | 98
7 |     12 | ['B', 'C']      | 99

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) puis par programmation dynamique. LDS devra converger vers cette valeur à mesure que \(k\) croît — idéalement pour un \(k\) petit, bien avant l’énumération complète.

from itertools import product

def exhaustive_knapsack(items, capacity):
    # Optimum exact par enumeration exhaustive (2^n) -- reference de verite.
    n = len(items)
    best_v, best_sel, nodes = -1, None, 0
    for bits in product([0, 1], repeat=n):          # 2^n combinaisons
        nodes += 1
        w = sum(items[i][1] for i in range(n) if bits[i])
        v = sum(items[i][2] for i in range(n) if bits[i])
        if w <= capacity and v > best_v:
            best_v, best_sel = v, [items[i][0] for i in range(n) if bits[i]]
    return best_v, best_sel, nodes


def dp_knapsack(items, capacity):
    # Optimum exact par programmation dynamique (pseudo-polynomial) -- 2e reference.
    n = len(items)
    # dp[c] = meilleure valeur avec capacite c
    dp = [0] * (capacity + 1)
    keep = [[False] * (capacity + 1) for _ in range(n)]
    for i in range(n):
        name, w, v = items[i]
        for c in range(capacity, w - 1, -1):
            if dp[c - w] + v > dp[c]:
                dp[c] = dp[c - w] + v
                keep[i][c] = True
    # Reconstruction de la selection
    sel, c = [], capacity
    for i in range(n - 1, -1, -1):
        if keep[i][c]:
            sel.append(items[i][0])
            c -= items[i][1]
    return dp[capacity], list(reversed(sel))


opt_v, opt_sel, ex_nodes = exhaustive_knapsack(items, CAPACITY)
dp_v, dp_sel = dp_knapsack(items, CAPACITY)
print(f"Optimum (exhaustif, 2^{len(items)} = {2**len(items)} feuilles) : valeur = {opt_v}, selection = {opt_sel}")
print(f"Optimum (DP)                                         : valeur = {dp_v}, selection = {dp_sel}")
print(f"nœuds explores par l'exhaustif : {ex_nodes}")

Optimum (exhaustif, 2^7 = 128 feuilles) : valeur = 12, selection = ['B', 'C']
Optimum (DP)                                         : valeur = 12, selection = ['B', 'C']
nœuds explores par l'exhaustif : 128

# Tableau comparatif : greedy vs LDS(k) vs exhaustif -- QUALITE de solution et COUT (nœuds).
print(f"{'strategie':<18}{'valeur':>8}{'optimal?':>11}{'nœuds':>10}{'% exhaustif':>14}")
print("-" * 61)
ex_total = ex_nodes

def row(label, val, nd):
    opt = "OUI" if val == opt_v else "non"
    pct = 100.0 * nd / ex_total if ex_total else 0
    print(f"{label:<18}{val:>8}{opt:>11}{nd:>10}{pct:>13.1f}%")

gv, _, _ = greedy_knapsack(items, CAPACITY)
row("greedy (k=0)", gv, len(items) + 1)
for k in range(len(items) + 1):
    val, _, nd = lds_knapsack(items, CAPACITY, k)
    row(f"LDS(k={k})", val, nd)
row("exhaustif (ref)", opt_v, ex_total)

strategie           valeur   optimal?     nœuds   % exhaustif
-------------------------------------------------------------
greedy (k=0)            10        non         8          6.2%
LDS(k=0)                10        non         8          6.2%
LDS(k=1)                12        OUI        19         14.8%
LDS(k=2)                12        OUI        34         26.6%
LDS(k=3)                12        OUI        52         40.6%
LDS(k=4)                12        OUI        73         57.0%
LDS(k=5)                12        OUI        91         71.1%
LDS(k=6)                12        OUI        98         76.6%
LDS(k=7)                12        OUI        99         77.3%
exhaustif (ref)         12        OUI       128        100.0%

Lecture du résultat

Le greedy (k=0) est sous-optimal (valeur 10, sélection {A, D}) : 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} = 12 — pour 19 nœuds seulement, soit 14,8 % des 128 feuilles de l’exhaustif \(2^7\).

Au-delà du \(k\) suffisant, LDS continue d’explorer mais ne trouve rien de meilleur (l’optimum est déjà atteint, la valeur stagne à 12 de k=1 à k=7) : c’est le signal pour arrêter. C’est précisément ce qu’exploite Iterative LDS (exercice 1) : incrémenter \(k\) jusqu’à ce que la valeur cesse de croître, sans jamais payer le \(2^n\) de l’exhaustif. La leçon générale tient en une phrase : quand l’heuristique est bonne, l’optimum est un proche voisin du greedy, et LDS le trouve en bornant les écarts plutôt qu’en énumérant l’arbre entier.

5. Ponts avec le reste de la série

Direction	Lien	Relation
← Fondations	Search-3 — Informed	A\, heuristiques admissibles — LDS suppose une heuristique ordonnante* (qui range les enfants), notion voisine
↔︎ Search-03b	Search-03b — Pattern Databases	Autre voie avancée : renforcer l’heuristique (PDB) plutôt que borner les écarts (LDS). Deux réponses à « l’heuristique ne suffit pas »
→ Partie 4	Métaheuristiques	LDS garde l’exigence d’optimalité (la trouve pour k assez grand) ; les métaheuristiques l’abandonnent

Référence fondatrice : Harvey, W. D., & Ginsberg, M. L. (1995) — Limited Discrepancy Search, Proceedings of IJCAI. L’article qui formalise le principe « l’optimum est un voisin du greedy » et l’algorithme LDS(k).

6. Exercices

Exercice 1 : Iterative LDS (ILDS)

Implémentez ILDS : exécutez LDS pour k=0, 1, 2, … en vous arrêtant dès que la valeur stagne (deux increments 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 naturel est « la valeur n’a pas augmenté au pas k » (l’optimum est trouvé). Attention : stagnation ponctuelle ≠ optimum assuré tant que k < n — justifiez votre critère d’arrêt. - Objectif : mesurer le gain (ratio des nœuds ILDS / exhaustif).

# Exercice 1 a completer
# Conseil : bouclez k = 0..n, accumulez les nœuds, arretez quand la valeur cesse de croitre.
# Comparez le total accumule a ex_nodes (l'exhaustif calcule ci-dessus).
total_nodes_ilds = 0
print("Exercice 1 a completer")

Exercice 1 a completer

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). 2. Le ratio de nœuds LDS(k*) / exhaustif (\(2^{18} = 262\,144\) feuilles). - Indice : pour n=18 l’exhaustif est encore calculable ( DP ou 2^18) et sert de référence. Observez comment le ratio de nœuds se dégrade quand l’heuristique est mauvaise (ratio aléatoire) vs bonne (vraie valeur/poids).

# Exercice 2 a completer
# Conseil : genere n=18 objets avec des (poids, valeur) aleatoires, calcule l'optimum par DP,
# puis balaye k jusqu'a l'atteindre. Affiche le ratio LDS(k*)/2**18.
print("Exercice 2 a completer")

Exercice 2 a completer

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 l’optimum s’écarte du greedy, donc plus le k nécessaire est grand — LDS y perd son avantage. C’est la limite du paradigme : LDS n’est efficace que si l’heuristique est effectivement bonne.

# Exercice 3 a completer
# Conseil : permutez `items` selon differents ordres, et pour chacun cherchez le k min.
# Perturbation : essayez random.shuffle(items) (avec une graine fixee pour la reproductibilite).
print("Exercice 3 a completer")

Exercice 3 a completer

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 (choix contraires à la recommandation), elle trouve l’optimum pour un coût bien inférieur à \(2^n\), sans renoncer à l’optimalité (contrairement aux métaheuristiques de la Partie 4).

La limite est symétrique du avantage : LDS n’est efficace que dans la mesure où l’heuristique est effectivement bonne — une heuristique mauvaise repousse l’optimum loin du greedy, et le \(k\) nécessaire devient si grand que l’énumération bornée rejoint l’exhaustive (exercice 3). C’est un algorithme qui parie sur la qualité de l’heuristique, et qui gagne ce pari précisément quand les Pattern Databases de Search-03b ont déjà fait leur travail de renforcement heuristique : les deux notebooks sont complémentaires — l’un fabrique une meilleure heuristique, l’autre exploite au mieux celle dont on dispose.

Prochaines étapes : LDS se généralise en ILDS (itération sur k) et se combine avec le beam search et l’élagage par borne (branch-and-bound). Elle s’applique à tout arbre de recherche muni d’une heuristique ordonnante : ordonnancement, planification, satisfaction de contraintes.

Retour au sommet