Travelling Salesman Problem
Was das Travelling Salesman Problem ist und wie es gelöst wird, erfährst du hier und im Video dazu!
Inhaltsübersicht
Travelling Salesman Problem einfach erklärt
Das Travelling Salesman Problem (kurz TSP) ist ein Problem aus dem Bereich der Optimierung. Es besteht darin, die beste Reiseroute zwischen einer bestimmten Anzahl an Orten zu finden.
Das Problem entsteht beispielsweise, wenn ein Paketbote vier verschiedene Orte in möglichst kurzer Zeit besuchen soll. Das Ziel ist es, die schnellste Route zu finden. Zum Lösen verwendest du verschiedene Algorithmen. Dabei gibt es exakte und heuristische Lösungen:
- Exakte Lösung: Sie ist die beste von allen möglichen Routen. Jedoch nimmt der Rechenaufwand mit steigenden Orten sehr stark zu. Schon ab 15 bis 20 Orten sind mit heutiger Technik keine exakten Lösungen mehr möglich.
- Heuristische Lösung: Hierbei handelt es sich um Annäherungen. Mit ihnen kann das TSP auch für deutlich mehr Orte gelöst werden.
NP Probleme sind in der Informatik Probleme, die mit heutiger Technik praktisch nicht lösbar sind. Das Travelling Salesman Problem ist ein bekanntes NP Problem. Der Grund dafür ist die schnell ansteigende Komplexität:
Beispielsweise gibt es für 4 Städte 3·2·1 / 2 = 3 unterschiedliche Routen. Für 10 Städte sind es bereits 9·8·…·1 / 2 = 181.440 verschiedene Wege. Bei n Städten gibt es allgemein (n-1)! / 2 („!“ = Fakultät ) verschiedene Routen. Sind Hin- und Rückweg einer Strecke unterschiedlich lang, handelt es sich um (n-1)! verschiedene Routen.
Travelling Salesman Problem — grafische Darstellung
Ein Paketbote möchte jetzt die 4 Städte A, B, C und D besuchen. Um das Problem vereinfacht darzustellen, modellierst du es in einem Graphen. Dabei stellen die Punkte („Knoten“) die Städte und die Linien („Kanten“) die Wege dar.
Alle Städte werden miteinander verbunden. An die Linien schreibst du die jeweilige Reisedauer (bspw. in Minuten). Alternativ zur Reisedauer können dort auch andere Ressourcen stehen, wie: Entfernung, Kosten, Emissionen oder Kraftstoff.
Der Handlungsreisende startet bei A und möchte alle Städte anfahren und am Ende wieder in A landen. Die grüne Linie ist eine mögliche Route. Addierst du die jeweiligen Zeiten, kommst du auf 5 + 5 + 20+ 15 = 45 min.
Es gibt aber eine bessere Lösung. Folgt er der orangenen Route, benötigt er nur 40 min (15 + 10 + 5 + 10).
Gerichtete und ungerichtete Kanten
In der Realität sind die Wege in Hin- und Rückrichtung häufig verschieden lang. Das kann beispielsweise durch eine Baustelle auf einer Straßenseite vorkommen. Daher wird in gerichtete und ungerichtete Kanten (Wege) unterteilt. Bei gerichteten Kanten sind Hin- und Rückweg verschieden lang. Dagegen sind ungerichtete Kanten in beide Richtungen gleich lang.
Jetzt ist die rote Route mit einer Zeit von 5 + 5 + 10+ 15 = 35 min der schnellste Weg.
Übrigens: Kommen ungerichtete Kanten im Graphen vor, sprichst du von einem asymmetrischen Graphen. Liegen nur gerichtete Kanten vor, ist der Graph symmetrisch.
Travelling Salesman Problem — Algorithmen
Um das Travelling Salesman Problem zu lösen und die beste Route zu finden, werden verschiedene Algorithmen verwendet.
Für kleinere Probleme können exakte Lösungsalgorithmen verwendet werden. Neben der Brute-Force-Methode, die einfach alle Lösungen nacheinander ausprobiert, zählen dazu:
- der Branch-and-Bound Algorithmus
- der Held-Karp-Algorithmus
Um auch größere Probleme zu lösen, verwendest du heuristische Algorithmen. Dazu zählen unter anderem:
- der Nearest-Neighbor-Algorithmus
- der 2-Opt-Algorithmus
Die Wissenschaft versucht dabei, immer bessere Algorithmen zu finden. Ein möglicher Ansatz ist der Einsatz von künstlicher Intelligenz und Quantencomputern. Mit ihnen könnte es in Zukunft auch exakte Lösungen für deutlich mehr als 15-20 Orte geben.
Travelling Salesman Problem — häufigste Fragen
-
Was ist das Travelling Salesman Problem?
Das Travelling Salesman Problem behandelt die Frage, welche Route die schnellste ist, um alle gegebenen Orte zu besuchen. Zur Lösung gibt es aufwendige, exakte Lösungsverfahren und vereinfachte Näherungsverfahren.
-
Was ist ein Travelling Salesman Problem Beispiel?
Ein typisches Beispiel ist ein Paketbote, der fünf verschiedene Orte anfahren soll. Das Travelling Salesman Problem ist es, die beste Route zu finden.
- Wie löst man das Travelling Salesman Problem?
Das Problem wird durch exakte oder heuristische Algorithmen gelöst.
Branch-and-Bound Algorithmus
Jetzt weißt du, was das Travelling Salesman Problem ist. Um das Problem zu lösen, gibt es verschiedene Lösungsalgorithmen. Einer der Bekanntesten ist der Branch-and-Bound Algorithmus. Hier im Beitrag erfährst du, wie genau er das Problem löst.
