O PROBLEMA DO CAIXEIRO VIAJANTE

[pic 1]

UNIVERSIDADE ESTADUAL DA PARAÍBA - UEPB

CENTRO DE CIÊNCIAS EXATAS E SOCIAIS APLICADAS

CURSO DE LICENCIATURA EM MATEMÁTICA

O PROBLEMA DO CAIXEIRO VIAJANTE

O problema do caixeiro viajante (pcv) consiste em determinar a rota com menor custo para percorrer uma serie de cidades, visitando cada cidade exatamente uma vez e voltando ao ponto de partida.

O pcv e problema relacionado a combinação, devido a melhor rota está contida dentro do conjunto de todas as possíveis rotas. Podemos determinar a melhor rota através do algoritmo de força bruta, que consiste em: se tivermos um números  de cidades, na qual temos que encontra a rota mais curta, saindo da cidade de origem passando apenas uma vez em cada cidade e retomando para acidade origem; a rota mais curta será obtida  através da análise de todas as possíveis permutação de cidades. O problema desse método de resolução e que a medida que o número de cidades aumenta, os cálculos juntamente com análise se torna mais cansativos e demorados, até mesmo para alguns computadores que tem a capacidade de fazer milhares de cálculos por segundo, passam dias e dias para determina a rota mais curta.[pic 2][pic 3]

Além do método de resolução citado logo acima temos o método   Heurísticas que são algoritmos que nos fornece soluções rápida e aproximadas, são eles:

• Partindo da cidade inicial escolha a cidades mais próxima que ainda não foi visitada e adicione esse trajeto a rota que era percorrida, continue desse modo até completa o ciclo hamiltoniano
• Ordena os trechos entre as cidades pela distância e cria um ciclo hamiltoniano a partir dessa sequência.

O pcv tem aplicações em diversas áreas tais como: problemas de transporte (entrega e coleta de cargas, transporte de funcionários, ônibus escolar, roteamento de veículos), linha de produção, problemas de manufatura (programação de operações em máquinas, programação de transporte entre células de manufatura, otimização do movimento de ferramentas de corte). Além dessas aplicações outras inúmera podem ser elaboradas.

Leonard Adleman ao perceber as semelhanças entra o DNA e os computadores, pois ambas têm um sistema de armazenamento de informações no caso do DNA utiliza a base: Adenina, Timina, Guanina e Citosina; já o computador utiliza a base binaria: 0 e 1. Ao nota essa semelhança, ele envolveu um protótipo de um computador genético para resolver problemas da mesma natureza do pcv.

       

...