Aplicação do Problema do Caixeiro Viajante na Otimização de Rotas entre Capitais Brasileiras ✈️

import pandas as pd
import itertools
import time
import math

# Configurações do Problema
ARQUIVO_CSV = "matriz_distancias_capitais_brasil.csv"
CAPITAL_INICIAL = "Brasília"
QUANTIDADE_CAPITAIS = 5  # Quantidade de capitais mais próximas de Brasília
TEMPO_LIMITE_MINUTOS = 180

print("=" * 70)
print("CAIXEIRO VIAJANTE - FORÇA BRUTA COM TEMPO LIMITE")
print("=" * 70)

print("\n[1] Carregando matriz de distâncias...")
matriz = pd.read_csv(ARQUIVO_CSV, index_col=0)
print(f"Arquivo carregado! Total de capitais disponíveis: {len(matriz)}")

print("\n[2] Selecionando capitais mais próximas...")
distancias_brasilia = matriz.loc[CAPITAL_INICIAL].drop(CAPITAL_INICIAL)
capitais_proximas = distancias_brasilia.sort_values().head(QUANTIDADE_CAPITAIS)
capitais_para_visitar = list(capitais_proximas.index)

for i, capital in enumerate(capitais_para_visitar, start=1):
    print(f"{i}. {capital} - {capitais_proximas[capital]} km de Brasília")

total_possibilidades = math.factorial(QUANTIDADE_CAPITAIS)
print(f"\nTotal de rotas possíveis: {total_possibilidades:,}")

def calcular_distancia_rota(rota, matriz_distancias):
    """Calcula a distância total de uma rota (ida e volta)."""
    distancia_total = 0
    for i in range(len(rota) - 1):
        origem = rota[i]
        destino = rota[i + 1]
        distancia_total += matriz_distancias.loc[origem, destino]
    return distancia_total

print("\n[4] Iniciando busca por força bruta...")
tempo_limite_segundos = TEMPO_LIMITE_MINUTOS * 60
inicio_tempo = time.time()
menor_distancia = float("inf")
melhor_rota = None
rotas_testadas = 0

for rota_permutada in itertools.permutations(capitais_para_visitar):
    tempo_atual = time.time()
    tempo_decorrido = tempo_atual - inicio_tempo
    
    # Condição de parada por tempo
    if tempo_decorrido >= tempo_limite_segundos:
        print("\nTempo limite atingido.")
        break
    
    # Monta a rota completa: Brasília -> Capitais -> Brasília
    rota_completa = [CAPITAL_INICIAL] + list(rota_permutada) + [CAPITAL_INICIAL]
    distancia_total = calcular_distancia_rota(rota_completa, matriz)
    rotas_testadas += 1
    
    # Atualiza se encontrar uma rota mais curta
    if distancia_total < menor_distancia:
        menor_distancia = distancia_total
        melhor_rota = rota_completa
        print(f"\nNova melhor rota encontrada! Distância: {menor_distancia:.2f} km")
        print(" -> ".join(melhor_rota))

    # Log de progresso a cada 10.000 iterações
    if rotas_testadas % 10000 == 0:
        percentual = (rotas_testadas / total_possibilidades) * 100
        print(f"Progresso: {percentual:.4f}% | Testadas: {rotas_testadas:,}")

fim_tempo = time.time()
tempo_total = fim_tempo - inicio_tempo

print("\n" + "=" * 70)
print("RESULTADO FINAL")
print("=" * 70)
print(f"Rotas testadas: {rotas_testadas:,} ({ (rotas_testadas/total_possibilidades)*100:.4f}%)")
print(f"Tempo real de execução: {tempo_total:.2f} segundos")