Tour durch 107 Städte Deutschlands Kürzeste Rundtouren: Das Problem des Handlungsreisenden Technische Universität München

Kürzeste Rundtouren

Willkommen zum TSP-Spiel!

Auf dieser Seite geht es um das sogenannte "Problem des Handlungsreisenden" oder auch "Traveling Salesman Problem".

Dieses Problem beschäftigt sich mit der Frage, wie man eine Tour durch eine bestimmte Anzahl Städte und zurück zum Ausgangspunkt planen muss, damit der insgesamt zurückgelegte Weg möglichst klein ist. Sie ist beispielsweise für vier Städte sehr leicht zu beantworten, doch bereits bei zehn Städten sind potenziell 181.440 verschiedene solcher Rundtouren möglich.

Wie schafft man es also, zwanzig oder noch mehr Städte auf dem kürzesten Weg zu besuchen?

Zu diesem Zweck wurden in den letzten Jahrzenten verschiedene Algorithmen entwickelt, die das Problem des Handlungsreisenden möglichst schnell beantworten.

Doch jetzt bist du am Zug!

Erstelle im nächsten Tab ein Spiel und versuche selbst, die kürzeste Rundtour zu finden! Anschließend kannst du dir die Lösung, sowie die Berechnungsschritte der verwendeten Algorithmen ansehen.

Viel Spaß!

Was möchtest du zuerst tun?

Tour durch 107 Städte Deutschlands