informatique (tronc commun des prépas scientifiques) · Chapitre 14 · Exercice de TD
L'heuristique qui ment
Plus courts chemins : Dijkstra et au-delà · niveau 3 (difficile)
Énoncé
Construire un exemple de grille comportant des obstacles pour lequel une heuristique surestimée ( 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 fonce vers le mur car cela réduit drastiquement l'heuristique .
- 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é de cette autre voie est artificiellement très élevée en raison du coefficient multiplicateur 3 appliqué à .
- 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é.
