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 en largeur, en réduisant la mémoire nécessaire à son exécution. Contrairement à l'algorithme best-first où l'on explore tous les états candidats à la solution recherchée en partant du meilleur (estimé), la recherche en faisceau n'explore qu'un nombre limité de ces candidats. C’est donc un algorithme glouton.

La recherche en faisceau utilise l'algorithme de parcours en largeur pour explorer le graphe. À chaque niveau, elle génère tous les successeurs du nœud courant, en les classant selon leur coût heuristique. Cependant, elle ne mémorise qu'un nombre prédéterminé de ces états à chaque niveau (nombre appelé la largeur du faisceau). Plus grande est la largeur, moins d'états sont ignorés. Avec une largeur infinie, tous les états sont considérés et l'algorithme devient identique au parcours en largeur. La largeur du faisceau limite la mémoire requise pour exécuter la recherche. Sachant qu'un état d'arrivée (but de la recherche) peut être ignoré par l'algorithme, la recherche en faisceau sacrifie la complétude (garantie que l'algorithme trouvera la solution si elle existe) et l'optimalité (garantie de trouver la meilleure solution possible).

La largeur du faisceau peut être fixe ou variable. Un exemple d'approche utilise une largeur minimale ; si aucune solution n'est trouvée, la procédure est répétée avec une largeur plus grande.

Utilisations

Une recherche en faisceau est le plus souvent utilisée pour étudier des systèmes trop complexes pour pouvoir stocker la totalité du graphe de recherche. Par exemple, l'algorithme est utilisé dans de nombreux traducteurs automatiques. Pour sélectionner la meilleure traduction, chaque partie de la phrase est traitée et de très nombreuses définitions du mot apparaissent. En considérant leur structure grammaticale, les meilleures sont conservées. Le programme évalue ensuite les traductions selon certains critères, choisissant celle qui semble la plus cohérente. La première utilisation d'une recherche en faisceau a été faite par le Harpy Speech Recognition System en 1976, à l'UCM.

Améliorations

Le parcours en faisceau a été complété (de sorte qu'elle termine avec une solution) en le combinant avec le parcours en profondeur, créant le Beam Stack Search et le Depth-First Beam Search, ainsi qu'avec le parcours à écart limité, créant le Beam Search Using Limited Discrepancy Backtracking (BULB). Ces algorithmes peuvent retourner rapidement une solution valide (généralement sous-optimale) à n'importe quel moment, puis continuent à trouver des meilleures solutions (par retour sur trace) jusqu'à converger vers une solution optimale. Ce sont donc des algorithmes anytime.

Histoire

Le terme de recherche en faisceau (beam search) est dû à Raj Reddy, de l'Université Carnegie-Mellon, en 1976.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Beam search » (voir la liste des auteurs).