Informierte Suche
Informierte Suchalgorithmen nutzen zusätzliches Wissen über das Problem (Heuristiken), um effizienter zum Ziel zu gelangen. Im Gegensatz zu uninformierten Algorithmen wie BFS und DFS haben sie eine Vorstellung davon, wie "vielversprechend" ein Zustand ist.
Was ist eine Heuristik?
Eine Heuristik ist eine Schätzfunktion h(n), die für jeden Zustand n schätzt, wie weit das Ziel noch entfernt ist.
Eigenschaften einer guten Heuristik:
- Zulässig (Admissible): h(n) überschätzt niemals die tatsächlichen Kosten zum Ziel (h(n) ≤ tatsächliche Kosten)
- Konsistent: Für jeden Zustand n und jeden Nachfolger n': h(n) ≤ kosten(n,n') + h(n')
- Informativ: Je näher h(n) an den tatsächlichen Kosten ist, desto effizienter die Suche
Beispiel - Schlechte vs. Gute Heuristik:
- Schlechte Heuristik: h(n) = 0 für alle Zustände (keine Information → wird zu BFS)
- Perfekte Heuristik: h(n) = tatsächliche Restkosten (unmöglich zu berechnen, sonst bräuchten wir keine Suche)
- Gute Heuristik: h(n) = geschätzte Restkosten, die nah an der Realität sind
Distanzmetriken in Gittern
Für gitterbasierte Probleme (Labyrinthe, Karten) gibt es verschiedene Möglichkeiten, die Distanz zwischen zwei Punkten zu messen:
Manhattan-Distanz (L1-Metrik)
Formel: |x₁ - x₂| + |y₁ - y₂|
Beschreibung: Summe der absoluten Differenzen in x- und y-Richtung. Entspricht der Anzahl der Schritte, wenn man nur horizontal und vertikal gehen kann (keine Diagonalen).
Wann verwenden: Wenn nur 4-Richtungs-Bewegung erlaubt ist (oben, unten, links, rechts).
Beispiel:
Von (0,0) zu (3,2):
Manhattan = |0-3| + |0-2| = 3 + 2 = 5 Schritte
Visuell:
S . . G
. . . .
. . . .Python-Implementation:
def manhattan_distanz(x1, y1, x2, y2):
return abs(x1 - x2) + abs(y1 - y2)Euklidische Distanz (L2-Metrik)
Formel: √((x₁ - x₂)² + (y₁ - y₂)²)
Beschreibung: "Luftlinie" zwischen zwei Punkten. Entspricht der geometrischen Distanz.
Wann verwenden: Wenn auch diagonale Bewegung erlaubt ist (8 Richtungen) oder für kontinuierliche Räume.
Beispiel:
Von (0,0) zu (3,2):
Euklidisch = √((0-3)² + (0-2)²) = √(9 + 4) = √13 ≈ 3.6Python-Implementation:
import math
def euklidische_distanz(x1, y1, x2, y2):
return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)Chebyshev-Distanz (L∞-Metrik)
Formel: max(|x₁ - x₂|, |y₁ - y₂|)
Beschreibung: Die größere der beiden Koordinatendifferenzen. Entspricht der Anzahl der Schritte, wenn diagonale Bewegung die gleichen Kosten hat wie gerade Bewegung.
Wann verwenden: Wenn 8-Richtungs-Bewegung erlaubt ist und Diagonalen gleich kosten wie gerade Bewegungen.
Beispiel:
Von (0,0) zu (3,2):
Chebyshev = max(|0-3|, |0-2|) = max(3, 2) = 3Python-Implementation:
def chebyshev_distanz(x1, y1, x2, y2):
return max(abs(x1 - x2), abs(y1 - y2))Vergleich der Metriken
| Metrik | Bewegung | Formel | Beispiel (0,0)→(3,2) |
|---|---|---|---|
| Manhattan | 4 Richtungen | |Δx| + |Δy| | 5 |
| Euklidisch | Luftlinie | √(Δx² + Δy²) | ≈3.6 |
| Chebyshev | 8 Richtungen | max(|Δx|, |Δy|) | 3 |
Für unsere Labyrinth-Aufgaben: Wir verwenden Manhattan-Distanz, da nur 4-Richtungs-Bewegung erlaubt ist.
Greedy Best-First Search
Beschreibung der Suchstrategie
Greedy Best-First Search (gierige Bestensuche) wählt immer den Zustand mit der niedrigsten Heuristik h(n) aus. Sie ist "gierig", weil sie nur auf das unmittelbare Ziel schaut, ohne die bereits zurückgelegten Kosten zu berücksichtigen.
Kernidee: Gehe immer in die Richtung, die am vielversprechendsten erscheint (niedrigste h(n)).
Datenstruktur: Greedy BFS verwendet eine Prioritätswarteschlange (Priority Queue), sortiert nach h(n). Der Zustand mit der niedrigsten Heuristik wird zuerst entfernt.
Bewertungsfunktion: f(n) = h(n)
Eigenschaften:
- Vollständig: Nein (kann in Schleifen steckenbleiben)
- Optimal: Nein (findet nicht immer den kürzesten Pfad)
- Effizienz: Oft sehr schnell, da sie direkt zum Ziel "zusteuert"
- Speicherkomplexität: O(b^m) - kann viel Speicher benötigen
Beispiel: Labyrinth
Gegeben ist folgendes Labyrinth (mit Manhattan-Distanzen zum Ziel):
S(6) . . . . .
. X . . X .
. . . . . .
. X X X . .
. . . . . Z(0)Zahlen in Klammern sind h(n) = Manhattan-Distanz zum Ziel Z bei (5,4).
Greedy BFS-Ablauf:
Start: PriorityQueue = [S(6)], Besucht = [S]
- Entferne S, h(S) = 6
- Nachbarn: (0,1) mit h=7, (1,0) mit h=8
- Füge beide zur Queue hinzu
Schritt 2: PriorityQueue = [(0,1)(7), (1,0)(8)], sortiert nach h
- Entferne (0,1) (niedrigste h=7)
- Nachbarn: (0,2) mit h=6, ...
- Greedy wählt immer den Weg mit niedrigster Heuristik
Greedy navigiert direkt Richtung Ziel, auch wenn das nicht immer der kürzeste Pfad ist!
Problem: Greedy kann einen längeren Weg nehmen, wenn die Heuristik sie in eine Sackgasse führt. Sie berücksichtigt nicht die bereits zurückgelegten Kosten.
Pseudocode
GreedyBFS(Start, Ziel):
1. Erstelle leere Prioritätswarteschlange (sortiert nach h(n))
2. Füge Start zur Queue hinzu mit h(Start)
3. Markiere Start als besucht
4. Solange Queue nicht leer:
a. Entferne Zustand mit niedrigstem h(n) aus Queue
b. Wenn dieser Zustand das Ziel ist:
- Gib Lösung zurück
c. Sonst:
- Für jeden Nachbarn dieses Zustands:
* Wenn Nachbar noch nicht besucht:
- Berechne h(Nachbar)
- Markiere als besucht
- Füge Nachbar zur Queue hinzu mit h(Nachbar)
5. Wenn Queue leer und kein Ziel gefunden:
- Gib "Keine Lösung" zurückIn Python-ähnlicher Syntax:
import heapq
def greedy_bfs(start, ziel, hole_nachbarn, heuristik):
# Priority Queue: (h(n), zustand)
pq = [(heuristik(start, ziel), start)]
besucht = [start]
while pq:
h, aktuell = heapq.heappop(pq) # Entferne mit niedrigstem h
if aktuell == ziel:
return "Ziel gefunden!"
for nachbar in hole_nachbarn(aktuell):
if nachbar not in besucht:
besucht.append(nachbar)
h_nachbar = heuristik(nachbar, ziel)
heapq.heappush(pq, (h_nachbar, nachbar))
return "Keine Lösung gefunden"A* (A-Stern) Search
Beschreibung der Suchstrategie
A* kombiniert die Vorteile von BFS (findet kürzesten Pfad) und Greedy BFS (nutzt Heuristik für Effizienz). Es berücksichtigt sowohl die bereits zurückgelegten Kosten g(n) als auch die geschätzten Restkosten h(n).
Kernidee: Wähle den Zustand mit den niedrigsten Gesamtkosten f(n) = g(n) + h(n).
Bewertungsfunktion:
- g(n): Tatsächliche Kosten vom Start zu n (Anzahl Schritte)
- h(n): Geschätzte Kosten von n zum Ziel (Heuristik)
- f(n) = g(n) + h(n): Geschätzte Gesamtkosten über n
Datenstruktur: A* verwendet eine Prioritätswarteschlange (Priority Queue), sortiert nach f(n).
Eigenschaften:
- Vollständig: Ja (findet immer eine Lösung, wenn eine existiert)
- Optimal: Ja, wenn die Heuristik zulässig ist (h(n) überschätzt nie)
- Effizienz: Optimal-effizient (kein anderer Algorithmus mit gleicher Heuristik expandiert weniger Knoten)
- Speicherkomplexität: O(b^d) - kann viel Speicher benötigen
Warum ist A* optimal?
Wenn h(n) zulässig ist (nie überschätzt), dann garantiert A*, dass:
- Wenn ein Ziel gefunden wird, ist es das mit den niedrigsten Kosten
- Kein vielversprechenderer Pfad wurde übersehen
Beweis-Intuition: Angenommen, A* findet einen suboptimalen Pfad mit Kosten C₁, aber es existiert ein optimaler Pfad mit Kosten C₂ < C₁. Da h(n) nicht überschätzt, wäre f(n) für einen Knoten auf dem optimalen Pfad kleiner als C₁, und A* hätte ihn zuerst expandiert.
Beispiel: Labyrinth
Gleiches Labyrinth, nun mit g(n) und f(n):
S(0+6=6) → (1+5=6) → (2+4=6) → Z(3+0=3)A*-Ablauf:
Start: PriorityQueue = [S(f=6)], g(S)=0, h(S)=6
- Entferne S, f(S) = 0 + 6 = 6
- Nachbarn: (0,1) mit g=1, h=7, f=8
Schritt 2: PriorityQueue = [(0,1)(f=8), ...], sortiert nach f
- Entferne Knoten mit niedrigstem f
- A* balanciert zwischen "schon zurückgelegtem Weg" und "Restweg"
A* findet den optimalen Pfad, da es beide Faktoren berücksichtigt!
Pseudocode
A*(Start, Ziel):
1. Erstelle leere Prioritätswarteschlange (sortiert nach f(n))
2. Füge Start zur Queue hinzu mit f(Start) = h(Start)
3. Setze g(Start) = 0
4. Markiere Start als besucht
5. Solange Queue nicht leer:
a. Entferne Zustand mit niedrigstem f(n) aus Queue
b. Wenn dieser Zustand das Ziel ist:
- Gib Lösung zurück
c. Sonst:
- Für jeden Nachbarn dieses Zustands:
* Berechne g_neu = g(aktuell) + 1 # Kosten für einen Schritt
* Wenn Nachbar noch nicht besucht oder g_neu < g(Nachbar):
- Setze g(Nachbar) = g_neu
- Setze f(Nachbar) = g_neu + h(Nachbar)
- Markiere als besucht
- Füge Nachbar zur Queue hinzu mit f(Nachbar)
6. Wenn Queue leer und kein Ziel gefunden:
- Gib "Keine Lösung" zurückIn Python-ähnlicher Syntax:
import heapq
def a_stern(start, ziel, hole_nachbarn, heuristik):
# Priority Queue: (f(n), zustand)
g = {start: 0} # g(n): Kosten vom Start zu n
f_start = heuristik(start, ziel)
pq = [(f_start, start)]
besucht = [start]
while pq:
f, aktuell = heapq.heappop(pq)
if aktuell == ziel:
return "Ziel gefunden!"
for nachbar in hole_nachbarn(aktuell):
g_neu = g[aktuell] + 1 # Kosten für einen Schritt
if nachbar not in besucht or g_neu < g.get(nachbar, float('inf')):
g[nachbar] = g_neu
h = heuristik(nachbar, ziel)
f_neu = g_neu + h
besucht.append(nachbar)
heapq.heappush(pq, (f_neu, nachbar))
return "Keine Lösung gefunden"Vergleich: Greedy BFS vs. A*
| Eigenschaft | Greedy BFS | A* |
|---|---|---|
| Bewertungsfunktion | f(n) = h(n) | f(n) = g(n) + h(n) |
| Berücksichtigt zurückgelegte Kosten | Nein | Ja |
| Vollständigkeit | Nein | Ja |
| Optimalität | Nein | Ja (mit zulässiger Heuristik) |
| Effizienz | Sehr schnell | Schnell und optimal |
| Anwendung | Schnelle Näherungslösung | Wenn optimaler Pfad benötigt |
Wann Greedy BFS verwenden:
- Schnelle Lösung wichtiger als optimale Lösung
- Heuristik ist sehr gut (nah an tatsächlichen Kosten)
- Speicher ist begrenzt
Wann A* verwenden:
- Optimaler Pfad wird benötigt
- Gute zulässige Heuristik verfügbar
- Genug Speicher vorhanden
Zusammenfassung: Uninformierte vs. Informierte Suche
| Algorithmus | Typ | Datenstruktur | f(n) | Optimal | Vollständig |
|---|---|---|---|---|---|
| BFS | Uninformiert | Queue (FIFO) | - | Ja | Ja |
| DFS | Uninformiert | Stack (LIFO) | - | Nein | Nein* |
| Greedy BFS | Informiert | Priority Queue | h(n) | Nein | Nein |
| A* | Informiert | Priority Queue | g(n)+h(n) | Ja** | Ja |
* DFS ist nicht vollständig in unendlichen Räumen ** A* ist optimal, wenn die Heuristik zulässig ist
Kernprinzip informierter Suche: Nutze Problemwissen (Heuristik), um effizienter zu suchen!