Sobald eine Maschine eine Karte hat, kann sie planen. Eine Navigations-App, ein Lieferroboter und ein Robotaxi lösen täglich tausendfach dieselbe Grundaufgabe: die kürzeste Route von hier nach dort durch ein Netz aus Straßen oder Gängen finden. Das klingt einfach, doch eine Stadt hat Zehntausende Kreuzungen, und jede mögliche Route zu prüfen, würde ewig dauern. Die Verfahren, die das schnell lösen, gehören zu den ältesten und wichtigsten Algorithmen der Informatik.
Dies ist Teil 2 von Level 2 in unserem Lernpfad Physical AI. Wir haben das echte Straßennetz eines Teils von San Francisco, einer Stadt, in der Robotaxis zum Alltagsverkehr gehören, aus OpenStreetMap geladen und 300 zufällige Routen mit fünf verschiedenen Suchverfahren geplant. Sie erfahren, wie aus einem Stadtplan ein Graph wird, wie Dijkstras Algorithmus und A* ihn durchsuchen und warum die schnellsten Verfahren nicht immer die kürzeste Route finden.
Das Straßennetz als Graph
Für einen Computer ist ein Stadtplan ein Graph: Kreuzungen und Knicke sind Knoten, die Straßenstücke dazwischen Kanten, und jede Kante hat ein Gewicht, hier ihre Länge in Metern. Unser Ausschnitt von San Francisco, von Downtown bis zur Mission, enthält 6.170 Knoten, die alle voneinander erreichbar sind, und 187 Kilometer Straße. 46,9 % der Straßenstücke sind nur in einer Richtung befahrbar — das zwingt Routen in Umwege, die ein Fußgänger nicht bräuchte.
| Begriff | Bedeutung | In unserer Karte |
|---|---|---|
| Knoten | Ein Punkt, an dem sich die Route ändern kann | Kreuzungen und Knicke |
| Kante | Eine Verbindung zwischen zwei Knoten | Ein Straßenstück zwischen zwei Kreuzungen |
| Gewicht | Was die Nutzung einer Kante kostet | Länge in Metern |
| Einbahnkante | Eine Kante nur in einer Richtung | Fast die Hälfte aller Stücke |
| Schätzung (Heuristik) | Eine Vermutung über die Restkosten | Luftlinie zum Ziel |
Dijkstra: Suche in alle Richtungen
Dijkstras Algorithmus, 1959 veröffentlicht, arbeitet wie eine Welle, die sich vom Start ausbreitet. Er macht immer mit dem nächstgelegenen Knoten weiter, den er noch nicht abgeschlossen hat, und erreicht so jeden Knoten auf dem kürzestmöglichen Weg. Erreicht die Welle das Ziel, ist die Route garantiert die kürzeste. Der Haken: Die Welle breitet sich in alle Richtungen aus, auch vom Ziel weg.
Für unsere Routen von 1 bis 3 Kilometern prüfte Dijkstra im Median 4.132 Knoten, etwa zwei Drittel des ganzen Netzes. Auf der Beispielroute oben, 2,60 Kilometer lang bei 2,38 Kilometern Luftlinie, waren es 4.992 Knoten.
A*: ein Gespür für die Richtung
A* („A-Stern“) fügt ein Stück Wissen hinzu: eine Schätzung der restlichen Strecke. Wir nutzen die Luftlinie zum Ziel. A* macht immer mit dem Knoten weiter, bei dem bisherige Strecke plus Schätzung am kleinsten ist — die Suche neigt sich also zum Ziel. Solange die Schätzung die wahre Reststrecke nie überschätzt, und keine Straße ist kürzer als die Luftlinie, findet A* weiterhin die kürzeste Route.
Auf unseren Routen prüfte A* im Median 816 Knoten, im Mittel 76,4 % weniger als Dijkstra, und fand jedes einzelne Mal die kürzeste Route. Auf der Beispielroute brauchte es nur 352 Knoten.
Schneller, aber nicht mehr die kürzeste
Noch schneller wird A*, wenn man der Schätzung mehr vertraut. Gewichtetes A* multipliziert die Schätzung mit einem Faktor. Mit Faktor 3 prüfte die Suche im Median nur 133 Knoten, fand die kürzeste Route aber nur in 12,3 % der Fälle, mit einem Umweg von im Mittel 6,3 %. Der Extremfall ist die gierige Bestensuche, die nur der Schätzung folgt und die schon gefahrene Strecke ignoriert. Sie war genauso schnell, im Median 133 Knoten, doch ihre Routen waren im Mittel 11,7 % länger und bis zu 67,9 %: Sie hält direkt aufs Ziel zu und kann dabei in Einbahnstraßen und Sackgassen geraten, die lange Umwege erzwingen.
| Verfahren | Geprüfte Knoten (Median) | Kürzeste Route gefunden | Umweg im Mittel | Größter Umweg |
|---|---|---|---|---|
| Dijkstra | 4.132 | 100,0 % | 0,0 % | 0,0 % |
| A* (Luftlinie als Schätzung) | 816 | 100,0 % | 0,0 % | 0,0 % |
| Gewichtetes A* (Faktor 1,5) | 168 | 16,7 % | 3,0 % | 25,0 % |
| Gewichtetes A* (Faktor 3) | 133 | 12,3 % | 6,3 % | 40,3 % |
| Gierige Bestensuche | 133 | 7,7 % | 11,7 % | 67,9 % |
Daten: © OpenStreetMap-Mitwirkende, Lizenz ODbL 1.0, abgerufen am 18.10.2026; Ausschnitt San Francisco (Downtown, SoMa, Mission), 6170 Kreuzungen und Knoten, 187 km Straße, Einbahnstraßen beachtet. Unsere Auswertung: 300 zufällige Routen mit 1–3 km Luftlinie, fester Startwert; gezählt werden die abgeschlossenen Knoten.
Was echte Systeme ergänzen
Unser Experiment zeigt den Kern der Routenplanung. Echte Systeme bauen auf mehrere Arten darauf auf:
- Zeit statt Strecke. Navigation gewichtet Kanten nach erwarteter Fahrzeit, mit Tempolimits, Verkehr, Wartezeiten an Ampeln und den Mehrkosten von Linksabbiegern.
- Vorbereitung im Voraus. Navigationsdienste bereiten ihre Straßennetze so vor, dass Routen quer über einen Kontinent in Millisekunden beantwortet werden; die Suche selbst prüft dann nur wenige Hundert Knoten.
- Schichten der Planung. Ein Robotaxi plant zuerst die Route durch die Stadt, dann sein Verhalten, etwa wann es die Spur wechselt, und schließlich die genaue Bahn für die nächsten Sekunden, der die Regelung folgen muss.
- Neu planen. Ist eine Straße gesperrt oder trifft ein Roboter auf ein Hindernis, wird der Plan neu berechnet — wenn nötig viele Male pro Minute.
So haben wir die Daten ausgewertet
Wir haben alle befahrbaren Straßen eines Ausschnitts von San Francisco aus OpenStreetMap geladen, Einbahnstraßen beachtet und nur den Teil des Netzes behalten, in dem jeder Knoten von jedem anderen erreichbar ist. Mit festem Zufallsstartwert haben wir 300 zufällige Start- und Zielpunkte mit 1 bis 3 Kilometern Luftlinie gezogen und alle fünf Verfahren auf jedes Paar angewendet. Wir zählen die Knoten, die ein Verfahren abgeschlossen hat — ein Maß, das nicht von der Geschwindigkeit des Rechners abhängt. Der nächste Teil folgt einer geplanten Route auf der Straße: Wie ein selbstfahrendes Auto entlang der Bahn lenkt.