direkt zum Inhalt zur Hauptnavigation

Haus der Wissenschaft - Kinderblog

Wie findet ein Navigationsgerät den kürzesten Weg?

Kategorie: Besserwisser, 31. Januar 2011 um 16:09

(erschienen in der Braunschweiger Zeitung am Samstag, den 29. Januar 2011)

Das-ist-das-Haus-des-Nikolaus. Jeder von Euch kennt das Rätsel, bei dem es gilt, ein Haus ohne Absetzen des Stiftes zu zeichnen. Was das Haus des Nikolaus mit der Suche nach dem kürzesten Weg zu tun hat, erklärt uns Professor Sándor Fekete, Sprecher des Departments für Informatik an der Technischen Universität Braunschweig.

Damit ein Navigationsgerät den kürzesten Weg vom Hauptbahnhof zum Haus der Wissenschaft in Braunschweig berechnen kann, bedarf es einiger Voraussetzungen: „Eine Landkarte muss digitalisiert sein: Alle wichtigen Informationen sind dann so verpackt, dass der Computer mit ihnen arbeiten kann. Dabei beschränkt man sich auf die wichtigsten Kreuzungen und deren Verbindungen, also Straßen und Hausnummern“, erklärt Fekete. Wie beim Haus des Nikolaus ergibt sich ein Gerüst aus Knotenpunkten (beim Haus sind es die Ecken) und Kanten als Verbindungslinien. In der Mathematik spricht man bei so einem Gerüst von einem Graphen. „Mit Hilfe von Graphen lassen sich die verschiedenen Wege erkennen, die zum Ziel führen“, sagt Professor Fekete.

„Jetzt muss der Computer ein anderes Problem als beim Haus des Nikolaus lösen: Unter den vielen Wegen, die vom Hauptbahnhof zum Haus der Wissenschaft führen, soll er den kürzesten herausfinden“, erläutert Fekete. Dafür braucht man erst einmal eine Idee: Man kann sich von nahe gelegenen Knoten schrittweise zu entfernteren vorarbeiten. Wenn man sich dabei die Entfernungen für bereits erreichte Knoten merkt und immer die kürzeste Möglichkeit hinzufügt, um einen neuen Knoten zu erreichen, dann breitet sich die Suche nach dem kürzesten Weg im Graphen aus wie eine Welle. Daraus kann man eine Anleitung für das Navigationssystem und sein Computerprogramm machen. In der Fachsprache nennt man so etwas einen Algorithmus. „Das Navigationsgerät bekommt eine Art Gebrauchsanweisung, mit der es den kürzesten Weg suchen kann“, erklärt Professor Fekete. „Wie schnell man den kürzesten Weg findet, hängt auch davon ab, wie groß ein Graph ist. Ein Puzzle mit 20 Teilen lässt sich schneller zusammensetzen als eines mit 5000 Teilen“, vergleicht Fekete.

Für alle, die sich noch mehr für das Thema Routenplanung interessieren, empfiehlt Professor Fekete das Buch „Das Geheimnis des kürzesten Weges. Ein mathematisches Abenteuer“ von Peter Gritzmann und René Brandenberg.

Hier seht ihr einen vereinfachten Graphen zur Bestimmung des kürzesten Weges vom Bahnhof zum Haus der Wissenschaft. Probiert euch doch mal als Navigationssystem und bestimmt den kürzesten Weg! Ist euer Ergebnis 4000 Meter, so habt ihr den kürzesten Weg richtig bestimmt.

(Autorin: Maike Kempf)

Wollt ihr auch ganz genau wissen, wie etwas funktioniert? Habt ihr eine Frage, die unsere “Besserwisser”-Wissenschaftler beantworten sollen? – Dann mailt uns an info@hausderwissenschaft.org! Die Antwort auf eure Fragen lest ihr samstags in der Braunschweiger Zeitung und etwas später in diesem Blog.

RSS-feed für Kommentare zu diesem Artikel. TrackBack-URL

Hinterlasse eine Antwort