Funktionsweise von Navis: Wie finden sie für uns den kürzesten Weg?

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Auf dieser Wiki-Seite möchte ich euch einen sehr nützlichen und mittlerweile fast unverzichtbaren Alltagsgegenstand vorstellen: Das Navigationsgerät.

Hauptsächlich eingehen werde ich darauf, wie ein Navi für uns den kürzesten Weg von einem beliebigen Startpunkt zu unserem gewünschten Ziel findet. Ein wichtiges Schlagwort hierbei ist der sogenannte Dijkstra-Algorithmus, der speziell für das Finden des kürzesten Weges zwischen zwei Punkten entwickelt wurde.


Inhaltsverzeichnis

Einführung

Du bist unterwegs zu einem bestimmten Ziel, findest aber beim besten Willen den Weg dorthin nicht – jeder kennt dieses Problem, ob als Fahrer, Beifahrer oder auch zu Fuß. Zur Lösung dieses Problems gibt es mehrere Möglichkeiten:

Man geht in das nächstliegende Geschäft, welches Stadtpläne führt, kauft sich einen passenden Stadtplan und sucht anhand des Stadtplans (so richtig tourimäßig) nach dem richtigen Weg. Was im ersten Moment absurd klingt, war früher gang und gäbe. Diese Methode ist heute allerdings so gut wie ausgestorben, weshalb viele Leute sich irgendwie anders aus der misslichen Lage helfen wollen.

Eine andere Möglichkeit wäre, eine möglichst kompetent aussehende Person anzuvisieren und diese höflich nach dem Weg zu fragen. Das kann zum Ziel führen, doch diese Methode birgt auch einige Risiken: "Weiß die Person wirklich wovon sie redet? Oder ist sie gar nicht so kompetent wie sie aussieht? Sagte sie jetzt links oder rechts?" Ja, auch diese Methode ist nicht immer die beste...ganz davon abgesehen, dass man erstmal seinen Stolz überwinden muss…:-)

Heutzutage greift in so einer Situation so gut wie jeder nach einem Navi, sei es als App auf dem Smartphone oder ein ins Auto integriertes Navi. Man gibt seinen Standort ein (oder lässt diesen sogar mit Hilfe von GPS bestimmen) und die Adresse seines Zielortes. Dann wartet man kurz, bis das Navi den kürzesten Weg berechnet hat und folgt diesem Weg – schon ist man am Ziel.

Was so einfach klingt, erfordert äußert komplexe Technik. Ein Navi muss die Namen und die geografische Lage aller Städte, Dörfer und Straßen kennen, muss über die jeweiligen Verbindungswege Bescheid wissen und den kürzesten, schnellsten oder kostengünstigsten Weg von A nach B berechnen können. Nicht zuletzt benötigt es zur Standortbestimmung die Informationen von Satelliten, die in mehreren Tausend Kilometern Höhe um die Erde kreisen.

Im Folgenden möchte ich euch diese komplexe Technik etwas vereinfacht näher bringen.


Geschichte des Navis

Navis gibt es schon einige Zeit, im alltäglichen Gebrauch finden sie allerdings erst seit Anfang des 20. Jahrhunderts Verwendung.

Erstmals in Gebrauch genommen wurden sie im 2. Weltkrieg. Dort dienten sie zur Navigationserleichterung von Kampfflugzeugen. Mit der Zeit und der Verbesserung der Technik begann man Navis auch im "normalen" Flugverkehr zu verwenden. Dann weitete sich der Einsatz von Navis auch auf den Bereich der Schiffahrt aus. Erst in den 90ern war die Technik soweit, dass Navis auch im alltäglichen Straßenverkehr getestet und nach und nach dort etabliert wurden. Heutzutage hat fast jeder ein Navi - sei es im Auto oder als App für das Smartphone.


Orte als Knotenpunkte eines Graphen

Um zu verstehen, wie ein Navi für uns einen Weg findet, muss man sich erst einmal das Prinzip eines Graphen klar machen.

Ein Graph besteht aus Knotenpunkten und Kanten. Die Knoten sind durch die Kanten miteinander verbunden.

Ein möglicher Graph sieht folgendermaßen aus:

Graph zu Beginn

Die Knoten haben unterschiedliche Namen, in unserem Beispiel Buchstaben aus dem Alphabeth. Die Zahlen an den Kanten geben in einer bestimmten Einheit an, wie weit zwei Knoten voneinander entfernt sind. Diese Einheit kann zum Beispiel Kilometer sein, aber auch Schritte oder sogar Minuten, also eine Zeitdauer darstellen.

Man muss sich nun die Knoten eines Graphen als Orte einer Landkarte vorstellen und die Kanten als Verbindungsstraßen zwischen den jeweiligen Orten.

Der Graph gibt dann also an, welche Orte mit welchem Abstand (egal ob zeitlich oder geographisch) miteinander verbunden sind.


Mit diesem Wissen können wir uns nun schon diesem ominösen Algorithmus zuwenden, der für uns einen kürzesten Weg ausfindig machen kann :-)


Der Dijkstra-Algorithmus

Nun kommen wir also zum wichtigsten Teil des "kürzesten-Wege-Problems" - dem Dijkstra-Algorithmus.

Der Dijkstra-Algorithmus ist benannt nach seinem Entwickler, dem niederländischem Informatiker Edsger W. Dijkstra.

Da E. W. Dijkstra so ein wichtiger Mann in der Informatik war, möchte ich ihn euch ganz kurz vorstellen.


Edsger W. Dijkstra

Edsger W. Dijkstra im Jahre 2002 kurz vor seinem Tod

Edsger W. Dijkstra wurde 1930 in Rotterdam geboren und widmete sich nach seinem Schulabschluß erst einmal der Mathematik und der theoretischen Physik. Schnell entdeckte er dabei aber sein sehr großes Interesse an der Informatik und wechselte nach eingen Jahren seines Studiums gänzlich in die Fachrichtung der Informatik. Im Jahre 1959 schrieb er sogar seine Doktorarbeit im Fach Informatik, indem er für den in der Entwicklung steckenden Digital-Computer Electrologica X1 die grundlegende Software schrieb.

Trotz seiner hohen Qualifikation wollte er aber nicht Professor der Informatik werden, sondern wurde 1962 Mathematikprofessor in Eindhoven. Forschend war er in der Informatik allerdings immer noch aktiv und bekam 1972 für seine Arbeit den Turing-Award.

Im Jahre 2002 starb er in Nuenen an einem Krebsleiden.

Dijkstra gilt als der erste Informatiker der Niederlanden und ist neben dem nach ihm benannten Dijkstra-Algorithmus auch bekannt für einige andere wichtige Methoden der Informatik, so entwickelte er zum Beispiel das Prinzip der Semaphoren zur Synchronisierung von Threads.

Wer noch ein bisschen mehr über Edsger W. Dijkstra erfahren möchte, schaut am besten im Wikipedia , liest sich seine berühmtesten Zitate durch oder schaut mal hier. Dies ist eine Sammlung seiner Manuskripte und anderer Veröffentlichungen.


Das Prinzip des Dijkstra-Algorithmus

Der Dijkstra-Algorithmus funktioniert folgendermaßen:

Als Voraussetzung haben wir eine Anzahl von Knotenpunkte und von Kanten, also Verbindungen zwischen den einzelnen Knoten. Außerdem muss unser Start- und unser Zielort festgelegt sein.

Für jeden Knotenpunkt müssen wir ein paar Attribute speichern. Diese sind natürlich der Name des Knotenpunkts, die Info, ob wir den Punkt schon besucht haben, den Punkt, von dem wir zu diesem Punkt gelangt sind (also sein "Vorgänger") und mit welcher Gesamtentfernung wir den Punkt erreicht haben.

Bei den Kanten müssen wir uns ebenfalls 3 Attribute merken. Erstens natürlich die Länge der jeweiligen Kante (also die Entfernung zwischen zwei Punkten) zweitens, welche Punkte die jeweilige Kante verbindet und drittens, ob wir die Kante schon abgelaufen sind.

Start- und Zielpunkt müssen auch gesondert markiert sein.

Nun beginnen wir beim Startpunkt und gehen wie folgt vor:

Betrachte alle möglichen Kanten, die mit unserem Startpunkt verbunden sind.

1. In jedem erreichbaren Punkt setzen wir den Vorgänger auf unseren Startpunkt und schreiben

2. die Entfernung vom Start zu diesem Punkt auf - also gerade die Kantenlänge zwischen diesen beiden Punkten. Außerdem müssen wir

3. die entsprechenden Kanten als abgelaufen markieren.

Sind wir bei allen möglichen Wegen so vorgegangen, schauen wir, welcher von ihnen die kürzeste Entfernung aufweist. Diesen Knoten markieren wir nun als "besucht" und setzen ihn als unseren neuen Startpunkt.

Nun gehen wir von unserem neuen Startpunkt genauso vor wie gerade eben (Schritte 1- 3), nur dass wir natürlich die bereits abgelaufen Kanten und bereits als besucht markierten Knoten außer Acht lassen Außerdem müssen wir, um die Entfernung zu den neuen Punkten zu ermitteln, zur jeweiligen Kantenlänge noch die Entfernung zu unserem aktuellen Punkt dazu addieren.

Haben wir die Schritte alle befolgt, schauen wir uns unsere verbliebenen, noch nicht besuchten Punkte an, wählen wieder denjenigen, der die geringste Entfernung aufweist, als unseren neuen Startpunkt und markieren ihn als besucht.

Dies wiederholen wir, bis wir alle Knoten besucht haben bzw. den kürzesten Weg zu unserem Ziel gefunden haben.


Da diese Erklärung zum Dijkstra-Algorithmus sehr theoretisch und unanschaulich ist, machen wir gleich noch ein anschauliches Beispiel dazu.


Falls einige von euch schon Programmiererfahrungen haben, könnt ihr euch hier den Pseudocode zum Dijkstra-Algorithmus anschauen.


Ein Beispiel zum Dijkstra-Algorithmus

Schauen wir uns nun einmal ein konkretes Beispiel an:

Wir befinden uns im Infoland, ein fiktives Land, in dem es 6 Städte gibt: Algoberg, Bitstadt, Computerau, Datenheim, Elektroburg und Findingen. Derzeit halten wir uns in unserer Ferienresidenz in Algoberg auf, wollen demnächst aber Freunde besuchen gehen, die in Findingen wohnen. Da wir kein Navi zur Hand haben, werden wir uns den kürzesten Weg mit Hilfe des Dijkstra-Algorithmus selber heraus suchen. Die Städte sind folgendermaßen durch – mehr oder weniger gute – Straßen miteinander verbunden:

(Zur Vereinfachung sind jeweils nur die Anfangsbuchstaben angegeben, die wir im Folgenden auch verwenden werden.)

Graph zu Beginn

Die Zahlen an den Verbindungsstrecken geben jeweils die Entfernung zwischen den Orten in Kilometern an.

Um bei der Suche nicht den Überblick zu verlieren, legen wir uns eine Tabelle an, die wie folgt aussieht:

Knoten besucht Vorgänger Entfernung
A
B
C
D
E
F

In der ersten Spalte stehen unsere Knotenpunkte, die Städte A – F. In der zweiten Spalte werden wir uns markieren, ob wir die jeweilige Stadt schon besucht haben bzw. schon einen kürzesten Weg zu ihr gefunden haben. In den nächsten beiden Spalten notieren wir jeweils, von welcher Stadt wir diese erreicht haben und was für eine Entfernung wir bis hierhin zurückgelegt haben.

Am besten legt ihr euch auch so eine Tabelle an, damit ihr nicht nur mitlesen, sondern auch aktiv mitdenken könnt.

Da A unser Startpunkt ist, können wir diesen bereits als besucht kennzeichnen. A hat keinen Vorgänger und die Entfernung ist hier noch 0 km. Unsere Tabelle sieht nun also so aus:

Knoten besucht Vorgänger Entfernung
A x - 0
B
C
D
E
F

Schauen wir uns nun wieder unseren Graphen an. In diesem markieren wir nun ebenfalls A als Startpunkt und färben alle Wege, die wir von A aus gehen können, rot ein.

Graph nach 1. Schritt

Von A nach B gibt es nun einen Weg mit der Entfernung 6 km, von A nach C einen 2 km langen Weg und von A nach D müssten wir 8 km zurücklegen. Diese neuen Erkenntnisse tragen wir nun in unsere Tabelle ein. Als Vorgänger der Städte wird natürlich jeweils A eingetragen. Außerdem sehen wir gleich, dass der kürzeste Weg im Moment von A nach C ist (2 km) und markieren somit C als besucht bzw. als Stadt, zu der wir bereits einen kürzesten Weg gefunden haben.

Knoten besucht Vorgänger Entfernung
A x - 0
B A 6
C x A 2
D A 8
E
F

Wir markieren also auch in unserem Graphen C als besucht und färben die möglichen zu gehenden Wege rot ein.

Graph nach 2. Schritt

Ein möglicher Weg wäre der Weg nach B mit der gesamten Entfernung von 5 km (2 + 3 km), nach D wäre die Entfernung 6 km und nach E ganze 11 km. Uns fällt nun auf, dass wir nach B und nach D kürzere Wege gefunden haben als bisher, deshalb ersetzen wir in unserer Tabelle die jeweiligen Werte der Entfernungen und ändern auch jeweils den Vorgänger ab zu C.

Versuche mal, die neu gewonnenen Erkenntnisse in deine Tabelle einzutragen. Wenn du denkst, die richtige Lösung zu haben, kannst du hier nachschauen:



In der Tabelle konnten wir auch direkt B als besucht markieren, da die Entfernung zu B von den Entfernungen aller bisher unbesuchten Städten die kürzeste ist.

Wir sind nun also bei B und schauen uns die möglichen Wege von B an.

Graph nach 3. Schritt

Von B gibt es nur zwei mögliche Wege zu bisher unbesuchten Städten, den Weg nach E und den nach F. Nach E sind es nun insgesamt 10 km. Da dieser Weg wieder kürzer ist, als der, den wir bisher nach E gefunden hatten, ändern wir die Daten in der Tabelle ab von 11 km zu 10 km und von Vorgänger C zu Vorgänger B. Für F hatten wir bisher noch keinen Weg gefunden, deshalb tragen wir in die Tabelle die Entfernung 14 km ein (2 + 3 + 9 km) und als Vorgänger ebenfalls die Stadt B.

Versuche wieder alles einzutragen, bevor du dir die Lösung anschaust.



Mit einem Blick auf die Tabelle siehst du, dass D jetzt als bereits besucht markiert ist, also unser nächster Ausgangspunkt sein wird. Vielleicht hast du das in deiner Tabelle auch schon gemacht und hast den Algorithmus wohl schon ziemlich gut verstanden. Falls nicht, erinnere ich dich nochmal daran, dass wir - bis wir alle Städte besucht haben - immer zur nächsten bisher unbesuchten Stadt mit der geringsten Entfernung gehen und diese als neuen Ausgangspunkt wählen. In der Tabelle sieht man schnell, dass D mit nur 6 km die Stadt mit der kürzesten Entfernung ist.

Wir befinden uns nun also bei D und sehen uns wieder die möglichen Wege an.

Graph nach 4. Schritt

Nach F gibt es einen Weg mit insgesamt 13 km (kürzer als der bisherige --> in der Tabelle ersetzen!) und nach E beträgt die Distanz 11 km (kein kürzerer Weg --> nicht ersetzen).



E ist wieder als besucht markiert und somit unserer nächster Ausgangspunkt. Du weißt bestimmt warum!?

Genau, weil sie von den beiden bisher unbesuchten Städten die kürzeste Entfernung aufweisen konnte.

Graph nach 5. Schritt

Von E gibt es nun nur einen möglichen Weg und zwar den nach F. Da der Weg nur insgesamt 12 km beträgt, ersetzen wir den Wert in der Tabelle natürlich durch den neuen Wert. Vergesst nicht, auch den Vorgänger abzuändern.



Da F die einzige noch nicht besuchte Stadt war, sind wir nun am Ende unseres Algorithmus angekommen. Und wie man sieht, haben wir erfolgreich den kürzesten Weg von A nach F gefunden. Diesen können wir ganz einfach aus unserer Tabelle ablesen, indem wir - beginnend beim Ziel F - jeweils den Vorgänger ablesen und notieren und dann zu diesem Punkt wiederum den Vorgänger ablesen und notieren, bis wir am Startpunkt angekommen sind. Jetzt müssen wir die Reihenfolge nur noch umkehren und schon haben wir den kürzesten Weg von A nach F.



Falls du das Gefühl hast, noch nicht alles ganz 100%ig verstanden zu haben, kann ich dir auch noch 2 schöne Youtube-Videos empfehlen, die dir live ein Beispiel vorführen.


Dies ist ein sehr ausführliches Beispiel mit 8 verschiedenen Knotenpunkten.


Dieses Youtube-Video geht noch etwas mehr auf die Dinge ein, die für den Code des Dijkstra-Algorithmus wichtig sind.


So ich hoffe, ihr habt nun verstanden, was der Dijkstra-Algorithmus ist und wie er funktioniert.

Ein Navi arbeitet im Prinzip mit diesem Algorithmus, nur ist natürlich alles sehr viel komplexer als hier beschrieben. Darauf werde ich aber hier nicht mehr näher eingehen.


Ich hoffe, ihr hattet Spaß mit meiner Selbstlerneinheit zum Thema "Funktionsweise von Navis: Wie finden sie für uns den kürzesten Weg?" und habt einiges mitgenommen :-)