Un algorithme heuristique de recherche sur graphe/arbre qui explore l'espace de recherche en ne conservant qu'un nombre fixe (largeur de faisceau) des solutions partielles les mieux classées à chaque profondeur, élaguant les alternatives moins bien classées pour limiter le coût de calcul tout en sacrifiant la complétude ou l'optimalité selon la largeur et l'heuristique de classement.

Principe

À chaque niveau d'expansion, évaluer les candidats partiels par une heuristique ou une vraisemblance de modèle, retenir les B meilleurs candidats (faisceau), les développer pour le niveau suivant et répéter ; cette stratégie à largeur limitée échange exploration exhaustive contre un contrôle praticable de l'élargissement selon un critère de classement.

Démonstration

En décodage de séquences (p. ex. traduction automatique), la recherche en faisceau conserve aux chaque pas temporel les B séquences partielles les plus probables selon les probabilités conditionnelles du modèle ; elle produit des sorties plausibles efficacement mais peut manquer des séquences globalement optimales à cause d'élagages précoces ou d'un mauvais score.

Mauvaise application

Utiliser un faisceau trop étroit pour des tâches à dépendances longue portée, s'appuyer sur un score local naïf qui favorise préfixes courts ou très probables, ou supposer que la recherche en faisceau donne des sorties optimales ou diversifiées sans ajustements (p. ex. normalisation de longueur, heuristiques promouvant la diversité).

Conséquence

Permet un décodage et une recherche pratiques dans de grands espaces combinatoires en contrôlant le facteur de branchement par la largeur du faisceau ; les résultats sont plus rapides et souvent de bonne qualité en pratique mais peuvent être biaisés par le scoring, sous‑représenter des chemins globalement bons de faible probabilité et manquer de garanties de complétude sauf si le faisceau est illimité.

Inversion

La recherche en largeur complète ou exhaustive (largeur du faisceau égale à l'ensemble du front) est le renversement : elle restaure les garanties de complétude et d'optimalité à un coût de calcul et mémoire bien plus élevé.

Limite

Applicable lorsque des solutions partielles peuvent être évaluées et comparées de manière significative ; non approprié quand le scoring est peu fiable, quand la complétude est requise ou quand la mémoire/le faisceau doit être extrêmement petit par rapport au facteur de branchement ; des ajustements sont nécessaires pour des réglages stochastiques ou adversariaux.

Tension sémantique

Souvent confondu avec la recherche gloutonne ou la best‑first ; la recherche en faisceau généralise la gloutonne en conservant plusieurs candidats par niveau (B>1), la gloutonne étant le cas B=1, tandis que la best‑first peut développer selon un score global de front et non par niveaux fixes.

Synthèse

La recherche en faisceau est une heuristique par niveau qui retient un nombre fixe de meilleures solutions partielles pour garder la recherche praticable : une approximation efficace dépendante de la qualité du scoring et de la largeur du faisceau, qui équilibre rapidité et mémoire face à la complétude et l'optimalité.