O PROBLEMA DO CAIXEIRO VIAJANTE

Prévia do material em texto

O PROBLEMA DO CAIXEIRO VIAJANTE 
Imaginem que o trabalho de vocês é ser caixeiro viajante (representante de vendas que viaja por conta de uma firma oU por conta própria, encarregado dos negócios de várias casas) se vocês colocarem isso em situações do dia a dia, vocês poderiam citar (.....), assim sendo, uma boa parte das despesas de vocês é em combustível, mas como vocês sabem, a gasolina tá cara pra caramba, então vocês tem que pegar o percurso mais rápido e barato.
	Nos dias mais fraquinhos vocês saem de casa para visitar um ou dois clientes. Claro que esses dias a escolha do percurso não é um problema. Mas tem dias que você sai de casa para visitar um monte de clientes espelhados aí pelo brasil a fora, ENTÃO vamos supor que vocês saiam de casa aqui em são luís e tem que visitar 4 clientes em 4 cidades diferentes e depois voltar para casa.
	Isso parece ser muito fácil, mas a ideia do caixeiro viajante é calcular previamente a ordem da visitação dos clientes, tentando gastar menos gasolina.
	Primeiro a gente tem que numerar as diferentes opções: - Podemos sair de São Luís e ir direto a uma das 4 cidades, aí isso dá a nós 4 possibilidades de escolha. Depois de escolher a primeira cidade, escolhemos uma das 3 restantes, aí depois a gente escolhe uma das duas que sobraram e a última que sobrou. Isso nos dá 24 possibilidades. Depois é só ver quantos Km faz em cada uma das 24 opções e escolher a que fará menos km e essa será a melhor escolha.
	A gente faz a mesma coisa se tiver 5 cidades para visitar e isso nos dá 120 opções ou 720 pra um percurso com 6 cidades
	O problema é quando o número de cidades aumenta MUITO, tipo muito mesmo. Por exemplo: se a gente tivesse que visitar 41 cidades, nós teríamos que analisar essas opções, ou seja, mais ou menos o número de átomos existentes em todo o planeta terra. Assim, mesmo que a gente saiba calcular o número de rotas diferentes, mesmo os mais potentes computadores do mundo levariam anos pra analisar todas essas rotas e comparar elas pra encontrar a melhor! 
	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. 
E esse é o problema viajante...................
A gente poderia escolher um percurso só no olhan,do, mas a gente acaba gastando bem mais e detalhe, se estima que de 10 a 15% do preço de um produto está associado ao transporte dele, enfim
O PROBLEMA DO CAIXEIRO VIAJANTE ESTÁ NO CENTRO DE UMA DAS MAIORES QUETÕES CIENTÍFICAS EM ABERTO DO NOSSO TEMPO.
Os matemáticos especialistas em ciência da computação classificam os problemas pela dificuldade dos algoritmos usados para resolver eles e há um grande grupo chamado PROBLEMAS NP que é o grupo que o problema do caixeiro viajante pertence.
Acontece que ninguém sabe se os problemas desse grupo são mesmo tão difíceis porque não existe nenhum algoritmo para resolver eles de forma simples ou se ele não existe ainda porque ninguém encontrou.
E esse é um problema tão pertinente que ele é um dos 6 problemas do prémio milolennium. Se trata de 6 problemas que o  Instituto Clay de Matemática oferece um milhão de dólares pela solução. 
A verdade é que se alguém encontrar um algoritmo eficiente para resolver o problema do caixeiro viajante, imediatamente todos os problemas em NP também poderão ser resolvidos de maneira eficiente, além disso um desses problemas é o problema de quebra de criptografia da chave pública que é um elemento usado em transações comerciais na internet. Enfim pô.
No dia que esse algoritmo for descoberto, toda a sociedade moderna baseada na internet irá no mínimo tremer