Solucionador do Caixeiro Viajante (TSP)

Encontre a rota mais curta que visita cada cidade uma vez e retorna ao início. Usa programação dinâmica exata de Held-Karp para instâncias pequenas e vizinho mais próximo com 2-opt para maiores, a partir de coordenadas ou matriz.

Uso gratuitoSem cadastroResultados instantâneos

Solucionador do Caixeiro Viajante (TSP)Experimente agora — grátis ▼

Exemplos rápidos:

5 cidades quadrado+pico 8 cidades aleatórias 8 capitais da UE Matriz 4×4 Benchmark 10 cidades Triângulo (caminho aberto)

⌖ Coordenadas (x, y) ▦ Matriz de distância

Cidades ou matriz

Linhas de coordenadas: A, 10, 20 ou 10 20. Linhas da matriz: 0 10 15 20 — uma linha por vez, quadrada, não negativa. Máx 40 cidades.

Etiquetas da matriz (opcional)

Etiquetas separadas por vírgula ou espaço, uma por linha da matriz. Padrão A, B, C… se omitido.

Algoritmo

Tipo de rota

Embed Solucionador do Caixeiro Viajante (TSP) Widget

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:

minimizar Σ_i=1^n-1 d(π(i), π(i+1)) + d(π(n), π(1))

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:

C(S, j) = min_{k ∈ S \ {j}} [ C(S \ {j}, k) + d(k, j) ]

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:

Antes: ... a — b ... c — d ... Após troca 2-opt: ... a — c ... b — d ... Se d(a,c) + d(b,d) < d(a,b) + d(c,d) → aceitar troca, inverter a sub-rota b..c

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.

A, 10, 20 B, 40, 70 C, 75, 30 Paris: 2.35, 48.86 10 20 ← etiqueta auto C1

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.

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0

Comparação de Algoritmos

Algoritmo	Complexidade de tempo	Memória	Qualidade do resultado	Tamanho prático
Força bruta	O(n!)	O(n)	Ideal	n ≤ 10
Held–Karp DP	O(2ⁿ · n²)	O(2ⁿ · n)	Ideal	n ≤ 20
Vizinho Mais Próximo	O(n²)	O(n)	~25% pior que o ideal	n ≤ milhares
NN + 2-opt	O(n² · passagens)	O(n)	~2–5% pior que o ideal	n ≤ centenas

Como Usar Este Solucionador

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.
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.
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.
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.
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.8), 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

Cite este conteúdo, página ou ferramenta como:

"Solucionador do Caixeiro Viajante (TSP)" em https://MiniWebtool.com/br/solucionador-do-caixeiro-viajante-tsp/ de MiniWebtool, https://MiniWebtool.com/

pela equipe miniwebtool. Atualizado: 21 de abr de 2026

Você também pode experimentar nosso Solucionador de Matemática AI GPT para resolver seus problemas de matemática através de perguntas e respostas em linguagem natural.

Solucionador do Caixeiro Viajante (TSP)

Solucionador do Caixeiro Viajante (TSP)

O Que é o Problema do Caixeiro Viajante?

Como Funciona Este Solucionador

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

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

Formatos de Entrada

Modo Coordenadas (x, y)

Modo Matriz de distância

Comparação de Algoritmos

Como Usar Este Solucionador

Exemplo Prático

Aplicações no Mundo Real

Perguntas Frequentes

O que é o Problema do Caixeiro Viajante?

O que é o algoritmo Held–Karp?

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

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

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

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

Leitura Adicional

Operações matemáticas avançadas:

Ferramentas populares e atualizadas:

Baixe tudo em um único ZIP com o Pro