Caixeiro viajante algoritimo geneticox

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1666 palavras )
  • Download(s) : 0
  • Publicado : 1 de dezembro de 2012
Ler documento completo
Amostra do texto
ENGENHARIA DE PRODUÇÃO
PESQUISA OPERACIONAL II- ENG0829
PROFESSORA:


Problema do caixeiro viajante

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 problemascombinató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 naprimeira 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 pararesolver 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. ( É 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 parao 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ãoteríamos nenhuma escolha, pois sobrou apenas uma cidade; consequentemente, o número de rotas é 3 x 2 x 1 = 6, resultado que tínhamos 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 defazer 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...
tracking img