Neuer Algorithmus verbessert Annäherung an das Handlungsreisenden-Problem Rekord bei mathematischer Rundreise - scinexx | Das Wissensmagazin
Anzeige
Anzeige

Neuer Algorithmus verbessert Annäherung an das Handlungsreisenden-Problem

Rekord bei mathematischer Rundreise

Das Handlungsreisenden-Problem klingt zunächst trivial, ist aber eine überraschend harte mathematische Nuss. © Barbara Frommann/Uni Bonn

Städte-Tour mit hoher Mathematik: Ein neuer Algorithmus liefert mit Abstand die beste Näherung an das mathematische Handlungsreisenden-Problem. Bereits seit über 60 Jahren suchen Mathematiker nach einer Lösung, wie sich eine Reiseroute optimieren lässt – die Aufgabe überfordert selbst Supercomputer. Die Bestmarke für eine Annäherung haben deutsche und französische Wissenschaftler nun auf das 1,4-fache der kürzesten Wegstrecke herabgesetzt.

Wie plant man eine Rundreise durch mehrere Städte so, dass die gesamte Reiseroute möglichst kurz ist? „Dieses Rundreiseproblem klingt trivial, ist aber eine harte Nuss“, sagt Jens Vygen vom Forschungsinstitut für Diskrete Mathematik der Universität Bonn. Bei wenigen Städten auf der Route ist die Lösung einfach: Man berechnet die Wegstrecken aller möglichen Verbindungen und wählt die kürzeste aus.

Steigt aber die Zahl der Zielorte, so wächst auch die Komplexität des sogenannten Handlungsreisenden-Problems rasant an. Bei 15 Städten gibt es bereits mehr als 43 Milliarden verschiedene Rundreisen, mit 18 Städten steigt die Zahl der Möglichkeiten auf über 177 Billionen. Die dafür nötige Rechenzeit überfordert selbst die modernsten Supercomputer.

Zentrale Bedeutung für mathematische Optimierung

Dabei ist das Problem nicht nur für Touristen, Handlungsreisende oder Paketdienste interessant: „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“, erklärt András Sebő von der Universität Grenoble. Bei astronomischen Himmelsdurchmusterungen ist beispielsweise die kürzeste Strecke von Stern zu Stern gefragt. „Dieses populäre Problem hat seit Jahrzehnten eine zentrale Bedeutung für die mathematische Optimierung.“

Jens Vygen vom Forschungsinstitut für Diskrete Mathematik der Universität Bonn hilft Handlungsreisenden, den kürzesten Weg zu finden. © Barbara Frommann/Uni Bonn

Mathematiker suchen schon seit mehr als 60 Jahren nach einer einfacheren und vor allem allgemeinen Lösung – bisher ohne Erfolg. Es existieren jedoch einige Algorithmen, die sich der optimalen Route annähern. Dabei müssen die Wissenschaftler allerdings Zugeständnisse machen: Eine etwas längere Wegstrecke wird in Kauf genommen, wenn sich die Rechenzeit dadurch deutlich verkürzen lässt. Die Mindestlänge der Strecke lässt sich gut berechnen, allein für die nötige Reihenfolge der Städte ist ein hoher Rechenaufwand nötig. Der bisherige Rekordhalter lieferte Reiserouten, die um knapp die Hälfte der Strecke länger waren als der theoretische kürzest-mögliche Reiseweg.

Anzeige

Zwiebel-Algorithmus mit schönen Ohren

Sebő und Vygen haben diesen Rekord nun deutlich unterboten: Ihr neuer Algorithmus liefert das 1,4-fache der optimalen Rundreisestrecke. Möglich ist die neue Bestmarke durch ein mathematisches Verfahren namens „Schöne-Ohren-Zerlegung“. Dabei gehen die Mathematiker von außen nach innen vor, während sie die Orte miteinander verbinden. Vygen vergleicht die Zerlegung mit den Schichten einer Zwiebel: „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.“

Kurioserweise brüteten die Wissenschaftler zunächst gar nicht über dem Rundreiseproblem: „Wie so häufig war Zufall im Spiel“, sagt Vygen. Eigentlich wollten die Mathematiker Strom- und Telekommunikationsnetzwerke so optimieren, dass bei einem Kabelriss nicht das komplette System ausfällt. „Aber wie viele Mathematiker haben wir das Rundreiseproblem ständig im Hinterkopf“, so Vygen. Deshalb lag es nahe, den Ansatz für das Netzwerkproblem auch auf die ähnliche Rundreisefrage anzuwenden. (Combinatorica, 2014; doi: 10.1007/s00493-011-2960-3)

(Rheinische Friedrich-Wilhelms-Universität Bonn, 04.11.2014 – AKR)

Anzeige

In den Schlagzeilen

Diaschauen zum Thema

Dossiers zum Thema

Die wunderbare Welt des Pi - Geheimnisvolle Eigenheiten einer allgegenwärtigen Zahl

Vergessene Koryphäen - Frauen in der Wissenschaft gestern und heute

Wie viel ist eine Billion? - Überlegungen an den Grenzen unseres Zahlenverständnisses

Alan Turing - Genialer Computerpionier und tragischer Held

Auf dem Weg zum künstlichen Gehirn? - Wissenschaftler arbeiten an Computern nach dem Vorbild des Gehirns

Physik der Musik - Die Wissenschaft hinter dem schönen Klang

Rätsel der Wissenschaft - Von ungelösten Fragen, verblüffenden Funden und "Missing Links"

News des Tages

Marswind

So klingt Wind auf dem Mars

Wie die Chemotherapie dem Gehirn schadet

Weltweit erstes "Einmal"-Programm

Bioplastik: Von wegen klimafreundlich

Spanien: Einige Flüsse sind salziger als das Meer

Bücher zum Thema

Die berechnete Welt - Leben unter dem Einfluss von Algorithmen Von Nora S. Stampfl

Darf ich Zahlen? - Geschichten aus der Mathematik von Günter M. Ziegler

Top-Clicks der Woche

Anzeige
Anzeige