DAA - Problema do caixeiro viajante

Declaração do Problema

Um viajante precisa visitar todas as cidades de uma lista, onde as distâncias entre todas as cidades são conhecidas e cada cidade deve ser visitada apenas uma vez. Qual é o caminho mais curto possível para que ele visite cada cidade exatamente uma vez e volte para a cidade de origem?

Solução

O problema do caixeiro viajante é o problema computacional mais notório. Podemos usar a abordagem de força bruta para avaliar todas as viagens possíveis e selecionar a melhor. Paran número de vértices em um gráfico, há (n - 1)! número de possibilidades.

Em vez de força bruta usando abordagem de programação dinâmica, a solução pode ser obtida em menor tempo, embora não haja algoritmo de tempo polinomial.

Vamos considerar um gráfico G = (V, E), Onde V é um conjunto de cidades e Eé um conjunto de arestas ponderadas. Uma vantageme(u, v) representa os vértices u e vestão conectados. Distância entre vérticesu e v é d(u, v), que deve ser não negativo.

Suponha que tenhamos começado na cidade 1 e depois de visitar algumas cidades agora estamos na cidade j. Portanto, este é um passeio parcial. Certamente precisamos saberj, pois isso determinará quais cidades são mais convenientes para visitar em seguida. Também precisamos saber todas as cidades visitadas até agora, para não repetirmos nenhuma delas. Portanto, este é um subproblema apropriado.

Para um subconjunto de cidades S Є {1, 2, 3, ... , n} que inclui 1, e j Є S, deixei C(S, j) ser o comprimento do caminho mais curto visitando cada nó em S exatamente uma vez, começando em 1 e terminando em j.

Quando |S| > 1, nós definimosC(S, 1) = ∝ visto que o caminho não pode começar e terminar em 1.

Agora vamos expressar C(S, j)em termos de subproblemas menores. Precisamos começar em1 e termina em j. Devemos selecionar a próxima cidade de forma que

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

Análise

Existem no máximo $ 2 ^ nn $ subproblemas e cada um leva um tempo linear para ser resolvido. Portanto, o tempo total de execução é $ O (2 ^ nn ^ 2) $.

Exemplo

No exemplo a seguir, ilustraremos as etapas para resolver o problema do caixeiro viajante.

A partir do gráfico acima, a seguinte tabela é preparada.

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

$$ \ custo pequeno (2, \ Phi, 1) = d (2,1) = 5 \ custo pequeno (2, \ Phi, 1) = d (2,1) = 5 $$

$$ \ custo pequeno (3, \ Phi, 1) = d (3,1) = 6 \ custo pequeno (3, \ Phi, 1) = d (3,1) = 6 $$

$$ \ custo pequeno (4, \ Phi, 1) = d (4,1) = 8 \ custo pequeno (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] + Custo (3, \ Phi, 1) = 9 + 6 = 15custo (2, \ lbrace3 \ rbrace, 1) = d [2,3] + custo (3, \ Phi, 1) = 9 + 6 = 15 $$

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

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

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

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

$$ \ small Cost (4, \ lbrace 2 \ rbrace, 1) = d [4,2] + Custo (2, \ Phi, 1) = 8 + 5 = 13custo (4, \ lbrace2 \ rbrace, 1) = d [4,2] + custo (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] + Custo (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 = 25 \ pequeno Custo (2, \ lbrace 3,4 \ rbrace, 1) \\\ lbrace d [ 2,3] + \ custo pequeno (3, \ lbrace4 \ rbrace, 1) = 9 + 20 = 29d [2,4] + \ custo pequeno (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 \ end {casos} = 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] + Custo (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 = 25 \ small Cost (3, \ lbrace 2,4 \ rbrace, 1) \\\ lbrace d [ 3,2] + \ custo pequeno (2, \ lbrace4 \ rbrace, 1) = 13 + 18 = 31d [3,4] + \ custo pequeno (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 \ end {casos} = 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] + Custo (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 = 23 \ pequeno Custo (4, \ lbrace 2,3 \ rbrace, 1) \\\ lbrace d [ 4,2] + \ custo pequeno (2, \ lbrace3 \ rbrace, 1) = 8 + 15 = 23d [4,3] + \ custo pequeno (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 \ end {casos} = 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] + Custo (3, \ lbrace 2, 4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1, 4] + Custo (4, \ lbrace 2, 3 \ rbrace, 1) = 20 + 23 = 43 = 35 custo (1, \ lbrace 2,3,4 \ rbrace), 1) \\ d [1,2] + custo (2, \ lbrace 3,4 \ rbrace , 1) = 10 + 25 = 35 \\ d [1,3] + custo (3, \ lbrace 2,4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1,4] + custo (4 , \ lbrace 2,3 \ rbrace, 1) = 20 + 23 = 43 = 35 \ end {casos} $$

O caminho de custo mínimo é 35.

Comece pelo custo {1, {2, 3, 4}, 1}, obtemos o valor mínimo para d [1, 2]. Quandos = 3, selecione o caminho de 1 a 2 (o custo é 10) e volte para trás. Quandos = 2, obtemos o valor mínimo para d [4, 2]. Selecione o caminho de 2 a 4 (o custo é 10) e volte para trás.

Quando s = 1, obtemos o valor mínimo para d [4, 3]. Selecionando o caminho 4 a 3 (o custo é 9), então iremos para, então iremos paras = Φdegrau. Conseguimos o valor mínimo parad [3, 1] (o custo é 6).