Vor einigen Wochen beschäftigten wir uns im Informatikunterricht mit dem Travelling salesman problem. Ohne näher auf die existierenden Algorithmen zum Lösen dieses Problems einzugehen lernten wir, dass es sich bei diesem Problem um ein NP-Vollständiges Problem handelt. Das TSP ist also eine Problemstellung die sich nicht in polynomieller Zeit lösen lässt. Anders ausgedrückt, lässt sich die Laufzeitkomplexität dieses Problems in Abhängigkeit von der Problemgröße n (Anzahl der Knoten bzw. Städte) nicht ausschließlich mit einem Polynom beschreiben.
Es existieren zwar einige Algorithmen die die perfekte Lösung mehr oder weniger gut annähern können und dafür nur eine zu n quadratische Komplexität besitzen (O(n²)).
Eine perfekte Lösung lässt sich bis heute praktisch aber noch nicht exakt bestimmen.Diese etwas ernüchternde Erkenntnis animierte ich selber etwas zu experimentieren.
Mit der Natur als Vorbild (genetische Algorithmen) habe ich eine kreisförmige Rundereise angestrebt.
Auch in der Natur lassen sich häufig Kugel- / Kreisförmige Formen finden, da diese die kleineste Oberfläche besitzen uns so stabiler, robuster und kompakter sind.
Auf das TSP übertragen bildet also eine kreisförmige Rundreise kürzeste Strecke. Leider liegen unsere Knoten (Städte) nicht auf einem extakten Kreis. Wir müssen also die Kreisform annähern. Ich habe damit begonnen die äußersten Knoten mit einander zu verbinden. In den weiteren Schritten werden nun die verbleibenden Städte zu der Rundreise hinzugefügt. Hier bei müssen wir nur eine Regel beachten: Die Stadt, die die Rundereise am geringsten verlängern würde, wird als erstes in die Rundreise eingebunden.
Um das ganze etwas anschaulicher zu machen habe ich zwei animierte Gif’s erstellt, welche mein Vorgehen zeigen.
Nachdem Robert mich nach der Methode zur Ermittlung der Ersten Rundreise gefragt hat (siehe Kommentar) habe ich dazu auch nochmal eine Animation erstellt:
Und so weiter. Bis man wieder am ersten Knoten ist.
Und hier nun der zweite Teil.
Man merkt sicherlich das dieser Algorithmus nicht so einfach zu implementieren wäre. Für einen Menschen ist es jedoch recht einfach diese Methode anzuwenden.
Leider kann man diesen Lösungsansatz nicht auf alle mit dem TSP verwandten Probleme anwenden. Nicht immer sind die Enfernungen zwischen den Knoten die zu minimierende Kostengröße.
Auch Robert Nitsch präsentierte uns ein paar Wochen später einen Teil seiner besonderen Lernleistung, die das TSP unter dem Gesichtspunkt der evolutionären Algorithmen untersucht.
Hallo Steffen,
das ist genial!!
Du kannst die Kosten doch einfach in eine abstrakte „Distanz“ umrechnen. Ich sehe da kein Problem.
Mich würde allerdings interessieren, wie du die „äußeren“ Knoten erkennst/ermittelst.
Die Methode ist – wie die Animation mir gezeigt hat – noch viel vielversprechender (Wortspiel) als ich zuerst gedacht hatte…
Gruß, Robert
Ok, zu dem ersten Schritt habe ich mir auch schon etwas einfallen lassen. Ich denke, dass ich das am besten wieder durch eine kleine Animation verdeutlichen werden.
gruß Steffen