Solucionador do Caixeiro Viajante (TSP)

Solucionador do Caixeiro Viajante (TSP)

O Solucionador do Caixeiro Viajante é uma calculadora prática e educativa para o clássico Problema do Caixeiro Viajante (TSP): dado um conjunto de cidades e distâncias entre pares, encontre a rota mais curta possível que visite cada cidade exatamente uma vez e retorne ao início. Este solucionador aceita coordenadas planas ou uma matriz de distância personalizada, seleciona o melhor algoritmo automaticamente com base no tamanho do problema e renderiza a rota resultante como um mapa SVG animado.

O Que é o Problema do Caixeiro Viajante?

Formalmente, dado um grafo ponderado completo G = (V, E) com conjunto de vértices V = {1, 2, ..., n} e pesos de aresta d(i, j), o TSP busca uma permutação π dos vértices que minimize:

O termo final fecha o loop. O TSP é um dos problemas mais antigos e estudados em otimização combinatória — ele é NP-difícil no caso geral, o que significa que nenhum algoritmo conhecido resolve todas as instâncias em tempo polinomial. Apesar disso, ele aparece em inúmeras aplicações do mundo real: roteamento de veículos, perfuração de PCB, sequenciamento de DNA, rotas de coleta em armazéns, cronogramas de observação astronômica e até entrega de correspondência rural.

Como Funciona Este Solucionador

Programação Dinâmica Held–Karp (Exata)

Para instâncias pequenas (até 12 cidades), o solucionador calcula a rota comprovadamente ideal usando o algoritmo Held–Karp, publicado independentemente por Richard Bellman e Michael Held & Richard Karp em 1962. A recorrência chave, onde C(S, j) é o caminho mais curto do vértice 1 ao vértice j visitando exatamente o subconjunto S:

O custo da rota ideal é então min_j [C({1,...,n}, j) + d(j, 1)]. O Held–Karp é executado em tempo O(2ⁿ · n²) e memória O(2ⁿ · n) — uma melhoria enorme sobre a força bruta n!, mas ainda exponencial. Após cerca de 20 cidades, a pegada de memória torna-se impraticável.

Vizinho Mais Próximo + 2-opt (Heurística)

Para instâncias maiores, o solucionador usa uma heurística de dois estágios. Primeiro, o Vizinho Mais Próximo constrói uma rota rápida caminhando gananciosamente para a cidade não visitada mais próxima de cada vértice inicial. O solucionador tenta muitos vértices iniciais e mantém a melhor rota. Em seguida, a busca local 2-opt melhora a rota removendo iterativamente duas arestas e reconectando os dois caminhos resultantes da única outra maneira possível:

Geometricamente, o 2-opt remove todos os "cruzamentos" na rota: quaisquer dois segmentos que se cruzam podem sempre ser descruzados para um comprimento total menor. O algoritmo para em um ótimo local onde nenhuma troca única ajuda, chamado de rota 2-ideal. Em instâncias euclidianas realistas, o 2-opt normalmente encontra rotas de 2 a 5% do valor ideal real em milissegundos.

Formatos de Entrada

Modo Coordenadas (x, y)

Uma cidade por linha. Cada linha é etiqueta, x, y — a etiqueta é opcional. O solucionador calcula distâncias euclidianas automaticamente e visualiza as cidades em suas posições reais.

Modo Matriz de distância

Uma matriz quadrada n × n de distâncias não negativas, uma linha por vez, valores separados por espaços ou vírgulas. As matrizes podem ser simétricas ou assimétricas — as assimétricas modelam ruas de mão única, preços de passagens aéreas com disponibilidade variável e viagens dependentes do vento. Opcionalmente, forneça etiquetas no campo Etiquetas da matriz.

Comparação de Algoritmos

Como Usar Este Solucionador

1. Escolha um modo de entrada. Coordenadas se suas cidades tiverem posições (x, y) significativas; Matriz de distância se seus custos forem não euclidianos ou assimétricos.
2. Cole ou digite seus dados. Uma cidade ou linha por vez. Clique em um botão de exemplo rápido acima do formulário para preencher um exemplo válido.
3. Escolha o algoritmo. Deixe em Automático para o padrão correto: Held–Karp quando a instância for pequena o suficiente para a idealidade comprovável, NN + 2-opt caso contrário. Force um algoritmo específico se quiser comparar.
4. Escolha fechado ou aberto. Uma rota fechada retorna ao início — o TSP tradicional. O modo de caminho aberto resolve o problema relacionado do Caminho Hamiltoniano, onde o vendedor termina em uma cidade diferente.
5. Clique em Resolver. A página de resultados mostra o comprimento total da rota, um SVG animado do percurso (clique em "Replay da animação" para repetir), a sequência completa de cidades, um detalhamento por aresta e a matriz de distância com as arestas da rota destacadas.

Exemplo Prático

Considere cinco cidades — um retângulo mais um pico: A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5). O solucionador retorna:

• Rota: A → D → E → C → B → A
• Comprimento: 3 + √8 + √8 + 3 + 4 ≈ 15.66
• Ideal? Sim — Held–Karp prova que não existe rota mais curta.
• Por que esta ordem? A rota traça o fecho convexo dos cinco pontos (A → D → E → C → B → A). Uma propriedade clássica do TSP euclidiano é que uma rota ideal visita os pontos no fecho convexo em sua ordem cíclica; os pontos internos encaixam-se entre vizinhos adjacentes do fecho. Qualquer rota que cruze seu próprio caminho, como A → C → B → D → E → A (comprimento ≈ 21.2), pode sempre ser descruzada pelo 2-opt para um resultado mais curto.

Aplicações no Mundo Real

• Logística e entrega — otimize a rota diária de um motorista em 15 paradas para minimizar combustível e tempo.
• Manufatura — ordene os furos que uma furadeira CNC deve fazer em uma PCB para minimizar o deslocamento da cabeça.
• Montagem de genoma — ordene fragmentos de DNA por semelhança de sobreposição, codificados como uma matriz de distância.
• Astronomia — agende os movimentos do telescópio entre estrelas-alvo para maximizar o tempo de observação.
• Separação em armazém — sequencie as visitas aos corredores para atender a um pedido com o menor número de passos.
• Planejamento turístico — planeje uma viagem por várias cidades que minimize o tempo de viagem e o custo das passagens.

Perguntas Frequentes

O que é o Problema do Caixeiro Viajante?

O Problema do Caixeiro Viajante (TSP) busca a rota mais curta possível que visite cada cidade exatamente uma vez e retorne à cidade de partida. É um dos problemas mais famosos em otimização combinatória e é NP-difícil no caso geral, o que significa que nenhum algoritmo conhecido resolve todas as instâncias em tempo polinomial.

O que é o algoritmo Held–Karp?

Held–Karp é um algoritmo de programação dinâmica que resolve o TSP exatamente em tempo O(2ⁿ · n²) e memória O(2ⁿ · n). É dramaticamente mais rápido que a força bruta (n fatorial), mas ainda exponencial, portanto, na prática, é usado apenas para instâncias de até cerca de 20 cidades. Este solucionador usa Held–Karp quando há 12 cidades ou menos.

O que é o 2-opt e por que é usado?

O 2-opt é uma heurística de busca local que remove repetidamente duas arestas da rota atual e reconecta os dois caminhos resultantes da outra maneira possível. Quando a nova rota é mais curta, a troca é mantida. O 2-opt é executado em tempo polinomial por iteração e consistentemente encontra rotas a poucos pontos percentuais da ideal, por isso é a heurística clássica para instâncias maiores de TSP.

Quando devo usar coordenadas versus uma matriz de distância?

Use coordenadas quando suas cidades estiverem em um plano com distâncias em linha reta — por exemplo, pontos em um mapa, locais de armazéns ou furos em uma placa de circuito. Use uma matriz de distância quando o custo entre os pares não for euclidiano — por exemplo, preços de passagens aéreas, tempos de viagem com tráfego, distâncias rodoviárias de mão única ou custos assimétricos. O modo matriz aceita quaisquer distâncias não negativas, mesmo as assimétricas.

A solução 2-opt é a ideal?

Não, o 2-opt retorna uma rota 2-ideal, o que significa que nenhum par único de arestas pode ser trocado para produzir uma rota mais curta. Este é um ótimo local e geralmente está a poucos pontos percentuais do ótimo global em instâncias bem comportadas, mas não há garantia de que seja o melhor global. Para uma rota comprovadamente ideal em instâncias pequenas, escolha Held–Karp.

Esta ferramenta suporta matrizes de distância assimétricas?

Sim. No modo Matriz de distância, você pode inserir qualquer matriz quadrada não negativa, incluindo as assimétricas onde D[i][j] difere de D[j][i]. Tanto Held–Karp quanto 2-opt lidam corretamente com matrizes assimétricas. Isso é útil para problemas de roteamento do mundo real com ruas de mão única, tráfego ou custos de voo dependentes do vento.

Leitura Adicional

• Problema do Caixeiro Viajante — Wikipédia
• Algoritmo de Held–Karp — Wikipédia
• 2-opt — Wikipédia
• Algoritmo do vizinho mais próximo — Wikipédia

Operações matemáticas avançadas:

• Calculadora de Matriz de Adjacência Novo
• Calculadora de Antilog
• Calculadora de Função Beta
• Calculadora de Coeficiente Binomial
• Calculadora de distribuição binomial
• Calculadora de Lógica Binária
• Simplificador de Álgebra Booleana Novo
• Calculadora do Teorema Central do Limite
• Calculadora do Teorema Chinês do Resto
• Calculadora de Combinação Popular
• Calculadora de Função de Erro Complementar
• Calculadora de Números Complexos Popular
• Calculadora de Frações Contínuas
• Calculadora de Desarranjo (Subfatorial)
• Calculadora de Caminho Mais Curto de Dijkstra
• Calculadora de Entropia Popular
• Calculadora da função de erro
• Calculadora da Função Totiente de Euler
• Calculadora de decaimento exponencial
• Calculadora de Crescimento Exponencial de Alta Precisão
• Calculadora de Integral Exponencial
• Calculadora de Expoentes (Alta Precisão)
• Calculadora do Algoritmo Euclidiano Estendido
• Calculadora de Fatorial
• Calculadora de Função Gama
• Calculadora de Proporção Áurea
• Calculadora de Coloração de Grafos Novo
• Validador de Sequência de Graus de Grafo
• Calculadora de Ordem em Teoria dos Grupos Novo
• Calculadora de Meia-Vida
• Verificador de Caminho Hamiltoniano Novo
• Calculadora de Inclusão-Exclusão Novo
• Solucionador de Mapa de Karnaugh (K-Map) Novo
• Solucionador de Programação Linear Novo
• Calculadora de Estado Estacionário da Cadeia de Markov
• Calculadora de Árvore Geradora Mínima
• Calculadora de Exponenciação Modular Novo
• Calculadora do Inverso Multiplicativo Modular
• Calculadora de Distribuição Binomial Negativa Novo
• Calculadora de Fluxo em Rede (Fluxo Máximo) Novo
• Calculadora de Taxa de Crescimento Percentual Popular
• Calculadora de Permutação
• Calculadora de Permutações com Repetição Novo
• Calculadora do Princípio da Casa dos Pombos
• Verificador de Grafo Planar Novo
• Calculadora de Distribuição de Poisson
• Calculadora de Raízes de Polinômios
• Calculadora de Raiz Primitiva
• Calculadora de Probabilidade
• Calculadora de Distribuição de Probabilidade
• Calculadora de Proporção Popular
• Calculadora de Fórmula Quadrática
• Calculadora de Anéis e Corpos Novo
• Calculadora de Arredondamento Popular
• Calculadora Científica
• Calculadora de notação científica
• Calculadora de Teoria dos Conjuntos
• Calculadora de Algarismos Significativos Novo
• Solucionador do Problema do Casamento Estável Novo
• Calculadora de Números de Stirling
• Calculadora de Soma de Cubos
• Calculadora de soma de inteiros positivos
• Calculadora de Soma dos Quadrados
• Calculadora de Ordenação Topológica Novo
• Solucionador do Caixeiro Viajante (TSP) Novo
• Gerador de Tabela Verdade Popular
• Gerador de Diagrama de Venn (3 Conjuntos)