Recherche heuristique et A*

La recherche heuristique utilise une estimation spécifique au problème du coût restant pour atteindre un objectif afin de guider les états à explorer en premier ; A* est son algorithme canonique, étendant les états par ordre de la somme du coût déjà encouru et du coût estimé restant.

Definition

La recherche heuristique est une recherche informée qui ordonne la frontière en utilisant une fonction d'évaluation combinant le coût connu depuis le début avec une estimation heuristique du coût restant ; A* utilise f(n) = g(n) + h(n) et est optimal lorsque h est admissible.

Scope

Ce sujet couvre les stratégies de recherche informée (heuristique), centrées sur la recherche au meilleur d'abord (best-first search) et l'algorithme A*, y compris la conception et les propriétés des fonctions heuristiques (admissibilité, cohérence/monotonicité), les garanties d'optimalité et d'efficacité que ces propriétés confèrent, et les variantes à mémoire limitée telles que l'A* à approfondissement itératif (IDA*). Il aborde la manière dont les heuristiques sont construites (problèmes relaxés, bases de données de motifs) et comment elles concilient précision et calcul. L'apprentissage des heuristiques à partir de données relève du sous-domaine de l'apprentissage automatique.

Core questions

• Qu'est-ce qui rend une heuristique admissible, et pourquoi l'admissibilité garantit-elle l'optimalité de A* ?
• Comment la cohérence (monotonicité) renforce-t-elle les garanties et empêche-t-elle la ré-expansion des nœuds ?
• Comment les bonnes heuristiques sont-elles conçues, par exemple à partir de versions relaxées du problème ?
• Comment les variantes à mémoire limitée telles que l'IDA* préservent-elles l'optimalité avec un espace limité ?

Key concepts

• fonction d'évaluation f = g + h
• heuristique admissible
• heuristique cohérente (monotone)
• recherche gloutonne au meilleur d'abord (greedy best-first search)
• recherche A*
• A* à approfondissement itératif (IDA*)
• dominance heuristique
• problème relaxé et bases de données de motifs

Key theories

Optimalité de A* sous des heuristiques admissibles

Lorsque l'heuristique h ne surestime jamais le coût réel restant, A* étend les nœuds par f = g + h croissant et est garanti de renvoyer un chemin de coût minimal ; parmi les algorithmes utilisant la même information heuristique, A* est optimalement efficace.

Conception heuristique par relaxation

Des heuristiques admissibles peuvent être dérivées systématiquement en résolvant une version relaxée du problème (une avec moins de restrictions sur les actions), car le coût exact d'un problème plus facile est une borne inférieure sur l'original ; les heuristiques dominantes (plus informées) étendent moins de nœuds.

Recherche heuristique à mémoire limitée

L'A* à approfondissement itératif effectue des recherches en profondeur successives bornées par un seuil de coût f croissant, atteignant une optimalité de type A* avec une mémoire linéaire par rapport à la profondeur de la solution.

Clinical relevance

La recherche heuristique alimente la recherche d'itinéraires dans les cartes et les jeux, la planification de mouvement en robotique, et les moteurs de recherche à l'intérieur des planificateurs automatisés et des solveurs de puzzles ; l'art pratique de la conception heuristique détermine directement si de grands problèmes sont solubles dans un délai acceptable.

History

L'algorithme A* a été introduit par Hart, Nilsson et Raphael (1968), donnant à la recherche heuristique une base formelle d'optimalité. La monographie de Pearl de 1984, Heuristics, a fourni le traitement théorique définitif, et l'IDA* de Korf en 1985 a abordé le coût mémoire de A*. Ces résultats restent un matériel essentiel dans l'enseignement de l'IA.

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

Qu'est-ce qu'une heuristique admissible ?

Une heuristique est admissible si elle ne surestime jamais le coût réel pour atteindre l'objectif depuis n'importe quel état. L'admissibilité est la condition sous laquelle A* est garanti de trouver une solution optimale (de coût minimal).

Quelle est la différence entre la recherche gloutonne au meilleur d'abord et A* ?

La recherche gloutonne au meilleur d'abord étend l'état qui semble le plus proche de l'objectif selon l'heuristique seule (h), ce qui est rapide mais peut être loin d'être optimal. A* ajoute le coût réel encouru jusqu'à présent (g), étendant par f = g + h, ce qui préserve l'optimalité lorsque l'heuristique est admissible.