DAA - Problema del commesso viaggiatore

Dichiarazione problema

Un viaggiatore deve visitare tutte le città da un elenco, in cui le distanze tra tutte le città sono note e ogni città dovrebbe essere visitata una sola volta. Qual è il percorso più breve possibile che visita ogni città esattamente una volta e ritorna alla città di origine?

Soluzione

Il problema del venditore ambulante è il problema computazionale più noto. Possiamo usare l'approccio della forza bruta per valutare ogni possibile tour e selezionare il migliore. Pern numero di vertici in un grafo, ci sono (n - 1)! numero di possibilità.

Invece della forza bruta utilizzando un approccio di programmazione dinamico, la soluzione può essere ottenuta in minor tempo, sebbene non esista un algoritmo temporale polinomiale.

Consideriamo un grafico G = (V, E), dove V è un insieme di città e Eè un insieme di bordi ponderati. Un bordoe(u, v) rappresenta quei vertici u e vsono collegati. Distanza tra i verticiu e v è d(u, v), che dovrebbe essere non negativo.

Supponiamo di aver iniziato in città 1 e dopo aver visitato alcune città ora siamo in città j. Quindi, questo è un tour parziale. Abbiamo sicuramente bisogno di saperej, poiché questo determinerà quali città è più conveniente visitare dopo. Abbiamo anche bisogno di conoscere tutte le città visitate finora, in modo da non ripeterne nessuna. Quindi, questo è un problema secondario appropriato.

Per un sottoinsieme di città S Є {1, 2, 3, ... , n} quello include 1, e j Є S, permettere C(S, j) essere la lunghezza del percorso più breve che visita ogni nodo in S esattamente una volta, a partire da 1 e termina a j.

Quando |S| > 1, definiamoC(S, 1) = ∝ poiché il percorso non può iniziare e finire in 1.

Ora, esprimi C(S, j)in termini di sotto-problemi minori. Dobbiamo iniziare da1 e termina a j. Dovremmo selezionare la prossima città in modo tale

$$ C (S, j) = min \: C (S - \ lbrace j \ rbrace, i) + d (i, j) \: dove \: i \ in S \: e \: i \ neq jc ( S, j) = minC (s- \ lbrace j \ rbrace, i) + d (i, j) \: dove \: i \ in S \: e \: 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)

Analisi

Ci sono al massimo $ 2 ^ nn $ sottoproblemi e ognuno richiede tempo lineare per risolverlo. Pertanto, il tempo di esecuzione totale è $ O (2 ^ nn ^ 2) $.

Esempio

Nell'esempio seguente, illustreremo i passaggi per risolvere il problema del venditore in viaggio.

Dal grafico sopra, viene preparata la seguente tabella.

	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 = Φ

$$ \ costo piccolo (2, \ Phi, 1) = d (2,1) = 5 \ costo piccolo (2, \ Phi, 1) = d (2,1) = 5 $$

$$ \ costo piccolo (3, \ Phi, 1) = d (3,1) = 6 \ costo piccolo (3, \ Phi, 1) = d (3,1) = 6 $$

$$ \ costo piccolo (4, \ Phi, 1) = d (4,1) = 8 \ costo piccolo (4, \ Phi, 1) = d (4,1) = 8 $$

S = 1

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

$$ \ small Cost (2, \ lbrace 3 \ rbrace, 1) = d [2,3] + Costo (3, \ Phi, 1) = 9 + 6 = 15cost (2, \ lbrace3 \ rbrace, 1) = d [2,3] + costo (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] + costo (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] + costo (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] + costo (4, \ Phi, 1) = 12 + 8 = 20 $$

$$ \ small Cost (4, \ lbrace 3 \ rbrace, 1) = d [4,3] + Costo (3, \ Phi, 1) = 9 + 6 = 15cost (4, \ lbrace3 \ rbrace, 1) = d [4,3] + costo (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] + costo (2, \ Phi, 1) = 8 + 5 = 13 $$

S = 2

$$ \ small Cost (2, \ lbrace 3, 4 \ rbrace, 1) = \ begin {cases} d [2, 3] + Cost (3, \ lbrace 4 \ rbrace, 1) = 9 + 20 = 29 \ \ d [2, 4] + Costo (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 = 25 \ small Cost (2, \ lbrace 3,4 \ rbrace, 1) \\\ lbrace d [ 2,3] + \ small cost (3, \ lbrace4 \ rbrace, 1) = 9 + 20 = 29d [2,4] + \ small Cost (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 \ end {case} = 25 $$

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

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

S = 3

$$ \ small Cost (1, \ lbrace 2, 3, 4 \ rbrace, 1) = \ begin {cases} d [1, 2] + Cost (2, \ lbrace 3, 4 \ rbrace, 1) = 10 + 25 = 35 \\ d [1, 3] + Costo (3, \ lbrace 2, 4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1, 4] + Costo (4, \ lbrace 2, 3 \ rbrace, 1) = 20 + 23 = 43 = 35 cost (1, \ lbrace 2,3,4 \ rbrace), 1) \\ d [1,2] + cost (2, \ lbrace 3,4 \ rbrace , 1) = 10 + 25 = 35 \\ d [1,3] + costo (3, \ lbrace 2,4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1,4] + costo (4 , \ lbrace 2,3 \ rbrace, 1) = 20 + 23 = 43 = 35 \ end {case} $$

Il percorso del costo minimo è 35.

Inizia dal costo {1, {2, 3, 4}, 1}, otteniamo il valore minimo per d [1, 2]. quandos = 3, seleziona il percorso da 1 a 2 (il costo è 10) quindi torna indietro. quandos = 2, otteniamo il valore minimo per d [4, 2]. Seleziona il percorso da 2 a 4 (il costo è 10) quindi torna indietro.

quando s = 1, otteniamo il valore minimo per d [4, 3]. Selezionando il percorso da 4 a 3 (il costo è 9), poi andremo a poi as = Φpasso. Otteniamo il valore minimo perd [3, 1] (il costo è 6).