Kurs:Algorithmen und Datenstrukturen/Vorlesung/Traveling Salesman
Traveling Salesman
[Bearbeiten]Ein Problem der Graphentheorie ist das Travelling Salesman Problem, welches repräsentativ für eine sehr interessante Problemklasse steht (NP vollständige Probleme).
Gegeben ist ein Graph mit n Knoten (Städten) und m Kanten (Straßen). Alle Straßen sind mit Entfernungen versehen. Gesucht wird die kürzeste Route, die alle Städte besucht und an den Startpunkt zurückkehrt.
Gegeben sind also n Städte, eine n x n Entfernungsmatrix mit und als die Entfernung von Stadt i nach Stadt j. Dies kann eventuell den Wert ∞ besitzen. Gesucht wird eine Rundreise über alle Städte mit insgesamt minimaler Länge. Die Permutation ist gibt an, welche Stadt im i-ten Schritt besucht wird. Gesucht wird nun die Permutation mit ist minimal.
Betrachtet wird g(i,S), die Länge des kürzesten Weges von der Stadt i über jede Stadt S nach Stadt 1. Da es sich um eine Rundreise handelt, kann die Stadt 1 beliebig gewählt werden. Es gilt:
Die Rundreise wird somit von hinten aufgebaut. Die Lösung ist g(1,{2,...,n})
Algorithmus
[Bearbeiten]G wird bottom up als Array berechnet.
for i=2 to n do g[i,{}]=m_{i,1} od; //{} ist der Rückweg
for k=1 to n-2
for all S with |S|=k and 1 ∉ S do
berechne g[i,S] nach Formel; // Teillösungen bzw. Reisen
od;
berechne g[1,{2,...,n}] nach Formel //Gesamtreise
Beispiel
[Bearbeiten]Wir haben 4 Städte mit symmetrischer Entfernung. M=
i\j | 1 | 2 | 3 | 4 |
1 | 0 | 4 | 9 | 8 |
2 | 4 | 0 | 12 | 2 |
3 | 9 | 12 | 0 | 10 |
4 | 8 | 2 | 10 | 0 |
Die Initialisierung sieht wie folgt aus:
Länge 1= Rückkehr von der letzten Station nach Station 1:
g[ 2 , { } ] = 4
g[ 3 , { } ] = 9
g[ 4 , { } ] = 8
Die letzten 2 Schritte inklusive Rückkehr zur Station 1:
g[ 2 , { 3 } ] = 12 + g[3, {} ] = 12 + 9 = 21
g[ 2 , { 4 } ] = 2 + 8 = 10
g[ 3 , { 2 } ] = 12 + 4 = 16
g[ 3 , { 4 } ] = 10 + 8 = 18
g[ 4 , { 2 } ] = 2 + 4 = 6
g[ 4 , { 3 } ] = 10 + 9 = 19
Lösung: 1,2,4,3,1
Die letzten 4 Schritte, d.h. komplette Rundreise:
Die letzten 3 Schritte inklusive Rückkehr zu Station 1:
Die letzten 2 Schritte inklusive Rückkehr zur Station 1:
g[ 2 , { 3 } ] = 12 + 9 = 21
g[ 2 , { 4 } ] = 2 + 8 = 10
g[ 3 , { 2 } ] = 12 + 4 = 16
g[ 3 , { 4 } ] = 10 + 8 = 18
g[ 4 , { 2 } ] = 2 + 4 = 6
g[ 4 , { 3 } ] = 10 + 9 = 19
Analyse
[Bearbeiten]Korrektheitstheorem
[Bearbeiten]Der HK‐Algorithmus löst das TSP.
Laufzeittheorem
[Bearbeiten]Der HK‐Algorithms hat eine Laufzeit von . TSP ist ein NP‐vollständiges Problem, d.h. vermutlich existiert kein polynomieller Algorithmus.