15.11.2025
Auf dieser Seite will ich Ihnen eine echte Anwendung von Algorithmen zeigen. Wenn Sie je eine Straßenkarte im Web benutzt haben wissen Sie, dass sie eine Route von A nach B automatisch erstellen kann, mehr oder weniger überall auf der Welt. Diese Route wird von einem Graphensuche Algorithmus berechnet, von denen wir hier mehrere vorstellen.
Oben sehen Sie eine Region einer Karte vom Open Street Map Projekt. Für diese Seite nutzen wir denselben Ausschnitt mit verschiedenen Einstellungen. Klicken Sie auf ↻ um durch eine Auswahl an Karten zu rotieren, die dann in diese Seite geladen werden.
Natürlich können die bunten Karten oben nicht als Eingabe an einen Algorithmus verwendet werden, dafür müssen die Daten auf einen Graphen von Straßen und Kreuzungen reduziert werden. Diese werden oben durch Kanten und Knoten im Graphen repräsentiert. Wenn Sie den Ausschnitt oben mit dem vorherigen vergleichen, werden Sie feststellen das sie den gleichen Ausschnitt auf verschiedene Weise darstellen.
Die verwendeten Daten beinhalten Informationen über Einbahnstraßen sowie zweispurige Straßen. Obwohl die Fahrtrichtungen hier nicht angezeigt werden, werden sie doch vom Algorithmus beachtet.
Der einfachste Weg eine Route durch den Graphen zu finden ist die Breitensuche, die auch auf einer anderen Seite hier präsentiert wird. Die Breitensuche findet die kürzeste Verbindung zwischen zwei Knoten im Hinblick auf die Anzahl der Knoten dazwischen. Dies ergibt dann eben nur eine Straßenverbindung mit der geringsten Anzahl an Kreuzungen zwischen Start- and Endpunkt.
Auf dem obigen Diagram sehen Sie den Startpunkt in grün und dem Endpunkt in rot. Wenn man auf ▶ klickt um die Animation zu starten, sieht man wie die Breitensuche eine Route durch den Graphen findet. Dies ist eine uninformierte Suche, das heißt die geometrische Lage wird nicht berücksichtigt, sondern nur die Knoten und Kanten im Graphen selbst.
Die Software mit der diese Karten gemacht werden erlaubt es, Ebenen mit Informationen übereinander zu legen. Mit geringem Aufwand können dann die durchsuchten Knoten des vorherigen Diagrams über die bunte Karte von oben gelegt werden. Man beachte wie gut Straßen und Kreuzungen mit den Vektorendaten übereinstimmen.
Wo Breitensuche die kürzeste Route nach der Anzahl der Knoten definiert, geht es bei Dijkstras Algorithmus um die kürzeste Verbindung nach tatsächlicher Länge auf dem Boden. Dafür muss jede Kante in den Daten mit einer Länge in Metern versehen sein. Wenn es darum geht, den nächsten Knoten für die Suche auszuwählen, nimmt Dijkstras Algorithmus die bisherige gesammte Distanz bis zum Knoten in betracht. Dies führt zu einer subtilen Veränderung im Suchmuster, was man auf diesen Diagrammen sehen kann. Es handelt sich hierbei immer noch um eine uninformierte Suche.
Um die Performanz der Straßenkartensuche weiter zu verbessern nehmen wir hier mal eine informierte Suche: der legendäre A* Algorithmus. Er nutzt eine sogenannte Heuristik um abzuschätzen welche Knoten es sich lohnt als nächstes zu bearbeiten. Wir nutzen eine einfache aber effektive Heuristik, die Luftlinie vom aktuellen Knoten zum Zielpunkt. Obwohl eine echte Reise auf dem Boden selten die Luftlinie nimmt, hilft es dem Algorithmus die richtige Richtung einzuschlagen.
Wenn Sie dieses Panel mit dem vorherigen vergleichen, sollten Sie sehen, dass dieselbe Route gefunden wurde, wie mit Dijkstras Algorithmus. Beide Algorithmen sind auf die gleiche Weise optimal, A* ist blos effizienter.
Danke an das Open Street Map Projekt und an das Team von OpenLayers! Weitere Inhalte kann man auf der Hauptseite finden.