Kurs:Algorithmen und Datenstrukturen/Vorlesung/Traveling Salesman

Traveling Salesman

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 $M=(m_{ij})$ und $m_{ij}$ 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 $\mathrm{\Pi }:\{1,...,n\}\to \{1,...,n\}d.h.\mathrm{\Pi }(i)$ gibt an, welche Stadt im i-ten Schritt besucht wird. Gesucht wird nun die Permutation $\mathrm{\Pi }$ mit $C(\mathrm{\Pi })=m_{\mathrm{\Pi }(n),\mathrm{\Pi }(1)}+\sum _{i=1}^{n-1}{m}_{\mathrm{\Pi }(i),\mathrm{\Pi }(i+1)}$ 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:

$g(i,S)=\{\begin{array}{cc}{m}_{i,1}& fallsS=\mathrm{\varnothing }\\ mi{n}_{j\in S}(m_{i,j}+g(j,S-\{j\}))& sonst\end{array}$

Die Rundreise wird somit von hinten aufgebaut. Die Lösung ist g(1,{2,...,n})

Algorithmus

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

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:

$g[1,\{2,3,4\}]=min(m_{1,2}+g[2,\{3,4\}],m_{1,3}+g[3,\{2,4\}],m_{1,4}+g[4,\{2,3\}])=25$

Die letzten 3 Schritte inklusive Rückkehr zu Station 1:

$g[2,\{3,4\}]=min(m_{2,3}+g[3,\{4\}],m_{2,4}+g[4,\{3\}])=min(12+18,2+19)=21$ $g[3,\{2,4\}]=min(m_{3,2}+g[2,\{4\}],m_{3,4}+g[4,\{2\}])=min(12+10,10+6)=16$ $g[4,\{2,3\}]=min(m_{4,2}+g[2,\{3\}],m_{4,3}+g[3,\{2\}])=min(2+21,10+16)=23$

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

Korrektheitstheorem

Der HK‐Algorithmus löst das TSP. 

Laufzeittheorem

Der HK‐Algorithms hat eine Laufzeit von $O(n^2{2}^n)$. TSP ist ein NP‐vollständiges Problem, d.h.  vermutlich existiert kein polynomieller Algorithmus.