problema do caixeiro

problema do
caixeiro-viajante
problema do técnico de vendas
J.A.Oliveira – DPS – U.Minho
1
problema do caixeiro viajante
• enunciado simples
dados um conjunto de cidades e as distâncias entre as
cidades, determinar qual é o percurso de menor comprimento
que passa por todas as cidades
• solução difícil
– não foi encontrado nenhum algoritmo eficiente
– crê-se que não exista
– solução exacta:
• abordagens baseadas em B&B – prob. de afectação
• relaxação lagrangeana – prob. da árv. sup. custo min.
pior caso: enumeração exponencial
– métodos não exactos de solução (heurísticas)
J.A.Oliveira – DPS – U.Minho
2
1
problema do caixeiro viajante
• obter circuito hamiltoniano de menor custo.
• soluções:
Afectação
Caix.Viajante
J.A.Oliveira – DPS – U.Minho
3
problema de afectação
• aplicações
– resolução do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
4
2
problema do caixeiro viajante
Caix.Viajante
solução óptima do
prob. afectação, mas
não é válida para o
caixeiro viajante
Afectação
Caix.Viajante
solução óptima do
prob. afectação, mas
não é válida para o
caixeiro viajante
Afectação
Caix.Viajante
Afectação
J.A.Oliveira – DPS – U.Minho
solução óptima do
prob. afectação e do
caixeiro viajante
5
problema do caixeiro viajante
• aplicações
J.A.Oliveira – DPS – U.Minho
6
3
problema do caixeiro viajante
• aplicações
J.A.Oliveira – DPS – U.Minho
7
problema do caixeiro viajante
• aplicações
J.A.Oliveira – DPS – U.Minho
8
4
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
9
problema do caixeiro viajante
15112
localidades
Alemanha
J.A.Oliveira – DPS – U.Minho
10
5
problema do caixeiro viajante
15112
localidades
Alemanha
J.A.Oliveira – DPS – U.Minho
11
problema do caixeiro viajante
furação
de uma
placa
J.A.Oliveira – DPS – U.Minho
12
6
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
13
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
14
7
problema do caixeiro viajante
ou
J.A.Oliveira – DPS – U.Minho
15
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
16
8
problema do caixeiro viajante
• partição
v2
v1
v3
J.A.Oliveira – DPS – U.Minho
17
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
18
9
problema do caixeiro viajante
• definição das restrições
xij = 0 
→ cij = ∞
xij = 1 
→ cij = 0
e ainda fixar restantes (linha i / coluna j ) a ∞
retirar linha i e coluna j
J.A.Oliveira – DPS – U.Minho
• exemplo
19
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
20
10
• exemplo
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
• exemplo
21
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
22
11
• exemplo
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
• exemplo
23
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
24
12
• exemplo
problema do caixeiro viajante
Solução
Óptima
J.A.Oliveira – DPS – U.Minho
25
problema do caixeiro viajante
•
melhorar indicação do prob. Afectação – eliminar sub-árvore
J.A.Oliveira – DPS – U.Minho
26
13
problema do caixeiro viajante
3+2
J.A.Oliveira – DPS – U.Minho
27
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
28
14
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
29
problema do caixeiro viajante
complexidade O ( n 2 )
J.A.Oliveira – DPS – U.Minho
30
15
problema do caixeiro viajante
complexidade O ( n3 )
J.A.Oliveira – DPS – U.Minho
31
problema do caixeiro viajante
1
1
1
1
5
4
4
4
J.A.Oliveira – DPS – U.Minho
4
5
3
3
3
3
5
2
2
2
2
5
1
1
1
1
6
8
0
5
+
+
+
+
0
1
7
3
-
1
0
4
0
=
=
=
=
5
9
3
8
32
16
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
33
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
34
17
problema do caixeiro viajante
• ver heurísticas de pesquisa local
• excel
J.A.Oliveira – DPS – U.Minho
35
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
36
18
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
37
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
38
19
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
39
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
40
20
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
41
problema do caixeiro viajante
J.A.Oliveira – DPS – U.Minho
42
21