Heuristique admissible
term_id: admissible_heuristic
Category: basic_concepts
Definition
Dans les problèmes de recherche de chemin et de recherche générale, une heuristique admissible fournit une borne inférieure du coût réel pour atteindre le nœud cible. En garantissant que le coût estimé est toujours inférieur ou égal au coût réel, elle assure que les algorithmes comme A* trouvent le chemin optimal.
Summary
Une fonction heuristique dans les algorithmes de recherche qui ne surestime jamais le coût réel pour atteindre l’objectif, garantissant l’optimalité.
Key Concepts
- Borne inférieure
- Garantie d’optimalité
- Recherche A*
- Estimation du coût
Use Cases
- Planification d’itinéraires de navigation GPS
- Résolution de puzzles (par exemple, le puzzle à 8 tuiles)
- Planification de mouvement robotique dans des environnements encombrés