Atividade Prática 02
Problema do Caixeiro Viajante
Desenvolver um programa para ajudar um caixeiro viajante a encontrar o caminho de menor distância ao visitar todas as cidades de uma rota e retornar à cidade inicial.
Dado um conjunto de cidades com suas posições (coordenadas), o programa deve:
- Calcular a distância entre todas as cidades usando a fórmula da distância euclidiana.
- Gerar todas as rotas possíveis que começam e terminam na cidade 0 .
- Avaliar cada rota e determinar qual tem a menor distância total.
Use 10 cidades numeradas de 0 a 9. Você pode fixar as coordenadas no código.
Cidade 0: [0, 0]
Cidade 1: [2, 3]
Cidade 2: [5, 4]
Cidade 3: [1, 1]
Cidade 4: [6, 2]
[…]
Quero que após o fornecimento(ou processamento) das coordenadas, seja exposto o cálculo para cada uma das rotas e por fim, declare qual seria a melhor rota para aquela instância.
Por fim, o estudante deve pesquisar uma solução que seria mais otimizada, descrever seu funcionamento e justificar o porquê ela seria mais otimizada.
O Aluno Deve Entregar
- Código-Fonte
-Arquivo com a implementação completa do sistema, devidamente comentados e organizados.
- Pesquisa da Solução Otimizada
-Documentação explicando o porquê a solução utilizada não ser a mais efetiva e como a solução proposta pelo estudante seria mais otimizada em relação a implementada no trabalho.
Cronograma e Data de Entrega
- Início do Projeto: 24 de junho de 2025
- Data de Entrega: 08 de julho de 2025
Contatos para Tirar Dúvidas
Email: georgeffv1@gmail.com
Discord: GeorgeFFV
Sala do Professor: Sala 30 do Bloco 2 dos professores
Horários: 9:30-13:00 (Seg, Ter, Qua)
Critérios de Avaliação
A avaliação do projeto será baseada nos seguintes critérios:
- Implementação Técnica: Correta utilização das estruturas vistas na disciplina.(3 pontos)
- Funcionalidade: O sistema deve atender a todos os requisitos funcionais descritos no enunciado.(3 pontos)
- Qualidade do Código: Estrutura, clareza, modularidade e documentação do código.(2 pontos)
- Proposta de Solução Otimizada (2 pontos).
Cidade 1: [2, 3]
Cidade 2: [5, 4]
Cidade 3: [1, 1]
Cidade 4: [6, 2]
[…]
-Arquivo com a implementação completa do sistema, devidamente comentados e organizados.
-Documentação explicando o porquê a solução utilizada não ser a mais efetiva e como a solução proposta pelo estudante seria mais otimizada em relação a implementada no trabalho.
Discord: GeorgeFFV
Sala do Professor: Sala 30 do Bloco 2 dos professores
Horários: 9:30-13:00 (Seg, Ter, Qua)
Passo 1
Resumo do problema: queremos implementar o problema do Caixeiro Viajante (TSP) para 10 cidades numeradas de 0 a 9, conhecidas suas coordenadas fixas. O conteúdo envolve:
- Distância euclidiana em
, - Geração de permutações (rotas) com cidade inicial/final fixa,
- Avaliação de custo total de cada rota (soma de distâncias),
- Seleção da rota de menor custo.
Passo 2
Calcular a matriz de distâncias: para cada par de cidades
com coordenadas
e
, usamos a fórmula
No código, armazene todas as
num array bidimensional para acesso rápido.
Passo 3
Gerar todas as rotas possíveis com retorno à cidade 0:
- Liste as cidades intermediárias de 1 a 9.
- Gere todas as permutações dessa lista (há
rotas). - Para cada permutação
, a rota completa é .
Passo 4
Avaliar o custo de cada rota: percorra a sequência de cidades da rota completa e acumule
onde
. Mantenha uma variável que armazene o menor custo encontrado e a rota correspondente.
Passo 5
Exibir o cálculo de cada rota: para fins didáticos, imprima para cada permutação a sequência de pares
e suas distâncias
, depois o custo total. Ao final, declare a “melhor rota” (aquela de menor custo) e o valor desse custo.
Passo 6
Esqueleto de código em Python (comentado e modular):
# cidades: lista de tuplas (x,y)
cidades = [(0,0),(2,3),(5,4),(1,1),(6,2),(...),(...),(...),(...),(...)]
def calcula_matriz_distancias(cidades):
n = len(cidades)
D = [[0]*n for _ in range(n)]
for i in range(n):
for j in range(i+1,n):
dx = cidades[i][0] - cidades[j][0]
dy = cidades[i][1] - cidades[j][1]
D[i][j] = D[j][i] = (dx*dx + dy*dy)**0.5
return D
def avalia_rotas(D):
from itertools import permutations
melhor_custo = float('inf')
melhor_rota = None
for perm in permutations(range(1, len(D))):
rota = (0,)+perm+(0,)
custo = sum(D[rota[k]][rota[k+1]] for k in range(len(rota)-1))
# aqui, imprimir detalhes de cada trecho e custo parcial se desejar
if custo < melhor_custo:
melhor_custo = custo
melhor_rota = rota
return melhor_rota, melhor_custo
def main():
D = calcula_matriz_distancias(cidades)
rota, custo = avalia_rotas(D)
print("Melhor rota:", rota)
print("Custo total:", custo)
if __name__ == "__main__":
main()
Passo 7
Limitação da abordagem: o método “força bruta” faz
avaliações, inviável para
.
Passo 8
Solução otimizada sugerida:
Utilizar o algoritmo de Programação Dinâmica de Held–Karp, que resolve o TSP em tempo. A ideia é usar uma tabela
que guarda o menor custo para visitar o subconjunto de cidades
e terminar em
. A recursão é
Utilizar o algoritmo de Programação Dinâmica de Held–Karp, que resolve o TSP em
Comparado a
, esse método é muito mais eficiente para
na casa das dezenas.
Resposta
Apresente o código-fonte completo seguindo o esqueleto acima, com comentários e relatórios de cada rota testada. Em seguida, na seção de pesquisa, descreva o algoritmo de Held–Karp (dinâmica sobre subconjuntos), explique a tabela
e justifique que, embora ainda exponencial, ele reduz drasticamente o custo computacional de
para
, tornando-o aplicável a problemas com até 30–40 cidades em máquinas modernas.