Komplizierte Rundreise

News: Komplizierte Rundreise

In Wirtschaft und Technik gilt es häufig, lange Wege zu vermeiden. Zurückgehen ist genauso verpönt wie warten, denn es kostet nur Zeit und damit Geld. In der Mathematik und Informatik spricht man vom 'Problem des Handlungsreisenden' und meint damit die Aufgabe, eine möglichst kurze Route zu finden, die über eine gewisse Anzahl von Zwischenstationen an bestimmten Positionen führt. Ein schnelles Lösungsverfahren existiert bislang nicht. Informatiker behelfen sich mit Modellen, die sich Schritt für Schritt an eine Lösung herantasten. Nun hat ein Wissenschaftler ein neues Verfahren entwickelt, das deutlich mehr leistet als die meisten bestehenden Rechenmethoden.

Das Travelling Salesman-Problem (TSP) oder Problem des Handlungsreisenden ist ein altes Rätsel der Mathematik. Ein Reisender soll eine Rundfahrt durch n Städte unternehmen und dabei eine möglichst kurze Wegstrecke zurücklegen. Die Entfernungen zwischen den einzelnen Städten sind der Person bekannt, nur die Reihenfolge der Städte muss sie festlegen. Wählt sie eine Stadt als Startpunkt, so gibt es (n-1)! Möglichkeiten, alle anderen Städte zu besuchen und wieder zur Ausgangsstadt zurückzukehren – auch bei einer kleinen Anzahl von Städten ergibt sich so eine sehr große Zahl an Möglichkeiten. Der Reisende hätte nicht die Zeit, alle Möglichkeiten durchzuprobieren und einfach die mit dem kürzesten Weg zu nehmen. Ein schnelleres Verfahren muss her.

Die Informatik bezeichnet das Problem des Handlungsreisenden als NP-vollständig. Diese Klasse von Problemen ist bekannt dafür, dass man nahezu endlos lange Rechenzeit braucht, um sie zu lösen. Es gibt aber einen Ausweg: Ein Algorithmus ermittelt nicht die beste Lösung, sondern nur eine sehr gute, die der besten beliebig nahe kommt und diese lässt sich vergleichsweise schnell mit einem Näherungsverfahren herausfinden.

Angenommen, man hat irgendeine Lösung für das Problem – in unserem Beispiel also eine Reihenfolge der Städte –, dann geht das Verfahren von dieser aus, variiert ein wenig die Reihenfolge und überprüft, ob der neue Weg kürzer als der ursprüngliche ist. Ist das der Fall, so rechnet der Algorithmus nun mit dieser Reihenfolge weiter. So hangelt sich das Verfahren immer weiter voran und kommt schließlich zu einer guten Lösung, die sich durch Variation nicht mehr verbessern lässt, die aber nicht unbedingt die beste sein muss. Algorithmen, die nach diesem Prinzip arbeiten, heißen approximative Verfahren. Weixiong Zhang von der Washington University in St. Louis hat nun einen neuen approximativen Algorithmus vorgestellt, der die meisten anderen Verfahren weit hinter sich lässt (Verhandlungen in einer kommenden Sonderausgabe des ACM Journal of Experimental Algorithmics).

Zhang hat zusammen mit seinem Kollegen David Johnson von den AT&T Bell Labs seinen Algorithmus auf zehn bekannte Probleme des Handlungsreisenden angewendet und herausgefunden, dass er in fünf Fällen die besten Resultate lieferte. An einem der gelösten Probleme hat der Telekommunikationskonzern AT&T besonderes Interesse, denn dabei geht es um die Route, die Kassierer nehmen sollten, um Telefonhäuschen zu leeren. Der Zhang-Algorithmus lieferte verglichen mit sechs anderen Verfahren den kürzesten Weg und berücksichtigte dabei auch Einbahnstrassen. Selbst eine halbe Million Knotenpunkte – in diesem Beispiel Telefonhäuschen – konnten das Rechenmodell nicht aus dem Konzept bringen.

Auch an anderen Problemen des Handlungsreisenden erwies sich Zhangs Algorithmus als tauglich: Zeitkritische Aufgaben, wie beispielsweise der Weg von Autos durch eine Lackiererei, meisterte der Algorithmus genauso gut wie technische Probleme, bei denen beispielsweise ein Lesekopf möglichst schnell Positionen auf einem Datenträger anfahren muss. Auch für die Chipherstellung erweist sich das Rechenverfahren als brauchbar, da hier unzählige elektrische Verbindungen hergestellt werden müssen.

Siehe auch