Traveling Santa Problem
Wie man das Problem des Handlungsreisenden blitzschnell und ideal löst
Für das Problem des Handlungsreisenden gibt es fertige Solver wie Concorde. Concorde verarbeitet aber nur symmetrische Graphen. Am Beispiel des Santa-Chilly-Rätsels zeigen wir, wie man vom verallgemeinerten Traveling Salesman Problem über ein asymmetrisches zu einem symmetrischen gelangt und so in kurzer Zeit die perfekte Lösung errechnet.
Beim letzten der drei Weihnachtsrätsel des vergangenen Jahres in c’t 28/2023 (S. 58) 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; mehr dazu im Kasten „c’t-Rückblick auf das Santa-Chilly-Rätsel“.
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, siehe Kasten „TSP und ein Quäntchen Graphentheorie“) 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.