Anzeige
Viele Wege führen Autofahrer von Karlsruhe nach Berlin, Lyon oder Rom. Um zu wissen, welcher der schnellste ist, halten sie sich an Routenplaner – die sind aber oft noch ungenau oder zu langsam. Sie zu verbessern ist das Ziel, das Professor Dr. Peter Sanders und Dominik Schultes vom Institut für Theoretische Informatik an der Universität Karlsruhe durch praxisorientierte Algorithmenforschung verfolgen.
Das Thema ist brandaktuell und wissenschaftlich heiß umkämpft, auch wenn es sich bei der Berechnung von kürzesten Wegen um ein klassisches Problem aus der Graphentheorie handelt, zu dem bereits 1959 eine Lösungsmöglichkeit vorgestellt wurde. Die Karlsruher Algorithmen-Experten begannen im August vergangenen Jahres, an einer bis zu einer Million mal schnelleren Technik namens „Transit Node Routing“ zu arbeiten.
„Wir investieren etwas Zeit in einen einmaligen Vorberechnungsschritt, der dann alle nachfolgenden Suchanfragen deutlich beschleunigt“, sagt Schultes. Dabei spielt eine einfache Alltagsbeobachtung eine zentrale Rolle: Wenn man eine längere Reise unternimmt, verlässt man seinen Startpunkt immer über einen von wenigen in Frage kommenden wichtigen Verkehrsknotenpunkten - im Falle von Karlsruhe beispielsweise die Auffahrten der A5 und die Rheinbrücke. Von da aus schlägt man nur die jeweils relevanten Verkehrsknotenpunkte jeder beliebigen anderen weiter entfernt gelegenen Stadt oder alle Abstände zwischen diesen nach. Der neue Ansatz ermöglicht durchschnittliche Suchzeiten von etwa fünf Millionstelsekunden. Er bescherte den Karlsruher Wissenschaftlern, die in diesem Projekt mit Kollegen des Max-Planck-Institut für Informatik kooperierten, bereits den ersten Platz beim letzten Programmierwettbewerb „DIMACS Implementation Challenge“. Dabei konkurrierten die weltweit besten Routingverfahren miteinander. Internationale Beachtung findet das „Transit Node Routing“ derzeit auch durch eine Veröffentlichung in der aktuellen Ausgabe der amerikanischen „Science“, einem der weltweit angesehensten Wissenschaftsmagazine.
Ein zuvor von Sanders und Schultes entwickeltes Verfahren, in dem große Straßennetze in hierarchische Netzwerkstrukturen aufgeteilt wurden - von der kleinen, nur von lokalen Anwohnern benötigten Straße bis hin zur wichtigen Fernverkehrsverbindung - dient den Wissenschaftlern nun zur Bestimmung der relevanten Verkehrsknotenpunkte rund um einen vorgegebenen Startpunkt.
Der Vorverarbeitungsschritt für das neue Verfahren nimmt selbst nicht sehr viel Zeit in Anspruch. In mehreren Experimenten beschäftigten sich Sanders und Schultes mit der Berechnung von schnellsten Routen in Westeuropa und den USA. Beide Netze bestehen aus jeweils etwa 20 Millionen Knoten. „Um solche großen Netze zu berechnen, müssen einmalig wenige Stunden investiert werden“ so Schultes. „Doch da sich die Straßennetze schließlich nicht täglich ändern, ist diese Berechnungszeit hinnehmbar, wenn man anschließend von superschnellen Suchanfragen profitieren kann“.
Kommerzielle Systeme verwenden heute Beschleunigungstechniken, die nicht selten auf Kosten der Optimalität gehen. Das Ergebnis einer Suchanfrage wird zwar schneller präsentiert als noch vor Jahren, ist aber dafür oftmals ungenauer. Die Karlsruher Wissenschaftler wissen um die einzigartige Schnelligkeit ihres Verfahrens bei gleichbleibend hoher Genauigkeit, sehen aber noch Verbesserungsmöglichkeiten hinsichtlich der Flexibilität und der Erweiterung der Funktionalität. So arbeiten sie bereits an Methoden, die auch kurzfristige Gründe für die Änderung einer Strecke berücksichtigen, zum Beispiel einen Stau.
Nähere Informationen:
Institut für Theoretische Informatik
Universität Karlsruhe (TH)
Professor Dr. Peter Sanders
Tel. +49 721 608 7580
E-Mail sanders@ira.uka.de1
Dominik Schultes
Tel. +49 721 608-6603
E-Mail schultes@ira.uka.de
Quelle: Universität Karlsruhe (TH)
Weitere Informationen: www.uni-karlsruhe.de
Weitere Berichte zu: Routenplaner > Routing > Startpunkt > Suchanfragen
Satellite telephony is unsafe: RUB scientists break security standards
08.02.2012 | Ruhr-Universität Bochum
Berlinale setzt auf Fraunhofer IIS Expertise bei der Prüfung digitaler Filmformate
07.02.2012 | Fraunhofer-Institut für Integrierte Schaltungen IIS
Wissenschaftler beobachten, wie Oxytocin zentrale Schaltstellen im Gehirn erreicht und das Verhalten beeinflusst
Kuschelhormon, Treuehormon, Angstlöser – häufig gebrauchte Schlagwörter für das Neuropeptid Oxytocin, das sich in den letzten Jahren als ein Stoff erwiesen hat, der unser Verhalten in zentralen Regionen des Gehirns positiv beeinflussen kann. Was jedoch bisher völlig unklar war: Wie gelangt dieser Botenstoff aus dem Hypothalamus in die Hirnbereiche, die ...
Ein neuartiger Biopolymer-Film aus Lachs-DNA mit Silber-Nanopartikeln speichert Informationen kostengünstig und umweltverträglich.
Entstanden ist das organische System in fächer- und länderübergreifender Zusammenarbeit von Wissenschaftlern des DFG-Centers for Functional Nanostructures (CFN) am KIT und des Institute of Photonics Technologies an der National Tsing Hua University in Taiwan. Der DNA-Datenspeicher eignet sich unter anderem für biotechnische Anwendungen, etwa als Bauteil in Biosensoren.
Das System ...
Bildveröffentlichung der Europäischen Südsternwarte (Garching) - Mit dem Very Large Telescope (VLT) der ESO haben das bislang detailreichste Infrarotbild der Sternkinderstube des Carinanebels aufgenommen. Es zeigt vor dem spektakulären Hintergrund einer himmlischen Landschaft auf Gas, Staub und jungen Sterne zahlreiche nie gesehene Details und zählt zu den atemberaubendsten VLT-Bildern überhaupt.
Im Herzen der südlichen Milchstraße, im Sternbild Carina (Der Schiffskiel, [1]), befindet sich in einer Entfernung von etwa 7500 Lichtjahren die Sternkinderstube des Carinanebels. Diese ausgedehnte Wolke aus leuchtendem Gas und Staub ist von der Erde aus gesehen eine der nächstgelegenen Geburtsstätten massereicher Sterne.
Der Nebel beinhaltet einige der hellsten und ...
Auf der embedded world identifizieren Wissenschaftler der Fraunhofer ESK Lücken im Funkspektrum, um diese für zusätzliche Übertragungen zu nutzen.
Der in Halle 5, Stand 5-228, vorgestellte Prototyp zeigt das Funkspektrum in einem 3D-Spektrogramm, markiert die prognostizierten Lücken und prüft deren Eintreffen. Diese Methode, Cognitive Radio, verbessert die Übertragungsqualität in einem bereits vollen Funkspektrum ohne aufwändiges, statisches Koexistenzmanagement. Ziel ist eine höhere Verfügbarkeit und Zuverlässigkeit von Funk für die Automatisierung.
...
Eine Puppe in der Puppe und noch eine drumherum – so erklärt Thomas Fässler seine Moleküle: Er packt ein Atom in einem Käfig in noch ein weiteres Atomgerüst.
Mit ihrer großen Oberfläche könnten solche Strukturen als hocheffiziente Katalysatoren dienen. Wie bei dem russischen Holzspielzeug sitzt ganz innen drin ein einzelnes kleines Zinnatom, eingepackt in eine Hülle aus zwölf Kupferatomen, und diese ist nochmals umgeben von weiteren 20 Zinnatomen.
In der Arbeitsgruppe von Professor Fässler am Institut für Anorganische ...
Anzeige
Anzeige

Zwerggalaxie hat großen Hunger
08.02.2012 | Physik Astronomie
Anti-Angst-Hormon Oxytocin wird gezielt an seine Wirkorte im Gehirn transportiert
08.02.2012 | Biowissenschaften Chemie
Obstacles No Barrier to Higher Speeds for Worms
08.02.2012 | Biowissenschaften Chemie
»Jede Sekunde zählt« Erster Internationaler Kongress zu Rettungsdienstsystemen in Neu Delhi
08.02.2012 | Veranstaltungsnachrichten
Bauwerke gebrauchstauglich halten
08.02.2012 | Veranstaltungsnachrichten
Wissenschaft im Dialog-Veranstaltungen im Wissenschaftsjahr 2012
08.02.2012 | Veranstaltungsnachrichten