DAA - Travelling Salesman Problem

Problemstellung

Ein Reisender muss alle Städte aus einer Liste besuchen, in der Entfernungen zwischen allen Städten bekannt sind und jede Stadt nur einmal besucht werden sollte. Was ist die kürzest mögliche Route, auf der er jede Stadt genau einmal besucht und in die Ursprungsstadt zurückkehrt?

Lösung

Das Problem des reisenden Verkäufers ist das berüchtigtste Rechenproblem. Wir können den Brute-Force-Ansatz verwenden, um jede mögliche Tour zu bewerten und die beste auszuwählen. Zumn Anzahl der Eckpunkte in einem Diagramm gibt es (n - 1)! Anzahl der Möglichkeiten.

Anstelle von Brute-Force unter Verwendung eines dynamischen Programmieransatzes kann die Lösung in kürzerer Zeit erhalten werden, obwohl es keinen Polynomzeitalgorithmus gibt.

Betrachten wir ein Diagramm G = (V, E), wo V ist eine Reihe von Städten und Eist eine Reihe von gewichteten Kanten. Eine Eckee(u, v) repräsentiert diese Eckpunkte u und vsind verbunden. Abstand zwischen Scheitelpunktu und v ist d(u, v), die nicht negativ sein sollte.

Angenommen, wir haben in der Stadt angefangen 1 und nachdem wir einige Städte besucht haben, sind wir jetzt in der Stadt j. Daher ist dies eine Teiltour. Wir müssen es auf jeden Fall wissenj, da dies bestimmt, welche Städte als nächstes am bequemsten zu besuchen sind. Wir müssen auch alle bisher besuchten Städte kennen, damit wir keine von ihnen wiederholen. Daher ist dies ein geeignetes Unterproblem.

Für eine Untergruppe von Städten S Є {1, 2, 3, ... , n} das schließt ein 1, und j Є S, Lassen C(S, j) ist die Länge des kürzesten Pfades, der jeden Knoten in besucht S genau einmal ab 1 und endet bei j.

Wann |S| > 1 definieren wirC(S, 1) = ∝ da der Pfad nicht bei beginnen und enden kann 1.

Lassen Sie uns jetzt ausdrücken C(S, j)in Bezug auf kleinere Unterprobleme. Wir müssen bei beginnen1 und ende bei j. Wir sollten die nächste Stadt so auswählen, dass

$$ C (S, j) = min \: C (S - \ lbrace j \ rbrace, i) + d (i, j) \: wobei \: i \ in S \: und \: i \ neq jc ( S, j) = minC (s- \ lbrace j \ rbrace, i) + d (i, j) \: wobei \: i \ in S \: und \: i \ neq j $$

Algorithm: Traveling-Salesman-Problem 
C ({1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      C (S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

Analyse

Es gibt höchstens $ 2 ^ nn $ Unterprobleme und jedes braucht lineare Zeit, um es zu lösen. Daher beträgt die Gesamtlaufzeit $ O (2 ^ nn ^ 2) $.

Beispiel

Im folgenden Beispiel werden die Schritte zur Lösung des Problems des Handlungsreisenden veranschaulicht.

Aus dem obigen Diagramm wird die folgende Tabelle erstellt.

	1	2	3	4
1	0	10	15	20
2	5	0	9	10
3	6	13	0	12
4	8	8	9	0

S = Φ

$$ \ kleine Kosten (2, \ Phi, 1) = d (2,1) = 5 \ kleine Kosten (2, \ Phi, 1) = d (2,1) = 5 $$

$$ \ kleine Kosten (3, \ Phi, 1) = d (3,1) = 6 \ kleine Kosten (3, \ Phi, 1) = d (3,1) = 6 $$

$$ \ kleine Kosten (4, \ Phi, 1) = d (4,1) = 8 \ kleine Kosten (4, \ Phi, 1) = d (4,1) = 8 $$

S = 1

$$ \ small Kosten (i, s) = min \ lbrace Kosten (j, s - (j)) + d [i, j] \ rbrace \ small Kosten (i, s) = min \ lbrace Kosten (j, s ) - (j)) + d [i, j] \ rbrace $$

$$ \ small Cost (2, \ lbrace 3 \ rbrace, 1) = d [2,3] + Cost (3, \ Phi, 1) = 9 + 6 = 15cost (2, \ lbrace3 \ rbrace, 1) = d [2,3] + Kosten (3, \ Phi, 1) = 9 + 6 = 15 $$

$$ \ small Cost (2, \ lbrace 4 \ rbrace, 1) = d [2,4] + Cost (4, \ Phi, 1) = 10 + 8 = 18cost (2, \ lbrace4 \ rbrace, 1) = d [2,4] + Kosten (4, \ Phi, 1) = 10 + 8 = 18 $$

$$ \ small Cost (3, \ lbrace 2 \ rbrace, 1) = d [3,2] + Cost (2, \ Phi, 1) = 13 + 5 = 18cost (3, \ lbrace2 \ rbrace, 1) = d [3,2] + Kosten (2, \ Phi, 1) = 13 + 5 = 18 $$

$$ \ small Cost (3, \ lbrace 4 \ rbrace, 1) = d [3,4] + Cost (4, \ Phi, 1) = 12 + 8 = 20cost (3, \ lbrace4 \ rbrace, 1) = d [3,4] + Kosten (4, \ Phi, 1) = 12 + 8 = 20 $$

$$ \ small Cost (4, \ lbrace 3 \ rbrace, 1) = d [4,3] + Cost (3, \ Phi, 1) = 9 + 6 = 15cost (4, \ lbrace3 \ rbrace, 1) = d [4,3] + Kosten (3, \ Phi, 1) = 9 + 6 = 15 $$

$$ \ small Cost (4, \ lbrace 2 \ rbrace, 1) = d [4,2] + Cost (2, \ Phi, 1) = 8 + 5 = 13cost (4, \ lbrace2 \ rbrace, 1) = d [4,2] + Kosten (2, \ Phi, 1) = 8 + 5 = 13 $$

S = 2

$$ \ small Kosten (2, \ lbrace 3, 4 \ rbrace, 1) = \ begin {Fälle} d [2, 3] + Kosten (3, \ lbrace 4 \ rbrace, 1) = 9 + 20 = 29 \ \ d [2, 4] + Kosten (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 = 25 \ small Kosten (2, \ lbrace 3,4 \ rbrace, 1) \\\ lbrace d [ 2,3] + \ kleine Kosten (3, \ lbrace4 \ rbrace, 1) = 9 + 20 = 29d [2,4] + \ kleine Kosten (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 \ end {case} = 25 $$

$$ \ small Cost (3, \ lbrace 2, 4 \ rbrace, 1) = \ begin {case} d [3, 2] + Cost (2, \ lbrace 4 \ rbrace, 1) = 13 + 18 = 31 \ \ d [3, 4] + Kosten (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 = 25 \ small Kosten (3, \ lbrace 2,4 \ rbrace, 1) \\\ lbrace d [ 3,2] + \ kleine Kosten (2, \ lbrace4 \ rbrace, 1) = 13 + 18 = 31d [3,4] + \ kleine Kosten (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 \ end {case} = 25 $$

$$ \ small Cost (4, \ lbrace 2, 3 \ rbrace, 1) = \ begin {case} d [4, 2] + Cost (2, \ lbrace 3 \ rbrace, 1) = 8 + 15 = 23 \ \ d [4, 3] + Kosten (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 = 23 \ small Kosten (4, \ lbrace 2,3 \ rbrace, 1) \\\ lbrace d [ 4,2] + \ kleine Kosten (2, \ lbrace3 \ rbrace, 1) = 8 + 15 = 23d [4,3] + \ kleine Kosten (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 \ end {case} = 23 $$

S = 3

$$ \ small Kosten (1, \ Klammer 2, 3, 4 \ Klammer, 1) = \ begin {Fälle} d [1, 2] + Kosten (2, Klammer 3, 4 \ Klammer, 1) = 10 + 25 = 35 \\ d [1, 3] + Kosten (3, \ lbrace 2, 4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1, 4] + Kosten (4, \ lbrace 2, 3 \ rbrace, 1) = 20 + 23 = 43 = 35 Kosten (1, \ lbrace 2,3,4 \ rbrace), 1) \\ d [1,2] + Kosten (2, \ lbrace 3,4 \ rbrace , 1) = 10 + 25 = 35 \\ d [1,3] + Kosten (3, \ lbrace 2,4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1,4] + Kosten (4 , \ lbrace 2,3 \ rbrace, 1) = 20 + 23 = 43 = 35 \ end {case} $$

Der Mindestkostenpfad beträgt 35.

Beginnen Sie mit den Kosten {1, {2, 3, 4}, 1}erhalten wir den Mindestwert für d [1, 2]. Wanns = 3Wählen Sie den Pfad von 1 bis 2 (Kosten sind 10) und gehen Sie dann rückwärts. Wanns = 2erhalten wir den Mindestwert für d [4, 2]. Wählen Sie den Pfad von 2 bis 4 (Kosten sind 10) und gehen Sie dann rückwärts.

Wann s = 1erhalten wir den Mindestwert für d [4, 3]. Wenn Sie den Pfad 4 bis 3 auswählen (Kosten sind 9), gehen wir zu und gehen dann zus = ΦSchritt. Wir bekommen den Mindestwert fürd [3, 1] (Kosten sind 6).