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).
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
Nach Beantwortung speichern wir deine Antwort, um Studyflix zu verbessern. Mehr dazu erfährst du in unserer Datenschutzerklärung.
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.
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.
Travelling Salesman Problem — häufigste Fragen
(ausklappen)
Travelling Salesman Problem — häufigste Fragen
(ausklappen)-
Muss man beim Travelling Salesman Problem am Ende wieder zum Startort zurückkehren?Beim klassischen Travelling Salesman Problem muss man nach dem Besuch aller Orte wieder zum Startort zurückkehren, also eine geschlossene Rundreise finden. Gesucht ist dann die Tour mit minimaler Gesamtdauer oder -distanz über alle Orte genau einmal.
-
Warum wächst die Anzahl der möglichen Touren schon bei wenigen Städten so stark?Die Anzahl wächst so stark, weil jede zusätzliche Stadt an sehr vielen Positionen in die Besuchsreihenfolge eingefügt werden kann, wodurch die Möglichkeiten faktoriell ansteigen. Bei
Städten gibt es im symmetrischen Fall 
verschiedene Touren, sonst 
.
-
Was ändert sich beim Travelling Salesman Problem, wenn die Strecke in die eine Richtung länger ist als in die andere?Wenn Hin- und Rückweg unterschiedlich lang sind, wird das TSP asymmetrisch und man modelliert die Wege als gerichtete Kanten mit unterschiedlichen Gewichten je Richtung. Dann zählt die Fahrtrichtung in der Tour, und die umgekehrte Reihenfolge derselben Orte hat oft eine andere Gesamtlänge.
-
Woran erkennt man, ob man für eine Aufgabe einen exakten Algorithmus oder eine Heuristik für das Travelling Salesman Problem verwenden soll?Man verwendet einen exakten Algorithmus, wenn die optimale Tour garantiert gefunden werden muss und die Instanz klein genug ist, um den Rechenaufwand zu schaffen. Eine Heuristik ist passend, wenn viele Orte vorkommen und schnell eine gute, aber nicht garantierte optimale Tour reicht, zum Beispiel bei Nearest Neighbor oder 2-Opt.
Optimierung verstehen
Das Travelling Salesman Problem ist ein klassisches Beispiel für Optimierung in Netzwerken und Routen. Du modellierst Probleme als Graphen, liest Gewichte an Kanten ab und suchst nach der besten Lösung unter vielen Möglichkeiten. Wenn du solche Aufgaben einordnest, erkennst du schnell den Unterschied zwischen exakten Verfahren und schnellen Näherungen. Weitere Videos dazu findest du in unserem Wirtschaftsbereich.