Antigamente muitos vendedores, chamados de caixeiros viajantes, ganhavam a vida oferecendo seus produtos em diferentes cidades. Imagine que um caixeiro viajante escolhesse algumas cidades e precisasse encontrar o caminho mais curto para suas andanças. Em que ordem ele deveria percorrer as cidades escolhidas? Se fossem poucas cidades, seria fácil descobrir. Mas e se o caixeiro estivesse em Brasília e quisesse percorrer as capitais de todos os 26 estados brasileiros? Em que ordem ele deveria visitar essas cidades? Como descobrir qual o caminho mais curto? Uma opção seria considerar todas as possíveis ordenações das 26 cidades. Mas são tantas, que se levássemos apenas 1 segundo para calcular a distância total de cada possível percurso, levaríamos cerca de um bilhão de vezes a idade do universo para encontrar a resposta. Isso acontece porque o número de percursos alternativos cresce assustadoramente quando aumentamos o número de cidades. Esse é o chamado Problema do Caixeiro Viajante, uma questão matemática muito importante para a indústria. Quem encontrar um método eficiente para resolvê-lo pode ganhar uma verdadeira fortuna!



INFORMAÇÕES COMPLEMENTARES

QUANTOS CAMINHOS SÃO POSSÍVEIS?

Se o caixeiro tivesse que passar por apenas 3 cidades, digamos, Rio de Janeiro, São Paulo e Curitiba, teria 6 possíveis ordenações para percorrê-las:

Rio – São Paulo – Curitiba
Rio – Curitiba – São Paulo
São Paulo – Rio – Curitiba
São Paulo – Curitiba – Rio
Curitiba – Rio – São Paulo
Curitiba – São Paulo – Rio

Como calculamos o número de ordenações? Veja: temos 3 opções para a primeira cidade: Rio, São Paulo ou Curitiba. Quando escolhemos a primeira cidade, ficamos com duas opções para escolher a segunda cidade, então são 3 x 2 = 6 maneiras de fixar qual serão a primeira e a segunda cidades. Claro que, uma vez que a primeira e a segunda estejam fixadas, não nos resta opção para a última. Então são 6 possíveis ordenações.

O número total de ordenações possíveis de N elementos é chamado de permutação de N elementos.

Mas e com as 26 capitais? Temos 26 opções para a primeira cidade. Para cada escolha de primeira cidade, ficamos com 25 opções de segunda cidade, logo são 26 vezes 25 formas de decidir quais serão as duas primeiras cidades. Para cada opção que fizermos com relação às duas primeiras cidades, ficaremos com 24 possibilidades para a terceira cidade. Logo há 26 x 25 x 24 formas de quais serão a primeira, a segunda e a terceira cidade. Seguindo esse raciocínio, vemos que o número total de formas de ordenar as 26 cidades é:

26 x 25 x 24 x 23 x 22 x 21 x ... x 5 x 4 x 3 x 2 x 1.

Para denotar mais facilmente produtos deste tipo, isto é, o produto de todos os números naturais de 1 até um certo número N utilizamos o símbolo N! e lemos N fatorial. Assim, temos 26! possíveis ordenações das 26 capitais.


FAZENDO AS CONTAS

A chamada de áudio nos conta que se levássemos apenas um segundo para calcular a distância total de cada percurso, gastaríamos cerca de um bilhão de vezes a idade do universo para terminar as contas. Vamos verificar essa informação?

Estima-se que o universo tem aproximadamente 13,7 bilhões de anos, isto é, 13.000.000.000 de anos.

Quantos segundos gastaríamos para fazer as contas das distâncias de todos os percursos possíveis do caixeiro para visitar as 26 capitais? Se são 26! percursos possíveis e gasta-se um segundo para cada percurso, gastaríamos 26! segundos. Mas quanto é 26 fatorial? Se você tiver uma calculadora científica, pode digitar 26 e depois calcar no ponto de exclamação e obterá o resultado. Se não tem calculadora científica, o jeito é fazer as multiplicações uma a uma: 26 x 25 x 24 x 23 x ... x 3 x 2 x 1.

De qualquer forma que você faça, vai descobrir que

26! = 403.291.461.126.605.635.584.000.000.

Isso quer dizer que gastaríamos 403.291.461.126.605.635.584.000.000 segundos para calcular as distâncias de todos os percursos. Como cada hora tem 60 minutos e cada minuto tem 60 segundos, resulta que cada hora tem 3.600 segundos. Logo, dividindo por 3.600, descobrimos que gastaremos

112.025.405.868.501.565.440.000 horas

para fazer todos os cálculos. Observando que cada dia tem 24 horas, isso equivale a

4.667.725.244.520.898.560.000 dias.

Como cada ano tem 365 dias, podemos calcular quantos anos levaremos dividindo por 365. Obtemos

12.788.288.341.153.146.739 anos (e mais alguns dias)

Como o universo tem aproximadamente 13 bilhões de anos, vamos dividir por 13 bilhões. Obtemos, arredondando, que

12.788.288.341.153.146.739 anos = 983.714.487 vezes a idade do universo.

Mas isso é praticamente um bilhão de vezes a idade do universo!!!


O PROBLEMA DO CAIXEIRO VIAJANTE

O problema do caixeiro viajante é uma importante questão da área de otimização matemática. Tem grande relevância para o campo da logística e da produção, além de outros.

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 aumenta-se 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. Em vez disso, pesquisadores buscam métodos alternativos que sejam viáveis computacionalmente e que gerem soluções próximas da solução ótima.

Para saber mais sobre crescimento exponencial, acesse: http://www.uff.br/cdme/exponencial/.


REFERÊNCIAS BIBLIOGRÁFICAS

Devlin, K. Os Problemas do Milênio – Sete Grandes Enigmas Matemáticos de Nosso Tempo. Editora Record, 2004.




Creative Commons License

Responsável: Anne Michelle Dysman Gomes.
Idealização: Anne Michelle Dysman Gomes e Humberto José Bortolossi.
Roteiro: Anne Michelle Dysman Gomes.
Informações complementares: Anne Michelle Dysman Gomes.
Locução: Eric Brasil.
Técnico de som: Eric Maia.
Revisão: Patrícia Maia.
Página WEB: Anne Michelle Dysman Gomes e Humberto José Bortolossi.

Dúvidas? Sugestões? Nós damos suporte! Contacte-nos pelo e-mail:
conteudosdigitais@im.uff.br.