PhilKa: Die Seite wurde neu angelegt: „= Beam Search = '''Beam Search''' ist ein heuristisches Suchverfahren aus der Künstlichen Intelligenz, das zur Lösung von Such- und Optimierungsproblemen verwendet wird. Es stellt eine speichereffiziente Variante der Best-First Search dar und kombiniert Merkmale von Breitensuche und heuristischer Suche. Die Grundidee besteht darin, in jeder Suchebene nur eine begrenzte Anzahl der vielversprechendsten Kandidaten weit…“

2026-05-30T11:02:07Z

Die Seite wurde neu angelegt: „= Beam Search = '''Beam Search''' ist ein heuristisches Suchverfahren aus der Künstlichen Intelligenz, das zur Lösung von Such- und Optimierungsproblemen verwendet wird. Es stellt eine speichereffiziente Variante der Best-First Search dar und kombiniert Merkmale von Breitensuche und heuristischer Suche. Die Grundidee besteht darin, in jeder Suchebene nur eine begrenzte Anzahl der vielversprechendsten Kandidaten weit…“

Neue Seite

= Beam Search =

'''Beam Search''' ist ein heuristisches Suchverfahren aus der [[Künstliche Intelligenz|Künstlichen Intelligenz]], das zur Lösung von Such- und Optimierungsproblemen verwendet wird. Es stellt eine speichereffiziente Variante der [[Best-First Search]] dar und kombiniert Merkmale von [[Breitensuche]] und heuristischer Suche.

Die Grundidee besteht darin, in jeder Suchebene nur eine begrenzte Anzahl der vielversprechendsten Kandidaten weiterzuverfolgen. Dadurch wird der Speicherbedarf erheblich reduziert, allerdings besteht die Gefahr, optimale Lösungen zu verwerfen.

Beam Search wird unter anderem in folgenden Bereichen eingesetzt:

* [[Maschinelles Lernen]]
* [[Natural Language Processing]]
* [[Spracherkennung]]
* [[Maschinelle Übersetzung]]
* [[Robotik]]
* [[Planungssysteme]]
* [[Kombinatorische Optimierung]]

== Motivation ==

Viele Suchprobleme besitzen einen sehr großen Suchraum.

Beispiele:

* Routenplanung
* Schachprogramme
* Produktionsplanung
* Textgenerierung durch Large Language Models
* Optimierungsprobleme mit vielen Entscheidungsvariablen

Eine vollständige Suche ist häufig nicht praktikabel, da die Anzahl möglicher Zustände exponentiell wächst.

Beam Search reduziert den Suchaufwand, indem nur die besten Kandidaten jeder Ebene betrachtet werden.

== Grundidee ==

Beam Search erweitert die aktuell vielversprechendsten Zustände.

Nach jeder Erweiterung werden die erzeugten Nachfolger bewertet.

Anschließend werden nur die besten Zustände beibehalten.

Alle anderen Zustände werden dauerhaft verworfen.

Die maximale Anzahl gespeicherter Zustände wird als '''Beam Width''' bezeichnet.

== Beam Width ==

Die Beam Width wird häufig mit ''k'' bezeichnet.

Beispiel:

<math>
k = 5
</math>

Dann werden in jeder Ebene höchstens fünf Zustände weiterverfolgt.

Je größer ''k'' gewählt wird:

* desto höher die Lösungsqualität
* desto größer der Speicherbedarf
* desto höher die Rechenzeit

Je kleiner ''k'' gewählt wird:

* desto schneller die Suche
* desto höher das Risiko, gute Lösungen zu verwerfen

== Ablauf des Verfahrens ==

=== Schritt 1: Startzustand ===

Die Suche beginnt mit einem Startknoten.

=== Schritt 2: Erweiterung ===

Alle aktuell gespeicherten Zustände werden expandiert.

=== Schritt 3: Bewertung ===

Jeder Nachfolger erhält einen Bewertungswert.

Dieser kann beispielsweise durch:

* Kostenfunktionen
* Heuristiken
* Wahrscheinlichkeiten

bestimmt werden.

=== Schritt 4: Auswahl ===

Die Nachfolger werden sortiert.

Nur die besten ''k'' Zustände bleiben erhalten.

=== Schritt 5: Wiederholung ===

Die Schritte werden solange wiederholt, bis:

* eine Lösung gefunden wurde
* ein Abbruchkriterium erfüllt ist

== Beispiel ==

Angenommen, die Beam Width beträgt:

<math>
k = 2
</math>

Der Startknoten besitzt vier Nachfolger:

{| class="wikitable"
! Zustand
! Bewertung
|-
| A
| 10
|-
| B
| 7
|-
| C
| 5
|-
| D
| 2
|}

Es werden nur die beiden besten Zustände weiterverfolgt:

* A
* B

Die Zustände C und D werden verworfen.

== Pseudocode ==

<syntaxhighlight lang="text">
BeamSearch(Start, k):

Beam ← {Start}

while nicht beendet:

Kandidaten ← {}

für jeden Zustand in Beam:
Nachfolger erzeugen
Kandidaten hinzufügen

Kandidaten sortieren

Beam ← beste k Kandidaten

return beste Lösung
</syntaxhighlight>

== Mathematische Beschreibung ==

Sei:

<math>
B_t
</math>

die Menge der Zustände im Suchstrahl (Beam) zum Zeitpunkt t.

Nach der Expansion entsteht:

<math>
C_t
</math>

als Menge aller Nachfolger.

Anschließend wird ausgewählt:

<math>
B_{t+1}
=
Top_k(C_t)
</math>

wobei:

<math>
Top_k
</math>

die Auswahl der k besten Zustände beschreibt.

== Eigenschaften ==

=== Unvollständigkeit ===

Beam Search ist nicht vollständig.

Eine existierende Lösung kann verworfen werden.

=== Keine Optimalitätsgarantie ===

Das Verfahren garantiert nicht das Auffinden der optimalen Lösung.

=== Speicherbegrenzung ===

Der Speicherbedarf bleibt kontrollierbar.

=== Hohe Geschwindigkeit ===

Beam Search ist deutlich schneller als vollständige Suchverfahren.

== Vergleich mit anderen Suchverfahren ==

{| class="wikitable"
! Verfahren
! Vollständig
! Optimal
! Speicherbedarf
|-
| Breitensuche
| Ja
| Ja
| Sehr hoch
|-
| Tiefensuche
| Nein
| Nein
| Gering
|-
| A*
| Ja
| Ja
| Hoch
|-
| Beam Search
| Nein
| Nein
| Kontrollierbar
|}

== Beam Search und A* ==

Beam Search wird häufig als speicherbegrenzte Variante von [[A*-Algorithmus|A*]] betrachtet.

Während A* alle vielversprechenden Zustände speichert, begrenzt Beam Search deren Anzahl.

Dadurch wird Speicher eingespart.

Allerdings gehen Optimalitätsgarantien verloren.

== Einfluss der Beam Width ==

=== Kleine Beam Width ===

Beispiel:

<math>
k = 1
</math>

Dies entspricht einer Greedy Search.

Vorteile:

* Sehr schnell
* Sehr geringer Speicherbedarf

Nachteile:

* Schlechte Lösungsqualität

=== Große Beam Width ===

Beispiel:

<math>
k = 100
</math>

Vorteile:

* Höhere Wahrscheinlichkeit guter Lösungen

Nachteile:

* Höherer Ressourcenverbrauch

== Anwendungen in der Künstlichen Intelligenz ==

=== Maschinelle Übersetzung ===

Neuronale Übersetzungsmodelle erzeugen für jedes Wort mehrere mögliche Fortsetzungen.

Beam Search behält die wahrscheinlichsten Übersetzungen.

=== Sprachmodelle ===

Viele Large Language Models verwenden Beam Search zur Textgenerierung.

Dabei werden mehrere mögliche Satzfortsetzungen parallel betrachtet.

=== Spracherkennung ===

Mehrere mögliche Wortfolgen werden bewertet und verglichen.

=== Bildbeschreibung ===

KI-Systeme erzeugen mehrere Kandidatensätze für Bildbeschreibungen.

== Anwendungen in der Optimierung ==

Beam Search wird häufig für kombinatorische Optimierungsprobleme eingesetzt.

Beispiele:

* Produktionsplanung
* Tourenplanung
* Ressourcenallokation
* Scheduling
* Netzwerkoptimierung

== Beispiel aus der Produktionsplanung ==

Eine Fabrik möchte eine optimale Produktionsreihenfolge bestimmen.

Jede Entscheidung erzeugt neue Teilpläne.

Eine vollständige Suche wäre zu teuer.

Beam Search verfolgt nur die vielversprechendsten Teilpläne weiter.

Dadurch können gute Lösungen in akzeptabler Zeit gefunden werden.

== Beam Search in der Multi-Objective-Optimierung ==

Bei Mehrzielproblemen kann die Bewertung eines Zustands beispielsweise erfolgen durch:

* gewichtete Summe der Zielfunktionen
* Pareto-Rang
* Dominanzbeziehungen

Beam Search dient dabei häufig als Metaheuristik zur Approximation guter Lösungen.

== Varianten ==

=== Stochastic Beam Search ===

Die Auswahl erfolgt zufallsbasiert entsprechend einer Wahrscheinlichkeitsverteilung.

Dadurch wird die Diversität erhöht.

=== Local Beam Search ===

Mehrere lokale Suchprozesse laufen parallel.

Die besten Zustände werden gemeinsam betrachtet.

=== Diverse Beam Search ===

Zusätzlich wird die Vielfalt der Kandidaten berücksichtigt.

Dies wird häufig bei Sprachmodellen verwendet.

=== Beam Stack Search ===

Kombination aus Beam Search und Backtracking.

Dadurch können zuvor verworfene Bereiche erneut untersucht werden.

== Vor- und Nachteile ==

=== Vorteile ===

* Einfach zu implementieren
* Geringer Speicherbedarf
* Gute Skalierbarkeit
* Schnelle Laufzeiten
* Für große Suchräume geeignet

=== Nachteile ===

* Keine Optimalitätsgarantie
* Nicht vollständig
* Empfindlich gegenüber der Wahl der Beam Width
* Gute Lösungen können früh verworfen werden

== Komplexität ==

Seien:

* b = Verzweigungsfaktor
* d = Suchtiefe
* k = Beam Width

Dann ergibt sich näherungsweise:

Zeitaufwand:

<math>
O(k \cdot b \cdot d)
</math>

Speicherbedarf:

<math>
O(k)
</math>

Der Speicherbedarf wächst somit linear mit der Beam Width.

== Literatur ==

* Russell, S.; Norvig, P.: ''Artificial Intelligence: A Modern Approach''. Pearson.
* Pearl, J.: ''Heuristics: Intelligent Search Strategies for Computer Problem Solving''. Addison-Wesley.
* Jurafsky, D.; Martin, J.: ''Speech and Language Processing''. Pearson.
* Koehler, G.: ''Künstliche Intelligenz''. Springer Vieweg.
* Ghallab, M.; Nau, D.; Traverso, P.: ''Automated Planning''. Morgan Kaufmann.

== Siehe auch ==

* [[Künstliche Intelligenz]]
* [[Heuristik]]
* [[Breitensuche]]
* [[Tiefensuche]]
* [[A*-Algorithmus]]
* [[Best-First Search]]
* [[Metaheuristik]]
* [[Multi-Objective Optimization]]
* [[Genetischer Algorithmus]]

Beam Search - Versionsgeschichte