03.10.2008, 11:50 Uhr
Ein Turbo fürs Navi
Zwei Informatiker haben ein Verfahren entwickelt, mit dem die Routenberechnung in Navigationsgeräten um das 100-Fache beschleunigt werden kann.
Stefan Funke von der Uni Greifswald beschleunigt die Berechnung einer Route um das 100-Fache.
Die Routenplanung, also die Berechnung des kürzesten, beziehungsweise schnellsten Wegs von A nach B, ist das Herzstück eines jeden Navigationsgeräts. Stefan Funke von der Universität des norddeutschen Greifswald hat zusammen mit dem Max-Planck-Institut für Informatik einen Durchbruch bei dieser komplexen Berechnung erzielt.
Die beiden Wissenschaftler haben in dem Projekt Ultrafast Shortest-Path Queries via Transit Nodes ein Verfahren entwickelt, das um den Faktor 100 schneller als der schnellste bislang bekannte Ansatz ist. Doch das ist noch nicht alles: Die Algorithmen der beiden errechnen mit Garantie den optimalen Weg.
Dies bedeutet, dass die Wartezeit nach Eingabe von Start- und Zielort, bis das Navigationsgerät den optimalen Weg berechnet hat, statt zehn bis 20 Sekunden nur noch den Bruchteil einer Sekunde beträgt. Das hat vor allem Vorteile für die Betreiber von Routenplanern im Internet. Sie können zukünftig die gleiche Anzahl an Anfragen, für die bislang 100 Server nötig waren, mit nur einem Rechner bedienen.
