Wo Supercomputer scheitern: Mathematiker finden bislang beste Lösung für Rundreiseproblem

4. November 2014, 15:08
44 Postings

Neue Bestmarke liegt beim 1,4-fachen der optimalen Strecke

Das sogenannte "Problem des Handlungsreisenden", auch bekannt als "Rundreiseproblem", beschäftigt die Mathematiker bereits seit 1930. Damals erwähnte der Österreicher Karl Menger die Suche nach einer optimalen Rundreiseroute durch verschiedene Städte erstmals als mathematisches Optimierungsproblem. Eine einfache Formel dafür gibt es nicht, für komplexe Fälle mit mehreren tausend Städten kann man sich mit ausgeklügelten Rechenoperationen aber einer optimalen Lösung annähern. Nun hat eine Gruppe von Mathematikern eine Methode gefunden, die mit Abstand die beste Näherung liefert.

Harte Nuss, selbst für Supercomputer

"Dieses Rundreiseproblem klingt trivial, ist aber eine harte Nuss", meint Jens Vygen vom Forschungsinstitut für Diskrete Mathematik der Universität Bonn. 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 Jens Vygen von der Universität Bonn und András Sebö von der Universität Grenoble. Das ist aber noch nicht bewiesen. Bislang ist es den Mathematikern immerhin 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.

Bei der Entwicklung ihres Verfahrens stießen die Wissenschafter auf eine neue Struktur: die sogenannte "Schöne-Ohren-Zerlegung". Wie bei einer Zwiebel gingen die Mathematiker 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 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. (red, derStandard.at, 04.11.2014)

Share if you care.