O Problema do Caixeiro Viajante

 por Gabriela Pellegrini Morasco

O Problema do Caixeiro Viajante:

O problema do caixeiro viajante é um dos assuntos mais conhecidos e estudados no universo da Ciência da Computação. Suponha que um caixeiro tenha de visitar n cidades diferentes, iniciando e encerrando sua viagem na primeira cidade. Suponha, também, que não importa a ordem com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer outra. O problema do caixeiro viajante consiste em descobrir a rota que torna mínima a viagem total.

Complexidade computacional do problema do caixeiro:

O problema do caixeiro é um problema de otimização combinatória. A primeira coisa que podemos pensar para resolver esse tipo de problema é reduzi-lo a um problema de enumeração: achamos todas as rotas possíveis e, usando um computador, calculamos o comprimento de cada uma delas e então vemos qual a menor.

Para acharmos o número R(n) de rotas para o caso de n cidades, basta fazer um raciocínio combinatório simples e clássico. Por exemplo, no caso de n = 4 cidades, a primeira e última posição são fixas, de modo que elas não afetam o cálculo; na segunda posição podemos colocar qualquer uma das 3 cidades restantes B, C e D, e uma vez escolhida uma delas, podemos colocar qualquer uma das 2 restantes na terceira posição; na quarta posição não teríamos nenhuma escolha, pois sobrou apenas uma cidade; consequentemente, o número de rotas é 3 x 2 x 1 = 6. De modo semelhante, para o caso de n cidades, o número total de escolhas que podemos fazer é (n-1) x (n-2) x ... x 2 x 1. De modo que, usando a notação de fatorial: R(n) = (n - 1)!.

Método reducionista:

Nossa estratégia reducionista consiste em gerar cada uma dessas R(n) = (n - 1)! rotas, calcular o comprimento total das viagens de cada rota e ver qual delas tem o menor comprimento total. Mas será que este trabalho é computacionalmente viável?

Suponhamos temos um computador capaz de fazer 1 bilhão de adições por segundo. No caso de 20 cidades, o computador precisa apenas de 19 adições para dizer qual o comprimento de uma rota e então será capaz de calcular 109 / 19 = 53 milhões de rotas por segundo. Contudo, essa velocidade é pequena em relação às 19! rotas que deverão ser calculadas. O valor de 19! é 121.645.100.408.832.000 (ou, aproximadamente, 1.2 x 1017 em notação científica). Consequentemente, ele precisará de 1.2 x 1017 / ( 53 milhões ) = 2.3 x 109 segundos para completar sua tarefa, o que equivale a cerca de 73 anos. O problema é que a quantidade (n - 1)! cresce com uma velocidade alarmante, sendo que muito rapidamente o computador torna-se incapaz de executar o que lhe pedimos.

Observe que o aumento do número de pontos provoca uma muito lenta diminuição na velocidade com que o computador calcula o tempo de cada rota, mas provoca um imensamente grande aumento no tempo total de cálculo. Em outras palavras: a inviabilidade computacional é devida à presença da fatorial na medida do esforço computacional do método da redução. Então o método reducionista não é prático, a não ser para o caso de poucas cidades.

Utilizando grafos:

Uma alternativa para a modelagem matemática do problema é feita através de uma estrutura matemática denominada grafo. Um grafo é um conjunto de pontos (que chamamos de vértices), os quais podem ser associados através de linhas (que chamamos de arestas). Na figura a seguir temos um grafo com 5 vértices e 6 arestas.

No grafo associado ao problema do caixeiro viajante, cada cidade é representada por um vértice, e as arestas representam as vias (estradas, por exemplo) que ligam as cidades. A cada aresta podemos associar um número que representa a distância entre as duas cidades conectadas por ela. 

O obstáculo à resolução deste problema, como vimos, é o crescimento exponencial do número de trajetos quando aumentam o número de cidades. Esta característica torna inviável o uso da comparação de todas as trajetórias como forma de decidir qual a ótima. Vamos trabalhar, então, com mais uma estrutura de dados: a árvore geradora mínima. A ideia desta árvore é simplificar o grafo, gerando a menor rota computacionalmente viável entre os seus vértices.

Existem diversos algoritmos para o cálculo da árvore geradora mínima, tais como o algoritmo de Prim e o algoritmo de Kruskal. A condição mínima para que o grafo possua uma árvore geradora é que ele seja conexo. A árvore gerada deve ser percorrida em recursão, passando por todos os pontos, para que seja encontrada a rota. Sabemos que a descoberta da árvore geradora mínima a partir de um grafo de cidades não nos dá a melhor solução, pois não considera o ciclo entre as cidades, pelo contrário, a árvore gerada não deve ter nenhum ciclo, porém nos dá uma solução computacionalmente viável.

Bibliografia:

• http://www.mat.ufrgs.br/~portosil/caixeiro.html 
• http://www.uff.br/sintoniamatematica/grandestemaseproblemas/grandestemaseproblemas-html/audio-caixeiro-br.html
• http://www.lti.pcs.usp.br/pcs2059/trabalhos/Tema7-dia1.pdf