Algorithme de recherche best-first

Algorithme de recherche best-first

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 f(n) 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"[1],[2].

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[2].

La sélection du meilleur candidat à l'exploration est typiquement implémentée en utilisant une file à priorités.

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.

Sommaire

Algorithme

OUVERT = ensemble contenant uniquement l'état initial
Tant que OUVERT n'est pas vide
Répéter
        1. Retirer le meilleur élément de OUVERT. Soit N cet élément ;
        2. Si N est l'état d'arrivée, remonter le chemin depuis N (par parentés successives) et retourner le chemin ;
        3. Créer les successeurs de N ;
        4. Évaluer ces successeurs, les ajouter à OUVERT en mémorisant leur parent.
Fin Répéter

Noter que cette version[3] 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.

OUVERT = ensemble contenant uniquement l'état initial
FERME = ensemble vide
Tant que OUVERT n'est pas vide
Répéter
        1. Retirer le meilleur élément de OUVERT et l'ajouter à FERME. Soit N cet élément ;
        2. Si N est l'état d'arrivée, remonter le chemin depuis N (par parentés successives) et retourner le chemin ;
        3. Créer les successeurs de N ;
        4. Pour chaque successeur, faire :
                a. Si le successeur n'est pas dans FERME : l'évaluer, l'ajouter à OUVERT en mémorisant son parent ;
                b. Sinon : changer son parent si le nouveau chemin est meilleur que l'ancien.
Fin Répéter

Noter aussi que le pseudo-code des deux versions termine simplement si aucun chemin n'est trouvé. Une implémentation demanderait bien sûr un traitement spécial de ce cas.

Algorithme glouton

En utilisant un algorithme glouton, on explore le premier successeur du parent. Après génération du successeur[4] :

  • Si celui-ci est "meilleur" que son parent, il est placé au début de la file (et son parent est réinséré juste derrière lui), et la boucle reprend ;
  • Sinon, il est placé dans la file en fonction de sa valeur heuristique. La procédure évalue ensuite les autres successeurs du parent.

Voir aussi

Références

  1. (en) Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
  2. a et b (en) Stuart J. Russell et Peter Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 2003 (ISBN 0-13-790395-2) [lire en ligne], p. 94-95 (note 3) 
  3. (en) http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html Best First Search
  4. (en) http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Greedy Best-First Search when EHC Fails, Carnegie Mellon

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de recherche best-first de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Algorithme de recherche en faisceau — En informatique, la recherche en faisceau est un algorithme de recherche heuristique qui explore un graphe en ne considérant qu un ensemble limité de fils de chaque nœud. La recherche en faisceau est une optimisation de l algorithme de parcours… …   Wikipédia en Français

  • Bing (moteur de recherche) — Pour les articles homonymes, voir Bing. Logo de Bing URL …   Wikipédia en Français

  • Scale-invariant feature transform — Exemple de résultat de la comparaison de deux images par la méthode SIFT (Fantasia ou Jeu de la poudre, devant la porte d’entrée de la ville de Méquinez, par Eug …   Wikipédia en Français

  • Autostabilisation — L autostabilisation, ou auto stabilisation, est la propriété d un système réparti, composé de plusieurs machines capables de communiquer entre elles, qui consiste, lorsque le système est mal initialisé ou perturbé, à retourner automatiquement à… …   Wikipédia en Français

  • Bin packing problem — Problème de bin packing Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème… …   Wikipédia en Français

  • Probleme de bin packing — Problème de bin packing Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème… …   Wikipédia en Français

  • Problème de bin packing — Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème classique se définit en une …   Wikipédia en Français

  • Liste Des Sigles De Quatre Lettres — {{{image}}} Sigles d une seule lettre Sigles de deux lettres Sigles de trois lettres AAA à DZZ EAA à HZZ IAA à LZZ MAA à PZZ QAA à TZZ UAA à XZZ YAA à ZZ …   Wikipédia en Français

  • Liste de sigles de quatre lettres — Cette liste est incomplète ou mal ordonnée. Votre aide est la bienvenue ! Sigles d’une seule lettre Sigles de deux lettres Sigles de trois lettres Sigles de quatre lettres Sigles de cinq lettres Sigles de six lettre …   Wikipédia en Français

  • Liste de toutes les combinaisons de quatre lettres — Liste des sigles de quatre lettres {{{image}}} Sigles d une seule lettre Sigles de deux lettres Sigles de trois lettres AAA à DZZ EAA à HZZ IAA à LZZ MAA à PZZ QAA à TZZ UAA à XZZ YAA à ZZ …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”