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:
  1. Calcular a distância entre todas as cidades usando a fórmula da distância euclidiana.
  2. Gerar todas as rotas possíveis que começam e terminam na cidade 0 .
  3. 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).

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 \mathbb{R}^2,
  • 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 i,j com coordenadas (x_i,y_i) e (x_j,y_j), usamos a fórmula
d_{ij} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}.
No código, armazene todas as d_{ij} num array bidimensional para acesso rápido.

Passo 3

Gerar todas as rotas possíveis com retorno à cidade 0:
  1. Liste as cidades intermediárias de 1 a 9.
  2. Gere todas as permutações dessa lista (há (9!) rotas).
  3. Para cada permutação (c_1,c_2,\dots,c_9), a rota completa é [0,c_1,c_2,\dots,c_9,0].

Passo 4

Avaliar o custo de cada rota: percorra a sequência de cidades da rota completa e acumule
\text{custo} = \sum_{k=0}^{9} d_{c_k,c_{k+1}},
onde c_0=c_{10}=0. 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 (c_k,c_{k+1}) e suas distâncias d_{c_k,c_{k+1}}, 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 (n-1)! avaliações, inviável para n\gg10.

Passo 8

Solução otimizada sugerida:
Utilizar o algoritmo de Programação Dinâmica de Held–Karp, que resolve o TSP em O(n^2 2^n) tempo. A ideia é usar uma tabela dp[S][i] que guarda o menor custo para visitar o subconjunto de cidades S\subset\{1,\dots,n-1\} e terminar em i. A recursão é
dp[S][i] = \min_{j\in S\setminus\{i\}}\bigl(dp[S\setminus\{i\}][j] + d_{j,i}\bigr).
Comparado a (n-1)!, esse método é muito mais eficiente para n 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 dp[S][i] e justifique que, embora ainda exponencial, ele reduz drasticamente o custo computacional de (n-1)! para O(n^2 2^n), tornando-o aplicável a problemas com até 30–40 cidades em máquinas modernas.

Exercícios relacionados