La recherche best-first (littéralement : le meilleur en premier) est un algorithme de recherche qui parcourt un graphe en explorant le nœud le plus "prometteur" selon une règle spécifique.
Judea Pearl décrit la recherche best-first comme l'estimation de la qualité d'un nœud n par une "fonction heuristique d'évaluation qui, en général, peut dépendre de la description de n, de l'état d'arrivée, des informations amassées par l'algorithme au moment de l'évaluation et, surtout, de connaissances supplémentaires à propos du problème".
Certains auteurs utilisent le terme best-first pour désigner spécifiquement une recherche dont l'heuristique essaie de prédire la distance entre la fin d'un chemin et la solution, de sorte à explorer en priorité le chemin le plus proche de la solution. Ce type précis de recherche est nommé best-first glouton.
La sélection du meilleur candidat à l'exploration est typiquement implémentée en utilisant une .
L'algorithme A* est un exemple de recherche best-first. Ce type de recherche est souvent utilisée pour rechercher des chemins en optimisation combinatoire.
OUVERT = ensemble contenant uniquement l'état initial
Tant que OUVERT n'est pas vide
Répéter
Retirer le meilleur élément de OUVERT. Soit N cet élément ;
Si N est l'état d'arrivée, remonter le chemin depuis N (par parentés successives) et retourner le chemin ;
Créer les successeurs de N ;
Évaluer ces successeurs, les ajouter à OUVERT en mémorisant leur parent.
Fin Répéter
Noter que cette version de l'algorithme n'est pas complète : elle ne trouve pas toujours un chemin possible entre deux nœuds même s'il en existe un. Par exemple, l'algorithme boucle s'il arrive dans une impasse : un nœud dont le seul successeur est son parent. Dans ce cas, l'algorithme retourne vers le parent, ajoute le nœud-impasse à OUVERT, et ainsi de suite.
La version ci-dessous étend l'algorithme en utilisant un ensemble additionnel FERME, contenant tous les nœuds déjà évalués et qui ne seront plus explorés. On évite ainsi les boucles infinies en n'explorant pas deux fois un même nœud.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Explore les connaissances sur les modèles de recherche de faisceau et de décodage des séquences dans le NLP, en mettant l'accent sur la motivation cognitive derrière les algorithmes de recherche.
Couvre la planification avec des adversaires, des algorithmes de recherche heuristique et des stratégies pour les jeux avec le hasard, en soulignant l'importance des agents délibératifs.
En informatique, plus précisément en intelligence artificielle, l'algorithme de recherche A* (qui se prononce A étoile, ou A star en anglais) est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final tous deux donnés. En raison de sa simplicité il est souvent présenté comme exemple typique d'algorithme de planification, domaine de l'intelligence artificielle.
Au sens le plus large, l'heuristique est la psychologie de la découverte, abordée par différents mathématiciens. En algorithmique, une heuristique est une méthode de calcul qui fournit rapidement une solution réalisable, pas nécessairement optimale ou exacte, pour un problème d'optimisation difficile. On distingue en général plusieurs temps la prise en compte du problème (question, contexte : données, contraintes, acteurs, tenants et aboutissants) l'incubation, recherche de solution, rumination parfois très longue ; la méthode du problème résolu peut ici dégager les conditions nécessaires à respecter.
La recherche best-first (littéralement : le meilleur en premier) est un algorithme de recherche qui parcourt un graphe en explorant le nœud le plus "prometteur" selon une règle spécifique. Judea Pearl décrit la recherche best-first comme l'estimation de la qualité d'un nœud n par une "fonction heuristique d'évaluation qui, en général, peut dépendre de la description de n, de l'état d'arrivée, des informations amassées par l'algorithme au moment de l'évaluation et, surtout, de connaissances supplémentaires à propos du problème".
This course covers numerous powerful algorithmic techniques (greedy, local search, linear programming, multiplicative weight update, ...). The concepts are studied in clean and simple settings so as t
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
Concepts and tools to understand and use the modem chemical information environment Learn how to explore the scientific literature, how to use the information found in agreement with intellectual prop