Wie man das Problem des Handlungsreisenden blitzschnell löst
Wir zeigen, wie man vom verallgemeinerten Traveling Salesman Problem über ein asymmetrisches zu einem symmetrischen gelangt und die perfekte Lösung errechnet.
- Christian Rudolph
Beim letzten der drei Weihnachtsrätsel 2023 ging es darum, den Pinguin Chilly in einem Minispiel so übers Eis rutschen zu lassen, dass er mit möglichst wenigen Richtungswechseln alle in seinem Revier verteilten Geschenkpakete einsammelt und zum Ziel bringt. Anders als bei 2D-Spielen üblich bewegt sich Chilly nicht von Feld zu Feld, sondern rutscht so lange in eine Richtung, bis er auf ein Hindernis (Fels, Baum) trifft.
Alle Pakete einsammeln und das noch auf der kürzesten Route? Das klingt doch sehr nach dem Problem des Handlungsreisenden (Traveling Salesman Problem, TSP). Die einzusammelnden Geschenke entsprechen den Städten (Knoten) und die Anzahl der Richtungswechsel zwischen den Geschenken der Entfernung zwischen den Städten (Kanten). Chilly ist der Handlungsreisende. Weil die Distanz von einem Knoten A zu einem Knoten B eine andere sein kann als in der umgekehrten Richtung, ist der Graph gerichtet, das TSP mithin asymmetrisch. Anders als beim Hamilton-Kreis des TSP fallen im Chilly-Spielchen Start- und Endpunkt nicht in einem Knoten zusammen, sondern sind auf zwei verteilt.
- Das Santa-Chilly-Rätsel lässt sich auf ein Standardproblem der Graphentheorie abbilden: das Problem des Handlungsreisenden.
- Damit man den zugehörigen Graph einem Solver wie Concorde vorsetzen kann, sind ein paar Vorbereitungen nötig.
- Belohnt wird man mit einem idealen Ergebnis in sehr kurzer Zeit bei geringem Speicherverbrauch.
Das Problem des Handlungsreisenden geht zurück auf eine Schrift aus dem Jahre 1832: "Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Auftraege zu erhalten und eines gluecklichen Erfolgs in seinen Geschaeften gewiss zu sein – Von einem alten Commis-Voyageur". Sie behandelt das TSP zwar nicht aus mathematischer Sicht, beschreibt aber erstmals das Kernproblem: Wenn ein Handlungsreisender Kunden in einer Reihe von Städten besuchen will, dann ist es sinnvoll, die Städte in einer Rundreise auf dem kürzesten Weg abzufahren. Dabei soll er jede Stadt nur einmal ansteuern.
In der Graphentheorie nennt man dieses Szenario einen Hamilton-Kreis. Das ist ein geschlossener Graph (lies: Rundreise), der jeden Knoten (Stadt) genau einmal enthält. Den Weg von einem Knoten zu einem anderen nennt man Kante (engl. "edge"). Weil die Städte nicht einfach nur irgendwie lose zusammenhängen, sondern Straßen in einer bestimmten Richtung von einer zur anderen führen, spricht man von einem gerichteten Graph. Da der Hinweg nicht notwendigerweise identisch zum Rückweg ist, ist der Graph in einem TSP außerdem asymmetrisch. Sind alle Hin- und Rückwege gleich lang, nennt man das TSP symmetrisch.
Fies ist, dass die Geschenke nicht notwendigerweise auf Feldern (Knoten) liegen, an denen der Pinguin zum Halt kommt. Es kann sein, dass ein Geschenk "en glissant" (Anmerkung der Redaktion: Zitat des Teilnehmers Christian H.) aus bis zu vier Richtungen errutscht werden kann. Der Rutschvorgang des Pinguins kann also auf bis zu vier Feldern enden, nachdem er ein Geschenk eingesammelt hat. Deshalb kann man die Geschenke nicht ohne Weiteres als Knoten zum Graph hinzufügen, sondern muss sich etwas Clevereres einfallen lassen. Darum geht es im Wesentlichen in diesem Artikel.
Das war die Leseprobe unseres heise-Plus-Artikels "Wie man das Problem des Handlungsreisenden blitzschnell löst". Mit einem heise-Plus-Abo können sie den ganzen Artikel lesen und anhören.Immer mehr Wissen. Das digitale Abo für IT und Technik.
Mach ma' lauter: Sieben Bluetooth-Speaker für iPhone und Co. im Test
Internet aus der Steckdose: Mit Powerline das Netz in der Wohnung verteilen
Die lange Kindheit des Survival-Spiels "7 Days to Die"
Interview mit VanMoof-Chef Eliott Wertheimer: Pläne nach der Insolvenz
Kühlen mit der Wärmepumpe: Wenn die Fußbodenheizung Kälte liefert