Uninformierte Suche

Uninformierte Suchalgorithmen suchen in einem Zustandsraum nach einer Loesung, ohne zusaetzliches Wissen ueber das Problem zu verwenden. Sie erkunden systematisch alle moeglichen Zustaende.

Breitensuche (BFS - Breadth-First Search)

Beschreibung der Suchstrategie

Breitensuche erkundet den Zustandsraum in "Wellen" oder "Ebenen". Sie beginnt beim Startzustand und erkundet zuerst alle Zustaende, die genau einen Schritt entfernt sind, dann alle, die zwei Schritte entfernt sind, und so weiter.

Kernidee: Erkunde alle Zustaende auf Distanz k, bevor du Zustaende auf Distanz k+1 erkundest.

Datenstruktur: BFS verwendet eine Warteschlange (Queue) - nach dem FIFO-Prinzip (First In, First Out). Neue Zustaende werden hinten eingefuegt und vorn entfernt.

Eigenschaften:

• Vollstaendig: Findet immer eine Loesung, wenn eine existiert
• Optimal: Findet den kuerzesten Pfad (wenn alle Aktionen gleiche Kosten haben)
• Speicherkomplexitaet: O(b^d) - kann viel Speicher benoetigen

Beispiel: Labyrinth

Gegeben ist folgendes Labyrinth:

S . . Z
. X . .

Wobei:

• S = Start
• Z = Ziel
• X = Wand
• . = freier Weg

BFS-Ablauf:

1. Schritt 1: Warteschlange = [S], Besucht = [S]

   • Entferne S, pruefe: Ist es Ziel? Nein.
   • Fuege Nachbarn hinzu: (0,1) rechts von S

2. Schritt 2: Warteschlange = [(0,1)], Besucht = [S, (0,1)]

   • Entferne (0,1), pruefe: Ist es Ziel? Nein.
   • Fuege Nachbarn hinzu: (0,2) rechts, (1,1) unten (aber (1,1) ist Wand, also nur (0,2))

3. Schritt 3: Warteschlange = [(0,2)], Besucht = [S, (0,1), (0,2)]

   • Entferne (0,2), pruefe: Ist es Ziel? Nein.
   • Fuege Nachbarn hinzu: (0,3) rechts, (1,2) unten

4. Schritt 4: Warteschlange = [(0,3), (1,2)], Besucht = [S, (0,1), (0,2), (0,3), (1,2)]

   • Entferne (0,3), pruefe: Ist es Ziel? Ja! Ziel gefunden!

Visualisierung der Expansion:

Ebene 0: S
Ebene 1: (0,1)
Ebene 2: (0,2)
Ebene 3: (0,3) = Z

BFS findet den kuerzesten Weg (3 Schritte).

Pseudocode

BFS(Start, Ziel):
    1. Erstelle leere Warteschlange
    2. Fuege Start zur Warteschlange hinzu
    3. Markiere Start als besucht
    4. Solange Warteschlange nicht leer:
        a. Entferne vordersten Zustand aus Warteschlange
        b. Wenn dieser Zustand das Ziel ist:
             - Gib Loesung zurueck
        c. Sonst:
             - Fuer jeden Nachbarn dieses Zustands:
                 * Wenn Nachbar noch nicht besucht:
                     - Markiere als besucht
                     - Fuege Nachbar hinten zur Warteschlange hinzu
    5. Wenn Warteschlange leer und kein Ziel gefunden:
        - Gib "Keine Loesung" zurueck

In Python-aehnlicher Syntax:

def bfs(start, ziel, hole_nachbarn):
    warteschlange = [start]
    besucht = [start]
    
    while warteschlange:
        aktuell = warteschlange.pop(0)  # Entferne vorn
        
        if aktuell == ziel:
            return "Ziel gefunden!"
        
        for nachbar in hole_nachbarn(aktuell):
            if nachbar not in besucht:
                besucht.add(nachbar)
                warteschlange.append(nachbar)  # Fuege hinten hinzu
    
    return "Keine Loesung gefunden"

---

Tiefensuche (DFS - Depth-First Search)

Beschreibung der Suchstrategie

Tiefensuche erkundet den Zustandsraum, indem sie so tief wie moeglich in einen Zweig geht, bevor sie zurueckkehrt und einen anderen Zweig erkundet.

Kernidee: Gehe so tief wie moeglich entlang jedes Zweigs, bevor du zurueckgehst.

Datenstruktur: DFS verwendet einen Stapel (Stack) - nach dem LIFO-Prinzip (Last In, First Out). Neue Zustaende werden oben eingefuegt und oben entfernt.

Eigenschaften:

• Vollstaendig: Nicht immer! Kann in unendlichen Zweigen steckenbleiben
• Optimal: Nein - findet eine Loesung, nicht notwendigerweise die kuerzeste
• Speicherkomplexitaet: O(bd) - benoetigt weniger Speicher als BFS

Beispiel: Labyrinth

Gleiches Labyrinth wie oben:

S . . Z
. X . .

DFS-Ablauf:

1. Schritt 1: Stapel = [S], Besucht = [S]

   • Entferne S (von oben), pruefe: Ist es Ziel? Nein.
   • Fuege Nachbarn oben auf Stapel: (0,1) rechts von S

2. Schritt 2: Stapel = [(0,1)], Besucht = [S, (0,1)]

   • Entferne (0,1), pruefe: Ist es Ziel? Nein.
   • Fuege Nachbarn oben auf Stapel: (0,2) rechts, (1,1) unten (Wand, also nur (0,2))

3. Schritt 3: Stapel = [(0,2)], Besucht = [S, (0,1), (0,2)]

   • Entferne (0,2), pruefe: Ist es Ziel? Nein.
   • Fuege Nachbarn oben auf Stapel: (0,3) rechts, (1,2) unten

4. Schritt 4: Stapel = [(0,3), (1,2)], Besucht = [S, (0,1), (0,2), (0,3), (1,2)]

   • Entferne (0,3) (oberstes Element), pruefe: Ist es Ziel? Ja! Ziel gefunden!

Unterschied zu BFS: DFS koennte auch einen anderen Pfad nehmen, wenn die Reihenfolge der Nachbarn anders ist. DFS geht "tiefer" in einen Zweig, bevor sie andere erkundet.

Pseudocode

DFS(Start, Ziel):
    1. Erstelle leeren Stapel
    2. Fuege Start zum Stapel hinzu
    3. Markiere Start als besucht
    4. Solange Stapel nicht leer:
        a. Entferne obersten Zustand vom Stapel
        b. Wenn dieser Zustand das Ziel ist:
             - Gib Loesung zurueck
        c. Sonst:
             - Fuer jeden Nachbarn dieses Zustands:
                 * Wenn Nachbar noch nicht besucht:
                     - Markiere als besucht
                     - Fuege Nachbar oben auf Stapel hinzu
    5. Wenn Stapel leer und kein Ziel gefunden:
        - Gib "Keine Loesung" zurueck

In Python-aehnlicher Syntax:

def dfs(start, ziel, hole_nachbarn):
    stapel = [start]
    besucht = [start]
    
    while stapel:
        aktuell = stapel.pop()  # Entferne oben (letztes Element)
        
        if aktuell == ziel:
            return "Ziel gefunden!"
        
        for nachbar in hole_nachbarn(aktuell):
            if nachbar not in besucht:
                besucht.add(nachbar)
                stapel.append(nachbar)  # Fuege oben hinzu
    
    return "Keine Loesung gefunden"

---

BFS vs. DFS Vergleich

Eigenschaft	BFS	DFS
Datenstruktur	Warteschlange (FIFO)	Stapel (LIFO)
Vollstaendigkeit	Ja	Nein (in unendlichen Raeumen)
Optimalitaet	Ja (ungewichtet)	Nein
Speicherkomplexitaet	O(b^d)	O(bd)
Zeitkomplexitaet	O(b^d)	O(b^m)

Wobei b=Verzweigungsfaktor, d=Tiefe der Loesung, m=maximale Tiefe

Wann BFS verwenden:

• Kuerzester Pfad benoetigt
• Loesung ist nicht zu tief
• Genug Speicher vorhanden

Wann DFS verwenden:

• Loesung ist tief
• Viele Loesungen existieren
• Begrenzter Speicher
• Nur irgendeine Loesung benoetigt

Praktische Ueberlegungen

Unendliche Schleifen vermeiden: Immer ein besucht-Set fuehren, um zu vermeiden, dass derselbe Zustand zweimal verarbeitet wird.

Pfad rekonstruieren: Ein vorgaenger-Dictionary fuehren, das jeden Zustand auf den Zustand abbildet, der ihn entdeckt hat.

def rekonstruiere_pfad(vorgaenger, start, ziel):
    pfad = []
    aktuell = ziel
    while aktuell is not None:
        pfad.append(aktuell)
        aktuell = vorgaenger[aktuell]
    return pfad[::-1]  # Umkehren fuer start -> ziel