Das Problem des reisenden Politikers
Das Vereinigte Königreich ist im Wahlkampf und der Guardian nutzt die Gelegenheit, um die Informatik mit dem Problem des reisenden Politikers zu konfrontieren. Informatiker fühlen sich an ihre Vorlesungen erinnert.
Die optimale Reiseroute durch die 50 wichtigsten Wahlkreise.
(Bild: Google / Bill Cook)
Der Guardian nimmt den englischen Wahlkampf zum Anlass, für ein Standardproblem der Informatik eine reale Anwendung zu finden. Wollen Politiker nämlich im Wahlkampf alle Wahlkreise besuchen, stellt sich die Frage, welche Reiseroute dafür am kürzesten ist. Der Informatiker erkennt bei dieser Aufgabenstellung sofort das Problem des Handlungsreisenden.
Eine Rundreise mit 50 Zielen im ganzen Königreich
Der Guardian hat für sein Beispiel die 50 wichtigsten Wahlkreise im Vereinigten Königreich bestimmt und in jedem Wahlkreis ein Rathaus, ein Stadion oder eine Burg für einen möglichen Auftritt des Politikers herausgesucht. Diese konkreten Orte wurden dann Bill Cook von der der Universität Waterloo in Kanada übergeben, damit dieser die kürzeste Reiseroute berechnet.
Bei 50 Reisezielen gibt es für einen Handlungsreisenden bzw. Politiker 49! mögliche Routen. [Update:22.4. 11:34] Natürlich sind bei ca. 6×1062 Routen viele offensichtlich schlechte dabei, aber es ist mathematisch bewiesen, dass das Problem NP-Vollständig ist und damit für den Fall, dass P≠NP (worauf vieles hindeutet), nicht deterministisch in polynomieller Zeit gelöst werden kann.[/Update] In der Praxis heißt das, dass es bei vielen Stopps auf der Route des Reisenden sehr lange dauert, um sicher die optimale Route zu finden.
Planungshilfe aus Kanada
Der kanadische Spezialist hat mit Google Maps alle 2401 Strecken zwischen zwei Wahlkreisen bestimmt und das Problem mit Concorde, seiner für das Problem des Handlungsreisenden geschaffenen Software, gelöst. Dank moderner Hardware und vielen Softwareoptimierungen hat Concorde für die Lösung auf einem Kern von Cooks i7 mit 2,3 GHz nur 0,23 Sekunden gebraucht.
Würde der Politiker statt in 50 Wahlkreise in 2500 Städte reisen, stiege die Rechenzeit für die optimale Route bereits auf einen ganzen Tag. Bei einem Besuch aller 43.000 britischer Städte und Dörfer wären bereits etwa hundert Jahre Rechenzeit notwendig. "Mit Parallelisierung kann das in einigen Monaten auf dem Netzwerk, das ich hier in Waterloo habe, berechnet werden", kommentiert Cook. Das Netzwerk könnte auf insgesamt 312 Kerne mit je 2 GHz zurückgreifen. Die Zeitangabe ist aber nur eine Schätzung. "Ohne so ein Beispiel wirklich zu berechnen, könnte ich es nicht sicher wissen", antwortete er auf die Nachfrage von heise online.
Ob jetzt alle britischen Politiker auf dieser Route die Wahlkreise bereisen oder ob das Problem des reisenden Politikers nur zukünftige Informatikvorlesungen beschäftigt, kann höchstens vermutet werden. Sicher ist, dass der Guardian ein schönes Beispiel für eines der klassischen Probleme der Informatik geliefert hat. (pmk)
