Beam Search

Une beam search est un algorithme de recherche dans un graphe qui utilise une certaine heuristique, expliquée ci-dessous, pour réduire la complexité temporelle et spatiale.

Dans une beam search, « recherche en faisceau » en français, on arpente le graphe avec un parcours en largeur.

De plus, on se munit d’une heuristique et, à chaque nœud du graphe, on sélectionne une partie seulement des fils du nœud, en fonction de l’heuristique. L’idée est de parcourir uniquement les fils ayant la meilleure valeur de l’heuristique (par exemple, on parcourra les 10 meilleurs fils d’un nœud ayant 100 fils).

En peu de mots, comme un faisceau, on se concentre sur quelques nœuds les plus prometteurs pour réduire notre champ de recherche lors de l’exploration du graphe.