Suchalgorithmen in der Informatik: Best-First, A* und mehr

3) Best-First-Suche

Bei der Best-First-Suche wird der Knoten mit der besten Bewertung zuerst erweitert. Diese Funktion berücksichtigt alle bisher gesehenen Knoten, um die beste Entscheidung basierend auf der Evaluation zu treffen.

4) Breadth-First-Suche (Breitensuche)

Bei der Breadth-First-Suche wird jeder Knoten auf einem bestimmten Niveau vollständig ausgewertet, bevor zum nächsten übergegangen wird. Sie ist optimal und sucht nach der kürzesten Lösung.

• Funktionsweise: Der gesamte Graph wird in einer bestimmten Reihenfolge durchsucht, ohne Rücksicht auf das Ziel, bis dieses gefunden wird.
• Eigenschaften: Es wird keine Heuristik verwendet. Alle untergeordneten Knoten, die durch die Erweiterung eines Knotens entstehen, werden in eine FIFO-Warteschlange (First-In-First-Out) aufgenommen.

5) Depth-First-Suche (Tiefensuche)

Die Depth-First-Suche ist ein Algorithmus, der es ermöglicht, alle Knoten eines Graphen oder Baums rekursiv in einer geordneten, wenn auch nicht einheitlichen Weise zu durchlaufen. Wenn keine weiteren Knoten mehr vorhanden sind, erfolgt ein Rückschritt (Backtracking), um den Vorgang mit jedem Zweig zu wiederholen.

OPEN := [Erste]; GESCHLOSSEN := []; f'(START) := h'(INITIAL)
WIEDERHOLEN
  WENN OPEN = [] DANN FAILURE
  MEJORNODO := Auszug aus OPEN mit f'-Minimum (Priority-Queue)
  Verschiebe MEJORNODO von OPEN nach GESCHLOSSEN
  WENN MEJORNODO enthält estado_objetivo DANN SOLUCION_ENCONTRADA := TRUE
  SONST
    Generiere Nachfolger von MEJORNODO
    FÜR JEDEN Nachfolger: TRATAR_SUCESOR
BIS SOLUCION_ENCONTRADA ODER FAILURE

A*-Algorithmus

Der A*-Algorithmus berücksichtigt sowohl den heuristischen Wert eines Knotens als auch die tatsächlichen Kosten des bisherigen Pfades. Er verwendet die Bewertungsfunktion f(n) = g(n) + h(n):

• g(n): Die tatsächlichen Kosten, um den Knoten n zu erreichen.
• h(n): Der heuristische Schätzwert vom Knoten n bis zum Ziel.

A* verwaltet zwei Hilfsdatenstrukturen: OPEN (eine Prioritätswarteschlange) und CLOSED (Speicher für bereits besuchte Knoten). Der Algorithmus kombiniert Aspekte der Breitensuche (durch g(n)) und der Tiefensuche (durch h'(n)), um stets den geeignetsten Pfad zu wählen.

Dieser Algorithmus ist vollständig. Um die Optimalität zu gewährleisten, muss die Heuristik h(n) zulässig sein. Ist dies nicht der Fall, garantiert der Algorithmus nicht den Pfad mit den minimalen Kosten.

Pseudocode:

(Der Pseudocode folgt der Logik der oben genannten Suchstrategien.)