Suche im Graphen — Die Anfänge

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, die schon die frühesten KI-Programme antrieben: 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.

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 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).

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.

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. Im folgenden Beispiel verwenden wir einen 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.

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.

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 — dramatisch weniger als BFS.

BFS vs. DFS — Der Kompromiss

Es gibt keinen "besseren" Algorithmus — die Wahl hängt vom Problem ab.

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.