Solucionador do Caixeiro Viajante — Encontre a Rota Mais Curta Por Todas as Cidades
Nosso Solucionador do Caixeiro Viajante encontra o percurso de custo mínimo exato que visita cada cidade exatamente uma vez e retorna à cidade de partida, dada uma matriz de distâncias entre cidades, usando o algoritmo de programação dinâmica de máscara de bits de Held-Karp — um método exato deliberadamente limitado a no máximo 12 cidades, já que o problema é NP-difícil em geral.
Resposta rápida
Insira uma matriz de distâncias entre cidades para encontrar instantaneamente o percurso de ida e volta mais curto exato via programação dinâmica de Held-Karp.
Digite uma linha por cidade, distâncias separadas por vírgula, ex. 0,10,15,20 depois 10,0,35,25. Até 12 cidades.
Como usar Solucionador do Caixeiro Viajante — Programação Dinâmica Exata de Held-Karp Online
- 1
Insira uma matriz de distâncias, uma linha por cidade, com distâncias separadas por vírgulas, ex. 0,10,15,20 depois 10,0,35,25 e assim por diante.
- 2
A matriz deve ser quadrada, com cada entrada dando a distância entre duas cidades (as entradas diagonais são tipicamente 0).
- 3
Clique em 'Calcular' para encontrar o percurso ótimo exato via programação dinâmica de Held-Karp.
Por que usar Solucionador do Caixeiro Viajante — Programação Dinâmica Exata de Held-Karp Online?
O problema do caixeiro viajante pergunta pela rota mais curta possível que visita cada cidade exatamente uma vez e retorna ao início — um problema NP-difícil clássico onde verificar por força bruta todas as (n−1)!/2 rotas possíveis se torna impossível além de um punhado de cidades. O algoritmo de Held-Karp melhora drasticamente a força bruta usando programação dinâmica sobre subconjuntos: rastreia, para cada subconjunto de cidades visitadas e cada possível cidade final, a forma mais barata de alcançar esse estado, construindo a partir de subconjuntos pequenos até o conjunto completo em tempo O(n² · 2ⁿ) em vez de O(n!). Isso ainda é exponencial, então esta calculadora limita o problema a 12 cidades, onde Held-Karp permanece confortavelmente rápido enquanto ainda encontra o percurso exato e comprovadamente ótimo (não apenas uma boa aproximação).
Perguntas frequentes
Ferramentas relacionadas
Verificador de Caminho Hamiltoniano — Visite Cada Nó Uma Vez Online
Verifique se um grafo tem um caminho hamiltoniano — um caminho que visita cada nó exatamente uma vez — via busca com retrocesso. Calculadora gratuita, limitada a grafos de até 10 nós.
Calculadora de Árvore Geradora Mínima — Algoritmo de Kruskal Online
Encontre a árvore geradora mínima de um grafo ponderado usando o algoritmo de Kruskal. Calculadora gratuita com uma entrada simples de lista de arestas e detecção de ciclos via union-find.
Solucionador de Programação Linear — Método de Ponto de Vértice de 2 Variáveis Online
Resolva um programa linear de 2 variáveis encontrando e avaliando cada ponto de vértice da região factível. Calculadora gratuita, maximize ou minimize com restrições lineares.