Problema do Caixeiro Viajante (TSP)

Viabilidade da Solução Ótima

O Problema do Caixeiro Viajante (TSP) sempre possui uma solução ótima (o caminho de menor distância que visita todos os nós e retorna à origem). A questão central na ciência da computação não é a existência, mas a viabilidade computacional de encontrá-la.

1. A Barreira Fatorial

Para um grafo simétrico com $n$ cidades, o número de rotas únicas possíveis é dado por:

$$ \frac{(n-1)!}{2} $$

$n = 10$: $181.440$ rotas (Testável em microssegundos).
$n = 20$: $\approx 6 \times 10^{16}$ rotas (Levaria anos em um computador comum).
$n = 100$: O número de rotas supera a estimativa de átomos no universo observável.

2. Métodos Exatos e seus Limites Práticos

Para garantir matematicamente a solução ótima, utilizamos algoritmos exatos, mas eles esbarram em limites rígidos de hardware:

Método	Complexidade	Viabilidade Prática
Força Bruta	$O(n!)$	$n \leq 10$
Programação Dinâmica (Held-Karp)	$O(n^2 2^n)$	$n \leq 25$ (Limite de memória RAM)
Branch and Cut (ex: Concorde TSP)	Exponencial com poda agressiva	$n \leq 85.000$ (Exige clusters de supercomputadores por dias)

3. A Justificativa para Heurísticas

Em aplicações do mundo real, esperar dias por uma resposta é inviável. O objetivo da engenharia é encontrar o equilíbrio ótimo entre qualidade da solução e tempo de computação.

Por isso, sacrificamos a garantia absoluta de optimalidade em troca de velocidade, utilizando algoritmos que entregam soluções a menos de $1\%$ a $5\%$ da distância ótima real em milissegundos:

Vizinho Mais Próximo: $O(n^2)$. Rápido, mas a qualidade pode ser $20\%$ a $30\%$ pior que o ótimo.
2-Opt (Otimização Local): Remove cruzamentos de arestas iterativamente. Extremamente rápido e converge para soluções muito próximas do ótimo.
Christofides: Algoritmo aproximado com garantia matemática formal de entregar uma rota $\leq 1.5 \times$ o valor ótimo.

Código de Referência

Python (NetworkX + Christofides)

Python

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

def solve_tsp(n_cities=15, seed=42):
    np.random.seed(seed)
    cities = np.random.rand(n_cities, 2)
    
    G = nx.Graph()
    for i in range(n_cities):
        for j in range(i+1, n_cities):
            dist = np.linalg.norm(cities[i] - cities[j])
            G.add_edge(i, j, weight=dist)
    
    # Algoritmo de Christofides (garantia de 1.5x o ótimo)
    route = nx.approximation.traveling_salesman_problem(G, cycle=True)
    distance = sum(G[route[i]][route[i+1]]['weight'] for i in range(len(route)-1))
    
    plt.figure(figsize=(10, 6))
    plt.scatter(cities[:,0], cities[:,1], c='red', s=100)
    plt.scatter(cities[route[0],0], cities[route[0],1], c='green', s=200, marker='*', label='Origem')
    
    for i in range(len(route)-1):
        plt.plot([cities[route[i],0], cities[route[i+1],0]],
                 [cities[route[i],1], cities[route[i+1],1]], 'b-', alpha=0.6)
                 
    plt.title(f"TSP - {n_cities} Cidades (Distância: {distance:.3f})")
    plt.legend()
    plt.grid(True)
    plt.show()

solve_tsp(n_cities=15)

JavaScript (D3.js + 2-Opt Robusto)

JavaScript

// A lógica completa está ativa na Aba 2.
// Destaque para a correção do 2-Opt:
function twoOpt(route) {
    let uniqueRoute = route.slice(0, -1); // Remove duplicata da origem
    let bestRoute = [...uniqueRoute];
    let bestDistance = calculateTotalDistance([...bestRoute, bestRoute[0]]);
    let improved = true;
    const n = bestRoute.length;
    
    while (improved) {
        improved = false;
        for (let i = 1; i < n - 1; i++) {
            for (let j = i + 1; j < n; j++) {
                const newRoute = [
                    ...bestRoute.slice(0, i),
                    ...bestRoute.slice(i, j + 1).reverse(),
                    ...bestRoute.slice(j + 1)
                ];
                const newDistance = calculateTotalDistance([...newRoute, newRoute[0]]);
                if (newDistance < bestDistance) {
                    bestRoute = newRoute;
                    bestDistance = newDistance;
                    improved = true;
                }
            }
        }
    }
    return [...bestRoute, bestRoute[0]]; // Readiciona a origem
}