O problema do caixeiro viajante

Não se iluda com a aparência de brincadeira deste problema. Ele NÃO é mais uma curiosidade inconsequente para entreter alunos desmotivados. Em verdade, ele é um problema que deve fazer parte da bagagem de todo profissional competente da área matemática.

Por | @oficinadanet Programação

Não se iluda com a aparência de brincadeira deste problema. Ele NÃO é mais uma curiosidade inconsequente para entreter alunos desmotivados. Em verdade, ele é um problema que deve fazer parte da bagagem de todo profissional competente da área matemática. Sua importância resume-se em duas capacidades:

  • de modo simples e concreto, exemplifica a enorme velocidade de crescimento da fatorial

  • prova-se que muitos problemas combinatórios envolvem tantas alternativas de solução quanto este problema, de modo que ele é uma espécie de "metro" com o qual medimos a complexidade computacional dos problemas combinatórios ocorrendo em engenharia e no trabalho científico.

Formulando o problema do caixeiro:

Suponha que um caixeiro viajante 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.

Exemplificando o caso n = 4:
se tivermos quatro cidades A, B, C e D, uma rota que o caixeiro deve considerar poderia ser: saia de A e daí vá para B, dessa vá para C, e daí vá para D  e então volte a A. Quais são as outras possibilidades ? É muito fácil ver que existem seis rotas possíveis:

  • ABCDA

  • ABDCA

  • ACBDA

  • ACDBA

  • ADBCA

  • ADCBA

Complexidade computacional do problema do caixeiro:

O problema do caixeiro é um clássico exemplo de problema de otimização combinatória. A primeira coisa que podemos pensar para resolver esse tipo de problema é reduzí-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. ( É claro que se acharmos todas as rotas estaremos contando-as, daí podermos dizer que estamos reduzindo  o problema de otimização a um de enumeração ).

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, resultado que tinhamos obtido antes contando diretamente a lista de rotas acima.
De modo semelhante, para o caso de n cidades, como a primeira é fixa, o leitor não terá nenhuma dificuldade em ver que 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 )!.

Assim que 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. Trabalho fácil para o computador, diria alguém. Bem, talvez não. Vejamos o porquê.

Suponhamos temos um muito veloz computador, capaz de fazer 1 bilhão de adições por segundo. Isso parece uma velocidade imensa, capaz de tudo. Com efeito, 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 imensa velocidade é um nada frente à imensidão do número 19! de rotas que precisará examinar. Com efeito, acredite se puder, 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. Constate isso mais claramente na tabela a seguir:

n rotas por segundo ( n - 1 )! cálculo total
5 250 milhoes 24 insignific
10 110 milhoes 362 880 0.003 seg
15 71 milhoes 87 bilhoes 20 min
20 53 milhoes 1.2 x 1017 73 anos
25 42 milhoes 6.2 x 1023 470 milhoes de anos

Observe que o aumento no valor do n provoca uma muito lenta diminuição na velocidade com que o computador calcula o tempo de cada rota ( ela diminui apenas de um sexto ao n aumentar de 5 para 25 ), 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. Com efeito, se essa complexidade fosse expressa em termos de um polinómio em n o nosso computador seria perfeitamente capaz de suportar o aumento do n. Confira isso na seguinte  tabela que corresponde a um esforço computacional polinomial R( n ) = n5:

n rotas por segundo n 5 cálculo total
5 250 milhoes 3 125 insignific
10 110 milhoes 100 000 insignific
15 71 milhoes 759 375 0.01 seg
20 53 milhoes 3 200 000 0.06 seg
25 42 milhoes 9 765 625 0.23 seg

Então o método reducionista não é prático ( a não ser para o caso de muito poucas cidades ), mas será que não pode-se inventar algum método prático  ( por  exemplo, envolvendo esforço polinomial na variável número de ) para resolver o problema do caixeiro? Bem, apesar de inúmeros esforços, ainda não foi achado um tal método  e começa-se a achar que o mesmo não existe.

A existência ou não de um método  polinomial para resolver o problema do caixeiro viajante é um dos grandes  problemas em aberto da Matemática na medida em que  S. A. COOK ( 1971 ) e R. M. KARP ( 1972 )) mostraram que uma grande quantidade de problemas importantes ( como é o caso de muitos tipos de problemas de otimização  combinatória, o caso do problema da decifragem de senhas criptografadas com  processos modernos como o DES, etc ) podem ser reduzidos, em tempo polinomial, ao problema do caixeiro.
Consequentemente: se descobrirmos como resolver o problema do caixeiro  em tempo polinomial ficaremos sendo capazes de resolver, também em tempo polinomial, uma grande quantidade de outros problemas matemáticos importantes;  por outro lado, se um dia alguém provar que é impossível resolver o problema  do caixeiro em tempo polinomial no número de cidades, também se terá estabelecido  que uma grande quantidade de problemas importantes não tem solução prática.

Costuma-se resumir essas propriedades do problema do caixeiro dizendo que ele pertence à categoria dos problemas NP - completos.

Fonte: http://www.mat.ufrgs.br/~portosil/caixeiro.html

Recomendado
Comentários
Carregar comentários
Destaquesver tudo