problema do caixeiro
Transcrição
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