A*-Pfadfindung: Wände malen, Frontier zusehen

Zeichne ein Labyrinth, schiebe von Dijkstra zu A*, und sieh zu, wie das Open Set dem Ziel nachjagt, bis der kürzeste Pfad aufleuchtet.

y26w44

Letzte Woche hat ein Naive-Bayes-Spamfilter Wörter gezählt und gewürfelt. Diese Woche macht die Maschine etwas Älteres und Schärferes: Suche. Kein Lernen aus Daten, kein Geplauder; nur eine wachsende Frontier von Möglichkeiten, bis ein Pfad da ist.

A* ist Arbeitspferd in Spielkarten, Robotik und Rätsellösern. Du hältst ein Open Set von Zellen, die sich lohnen, mit Kosten bisher plus Heuristik Richtung Ziel. Mit einer sicheren Unter-Schätzung (Manhattan auf dem Gitter) bleibt der kürzeste Pfad optimal, aber du besuchst viel weniger Zellen als bei blindem Breitensuchen. Heuristik auf null: Dijkstra, optimal, geduldig, etwas verschwenderisch. Das ist klassische symbolische KI: explizite Zustände, explizite Kosten, ein Planer wie ein KI-Agent, dessen Schlussfolgerung du siehst.

So spielst du:

  1. Labyrinth lädt jedes Mal ein neues, zufälliges Layout (nochmal klicken = neues Labyrinth), oder selbst Wände setzen (gleiche Zelle nochmal klicken = weg).
  2. Start und Ziel mit den Bearbeiten-Chips verschieben.
  3. Suche starten und Open vs. Closed beobachten; Schritt für eine Expansion.
  4. Heuristik-Gewicht von 1 (A*) auf 0 (Dijkstra) und dieselbe Karte nochmal laufen lassen.

Probier das:

  1. Auf der Standardkarte (Start in der Mitte, Ziel oben rechts) mit Heuristik 1,00 laufen: die Frontier zieht zum Ziel; Knoten expandiert merken (oft etwa 40).
  2. Ohne Wände zu ändern, Heuristik 0 und nochmal laufen: die Welle füllt mehr vom Gitter; Knoten expandiert steigen stark (oft 100+), Pfadschritte bleiben gleich.
  3. Labyrinth laden und bei 1,00 vs 0 vergleichen: Dijkstra sollte deutlich mehr Zellen expandieren als A* (oft etwa 1,5×).
  4. Ziel mit Wänden einsperren: ehrliches „kein Pfad“.

Warum das zählt

Deep Blue gewann Schach durch Millionen Positionen pro Sekunde; Expertensysteme kodifizierten Planer in Regeln, bevor neuronale Netze Mode waren. Modernes AlphaGo mischt Lernen mit Suche (Monte-Carlo-Baumsuche), aber die Intuition beginnt hier: Welt als Graph, Züge bewerten, versprechendes expandieren. A* ist die höfliche Variante, die keinen Aufwand verschwendet, wenn ein Kompass zum Ziel existiert.

Die früheren Ausgaben verpasst? Perzeptron trainieren, Markov glucksen lassen, beim Tic-Tac-Toe-Minimax verlieren, Kanten sehen, Belohnung lernen, Tokens zählen, Gradient rollen, k-Means, Netz, Attention, Bandit, ELIZA, Hopfield oder Spam zählen.

Knoten expandiert: 0 Pfadschritte: -
1.00
Bearbeiten:
Start Ziel Wand Open Set Geschlossen Pfad
A* sortiert Zellen nach bisherigen Kosten plus Schätzung zum Ziel (hier Manhattan). Heuristik auf 0: Dijkstra, optimal, aber die Welle wächst gleichmäßig, bis das Ziel zufällig dran ist.