Atividade 1

Prévia do material em texto

Atividade 1 
Pergunta: Use o algoritmo do caixeiro viajante para determinar a melhor rota de 
entrega saindo de Curitiba, passando em todas as capitais e retornando à Curitiba, 
indicando o total em Km percorrido. A saber as capitais a serem percorrida são: 
Curitiba (CTB), São Paulo (SP), Campo Grande (CGD), Brasília (BSB), Vitória (VTR) e 
Salvador (SLV), veja a figura. 
Para solucionar o problema do caixeiro viajante não há somente um algoritmo, mas 
sim vários, o mais simples é denominado busca gulosa e consiste em chegando a 
um dado nó (cidade) escolhe-se a cidade com menor distância até que se percorra 
todas a cidades e retorne para a cidade de origem. Uma restrição é se houver uma 
opção não visitada contra outras visitadas está será preferida. O esquema 
apresentando no problema é muito simples e apenas para aumentar nitidez busquei 
uma topologia que permitisse traças a rota desejada (Linha vermelha). 
 
Nesse caso temos: 
(a) CTB → SP = 400; 
(b) SP → VTR = 940; 
(c) VTR → SLV = 1200; 
(d) SLV → BSB = 1440; 
(e) BSB → CGD = 1060; 
(f) CGD → SP = 980; 
(g) SP → CTB = 400
.
Logo a Distância Percorrida (DP) é: 
DP = a + b + c + d+ e +f + g 
DP = 400 + 940 + 1200 + 1440 + 1060 + 980 + 400 
DP = 6420 Km 
A distância percorrida foi de 6420 Km e passou por todas as capitais com a 
distâncias conhecidas.