Caixeiro Viajante ✈️

import pandas as pd
import itertools
import time
import math

# ============================================================
# CAIXEIRO VIAJANTE - FORÇA BRUTA COM CONDIÇÃO DE PARADA
# Ponto inicial: Brasília
# Para quando atingir um tempo máximo em minutos
# ============================================================

ARQUIVO_CSV = "matriz_distancias_capitais_brasil.csv"
CAPITAL_INICIAL = "Brasília"

# Quantidade de capitais mais próximas de Brasília que serão testadas
QUANTIDADE_CAPITAIS = 5

# Tempo máximo de execução em minutos
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("Arquivo carregado com sucesso!")
print(f"Total de capitais disponíveis: {len(matriz)}")


print("\n[2] Selecionando capitais mais próximas de Brasília...")

distancias_brasilia = matriz.loc[CAPITAL_INICIAL]
distancias_brasilia = distancias_brasilia.drop(CAPITAL_INICIAL)

capitais_proximas = distancias_brasilia.sort_values().head(QUANTIDADE_CAPITAIS)
capitais_para_visitar = list(capitais_proximas.index)

print(f"\nCapital inicial: {CAPITAL_INICIAL}")
print(f"Quantidade de capitais escolhidas: {QUANTIDADE_CAPITAIS}")

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


print("\n[3] Calculando quantidade total de possibilidades...")

total_possibilidades = math.factorial(QUANTIDADE_CAPITAIS)

print(f"Total de rotas possíveis: {total_possibilidades:,}")
print(f"Tempo limite: {TEMPO_LIMITE_MINUTOS} minuto(s)")


def calcular_distancia_rota(rota, matriz_distancias):
    """
    Calcula a distância total de uma rota.
    A rota começa em Brasília, passa pelas capitais e retorna para Brasília.
    """

    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

# Não usamos list(), porque para 27 capitais isso ocuparia muita memória.
# O itertools.permutations gera uma rota por vez.
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

    rota_completa = [CAPITAL_INICIAL] + list(rota_permutada) + [CAPITAL_INICIAL]

    distancia_total = calcular_distancia_rota(rota_completa, matriz)

    rotas_testadas += 1

    if distancia_total < menor_distancia:
        menor_distancia = distancia_total
        melhor_rota = rota_completa

        print("\nNova melhor rota encontrada!")
        print(f"Rota número: {rotas_testadas}")
        print(f"Distância: {menor_distancia:.2f} km")
        print(" -> ".join(melhor_rota))

    # Mostra progresso a cada 10.000 rotas testadas
    if rotas_testadas % 10000 == 0:
        percentual = (rotas_testadas / total_possibilidades) * 100
        print("\nProgresso:")
        print(f"Rotas testadas: {rotas_testadas:,}")
        print(f"Percentual aproximado: {percentual:.8f}%")
        print(f"Tempo decorrido: {tempo_decorrido:.2f} segundos")
        print(f"Melhor distância até agora: {menor_distancia:.2f} km")


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


print("\n" + "=" * 70)
print("RESULTADO FINAL")
print("=" * 70)

print(f"\nCapital inicial: {CAPITAL_INICIAL}")
print(f"Capitais visitadas: {QUANTIDADE_CAPITAIS}")

print(f"\nTotal de rotas possíveis: {total_possibilidades:,}")
print(f"Rotas testadas: {rotas_testadas:,}")

percentual_final = (rotas_testadas / total_possibilidades) * 100
print(f"Percentual testado: {percentual_final:.8f}%")

print(f"\nTempo limite configurado: {TEMPO_LIMITE_MINUTOS} minuto(s)")
print(f"Tempo real de execução: {tempo_total:.2f} segundos")

print("\nMelhor rota encontrada dentro do tempo:")
print(" -> ".join(melhor_rota))

print(f"\nMenor distância encontrada: {menor_distancia:.2f} km")

print("\n" + "=" * 70)
print("FIM DO PROCESSAMENTO")
print("=" * 70)