Problema do Caixeiro Viajante

Prévia do material em texto

Aula 30
Módulo 4.1 – Problema do Caixeiro Viajante by A.A.
Pesquisa Operacional II
1
Caixeiro Viajante
Caixeiro Viajante
3
2
1
4
Percorrer todas as cidades;
1
Passar por todas 1 única vez;
2
Minimizar a distância total.
3
4
3
2
1
1 4 2 3
4 2 3 1
2 3 1 4
3 1 4 2
4
3
2
1
1 4 2 3
4 2 3 1
2 3 1 4
3 1 4 2
4
3
2
1
1 3 2 4
3 2 4 1
2 4 1 3
4 1 3 2
4
3
2
1
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
Para o Problema do Caixeiro Viajante Simétrico existem 
(n-1)!/2 soluções distintas em termos de distância! 
Por exemplo, para 4 cidades (n=4), temos: (4-1)!/2= 6/2 = 3. 
Caixeiro Viajante
Cidades
(n-1)!/2
Tempo
5
12
Insignif.
10
181440
0.001 s
15
43 bilhões
10 min
20
6,0 x 1016
36 anos
25
3,1 x 1023
235 milhões
de anos
Quanto tempo 
para resolver
usando 1
computador
capaz de fazer
1 bilhão de 
adições por 
segundo ?
E para valores acima de 26 ?
Caixeiro Viajante
Caixeiro Viajante
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Caixeiro Viajante
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Caixeiro Viajante
Caixeiro Viajante
Caixeiro Viajante
Fonte:
logistica74.blogspot.com
Caixeiro Viajante
1
2
3
4
Caixeiro Viajante
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
Caixeiro Viajante
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
Aula 30
Módulo 4.1 – Problema do Caixeiro Viajante by A.A.
Pesquisa Operacional II
14