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.

 
Travelling Salesman

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.