Ein heuristischer Graph-/Baumsuchalgorithmus, der den Suchraum erkundet, indem er auf jeder Tiefe nur eine feste Anzahl (Beam‑Breite) der höchstbewerteten partiellen Lösungen hält und niedrigere Alternativen beschneidet, um die Rechenkosten zu begrenzen, dabei jedoch Vollständigkeit oder Optimalität je nach Beam‑Größe und Bewertungsheuristik opfert.

Prinzip

Auf jeder Expansionsstufe partielle Kandidaten durch eine Heuristik oder Modellwahrscheinlichkeit bewerten, die Top‑B‑Kandidaten (Beam) behalten, diese für die nächste Stufe expandieren und wiederholen; diese breitebegrenzte Strategie tauscht vollständige Erkundung gegen beherrschbare Verzweigungsbegrenzung mittels eines Rankingkriteriums.

Demonstration

Beim Sequenzdecoding (z. B. maschinelle Übersetzung) behält Beam‑Search in jedem Zeitschritt die B wahrscheinlichsten partiellen Ausgabesequenzen gemäß den bedingten Modellwahrscheinlichkeiten; es liefert effizient plausible Ausgaben, kann aber global optimale Sequenzen durch frühes Beschneiden oder schlechtes Scoring übersehen.

Fehlanwendung

Ein zu schmales Beam für Aufgaben mit Langzeitabhängigkeiten verwenden, sich auf naive lokale Scores verlassen, die kurze oder wahrscheinliche Präfixe bevorzugen, oder annehmen, Beam‑Search liefere optimale oder diverse Ausgaben ohne Anpassungen (z. B. Längennormalisierung, diversitätsfördernde Heuristiken).

Konsequenz

Ermöglicht praktisches Decoding und Suchen in großen kombinatorischen Räumen durch Kontrolle der Verzweigung via Beam‑Breite; Ergebnisse sind schneller und oft qualitativ gut in der Praxis, können jedoch durch Scoring verzerrt sein, global gute, niedrigwahrscheinliche Pfade unterrepräsentieren und fehlen Vollständigkeitsgarantien, sofern das Beam nicht unbegrenzt ist.

Umkehrung

Vollständige Breitensuche oder exhaustive Suche (Beam‑Breite gleich der gesamten Front) ist die Umkehr: Sie stellt Vollständigkeit und Optimalität wieder her, jedoch zu deutlich höheren Rechen‑ und Speicheranforderungen.

Abgrenzung

Anwendbar, wenn partielle Lösungen sinnvoll bewertet und verglichen werden können; nicht geeignet, wenn Scoring unzuverlässig ist, Vollständigkeit erforderlich ist oder Speicher/Beam im Verhältnis zum Verzweigungsfaktor extrem klein sein muss; Anpassungen für stochastische oder adversariale Settings nötig.

Semantische Spannung

Wird oft mit gieriger Suche oder Best‑First‑Suche gleichgesetzt; Beam‑Search verallgemeinert die gierige Suche, indem es mehrere Kandidaten pro Stufe behält (B>1), wobei die gierige Suche den Spezialfall B=1 darstellt, während Best‑First anhand globaler Frontscores expandieren kann statt nach festen Ebenen.

Synthese

Beam‑Search ist eine ebenenweise, beam‑begrenzte Heuristik, die eine feste Anzahl top‑bewerteter partieller Lösungen behält, um die Suche handhabbar zu machen: eine effiziente Approximation, deren Nutzen stark von der Bewertungsqualität und Beam‑Breite abhängt und die Geschwindigkeit und Speicher gegen Vollständigkeit und Optimalität abwägt.