O problema do caixeiro-viajante explicado

Dê a um caixeiro-viajante uma lista de cidades e peça-lhe a viagem mais curta que visite cada uma delas uma vez e regresse a casa. Qualquer pessoa consegue verificar um percurso proposto, e qualquer pessoa consegue melhorar um mau a olho, mas ninguém conhece um método rápido que encontre sempre o melhor. O problema do caixeiro-viajante tornou-se o exemplo clássico de um problema difícil, e os métodos inventados para o atacar planeiam hoje entregas, perfuram placas de circuito impresso e montam genomas.

Um mapa de cidades ligadas por um percurso fechado, com a cidade de partida assinalada e um percurso mais curto, esbatido, por baixo
Um mapa de cidades ligadas por um percurso fechado, com a cidade de partida assinalada e um percurso mais curto, esbatido, por baixo

O problema

Um percurso visita cada cidade exatamente uma vez e termina onde começou; o seu comprimento é a soma das distâncias pelo caminho. A tarefa é encontrar o percurso mais curto. Na versão aqui apresentada, as distâncias são linhas retas num mapa, por isso ir de A a C nunca é mais longo do que passar por B: é o problema do caixeiro-viajante métrico. O enigma foi discutido pelo matemático Karl Menger por volta de 1930, e o nome generalizou-se nas décadas seguintes, quando matemáticos da RAND Corporation se dedicaram a ele.

Karl Menger em 1970. Discutiu o problema do caixeiro-viajante por volta de 1930.
Karl Menger em 1970. Discutiu o problema do caixeiro-viajante por volta de 1930.

A explosão dos percursos

Fixe a cidade de partida. Há n − 1 escolhas para a cidade seguinte, n − 2 para a outra a seguir, e assim por diante, e cada percurso pode ser feito em dois sentidos, por isso há (n − 1)! / 2 percursos. Para 10 cidades são 181 440, fácil para um computador. Para 20 são cerca de 6 × 10¹⁶, e para 70 o número ultrapassa o de átomos do universo observável. Computadores mais rápidos pouco ajudam: cada cidade a mais multiplica o trabalho por cerca de n.

NP-difícil

Em 1972, Richard Karp mostrou que a questão de saber se um grafo tem um circuito que passa por todos os vértices, um ciclo hamiltoniano, pertence a uma família de problemas NP-completos que são todos igualmente difíceis. O problema do caixeiro-viajante contém essa questão, por isso é NP-difícil. Um método rápido para ele daria métodos rápidos para milhares de outros problemas de escalonamento, logística e criptografia. Saber se tal método existe é a questão P versus NP, um dos Problemas do Prémio do Milénio.

Um método exato: Held–Karp

Em 1962, Michael Held e Richard Karp, e independentemente Richard Bellman, usaram a programação dinâmica. Para cada conjunto S de cidades e cada cidade j em S, calcula-se o caminho mais curto que parte da cidade de origem, visita exatamente as cidades de S e termina em j. Cada valor decorre dos valores para S sem j, por isso a tabela é preenchida dos conjuntos pequenos para os grandes, e o percurso mais curto surge no fim. São precisos cerca de n² · 2ⁿ passos em vez de n!, o que, para 30 cidades, é a diferença entre minutos e a idade do universo, mas o crescimento continua a ser exponencial.

Richard Bellman em 1962, fotografado por Alfred Eisenstaedt. Deu o nome à programação dinâmica no início da década de 1950, quando trabalhava na RAND Corporation.
Richard Bellman em 1962, fotografado por Alfred Eisenstaedt. Deu o nome à programação dinâmica no início da década de 1950, quando trabalhava na RAND Corporation.

Regras de construção rápidas

O vizinho mais próximo viaja sempre para a cidade mais próxima ainda não visitada. É simples e rápido, mas tende a deixar para trás algumas cidades que têm de ser recolhidas com longos desvios no fim, por isso os seus percursos são tipicamente cerca de 25% mais longos do que o melhor. Os métodos de inserção, por sua vez, mantêm um circuito fechado e acrescentam as cidades restantes uma a uma onde custam menos. Em 1976, Nicos Christofides descobriu uma construção que garante no máximo 1,5 vezes o ótimo em qualquer mapa métrico, um limite que se manteve quase imbatível durante mais de quarenta anos.

Melhorar um percurso: 2-opt

A pesquisa local parte de um percurso qualquer e vai fazendo pequenas alterações que o encurtam. O movimento clássico, o 2-opt, remove duas arestas e volta a ligar as duas partes ao contrário, o que inverte o troço entre elas. Sempre que duas arestas se cruzam, este movimento desfaz o cruzamento e poupa comprimento, por isso um percurso que o 2-opt não consegue melhorar nunca se cruza a si próprio. Em mapas aleatórios, os percursos 2-opt ficam tipicamente cerca de 5% acima do ótimo. Movimentos mais fortes que trocam três arestas, ou o método de profundidade variável de Lin e Kernighan, de 1973, aproximam-se ainda mais.

Recozimento simulado

A pesquisa local pode ficar presa num percurso em que cada movimento isolado o piora, embora exista um percurso muito melhor. O recozimento simulado, aplicado a este problema por Scott Kirkpatrick, Daniel Gelatt e Mario Vecchi em 1983, inspira-se na metalurgia: aceita um movimento pior com uma probabilidade que depende de uma temperatura, alta no início e baixada lentamente. No início, o percurso vagueia livremente; no fim, só são aceites melhorias. Com um arrefecimento suficientemente lento, encontra de forma fiável percursos muito bons.

Explore

Abra a demonstração do caixeiro-viajante para colocar até 200 cidades ao acaso, num círculo, em aglomerados, numa grelha ou onde clicar. Veja o vizinho mais próximo deixar para trás as suas últimas cidades, veja o 2-opt desfazer cada cruzamento, acompanhe a temperatura do recozimento simulado à medida que arrefece e deixe o Held–Karp provar o percurso mais curto para até 12 cidades. Comparar todos executa cada método no mesmo mapa e mostra quanto cada percurso fica acima do mais curto encontrado.

Perguntas frequentes

Onde é usado o problema do caixeiro-viajante?

Sempre que algo tem de visitar muitos lugares numa ordem eficiente: rotas de entrega e de recolha, o trajeto de uma broca ou de um laser sobre uma placa de circuito impresso, a ordem em que um telescópio observa estrelas, a ordem de recolha de encomendas num armazém e, com outras distâncias, a ordem dos fragmentos na montagem de uma sequência de ADN.

Qual é o maior problema alguma vez resolvido de forma exata?

Em 1954, George Dantzig, Ray Fulkerson e Selmer Johnson provaram o percurso mais curto por 49 cidades dos Estados Unidos. Em 2006, o solucionador Concorde, de David Applegate, Robert Bixby, Vašek Chvátal e William Cook, provou o percurso ótimo por 85 900 pontos de um projeto de chip, após anos de tempo de computação.

O percurso mais curto está sempre livre de cruzamentos?

Sim, num mapa plano com distâncias em linha reta. Se duas arestas se cruzassem, trocá-las por dois lados do quadrilátero que formam encurtaria o percurso, por isso um percurso com cruzamentos não pode ser o mais curto.

As heurísticas dão sempre o mesmo percurso?

O vizinho mais próximo, a inserção mais barata e o 2-opt, tal como são usados aqui, são determinísticos: nas mesmas cidades dão o mesmo percurso. O recozimento simulado parte de um percurso aleatório e faz movimentos aleatórios, por isso duas execuções podem terminar com percursos diferentes, normalmente de comprimento quase igual.

Pronto para experimentar?

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

Abrir a demonstração do caixeiro-viajante