idw – Informationsdienst Wissenschaft

Nachrichten, Termine, Experten

Grafik: idw-Logo
Science Video Project
idw-Abo

idw-News App:

AppStore

Google Play Store



Instance:
Share on: 
11/04/2014 09:38

Mathematiker stellen neuen Rekord auf

Johannes Seiler Dezernat 8 - Hochschulkommunikation
Rheinische Friedrich-Wilhelms-Universität Bonn

    Wie lässt sich eine Rundreise durch verschiedene Städte auf dem kürzesten Weg organisieren? Darüber zerbrechen sich nicht nur Paketdienste, Handlungsreisende und Touristen den Kopf, sondern seit vielen Jahrzehnten auch Mathematiker. Eine endgültige Lösung des Problems für eine große Zahl von Orten ist noch nicht gelungen, aber Forscher der Universitäten Bonn und Grenoble haben einen Algorithmus gefunden, der mit Abstand die beste Näherung liefert. Sie berichten in der Fachzeitschrift „Combinatorica“ über ihre Ergebnisse, deren Druckausgabe nun vorliegt.

    Wie lässt sich die Reihenfolge für den Besuch mehrerer Orte so wählen, dass die gesamte Route möglichst kurz ist? „Dieses Rundreiseproblem klingt trivial, ist aber eine harte Nuss“, sagt Prof. Dr. Jens Vygen vom Forschungsinstitut für Diskrete Mathematik der Universität Bonn. Seit mehr als 60 Jahren zerbrechen sich Mathematiker darüber den Kopf – ohne es bislang gelöst zu haben. „Dieses populäre Problem hat seit Jahrzehnten eine zentrale Bedeutung für die mathematische Optimierung: Viele ursprünglich dafür entwickelte Methoden kamen später auch bei ganz anderen Problemen zum Einsatz“, erläutert sein Kollege Prof. Dr. András Sebö von der Universität Grenoble. „Es müssen beim Rundreiseproblem auch nicht unbedingt Städte sein, die durchlaufen werden sollen – sehr oft sucht man beispielsweise auch eine optimale Reihenfolge von Arbeitsschritten.“

    Komplexität überfordert sogar Supercomputer

    Mit wenigen Orten lässt sich die Aufgabe noch relativ einfach lösen, indem man die Weglängen aller möglichen Rundreisen berechnet und dann die kürzeste auswählt. Mit der Zahl der zu besuchenden Orte nimmt aber die Komplexität des Problems und damit die Rechenzeit rasch zu und überfordert dann auch die schnellsten Supercomputer. Mit 15 Städten gibt es bereits mehr als 43 Milliarden verschiedene Rundreisen, aus denen die kürzeste auszuwählen ist. Mit 18 Städten steigt die Zahl der Möglichkeiten auf über 177 Billionen an – und so weiter.

    „Viele Mathematiker vermuten, dass das Rundreiseproblem für eine große Anzahl von Städten überhaupt nicht lösbar ist“, berichten die beiden Wissenschaftler. Das ist aber noch nicht bewiesen. Bislang ist es den Mathematikern jedoch gelungen, sich mit verschiedenen Verfahren der optimalen Route anzunähern. Es handelt sich dabei um Kompromisslösungen mit dem Vorteil einer überschaubaren Rechenzeit, aber Abstrichen hinsichtlich der kürzesten Weglänge. Wenn zum Beispiel vorgegeben ist, dass die Gesamtstrecke insgesamt doppelt so lang sein darf wie die optimale Route, dann lässt sich das relativ einfach umsetzen: Zu jedem Punkt ist dann ein Hin- und Rückweg erlaubt.

    Neuer Rekord liegt beim 1,4-fachen der optimalen Strecke

    Lange Zeit hielt Nicos Christofides den Rekord: 1976 veröffentlichte er einen Algorithmus, der eine Rundreise ergab, die maximal um die Hälfte länger als die optimale Tour ist. 35 Jahre später gelang es Mathematikern aus Nordamerika erstmals, diese Annäherung im wichtigsten Spezialfall zu unterbieten, wenn auch nur um eine Winzigkeit. Nun stellen die Professoren Jens Vygen von der Universität Bonn und András Sebö von der Universität Grenoble (Frankreich) einen neuen Rekord auf: Gemeinsam beschreiben sie einen völlig neuen Algorithmus, der die bisherige Bestmarke deutlich auf das 1,4-fache der optimalen Rundreisestrecke verkürzt.

    Dabei brüteten die beiden Wissenschaftler während eines Forschungsaufenthaltes von Prof. Vygen in Grenoble gar nicht über dem Rundreiseproblem. „Wie so häufig war Zufall im Spiel“, erzählt der Mathematiker der Universität Bonn. Zusammen mit seinem Kollegen aus Frankreich ging er der Frage nach, wie sich zum Beispiel Strom- oder Telekommunikationsnetzwerke so optimieren lassen, dass es bei einem Kabelriss nicht zu einem Ausfall kommt. „Aber wie viele Mathematiker haben wir das Rundreiseproblem ständig im Hinterkopf“, berichtet Prof. Vygen. Deshalb lag es nahe, den Ansatz für das Netzwerkproblem auch auf die ähnliche Rundreisefrage anzuwenden.

    Prof. Sebö und Prof. Vygen entdeckten eine neue Struktur: die sogenannte „Schöne-Ohren-Zerlegung“. Wie bei einer Zwiebel gingen die Wissenschaftler bei der Verbindung der Orte von außen nach innen vor. „Das funktioniert nur, wenn man die richtige Zwiebelstruktur erfasst hat – und die sieht man der Landkarte mit den Straßen und Orten zunächst nicht an“, sagt Prof. Vygen. Der Algorithmus aus Bonn und Grenoble mit den bislang besten Ergebnissen für das Rundreiseproblem lässt sich nicht nur in der Logistikbranche nutzen: Zum Beispiel bei Himmelsdurchmusterungen der Astronomen ist ebenfalls die kürzeste Route von Stern zu Stern gefragt.

    Publikation: Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs, Fachjournal Combinatorica 34 (5) (2014), 597-629, online-Version vorab (DOI: 10.1007/s00493-011-2960-3)

    Kontakt für die Medien:

    Prof. Dr. Jens Vygen
    Forschungsinstitut für Diskrete
    Mathematik der Universität Bonn
    Tel. ++49 - (0)228 - 738741
    E-Mail: vygen@or.uni-bonn.de

    Prof. Dr. András Sebö
    Laboratoire G-SCOP
    Université Grenoble Alpes
    Tel. + 33 - 4 76 57 48 99
    E-Mail: Andras.Sebo@grenoble-inp.fr


    Images

    Prof. Dr. Jens Vygen vom Forschungsinstitut für Diskrete Mathematik der Universität Bonn.
    Prof. Dr. Jens Vygen vom Forschungsinstitut für Diskrete Mathematik der Universität Bonn.
    (c) Foto: Barbara Frommann/Uni Bonn
    None


    Criteria of this press release:
    Journalists, all interested persons
    Mathematics
    transregional, national
    Research results, Scientific Publications
    German


     

    Prof. Dr. Jens Vygen vom Forschungsinstitut für Diskrete Mathematik der Universität Bonn.


    For download

    x

    Help

    Search / advanced search of the idw archives
    Combination of search terms

    You can combine search terms with and, or and/or not, e.g. Philo not logy.

    Brackets

    You can use brackets to separate combinations from each other, e.g. (Philo not logy) or (Psycho and logy).

    Phrases

    Coherent groups of words will be located as complete phrases if you put them into quotation marks, e.g. “Federal Republic of Germany”.

    Selection criteria

    You can also use the advanced search without entering search terms. It will then follow the criteria you have selected (e.g. country or subject area).

    If you have not selected any criteria in a given category, the entire category will be searched (e.g. all subject areas or all countries).