Subsections

• Exakte Lösungen für das TSP

Hamiltonkreis

Gibt es eine Permutation (wie oben) mit endlichen Kantenkosten. (c(x_i,x_j) = $\infty$ , falls (i,j)$\notin$E )

Exakte Lösungen für das TSP

1.

Alle Permutationen testen. (Aufwand: O (n!) )

2.

Backtracking Skizze:

Datenstruktur: Keller (Aufwand bei vollbesetztem Graph: O(n!) )

3.

Dynamic Programming Sei S $\subset$ V , i $\in$ V . g(i,S) = Länge des kürzesten Weges, der von i aus über genau alle Knoten von S läuft und beim Knoten o endet.

g(i, $\emptyset$ ) : = c(i,o)
g(i,S) : = $\min\limits_{j\in S}^{}${g(j,S$\backslash${j}) + c(i,j)},(i$\notin$S)
Lösung des TSP: g(o,V$\backslash${o})
Platzbedarf (Speicher): ${n\choose 1}+{n \choose 2}+\ldots+{n\choose n}= O(2^n)$
Laufzeit: O(2ⁿ) (gute Verbesserung gegenüber O(n!) )

4.

Branch & Bound Teillösung (Fixierung einiger Variablen) = Teilproblem T = < w,b > ( w = fixierter Weg, b = untere Schranke)
Jede Lösung, die w enthält, kostet mindestens b .
Aus T entstehen Teilprobleme durch Expansion. (w_i = w $\cup$ {e_i},T_i = < w_i,b_i > )
Wir verwalten alle Teilprobleme in einem Heap.

Eine Schranke b_i für T_i lautet: c(w) + c(e_i) + c(S) + c(f ) ( f = billigste Kante von V$\backslash$w zum Knoten o ).

Algorithmus:

     Startproblem <o, 0 > in Heap.
     Sei L₀ eine Näherungslösung.
     REPEAT
          Entferne billigste Teillösung T = <w,b > aus Heap.
          Expandiere w zu w₁ , w₂ , ... , w_k mit b₁ , b₂ , ... , b_k .
          Falls Lösung entsteht und besser als L₀ , dann ersetzen.
          Sinnvolle Teilprobleme in den Heap tun.
     UNTIL Heap enthält keine sinnvollen Probleme mehr.
     L₀ ist Lösung.

(Teil-) Problem sinnvoll $\iff$ b -Wert < bisher beste Lösung ( L₀ ).

Laufzeit: exponentiell (z.B. O((1,2)ⁿ) )