London ist eine meiner Lieblingsstädte: Die schönen kleinen Steinhäuser, die multikulturellen Stadtviertel, die imposanten Wolkenkratzer und natürlich die gemütlichen Pubs machen die Stadt aus meiner Sicht einmalig. Das Problem an Städtetrips ist aber, dass sie ziemlich anstrengend sind. Würde man im Voraus genau wissen, welche Orte man sich ansehen möchte, könnte man eine möglichst effiziente Route planen, die zu jedem Punkt führt und am Ende wieder zurück ans Hotel, ohne dass man unnötige Umwege macht. Auch wenn die Aufgabe einfach klingt, sind solche Probleme extrem schwer zu lösen.

Aufgaben dieser Art sind als »Problem des Handlungsreisenden« bekannt: Eine Person sucht die kürzeste Route, die sie genau einmal durch jeden vorgegebenen Ort und dann wieder zum Ausgangspunkt zurückführt. Statt der kürzesten Route kann man natürlich auch nach der schnellsten Route suchen, was gerade für Kurier- und Lieferdienste wichtig ist.

Aber zurück zu einem einfacheren Beispiel: Angenommen, Sie möchten an einem Abend von Ihrem Londoner Hotel aus Ihre vier Lieblingspubs besuchen und dann wieder zurückkehren. Wie finden Sie die optimale Route für den Abend?

Eine naheliegende Möglichkeit besteht darin, zunächst die Längen aller möglichen Rundwege zu bestimmen und dann den kürzesten zu wählen. Auf diese Weise finden Sie mit Sicherheit die optimale Route. Um die verschiedenen Rundwege zu bestimmen, markiert man die vier Pubs und das Hotel auf einer Karte und zeichnet eine mögliche Route ein. Auf einer zweiten Karte trägt man wieder die fünf Orte ein und verzeichnet einen zweiten Rundweg und so weiter. Da Sie aber nicht über mehrere Karten verfügen, auf denen man herumkritzeln kann, hilft es, das Problem zu abstrahieren.

Graphentheorie hilft bei der Planung einer Kneipentour

Dabei kann man sich an der Art und Weise orientieren, wie ein U-Bahn-Netz dargestellt wird. Die darin verzeichneten Haltestellen und Verbindungen entsprechen nicht wirklich ihrer geografischen Lage. Für die Kneipentour kann man ähnlich vorgehen: Sie können die vier Pubs und das Hotel zum Beispiel durch fünf kreisförmig angeordnete Punkte darstellen. Dann kann man jeden Punkt mit jedem anderen verbinden und entlang der Linien die Distanz eintragen, die zwischen den beiden Orten liegt. Das Ergebnis ist dann ein so genannter Graph, eine Sammlung von Punkten, die durch Kanten verbunden sind.

Hat man eine Route ausgewählt, muss man also nur die Entfernungen zu den zugehörigen Verbindungen addieren und erhält dann die Länge des entsprechenden Rundwegs. Indem sie die Längen aller Rundwege miteinander vergleichen, können sie die kürzeste Route ermitteln. Statt mit Distanzen könnte man die Kanten auch mit Zeiten versehen, die angeben, wie lange es dauert, von einem Ort zum nächsten zu kommen. Damit würde man die zurückgelegte Zeit für eine Route berechnen. Aber wie viele mögliche Rundwege gibt es überhaupt?

Von Ihrem Hotel aus haben Sie vier Kneipen zur Auswahl, die Sie ansteuern können. Wenn Sie sich für eine davon entschieden haben, bleiben für den nächsten Besuch noch drei Kneipen zur Auswahl, anschließend noch zwei und als Letztes bleibt nur noch eine übrig, die Sie ansteuern, bevor Sie sich wieder auf den Heimweg zu Ihrem Hotel machen. Das heißt, insgesamt gibt es: 4 · 3 · 2 · 1 = 24 verschiedene Routen. Das ist eine ganze Menge! Aber wenn Sie genau hinsehen, werden Sie feststellen, dass man jeden Rundweg in zwei Richtungen ablaufen kann. Sprich: Wenn man vom Hotel zu Pub A, B, C, D und wieder zum Hotel läuft, entspricht das derselben Route, wie wenn man vom Hotel zu Pub D, C, B, A und wieder zum Hotel läuft. In der obigen Rechnung wurde also jede Route doppelt gezählt. Demnach gibt es bloß ½ · 4 · 3 · 2 · 1 = 12 unterschiedliche Rundwege für die beschriebene Kneipentour.

In der obigen Grafik sollen die Entfernungen der Punkte auch tatsächlich den Entfernungen innerhalb der Stadt entsprechen. In diesem Fall sieht man schon mit bloßem Auge, dass der erste Weg den kürzesten Rundweg beschreibt.

Wie Sie wahrscheinlich feststellen, ist die Aufgabe recht mühselig: Um die kürzeste Route zu finden, muss man zunächst die Entfernungen zwischen alle Punktepaaren kennen, dann alle möglichen Rundwege finden und für jeden davon die zurückgelegte Distanz berechnen. Und nun stellen Sie sich vor, dass Sie nicht nur vier Pubs abklappern wollen, sondern als DHL-Fahrer etwa 50 Stopps anfahren. Prinzipiell gilt: Für das Problem des Handlungsreisenden mit n Haltepunkten gibt es insgesamt ½ · (n–1) · (n–2) · … · 1 mögliche Rundwege. Abgekürzt lässt sich das als ½ · (n–1)! ausdrücken. Falls ein DHL-Fahrer also 50 Stopps auf seiner Route hat – und dann wieder zurück in das Lager muss – entspricht das einer Rundreise mit n = 51. Um die kürzeste Route zu finden, muss man also die Länge von ½ · (51–1)! = 1,52·10⁶⁴ Rundwegen berechnen. Eine solche Aufgabe können nicht einmal Supercomputer in angemessener Zeit bewältigen.

Ein quasi unlösbares Problem besitzt dennoch Lösungen

Dennoch schaffen es Logistikunternehmen, sinnvolle Routen für ihre Fahrer bereitzustellen. Und vielleicht noch beeindruckender: Die Forscher um William Cook von der University of Waterloo in Kanada haben 2018 die kürzeste Route bestimmt, um alle 49 687 Pubs in Großbritannien (inklusive Nordirland) zu besuchen. Falls Sie einen Roadtrip planen: Die ganze Reise ist exakt 63 739,687 Kilometer lang – und die Forscher konnten beweisen, dass es keine Tour entlang dieser Punkte gibt, die auch nur einen Meter kürzer ist.

Das Ergebnis der Forscher war nicht nur aus computerwissenschaftlicher Sicht kompliziert – schon allein, alle Daten zu beschaffen, gestaltete sich überaus schwierig. Zunächst brauchten sie eine vollständige Liste mit allen Pubs des Landes. Schon dieser Punkt bereitete ihnen Probleme: Sie hatten im Jahr 2016 bereits eine Lösung des Problems des Handlungsreisenden für knapp 25 000 Pubs veröffentlicht – und einen regelrechten Shitstorm geerntet. In den sozialen Medien und per Mail ärgerten sich zahlreiche Personen darüber, dass ihr Pub nicht auf der Route aufzufinden war. Offenbar hatten Cook und seine Kollegen einige Kneipen übersehen. Daher nahmen sie sich der Aufgabe noch einmal an und nutzten eine Liste mit etwa doppelt so vielen Pubs, die knapp 50 000 Einträge enthält.

Als Nächstes mussten die Forscher herausfinden, wie weit die einzelnen Pubs jeweils voneinander entfernt sind. »Dafür verlassen wir uns auf den fantastischen Service von Google Maps. Fragen Sie Google nach dem kürzesten Weg vom ›The Fiddler's Elbow‹ zum ›The Bald Face Stag‹, und Maps gibt Ihnen die Länge des Fußwegs an.« Doch damit standen die Informatiker erneut vor einem Problem: Um die Entfernungen zwischen jedem Pub Großbritanniens zu bestimmen, brauchten sie 1 232 159 688 Angaben von Google. Die Website hat aber ein tägliches Limit von ein paar tausend Anfragen. Also wandten sich die Forscher direkt an das US-Unternehmen, das ihnen glücklicherweise weiterhalf.

Erst dann konnten die Forscher loslegen: Sie nutzten einen Algorithmus, der zwar nicht zwingend den optimalen, aber immerhin einen kurzen Rundweg liefert. Nach vier Tagen lieferte das Programm sechs Ergebnisse: Sechs Touren, die jeweils 63 739,687 Kilometer lang waren. Das war zwar schön und gut, aber die Forscher konnten sich nicht sicher sein, ob es nicht doch noch eine kürzere Route gibt. Sie verbrachten mehr als ein Jahr damit, um sicherzustellen, dass ihr Ergebnis wirklich optimal ist. Dafür mussten sie mit Hilfe komplizierter Algorithmen ausschließen, dass es einen Weg geben kann, der kürzer ist als jene sechs. Der letzte Schritt erforderte umgerechnet 250 Jahre an Rechenzeit auf einem herkömmlichen Laptop (die Forscher haben ihre Berechnungen natürlich auf einem Supercomputer durchgeführt).

Angesichts dessen, dass bereits eine Route mit 50 Stopps jeden modernen Supercomputer überfordert, stellt sich die Frage: Wie konnten die Forscher eine optimale Route für knapp 50 000 Pubs berechnen? Und wie planen Kuriere und Logistikunternehmen tagtäglich die Touren ihrer Fahrerinnen und Fahrer, damit sie möglichst wenig Zeit und Treibstoff verbrauchen?

Eine exakte Lösung des Problems

1962 fanden die beiden Informatiker Michael Held und Richard M. Karp sowie unabhängig von ihnen Richard Bellman einen Algorithmus für das Problem des Handlungsreisenden, der weniger als ½ · (n–1)! Rechenschritte für n Halte benötigt. Aus praktischer Sicht stellte dieser aber leider keinen richtigen Durchbruch dar, denn die Anzahl der Rechenschritte wächst noch immer um n²2ⁿ mit der Anzahl an Stopps n an. Das heißt, um die optimale Route mit 51 Halten zu berechnen, sind noch immer etwa 5,86·10¹⁸ Rechenschritte nötig. Das ist zwar deutlich weniger, als wenn man alle möglichen Routen miteinander vergleicht, aber noch immer nicht wirklich praktikabel.

Zehn Jahre später machte ein Ergebnis schließlich alle Hoffnungen auf eine effiziente Lösung zunichte: Karp konnte zeigen, dass das Problem des Handlungsreisenden NP-schwer ist – und damit nachweislich zu den komplexesten Aufgaben für Computer gehört. Dass es eine schnelle Berechnungsmethode für große n gibt, scheint damit so gut wie ausgeschlossen.

Doch das ist kein Grund aufzugeben. Selbst wenn sich das allgemeine Problem nicht effizient lösen lässt, kann man für bestimmte Anwendungsfälle trotzdem selbst für große n eine optimale Lösung finden – so wie die Forscher um Cook es mit der Tour durch die britischen Pubs vorgemacht haben.

Zudem genügt es in vielen Anwendungsszenarien, wenn man einen Rundweg findet, der nah am Optimum ist: Ob ein Kurier nun 385 Kilometer zurücklegt oder 387 Kilometer, fällt nicht allzu sehr ins Gewicht. Häufig macht uns die Realität sowieso einen Strich durch die Rechnung, wenn etwa eine Straße plötzlich gesperrt wird oder man in einem Stau landet. Wirklich optimale Routen gibt es in der Realität nicht – deshalb kann man sich auch mit Ergebnissen zufriedengeben, die nahe am jeweiligen Optimum liegen.

Einer exakten Lösung kann man sich schrittweise nähern

Ohne es zu merken, nutzen wir im Alltag ständig Näherungsverfahren, um eine Route zu planen. Versetzen Sie sich zurück in die Situation, in der Sie vier Pubs in London abklappern möchten. Wahrscheinlich würden Sie nicht die zwölf verschiedenen Rundwege aufwändig analysieren, bevor Sie von Ihrem Hotel aus starten. Stattdessen würden Sie wohl zuerst die Kneipe ansteuern, die am nächsten zu Ihrem Hotel liegt. Von dort gehen Sie dann wahrscheinlich zu der Kneipe, die wiederum am nächsten liegt und so weiter. Dieser »Nächster-Nachbar-Ansatz« kann sich als sinnvolle Methode erweisen, um eine Route zu planen. Die Tour ist durchschnittlich 25 Prozent länger als das Optimum. Das klingt zunächst recht gut. Aber wie sich herausstellt, gibt es einige Szenarien, in denen der Ansatz das schlechtmöglichste Ergebnis liefert – also den längsten Weg überhaupt.

Weil man gerade diesen Extremfall vermeiden möchte, greifen viele Anwendungen auf den Christofides-Algorithmus zurück, benannt nach dem Informatiker Nicos Christofides, der ihn 1976 entwickelt hat. Im Durchschnitt liefert er ein Ergebnis, das um nur 10 Prozent vom Optimum abweicht. Der wahre Vorteil an dieser Näherung ist allerdings, dass sie im allerschlimmsten Fall um nur 50 Prozent danebenliegt. Es gibt also eine Garantie, dass man niemals mehr als das Eineinhalbfache der optimalen Strecke zurücklegen muss.

Das Erstaunliche ist, dass sich dieser Ansatz trotz intensiver Forschung nach knapp 50 Jahren kaum verbessern ließ. Den ersten »bahnbrechenden« Fortschritt erzielte eine Arbeitsgruppe um die Informatikerin Anna Karlin im Jahr 2020, als sie einen Algorithmus präsentierte, der im schlimmsten Fall um 50 Prozent minus 10^-36 danebenliegt. Dass eine Verbesserung auf der 36. Nachkommastelle einen Durchbruch markiert, verdeutlicht, wie festgefahren die Forschung in diesem Bereich ist.

Wie findet man Näherungen, wenn man die exakte Lösung nicht kennt?

Bevor wir uns dem Christofides-Algorithmus zuwenden, kann man sich fragen, wie sich überhaupt die Qualität einer Näherung bestimmen lässt, wenn man die optimale Lösung nicht kennt. Üblicherweise würde man einen Quotienten aus einem genäherten Ergebnis und dem Optimum bilden und dadurch ermitteln, um wie viel Prozent man danebenliegt. Aber wie konnten die Forscherinnen und Forscher herausfinden, dass der Nächste-Nachbar-Ansatz durchschnittlich um 25 Prozent danebenliegt und der Christofides-Agorithmus um 10 Prozent, wenn das Optimum in den meisten Fällen nicht berechnet werden kann?

Da sich für große n meist kein exaktes Ergebnis mehr erzielen lässt, ziehen Fachleute eine andere Größe heran: Eine untere Schranke, die an das betrachtete Problem angepasst ist. Dafür nutzt man das Konzept des minimalen Spannbaums, der auch im Christofides-Algorithmus eine entscheidende Rolle spielt. Hat man eine Menge von Punkten (etwa Orte, die man entlang einer Route abklappern möchte), dann ist der minimale Spannbaum der kürzeste Graph, in dem alle Punkte verbunden sind. Das klingt zwar ähnlich zum Problem des Handlungsreisenden, aber der Spannbaum bildet keinen Rundweg. Zudem gibt es effiziente Algorithmen, die diesen schnell berechnen können.

Wie sich herausstellt, ist der minimale Spannbaum stets kürzer als eine optimale Route. Um das zu sehen, hilft folgendes Beispiel: Angenommen, Sie haben den kürzesten Rundweg gefunden. Wenn Sie eine Kante aus diesem Rundweg entfernen, sind alle Punkte verbunden, ohne eine Schleife zu bilden, Sie haben also einen Spannbaum erzeugt. Dieser muss aber nicht minimal sein. Das heißt, selbst durch Entfernen einer Verbindung der optimalen Route erhalten Sie im besten Fall bloß ein Ergebnis, das dem minimalen Spannbaum entspricht. Also ist dieser notwendigerweise kürzer als die optimale Route.

Um die untere Schranke für eine Abschätzung aber näher an das tatsächliche Ergebnis (die optimale Route) zu bringen, vergrößert man den Graphen des minimalen Spannbaums: Man entfernt einen Punkt A (egal welchen) und verbindet dann die zwei nächsten Nachbarn von A mit diesem. Das Ergebnis nennt sich ein 1-Baum. Dann nimmt man wieder den minimalen Spannbaum und wiederholt das Ganze mit einem anderen Punkt, wodurch ein anderer 1-Baum entsteht. Das macht man so lange, bis man den 1-Baum mit der größten Gesamtlänge gefunden hat: den maximalen 1-Baum. Dieser eignet sich als untere Schranke, da er höchstens so lang sein kann wie die optimale Route.

An diesen maximalen 1-Bäumen sind die Beurteilungen von Näherungsmethoden für das Problem des Handlungsreisenden angelehnt. Man vergleicht das Ergebnis der Näherung (also die Länge einer Tour, die etwa der Nächste-Nachbar-Ansatz ausgibt) mit der Länge des maximalen 1-Baums des entsprechenden Problems.

Der Christofides-Algorithmus

Der Informatiker Christofides sah in den minimalen Spannbäumen einen weiteren Vorteil: Wenn diese bereits eine optimale Lösung darstellen (sie sind der kürzeste Baum), dann könnten sie sich als Ausgangspunkt für die Suche nach einem möglichst kurzen Rundweg eignen. Im ersten Schritt des Christofides-Algorithmus erzeugt man also den minimalen Spannbaum zu den Punkten (etwa den Orten, die man besuchen möchte). Nun kann es sein, dass einige der Punkte mit nur einer Kante oder mit drei Kanten verbunden sind. Diese ungerade Anzahl von Verbindungen kann es im Problem des Handlungsreisenden nicht geben: Dort sucht man nach einem Rundweg, bei dem jeder Ort genau einmal besucht wird. Das heißt, jeder Punkt ist mit genau zwei Kanten verbunden.

Darum isoliert man im zweiten Schritt des Christofides-Algorithmus alle Punkte, die eine ungerade Anzahl an Kanten besitzen. Aus diesen isolierten Punkten bildet man nun Paare, indem man je zwei Stück miteinander verbindet – und zwar so, dass die dadurch entstehenden Verbindungen möglichst kurz sind. Dadurch ist insgesamt ein neuer Graph mit zusätzlichen Kanten entstanden. Aus diesem lässt sich dann ein Rundweg erzeugen, der jeden Punkt nur exakt einmal durchläuft – und somit einer gesuchten Route entspricht.

Der für Computer aufwändigste Rechenschritt im Christofides-Algorithmus besteht darin, die optimale Paarung der isolierten Punkte zu finden: Also jene Punkte, die eine ungerade Anzahl von Verbindungen aufweisen. Insgesamt beträgt die dafür benötigte Menge an Berechnungen etwa n²log(n). Für eine Route ausgehend vom DHL-Lager mit 50 Stopps und zurück bedeutet das: Es sind 51²·log(51) ≈ 4441 Berechnungen nötig – was ein herkömmlicher Laptop locker leisten kann.

Die Näherungslösungen lassen sich verbessern

Hat man eine Tour mit dem Christofides-Algorithmus oder einem anderen Ansatz gefunden, gibt es noch ein paar Tricks, um das Ergebnis zu verbessern. Eine Möglichkeit besteht darin, die Reihenfolge zweier Stopps zu vertauschen und zu überprüfen, ob das die Gesamtroute verkürzt: Statt (A → B → C → D → E) untersucht man, ob zum Beispiel (B → A → C → D → E) ein kürzeres Ergebnis liefert. Indem man paarweise alle Punkte miteinander vertauscht, kann man eine Route unter Umständen noch etwas verbessern.

Eine andere Möglichkeit besteht darin, sich den Graphen der berechneten Route anzusehen. Falls sich darin zwei Verbindungen kreuzen, vertauscht man deren Endpunkte, wodurch eine Route entsteht, die womöglich kürzer ist. Mit diesen und ähnlichen Methoden lassen sich die berechneten Routen weiter optimieren. Wie sich aber herausstellt, kann man in einer Art Sackgasse landen: In diesem Fall hat man einen Graphen vor sich, der sich mit den geschilderten Verbesserungsmethoden nicht weiter optimieren lässt, aber dennoch nicht der besten Lösung entspricht.

Um einer solchen »Sackgasse« zu entkommen, muss man zulassen, dass sich die Situation verschlechtert. So kann man beispielsweise Änderungen an der Route vornehmen, die den gesamten Pfad zunächst verlängern. Wenn man diese dann aber wieder schrittweise verkürzt, ist es unter Umständen möglich, das Optimum zu erreichen.

Angesichts der hohen Relevanz des Themas wurden inzwischen zahlreiche ausgeklügelte Methoden entwickelt, um optimale Routen für bestimmte Spezialfälle zu bestimmen. Mit solchen Näherungsverfahren arbeiten zum Beispiel Logistikunternehmen und Lieferdienste, um ihre Routen zu planen. Und so gelang es auch Cook und seinen Kollegen, die kürzeste Tour durch alle britischen Pubs zu berechnen.

Die Forscher haben sich aber nicht nur Kneipentouren gewidmet, sondern auch eine Wanderung entlang der 100 höchsten österreichischen Gipfel (beginnend und endend an der Universität in Wien), für die man den Forschern zufolge 27 Tage braucht. Und sie haben ebenso die optimalen Routen ermittelt, um Stationen des beliebten Handyspiels Pokémon GO in verschiedenen Städten wie New York City oder Toronto abzuklappern.

Übrigens: Cook bietet jeder Person, die eine kürzere Kneipentour durch die britischen Pubs findet, eine Belohnung von 49 687 Yen an (das ist genau die Anzahl an Kneipen, für die seine Forschungsgruppe das Problem gelöst hat). Aber bevor Sie sich an die Arbeit machen: Das Preisgeld entspricht nur etwas mehr als 300 Euro – bei derzeit umgerechnet etwa 6 Euro pro Pint werden Sie damit bei Ihrer Kneipentour kaum über ein einziges Viertel in London hinauskommen.