Search-03d — Weighted A* : recherche à sous-optimalité bornée

Partie 3 — Recherche avancée. Ce notebook complète le triptyque de la Partie 3 sur la question « l’heuristique ne suffit pas à résoudre à l’optimum ». Là où Search-03b renforce l’heuristique (PDB) et Search-03c borne les écarts (LDS) — toutes deux en gardant l’optimalité — voici la troisième réponse : renoncer (partiellement) à l’optimalité pour gagner en vitesse, mais de façon contrôlée.

1. L’idée : payer l’optimalité pour acheter de la vitesse

Search-3 (Informed) a posé le compromis fondateur : A* (heuristique consistante pour la variante sans ré-ouverture) est optimal mais peut explorer beaucoup de nœuds ; Greedy (sans g) est rapide mais peut renvoyer une solution carrément mauvaise. Entre l’optimalité chère et la gloutonnerie aveugle, existe-t-il un juste milieu garanti ?

Weighted A* (Pohl, 1970) répond oui. On garde la structure d’A*, mais on inflate l’heuristique par un facteur \(W \geq 1\) :

\[f(n) = g(n) + W \cdot h(n)\]

  • \(W = 1\) : on retrouve A* (optimal, mais explore beaucoup).
  • \(W \to \infty\) : on tend vers Greedy (rapide, mais sous-optimal sans garantie).
  • \(1 < W < \infty\) : Weighted A*, qui explore bien moins de nœuds qu’A* tout en garantissant une solution de coût au pire \(W\) fois l’optimal (sous-optimalité bornée par \(W\)).

C’est le compromis « bon citizen » : on sait exactement jusqu’où on dérive de l’optimum, et on l’échange contre un gain de nœuds qui peut être de plusieurs ordres de grandeur.

2. Le banc d’essai : cheminement sur un terrain pondéré

Pour mettre Weighted A* en valeur, il faut un problème où A* explore beaucoup (où l’optimalité coûte de nombreux nœuds) et où le compromis vitesse/qualité est net : un terrain pondéré (routes rapides, herbe lente, marécages quasi-impraticables, murs). Sur un graphe à coût uniforme, A* dégenère en BFS et Weighted A* n’apporte rien (cf la leçon « problème dégénéré ») — il faut des coûts contrastés pour que l’heuristique et l’inflation discriminent.

import heapq
import random
from itertools import product

# --- Terrain pondere : chaque case a un cout de traversee ---
# 1 = route (rapide), 3 = herbe, 8 = marécage, '#' = mur infranchissable.
# Coûts CONTRASTES -> A* explore beaucoup, Greedy se trompe (non-dégenéré).
TERRAIN_COST = {".": 1, "g": 3, "s": 8, "#": None}   # s = swamp, g = grass

def make_grid(rows, cols, seed=42):
    rng = random.Random(seed)
    grid = {}
    for r, c in product(range(rows), range(cols)):
        x = rng.random()
        if x < 0.15:
            grid[(r, c)] = "#"          # mur (15%)
        elif x < 0.45:
            grid[(r, c)] = "g"          # herbe (30%)
        elif x < 0.60:
            grid[(r, c)] = "s"          # marécage (15%)
        else:
            grid[(r, c)] = "."          # route (40%)
    # garantir départ + arrivée franchissables
    start, goal = (0, 0), (rows - 1, cols - 1)
    grid[start], grid[goal] = ".", "."
    return grid

ROWS, COLS = 25, 25
grid = make_grid(ROWS, COLS, seed=42)
start, goal = (0, 0), (ROWS - 1, COLS - 1)

def step_cost(grid, cur, nxt):
    t = grid.get(nxt, "#")
    return TERRAIN_COST.get(t)          # None si mur

def neighbors(grid, s):
    r, c = s
    out = []
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        n = (r + dr, c + dc)
        if 0 <= n[0] < ROWS and 0 <= n[1] < COLS and step_cost(grid, s, n) is not None:
            out.append(n)
    return out

# Heuristique : Manhattan (admissible : min cost = 1, distance >= Manhattan*1).
def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

n_walls = sum(1 for v in grid.values() if v == "#")
print(f"Grille {ROWS}x{COLS} : {n_walls} murs ({100*n_walls/(ROWS*COLS):.0f}%), "
      f"départ {start}, but {goal}.")
print("Coûts contrastés (route=1, herbe=3, marécage=8) -> A* va explorer, "
      "Greedy va se tromper : terrain non-dégénéré.")
Grille 25x25 : 90 murs (14%), départ (0, 0), but (24, 24).
Coûts contrastés (route=1, herbe=3, marécage=8) -> A* va explorer, Greedy va se tromper : terrain non-dégénéré.

3. A*, Greedy, et Weighted A* : un seul algorithme paramétré

Les algorithmes se ramènent à un même best-first search sur \(f(n) = g(n) + W \cdot h(n)\) : le poids \(W\) de l’heuristique est le seul paramètre. \(W=1\) → A* (optimal) ; \(W>1\) → Weighted A* (sous-optimalité bornée par \(W\)) ; \(W \to \infty\) → Greedy (l’heuristique domine, \(g\) devient négligeable). À noter : \(W=0\) donne \(f=g\), c’est-à-dire Dijkstra/UCS (optimal mais aveugle à l’heuristique) — pas Greedy ; le vrai Greedy (\(f=h\), \(g\) ignoré) est traité à part comme pôle non borné. On instrumente le nombre de nœuds développés (coût de la recherche) et le coût de la solution trouvée (sa qualité).

def best_first(grid, start, goal, W, h=manhattan):
    # f(n) = g(n) + W*h(n). W=1 -> A* ; W>1 -> Weighted A* (borne W).
    g = {start: 0}
    parent = {start: None}
    open_h = [(W * h(start, goal), start)]      # file de priorité sur f
    developed = 0
    while open_h:
        _, cur = heapq.heappop(open_h)
        developed += 1
        if cur == goal:
            # reconstruire le chemin
            path = []
            while cur is not None:
                path.append(cur)
                cur = parent[cur]
            return list(reversed(path)), g[goal], developed
        for nxt in neighbors(grid, cur):
            nc = g[cur] + step_cost(grid, cur, nxt)
            if nxt not in g or nc < g[nxt]:
                g[nxt] = nc
                parent[nxt] = cur
                heapq.heappush(open_h, (nc + W * h(nxt, goal), nxt))
    return None, float("inf"), developed     # pas de chemin

# Vrai Greedy best-first (f = h uniquement, g ignore) : le pole NON BORNE.
# On garde g pour reconstruire le chemin et mesurer son cout reel.
def true_greedy(grid, start, goal, h=manhattan):
    g = {start: 0}; parent = {start: None}
    open_h = [(h(start, goal), start)]
    developed = 0; seen = set()
    while open_h:
        _, cur = heapq.heappop(open_h); developed += 1
        if cur in seen: continue
        seen.add(cur)
        if cur == goal:
            path = []
            while cur is not None: path.append(cur); cur = parent[cur]
            return list(reversed(path)), g[goal], developed
        for nxt in neighbors(grid, cur):
            nc = g[cur] + step_cost(grid, cur, nxt)
            if nxt not in g or nc < g[nxt]:
                g[nxt] = nc; parent[nxt] = cur
                heapq.heappush(open_h, (h(nxt, goal), nxt))   # f = h seulement
    return None, float("inf"), developed

# Repères : A* (W=1) = référence optimale ; Greedy (f=h) = pôle rapide non borné.
astar_path, astar_cost, astar_nodes = best_first(grid, start, goal, W=1)
greedy_path, greedy_cost, greedy_nodes = true_greedy(grid, start, goal)
print(f"A*     (W=1, optimal)   : coût = {astar_cost:3d} | nœuds développés = {astar_nodes}")
print(f"Greedy (f=h, non borné) : coût = {greedy_cost:3d} | nœuds développés = {greedy_nodes}"
      f"  (ratio = {greedy_cost/astar_cost:.2f}× optimal, AUCUNE borne)")
optimal = astar_cost   # A* admissible -> référence d'optimalité
print(f"\nRéférence d'optimalité (A* admissible) : {optimal}.")
A*     (W=1, optimal)   : coût =  78 | nœuds développés = 472
Greedy (f=h, non borné) : coût = 143 | nœuds développés = 60  (ratio = 1.83× optimal, AUCUNE borne)

Référence d'optimalité (A* admissible) : 78.

4. Le balayage de \(W\) : la frontière coût/nœuds

Faisons varier \(W\) de 1 (A* optimal) à de grandes valeurs (proche Greedy). À chaque \(W\), on mesure le coût de la solution et le nombre de nœuds développés. La promesse de Weighted A* est double, et on la vérifie honnêtement :

  1. Vitesse — à mesure que \(W\) croît, le nombre de nœuds chute.
  2. Garantie — le coût de la solution reste \(\leq W \cdot \text{optimal}\) (Pohl 1970).
# Balayage de W >= 1 (le régime Weighted A*) : A* (W=1) -> de plus en plus "confiant".
# Greedy (f=h, pôle non borné) a déjà été mesuré ci-dessus ; ici on explore la BORNE W.
weights = [1.0, 1.5, 2.0, 3.0, 5.0, 8.0, 12.0]
print(f"{'W':>5} | {'coût':>5} | {'ratio/opt':>9} | {'borne W':>7} | {'nœuds':>6} | {'% A*':>6} | garantie?")
print("-" * 66)
rows = []
for W in weights:
    path, cost, nodes = best_first(grid, start, goal, W=W)
    ratio = cost / optimal
    pct = 100.0 * nodes / astar_nodes
    garantit = "OUI" if cost <= W * optimal + 1e-9 else "NON"
    print(f"{W:5.1f} | {cost:5d} | {ratio:9.3f} | {W:7.2f} | {nodes:6d} | {pct:5.1f}% | {garantit}")
    rows.append((W, cost, ratio, nodes, pct))
    W |  coût | ratio/opt | borne W |  nœuds |   % A* | garantie?
------------------------------------------------------------------
  1.0 |    78 |     1.000 |    1.00 |    472 | 100.0% | OUI
  1.5 |    78 |     1.000 |    1.50 |    162 |  34.3% | OUI
  2.0 |    78 |     1.000 |    2.00 |     80 |  16.9% | OUI
  3.0 |    89 |     1.141 |    3.00 |     57 |  12.1% | OUI
  5.0 |    89 |     1.141 |    5.00 |     55 |  11.7% | OUI
  8.0 |   104 |     1.333 |    8.00 |     52 |  11.0% | OUI
 12.0 |   104 |     1.333 |   12.00 |     52 |  11.0% | OUI
# Visualisation ASCII : le chemin trouvé par A* (W=1) vs Weighted A* (W=3) vs Greedy (W=0).
def render(grid, path):
    sym = {".": ".", "g": ",", "s": "~", "#": "#"}
    cells_map = {s: sym[t] for s, t in grid.items()}
    for s in path:
        cells_map[s] = "@"        # le chemin
    cells_map[start] = "S"; cells_map[goal] = "G"
    lines = []
    for r in range(ROWS):
        lines.append("".join(cells_map[(r, c)] for c in range(COLS)))
    return "\n".join(lines)

wa3_path, _, _ = best_first(grid, start, goal, W=3.0)
print("Légende : S départ · G but · @ chemin · . route · , herbe · ~ marécage · # mur\n")
print("=== A* (W=1, optimal) ===")
print(render(grid, astar_path))
print("\n=== Weighted A* (W=3) ===")
print(render(grid, wa3_path))
Légende : S départ · G but · @ chemin · . route · , herbe · ~ marécage · # mur

=== A* (W=1, optimal) ===
S#,,...#,#,~#,.~,~.#..,,.
@##....~.,~...~.#,,#,#,.,
@@,...,.,,..~...,#,,,..,.
,@~,,~,~.,,.~###..,#,.~..
#@@~,.#,~..,~,..,..,.~.~#
,#@..,#..#~#..#~~,.,,~.,,
..@~#,,~,,#.,..#,.,#.~~..
,#@,~...#,,.,,,,,,.,.~#..
..@,~,,#,.,.~,..~.,,.~~.#
~~@@@#,~.,#.,~.,~~.,.,,.,
,.#~@@#,,...,,.....#.,..#
##~,.@@@,~..#,,#..,.~,##.
.~.~##,@@@@,,#..,.,.....#
.,....,.#.@@@~,.,#,,..,.,
.~.#.,.,#,.,@~,~,.#.~...,
#.,,..,,,,,#@@@@@,~#,,~.~
,,~..,#~.,...,,#@~.#,.,.~
,.#..#,,.~#,.~..@~@@@.~.~
..~,,..~.,#,,,~#@@@#@~,,,
.~...,#,...,.~.,,,#,@,,~#
.#,~#.#~#,,,.,..,##~@@@@.
..,#,#.~,..,..#..##,..,@#
..#...#..,,,~,..#....,.@@
.~~,.,..#.,~.,#.,,.,..,#@
#.~...~.#,.,~~~,.,.,,#,#G

=== Weighted A* (W=3) ===
S#,,...#,#,~#,.~,~.#..,,.
@##....~.,~...~.#,,#,#,.,
@@,...,.,,..~...,#,,,..,.
,@~,,~,~.,,.~###..,#,.~..
#@@~,.#,~..,~,..,..,.~.~#
,#@@@@#..#~#..#~~,.,,~.,,
..,~#@,~,,#.,..#,.,#.~~..
,#,,~@@.#,,.,,,,,,.,.~#..
...,~,@#,.,.~,..~.,,.~~.#
~~.,.#@@@@#.,~.,~~.,.,,.,
,.#~..#,,@@@,,.....#.,..#
##~,..,.,~.@#,,#..,.~,##.
.~.~##,....@@#..,.,.....#
.,....,.#..,@~,.,#,,..,.,
.~.#.,.,#,.,@~,~,.#.~...,
#.,,..,,,,,#@@@@@,~#,,~.~
,,~..,#~.,...,,#@~.#,.,.~
,.#..#,,.~#,.~..@~@@@.~.~
..~,,..~.,#,,,~#@@@#@~,,,
.~...,#,...,.~.,,,#,@,,~#
.#,~#.#~#,,,.,..,##~@,...
..,#,#.~,..,..#..##,@@@@#
..#...#..,,,~,..#....,.@@
.~~,.,..#.,~.,#.,,.,..,#@
#.~...~.#,.,~~~,.,.,,#,#G

Lecture du résultat

Les repères et le balayage encadrent le compromis structurel de Weighted A* par ses deux pôles, puis l’interpolation bornée entre les deux :

  • Greedy (f=h) — pôle rapide, NON borné. Seulement 60 nœuds, mais un coût de 143 (1,83× l’optimal). Greedy « fonce » vers le but : parfois il tombe juste, parfois (comme ici) très mal — on n’a aucune garantie sur sa dérive, qui peut être arbitraire.
  • A* (W=1) — pôle optimal, cher. Coût 78 (optimal garanti), mais 472 nœuds : c’est le prix de l’optimalité stricte, A* explore largement autour du chemin pour prouver qu’aucun meilleur n’existe.
  • Weighted A* (1 < W) — l’interpolation bornée. C’est tout l’intérêt : à \(W=2\), on retrouve le coût optimal (78) en ne développant que 80 nœuds (17 % d’A*) — un gain quasi gratuit. À \(W=3\), 57 nœuds (12 %) pour un coût 89 (1,14× l’optimal). La colonne « garantie » confirme partout : \(\text{coût} \leq W \cdot \text{optimal}\).

La frontière de Pareto se lit ainsi : choisir \(W\), c’est choisir un point sur la courbe coût/nœuds. Un \(W\) modeste (\(2\) à \(3\)) capture l’essentiel du gain de vitesse pour une dérive qualité négligeable — tandis que Greedy, lui, abandonne toute borne sur la sienne.

La carte ASCII montre l’effet visuel : A* (\(W=1\)) contourne méthodiquement les zones coûteuses (chemin optimal), tandis que Weighted A* (\(W=3\)) « coupe » à travers des cases un peu plus chères pour aller plus droit — un chemin légèrement plus cher (89 vs 78), trouvé en développant 8 fois moins de nœuds (57 vs 472).

5. Pourquoi ça marche : la garantie de sous-optimalité bornée

La garantie \(\text{coût} \leq W \cdot \text{optimal}\) repose sur une idée simple. En gonflant l’heuristique par \(W\), on rend la recherche plus confiante dans l’estimation \(h\) : elle « fonce » vers le but en s’autorisant à développer moins de nœuds latéraux. Le prix de cette confiance est qu’on peut manquer le chemin optimal — mais le facteur d’inflation \(W\) borne exactement de combien on peut dévier.

Formellement (Pohl 1970) : si \(h\) est admissible (\(h \leq h^*\), vrai coût), alors la solution de Weighted A* avec facteur \(W\) a un coût au plus \(W \cdot C^*\), où \(C^*\) est le coût optimal. La preuve suit la même structure que l’optimalité d’A* : au moment où le but est développé, son \(f\)-valeur est bornée par \(W \cdot C^*\) via les nœuds sur le chemin optimal, dont l’\(f\) gonflé reste sous ce seuil.

Conséquences pratiques : - Choisir \(W\), c’est choisir le budget d’erreur acceptable. Si on tolère une solution 10 % trop chère, \(W = 1{,}1\) suffit — souvent avec un gain de nœuds déjà notable. - L’heuristique doit rester admissible. Gonfler une heuristique déjà inadmissible n’offre plus de garantie — Weighted A* suppose un \(h\) honnête qu’on choisit de sur-pondérer. - Anytime — on peut démarrer avec un grand \(W\) (solution rapide, grossière) puis le réduire progressivement en réutilisant la recherche, pour raffiner vers l’optimal (Anytime Repairing A*, Likhachev 2003 — exercice 3).

6. Ponts avec le reste de la série

Direction Lien Relation
↔︎ Search-03b Search-03b — Pattern Databases Autre réponse à « l’optimum est dur » : renforcer l’heuristique (rester optimal) vs ici relâcher l’optimalité
↔︎ Search-03c Search-03c — Limited Discrepancy Search LDS borne les écarts à l’heuristique (rester optimal) ; Weighted A* relâche l’optimalité — deux axes orthogonaux
← Partie 1 Search-3 — Informed A*, admissibilité, Greedy : les deux extrémités (\(W=1\) et \(W=0\)) que Weighted A* interpole
→ Partie 4 Métaheuristiques Weighted A* garde une borne sur la qualité ; les métaheuristiques l’abandonnent totalement

Triptyque de la Partie 3 — trois réponses à « l’heuristique ne suffit pas à résoudre à l’optimum » : renforcer l’heuristique (Search-03b, PDB), borner les écarts (Search-03c, LDS), relâcher l’optimalité (Search-03d, Weighted A*).

Référence fondatrice : Pohl, I. (1970) — Heuristic Search Viewed as Path Finding in a Graph, Artificial Intelligence 1(3-4). Première formalisation de Weighted A* et de sa garantie de sous-optimalité bornée par le facteur d’inflation \(W\).

7. Exercices

Exercice 1 : courbe de Pareto coût/nœuds

Tracez (ou affichez en ASCII) la frontière de Pareto : en abscisse le nombre de nœuds développés, en ordonnée le ratio coût/optimal, un point par valeur de \(W \in [1, 12]\). Identifiez le « genou » (knee) — la valeur de \(W\) au-delà de laquelle gagner encore en vitesse coûte cher en qualité. - Indice : le genou est typiquement autour de \(W \in [2, 3]\). Justifiez pourquoi l’utilité marginale d’augmenter \(W\) décroît (les nœuds économisés s’amenuisent, la dérive quality s’accumule).

# Exercice 1 a completer
# Conseil : reprenez le balayage ci-dessus (weights plus fin, ex. [1, 1.2, 1.5, 2, 2.5, 3, 4, 6, 9, 12]),
# collectez (nodes, ratio) pour chaque W, et repérez le "genou" de la frontière de Pareto.
print("Exercice 1 a completer")
Exercice 1 a completer

Exercice 2 : sensibilité à l’heuristique (admissible vs inadmissible)

Refaitez le balayage de \(W\) avec une heuristique inadmissible (par ex. Manhattan sans tenir compte du coût minimal : ou \(h\) sur-estimé d’un facteur 2 dès le départ). Vérifiez que la garantie \(\text{coût} \leq W \cdot \text{optimal}\) est alors violée. - Indice : la garantie suppose \(h\) admissible. Avec un \(h\) déjà inadmissible, l’inflation par \(W\) aggrave la triche et la borne n’a plus de raison de tenir. C’est pourquoi Weighted A* part toujours d’une heuristique honnête.

# Exercice 2 a completer
# Conseil : définissez h_bad(s) = 2*manhattan(s, goal) (inadmissible), relancez le balayage,
# et cherchez un W où cost > W*optimal (garantie violée).
print("Exercice 2 a completer")
Exercice 2 a completer

Exercice 3 : Anytime Repairing A* (ARA*)

Implémentez une version anytime : démarrez avec un grand \(W_0\) (solution rapide), puis décrémentez \(W\) par petits pas en réutilisant la liste OPEN déjà construite, jusqu’à \(W=1\) (solution optimale). À chaque étape, affichez le coût courant et le temps écoulé — l’utilisateur peut s’arrêter quand il est satisfait. - Indice : ARA* (Likhachev, Gordon & Thrun, 2003) réutilise l’OPEN en mettant juste à jour les clés \(f = g + W \cdot h\) quand \(W\) change, sans tout recalculer. L’intérêt : une solution immédiate qui s’améliore avec le budget temps. C’est l’usage typique de Weighted A* en robotique (planification de mouvement sous contrainte temps-réel).

# Exercice 3 a completer
# Conseil : boucle W = W0, W0-step, ... 1. À chaque W, re-triez l'OPEN existante par la
# nouvelle clé f=g+W*h (ou réinsérez), développez jusqu'au but, affichez (W, coût, t).
print("Exercice 3 a completer")
Exercice 3 a completer

Conclusion

Weighted A* referme le triptyque de la Partie 3. Face à un problème où A* optimal explore trop de nœuds, on dispose de trois leviers : renforcer l’heuristique (Search-03b, PDB), borner les écarts à l’heuristique (Search-03c, LDS) — qui préservent l’optimalité — ou, sujet de ce notebook, relâcher l’optimalité de façon contrôlée (Weighted A*). Ce troisième levier est le plus radical et souvent le plus efficace en pratique : on accepte une solution au plus \(W\) fois l’optimal, et on gagne en échange un facteur de nœuds qui peut être énorme.

La leçon générale est un compromis explicite qualité/vitesse : contrairement à Greedy (dérive non bornée) ou aux métaheuristiques de la Partie 4 (aucune garantie), Weighted A* offre une borne de qualité paramétrable. Choisir \(W\), c’est choisir son budget d’erreur — un compromis honnête, quantitatif, et qui se raffine en anytime (ARA*) quand on veut se rapprocher de l’optimal avec le temps restant.

Au-delà : Weighted A* est la brique de base de la planification sous contrainte temps-réel (robotique, jeux vidéo) et se combine aux PDB (heuristique forte ET relâchée) et au branch-and-bound borné. C’est le point où la série bascule de « garantir l’optimal » à « garantir une qualité calculable » — justo avant que la Partie 4 n’abandonne toute garantie.

Retour au sommet