Comprimento do percurso
Mais curto encontrado
Passos
Percursos possíveis
  • Percurso
  • Mais curto encontrado
  • Partida

Método Comprimento Acima do mais curto Passos
- - -
- - -
- - -
- - -
- - -

Mais sobre o problema do caixeiro-viajante

Problema do caixeiro-viajante

Um caixeiro-viajante tem de visitar cada cidade uma vez e regressar a casa. Que ordem torna a viagem mais curta? A pergunta é fácil de fazer e, à medida que o número de cidades cresce, impossível de responder experimentando todas as ordens: 30 cidades já permitem cerca de 4,4 × 10³⁰ percursos. Espalhe cidades num mapa ou coloque as suas com um clique e veja regras práticas rápidas, melhorias engenhosas e um método exato construírem os seus percursos passo a passo, e quão perto chegam os métodos rápidos. Escolha como as cidades estão dispostas e quantas são, escolha um método e prima Resolver para o ver construir um percurso de ida e volta passo a passo, ou Passo para avançar um movimento de cada vez. Clique no mapa para acrescentar uma cidade, ou clique numa cidade para a remover. Comparar todos executa cada método nas mesmas cidades e mostra a distância de cada um ao percurso mais curto encontrado. A cidade vermelha é onde a viagem começa.

Como funciona

  1. Escolha uma disposição e o número de cidades, ou clique no mapa para colocar as suas e clique numa cidade para a remover.
  2. Escolha um método e prima Resolver para o acompanhar passo a passo, ou Passo para avançar um movimento de cada vez.
  3. Prima Comparar todos para executar cada método nas mesmas cidades e veja quanto cada percurso fica acima do mais curto encontrado.

Porque é difícil

Com n cidades há (n − 1)! / 2 percursos diferentes, porque não importa onde se começa nem em que sentido se percorre o circuito. São 12 para 5 cidades, 181 440 para 10 e cerca de 6 × 10¹⁶ para 20. Não se conhece nenhum método que encontre a viagem mais curta para qualquer mapa num tempo que cresça apenas como uma potência de n; o problema é NP-difícil. O melhor método exato desta aplicação, a programação dinâmica de Held–Karp, de 1962, ainda precisa de cerca de n² · 2ⁿ passos, por isso aqui está limitado a 12 cidades.

Bons percursos, depressa

Na prática, encontram-se depressa percursos quase mínimos. O vizinho mais próximo vai sempre para a cidade não visitada mais próxima e termina tipicamente cerca de 25% acima do melhor percurso. A inserção mais barata faz crescer um circuito e acrescenta a cidade que menos o alonga. O 2-opt pega num percurso qualquer e vai substituindo duas arestas por duas mais curtas, o que elimina todos os cruzamentos e normalmente fica a cerca de 5%. O recozimento simulado faz movimentos 2-opt aleatórios e, enquanto ainda está «quente», aceita alguns que tornam o percurso mais longo, para poder sair de becos sem saída antes de estabilizar.

Perguntas frequentes

Existe uma fórmula para o percurso mais curto?

Não. O percurso mais curto depende das posições exatas de todas as cidades, e nenhum método conhecido o encontra para qualquer mapa sem, no pior caso, uma quantidade de trabalho que cresce exponencialmente. Para algumas centenas ou milhares de cidades, solucionadores exatos especializados como o Concorde provam mesmo assim percursos ótimos combinando programação linear com podas engenhosas, e a maior instância resolvida de forma exata até hoje tem 85 900 pontos.

Porque é que o 2-opt elimina todos os cruzamentos?

Se duas arestas de um percurso se cruzam, as quatro cidades que ligam formam um quadrilátero cujas diagonais são essas duas arestas. Trocá-las por dois lados opostos do quadrilátero é sempre mais curto, pela desigualdade triangular, e inverte o troço do percurso entre elas. O 2-opt continua a fazer essas trocas até nenhuma ajudar, por isso o seu percurso final nunca se cruza a si próprio.

O que é a temperatura no recozimento simulado?

Controla a disposição do método para aceitar um movimento que torna o percurso mais longo. Um movimento que acrescenta d ao comprimento é aceite com probabilidade e^(−d/T). A uma temperatura T alta quase tudo é aceite, o que permite ao percurso escapar a uma disposição fraca; à medida que T desce, o método torna-se guloso e estabiliza. O nome vem do arrefecimento lento de um metal para que os seus átomos encontrem uma disposição de baixa energia.

Porque é que o método exato está limitado a 12 cidades?

O Held–Karp guarda o caminho mais curto para cada subconjunto de cidades e cada última cidade possível, ou seja, cerca de n · 2ⁿ números, e calcula cada um com n comparações. Para 12 cidades são algumas centenas de milhares de passos; para 25 cidades seriam milhares de milhões. Mesmo assim, é enormemente mais rápido do que experimentar todos os (n − 1)! / 2 percursos: para 12 cidades seriam quase 20 milhões.

É enviado algo para um servidor?

Não. As cidades e os cinco métodos funcionam no seu navegador. As cidades que coloca com um clique ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor