L'heuristique qui ment

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 14 — Plus courts chemins : Dijkstra et au-delà

Énoncé

Construire un exemple de grille comportant des obstacles pour lequel une heuristique surestimée ( $h^{'} = 3 \times$ Manhattan) produit un chemin final sous-optimal.

Corrigé

Soit une grille comportant un mur formant un obstacle direct sur le chemin.

L'algorithme guidé par $h^{'}$ fonce vers le mur car cela réduit drastiquement l'heuristique $h^{'}$ .
Bloqué par l'obstacle, il doit faire un contournement coûteux.
Pour rebrousser chemin et explorer l'autre voie (la voie optimale de départ), la valeur de la priorité $f$ de cette autre voie est artificiellement très élevée en raison du coefficient multiplicateur 3 appliqué à $h^{'}$ .
L'algorithme valide la cible en sortie d'impasse et fournit un chemin final sous-optimal (ex: longueur 10 vs 8 pour le chemin réel), illustrant la nécessité du critère d'admissibilité.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.