Suche im Graphen — Die Anfänge
Graphsuche: das Erste, was KI tatsächlich konnte — und immer noch nützlich ist.
Dein Handy findet die schnellste Route durch Millionen von Straßen in Millisekunden. Wie? Es durchsucht einen Graphen. Diese Technik — Probleme als Graphen zu modellieren und systematisch zu durchsuchen — ist der Ausgangspunkt der Künstlichen Intelligenz.
In diesem Artikel lernst du die zwei fundamentalen Suchstrategien, auf denen schon die frühesten KI-Programme aufbauten: die Breitensuche (BFS) und die Tiefensuche (DFS). Du kennst Graphen bereits als Datenstrukturen — jetzt werden sie zu Werkzeugen der KI.
Zustandsraum — Jedes Problem ist ein Graph
Jedes Problem mit einem definierten Anfang, einem Ziel und erlaubten Aktionen lässt sich als Graph darstellen. Diese Abstraktion ist die zentrale Idee der klassischen KI: Ob Schach, Routenplanung oder Puzzle — alles wird zum selben mathematischen Gebilde.
Definition
Zustandsraum (State Space)
Analogie
Definition
Wo die Labyrinth-Analogie bricht: Ein Labyrinth ist zweidimensional und überschaubar. Schach hat dagegen rund 10⁴⁴ legale Stellungen — ein Labyrinth von der Größe einer Galaxie.
Nimm das 8-Puzzle (3×3-Schiebepuzzle): Startzustand ist eine zufällige lösbare Anordnung der Steine 1-8, Zielzustand ist die geordnete Reihenfolge. Jeder Zug verschiebt einen Stein in das leere Feld. Der Zustandsraum hat genau 181.440 erreichbare Zustände (9!/2).
8-Puzzle
181.440
Erreichbare Zustände (9!/2)
Schach
~10 ⁴⁴
Legale Stellungen
Go
~10 ¹⁷⁰
Legale Stellungen
Achtung
Irrtum: Der Algorithmus baut den gesamten Graphen im Speicher auf
Nein. Zustände werden zur Laufzeit generiert — der Algorithmus berechnet Nachfolgezustände erst dann, wenn er sie braucht. Den gesamten Graphen für Schach (10⁴⁴ Stellungen) zu speichern, würde mehr Speicher erfordern, als auf der Erde existiert.
Breitensuche (BFS) — Ebene für Ebene
Die Breitensuche (Breadth-First Search) untersucht den Zustandsraum Schicht für Schicht: erst alle Nachbarn des Startknotens, dann deren Nachbarn, und so weiter. Sie verwendet dazu eine Warteschlange (Queue, FIFO-Prinzip — wer zuerst reinkommt, wird zuerst bearbeitet, wie an der Supermarktkasse). Um zu sehen, wie diese Suche konkret funktioniert, wechseln wir vom Labyrinth zu einem anderen Bild: Stell dir vor, du suchst einen Freund in einem Gebäude. Du prüfst erst alle Räume auf deinem Stockwerk (Ebene 0), dann gehst du ein Stockwerk höher (Ebene 1). So findest du deinen Freund garantiert auf dem nächstgelegenen Stockwerk. Wo die Analogie bricht: Ein Gebäude hat wenige Stockwerke mit konstanter Raumzahl. In einem Zustandsraum hat jede Ebene exponentiell mehr Knoten. Das folgende Beispiel nutzt diesen kleinen Graphen: A ist der Startknoten. Von A führen Kanten zu B und C. Von B gehen Kanten zu D und E. Von C führt eine Kante zu F. Von E führt ebenfalls eine Kante zu F. Ziel ist F.
Merke
BFS Schritt für Schritt
- 1. Wir starten bei A und merken uns: A ist besucht.
- 2. Wir schauen uns A an. A hat zwei Nachbarn: B und C. Beide kommen in die Warteschlange.
- 3. Als Nächstes ist B dran. B hat die Nachbarn D und E — beide in die Warteschlange.
- 4. Jetzt ist C dran. C hat einen Nachbarn: F. F kommt in die Warteschlange.
- 5. D wird geprüft (Sackgasse). E wird geprüft (F ist schon bekannt).
- 6. F ist an der Reihe — das ist unser Ziel! Weg: A → C → F, nur 2 Kanten. Das ist der kürzeste Pfad.
BFS ist vollständig (findet immer eine Lösung, falls eine existiert) und optimal (findet den kürzesten Pfad nach Kantenzahl). Der Preis: Zeit- und Speicherkomplexität O(b^d) — exponentiell.
Achtung
Irrtum: BFS ist immer die beste Wahl
BFS braucht O(b^d) Speicher — exponentiell in der Lösungstiefe. Bei Schach mit Verzweigungsfaktor b=35 und Tiefe d=80 hätte der vollständige Suchbaum etwa 35⁸⁰ Knoten. Das sind mehr Knoten, als Atome im beobachtbaren Universum existieren (10⁸⁰). BFS ist optimal, aber oft physikalisch unmöglich.
Tiefensuche (DFS) — So tief wie möglich
Die Tiefensuche (Depth-First Search) geht den entgegengesetzten Weg: Sie folgt einem Pfad so tief wie möglich, bevor sie umkehrt und Alternativen ausprobiert. Sie verwendet einen Stapel (Stack, LIFO-Prinzip — was zuletzt draufgelegt wird, wird zuerst genommen, wie bei einem Stapel Teller) oder Rekursion. Stell dir vor, du navigierst durch ein Labyrinth und biegst immer links ab. Wenn du in einer Sackgasse landest, gehst du zur letzten Kreuzung zurück und versuchst rechts. Wo die Analogie bricht: "Immer links abbiegen" funktioniert in physischen Labyrinthen (Wände verhindern Schleifen). In Graphen kann DFS ohne eine Besuchsliste endlos kreisen.
Merke
DFS Schritt für Schritt
- 1. Wir starten bei A. A ist nicht das Ziel. Wir nehmen den ersten Nachbarn: B.
- 2. B ist nicht das Ziel. Weiter zum ersten Nachbarn von B: D.
- 3. D ist nicht das Ziel und hat keine Nachbarn — Sackgasse! Zurück zu B.
- 4. B hat noch einen Nachbarn: E. Versuchen wir den.
- 5. E ist nicht das Ziel. E hat einen Nachbarn: F.
- 6. F ist das Ziel — gefunden! Weg: A → B → E → F, das sind 3 Kanten.
DFS ist nicht vollständig (kann in Zyklen hängen bleiben) und nicht optimal (findet einen Pfad, nicht den kürzesten). Dafür braucht DFS nur O(b·m) Speicher (m = maximale Suchtiefe) — dramatisch weniger als BFS.
Achtung
Irrtum: DFS findet den kürzesten Pfad
Nein. DFS findet den ersten Pfad, auf den sie stößt — und welcher das ist, hängt von der Reihenfolge der Nachbarn ab. Im Beispiel fand DFS den Pfad [A, B, E, F] mit 3 Kanten, während BFS den kürzeren Pfad [A, C, F] mit 2 Kanten fand.
BFS vs. DFS — Der Kompromiss
Es gibt keinen "besseren" Algorithmus — die Wahl hängt vom Problem ab.
Datenstruktur: Warteschlange (FIFO). Findet kürzesten Pfad: Ja. Vollständig: Ja. Speicher: O(b^d) — exponentiell. Ideal für: Kleine Zustandsräume, kürzester Pfad gefragt.
Datenstruktur: Stapel (LIFO). Findet kürzesten Pfad: Nein. Vollständig: Nein (ohne Zykluserkennung). Speicher: O(b·m) — linear. Ideal für: Tiefe Zustandsräume, wenig Speicher, Existenzprüfung.
BFS gewinnt bei kleinen Zustandsräumen, wenn der kürzeste Pfad gebraucht wird. DFS gewinnt bei tiefen Zustandsräumen, bei begrenztem Speicher oder wenn jeder beliebige Pfad genügt.
Interaktiv: BFS und DFS live vergleichen
Du hast BFS und DFS theoretisch kennengelernt. Jetzt kannst du beide Algorithmen auf demselben Graphen ausprobieren. Wechsle zwischen BFS und DFS, klicke dich Schritt für Schritt durch — und beobachte, wie unterschiedlich sie den Graphen durchlaufen.
Interaktiv: PageRank — wenn Autorität durch Links fließt
BFS und DFS durchsuchen einen Graphen, um einen Pfad zu finden. Googles PageRank nutzt ebenfalls einen Graphen, stellt aber eine andere Frage: Welcher Knoten ist der wichtigste? Die Idee ist ein Zufalls-Surfer, der Links folgt und ab und zu zu einer beliebigen Seite springt (die Dämpfung). Baue unten einen kleinen Graphen, starte die Iteration und achte auf den Aha-Moment: Ein einziger Link von einem wichtigen Knoten kann mehr wert sein als viele Links von unwichtigen.
Claude Shannon analysierte 1950 in seinem wegweisenden Aufsatz "Programming a Computer for Playing Chess" zwei Strategien: Typ A (Brute Force — alle Züge bis zu einer festen Tiefe prüfen) und Typ B (selektiv — vielversprechende Züge bevorzugen). Die Typ-A-Strategie ähnelt blinder Suche wie BFS und DFS (sie lässt keinen Zug aus und bewertet erst die Stellungen in der festen Suchtiefe), Typ B weist den Weg zu heuristischen Suchverfahren.
Die exponentielle Explosion macht blinde Suche bei realen Problemen unmöglich: Das 8-Puzzle hat 181.440 Zustände (lösbar), das 15-Puzzle schon ca. 1,05 × 10¹³ (2005 erstmals komplett per Breitensuche durchsucht: 28 Tage, 1,4 Terabyte), ein Rubik's Cube ~4,3 × 10¹⁹, Schach ~4,8 × 10⁴⁴ und Go ~2,08 × 10¹⁷⁰.
Ein kluger Kompromiss ist die iterative Tiefensuche (Iterative Deepening): Man führt die Tiefensuche wiederholt aus, jedes Mal etwas tiefer. So bekommt man die Garantien der Breitensuche bei der Speichereffizienz der Tiefensuche.
Blinde Suche (BFS/DFS) kann reale KI-Probleme nicht allein lösen. Der nächste Artikel führt Heuristiken ein — intelligente Abkürzungen, die Suche erst praktikabel machen.
Merke
Kernaussagen
- Jedes Problem mit definierten Zuständen, Übergängen und Zielen lässt sich als Zustandsraum modellieren — und damit systematisch durchsuchen.
- BFS garantiert den kürzesten Pfad, verschlingt aber exponentiell Speicher. DFS braucht minimalen Speicher, findet aber Umwege oder kreist endlos.
- Blinde Suche funktioniert bei kleinen Zustandsräumen, ist aber bei komplexen Problemen wie Schach physikalisch unmöglich — deshalb braucht KI Heuristiken (nächster Artikel).
Prüfen
Quiz: Suche im Graphen
Was repräsentiert ein "Zustand" in einem Zustandsraum?
Wähle eine Antwort
1. Was repräsentiert ein "Zustand" in einem Zustandsraum?
2. Welche Datenstruktur nutzt BFS und welche Eigenschaft garantiert sie dadurch?
3. Eine Navigations-App soll die Route mit den wenigsten Straßenabschnitten zwischen zwei Städten finden. Das Straßennetz hat 500 Kreuzungen. Welcher Algorithmus ist geeignet?
4. Ein Roboter soll prüfen, ob irgendein Pfad durch ein Labyrinth mit 1.000 Ebenen existiert. Der Speicher ist auf 1 MB begrenzt. Welcher Algorithmus ist geeigneter?
5. Du verfolgst DFS und BFS auf demselben Graphen von A nach F. BFS liefert [A, C, F] (2 Kanten), DFS liefert [A, B, E, F] (3 Kanten). Warum fand DFS einen längeren Pfad?
6. Schach hat etwa 10⁴⁴ legale Stellungen bei einem Verzweigungsfaktor von rund 35. Ein Student behauptet: "Wir brauchen einfach einen schnelleren Computer, um BFS auf Schach laufen zu lassen." Bewerte diese Aussage.
Prüfen
Verständnischeck
Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.
0 von 3 sitzen