Das „Problem des Handlungsreisenden“ ist weltberühmt und wurde erstmals im Jahr 1930 formuliert: Gegeben sind ein Anfangs- und ein Endpunkt und weitere Punkte, die unterwegs besucht werden sollen. Ziel ist es, die kürzeste Tour durch all diese Punkte zu finden, indem man die Reihenfolge der zu besuchenden Punkte optimiert. Anwendungen findet das Problem etwa in der Logistik oder Tourenplanung: Man kann sich beispielsweise fragen, wie man auf kürzestem Weg von Kiel nach München reist, wenn man unterwegs alle weiteren 14 Hauptstädte der deutschen Bundesländer besuchen möchte. Für sehr wenige Punkte kann man noch alle möglichen Reihenfolgen ausprobieren, doch bereits bei der Tour durch die Landeshauptstädte gibt es über 80 Milliarden theoretische Möglichkeiten.
Ein NP-schweres Problem
Das Problem, die beste Reihenfolge für eine solche Tour zu finden, ist als besonders schwer klassifiziert. Probleme, die man algorithmisch „verhältnismäßig schnell“ (in sogenannter Polynomialzeit) lösen kann, zählen zur Klasse P. Probleme, deren gegebenen Lösungen man „verhältnismäßig schnell“ überprüfen kann, zählen zur Klasse NP. Bis heute weiß man nicht, ob man solche Probleme der Klasse NP dann auch „verhältnismäßig schnell“ lösen kann, ob also P=NP gilt. Dieses sogenannte „P-NP-Problem“ gilt als eines der wichtigsten ungelösten Probleme der Informatik und wurde vom Clay Mathematics Institute in die Liste der Millennium-Probleme aufgenommen. In der Klasse NP gibt es nun ausgezeichnete, als besonders schwer anzusehende Probleme, auf die sich alle anderen Probleme dieser Klasse zurückführen lassen. Probleme, die mindestens so schwer sind wie diese ausgezeichneten Probleme, werden als „NP-schwer“ bezeichnet. Das „Problem des Handlungsreisenden“ ist ein solch „NP-schweres“ Problem.
Ein neuer Algorithmus
Für den Spezialfall, bei dem Anfangs- und Endpunkt des Weges gleich sind – es sich also um eine Rundreise handelt – fand der zypriotische Mathematiker Nicos Christofides bereits im Jahr 1976 einen effektiven Algorithmus. Die dadurch ermittelte Rundreise ist höchstens um die Hälfte länger als die optimale Tour. Diese Garantie an die Güte des Rundwegs stellt eine Art natürliche Grenze da. Es erwies sich bislang als deutlich schwieriger, diese Grenze auch für Wege mit unterschiedlichem Anfangs- und Endpunkt zu erreichen. Mit einem neuen Ansatz, einem sogenannten „rekursiven dynamischen Programm“, gelang es nun Vera Traub und Jens Vygen auch in diesem Fall beliebig nah an die natürliche Grenze zu gelangen: Die mit dem neuen Algorithmus ermittelten Touren sind höchstens x-mal so lang wie die optimale Tour, wobei x beliebig nah an 1,5 liegt. Der neue Algorithmus könnte zukünftig auch bei anderen Optimierungsaufgaben Anwendung finden.
Ausgezeichnet wurde die Arbeit am 8. Januar 2018 mit dem „Best Paper Award“ des ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA ist die weltweit führende Konferenz über diskrete Algorithmen. 180 der 547 eingereichten Arbeiten wurden in diesem Jahr angenommen, und nur zwei davon erhielten den „Best Paper Award“.
Exzellente Forschung
Die Schwerpunkte des Forschungsinstituts für Diskrete Mathematik liegen im Bereich der Diskreten Mathematik und ihrer Anwendungen, insbesondere in der Kombinatorischen Optimierung und im Chip-Design. Das Forschungsinstitut für Diskrete Mathematik ist ein Institut des Hausdorff-Zentrums für Mathematik (Hausdorff Center for Mathematics/HCM), einem Exzellenzcluster an der Universität Bonn. Hier forschen deutsche und internationale Wissenschaftler über zahlreiche Fragestellungen der Mathematik und der mathematischen Ökonomie.
Kontakt für die Medien:
Stefan Hartmann
Öffentlichkeitsarbeit und Veranstaltungen
Hausdorff-Zentrum für Mathematik
Universität Bonn
Tel. 0228/733138
E-Mail: stefan.hartmann@hcm.uni-bonn.de