Problema do caixeiro-viajante
O Problema do Vendedor Viajante (freqüentemente chamado de TSP) é um problema algorítmico clássico no campo da ciência da computação e da pesquisa operacional. Ele está focado na otimização. Neste contexto, uma melhor solução muitas vezes significa uma solução mais barata, mais curta ou mais rápida. O TSP é um problema matemático. Ele é mais facilmente expresso como um gráfico descrevendo a localização de um conjunto de nós.
O problema do vendedor ambulante foi definido no século XIX pelo matemático irlandês W. R. Hamilton e pelo matemático britânico Thomas Kirkman. O Jogo Icosiano de Hamilton era um quebra-cabeça recreativo baseado em encontrar um ciclo Hamiltoniano. A forma geral do TSP parece ter sido estudada pela primeira vez por matemáticos durante a década de 1930 em Viena e em Harvard, notadamente por Karl Menger. Menger define o problema, considera o óbvio algoritmo de força bruta e observa a não-optimidade do vizinho mais próximo heurístico:
Denominamos por problema de mensageiro (já que na prática esta questão deve ser resolvida por cada carteiro, de qualquer forma também por muitos viajantes) a tarefa de encontrar, para finitely muitos pontos cujas distâncias em pares são conhecidas, a rota mais curta que liga os pontos. É claro que este problema pode ser resolvido por muitas tentativas finitas. Não são conhecidas regras que empurrariam o número de tentativas abaixo do número de permutações dos pontos em questão. A regra de que primeiro se deve ir do ponto de partida para o ponto mais próximo, depois para o ponto mais próximo a este, etc., em geral não produz o trajeto mais curto.
Hassler Whitney da Universidade de Princeton introduziu o problema do nome vendedor ambulante logo em seguida.
Um vendedor quer visitar todas as cidades,A,B,C e D. Qual é a melhor maneira de fazer isso (passagens aéreas mais baratas, e tempo mínimo de viagem)?
Rota ideal de um vendedor que visita as 15 maiores cidades da Alemanha. A rota mostrada é a mais curta das 43.589.145.600 possíveis.
William Rowan Hamilton
Avaliando o problema
O Problema do Vendedor Viajante descreve um vendedor que deve viajar entre N cidades. A ordem em que ele o faz é algo que não lhe importa, desde que ele visite cada um durante sua viagem, e termine onde estava no início. Cada cidade está conectada a outras próximas por cidades, ou nós, por aviões, ou por estrada ou ferrovia. Cada uma dessas ligações entre as cidades tem um ou mais pesos (ou o custo) anexados. O custo descreve como é "difícil" atravessar esta borda no gráfico, e pode ser dado, por exemplo, pelo custo de um bilhete de avião ou de trem, ou talvez pelo comprimento da borda, ou pelo tempo necessário para completar a travessia. O vendedor quer manter os custos de viagem, assim como a distância que ele percorre o mais baixo possível.
O Problema do Vendedor Viajante é típico de uma grande classe de problemas de otimização "difíceis" que há anos intrigam os matemáticos e cientistas da computação. O mais importante, ele tem aplicações na ciência e engenharia. Por exemplo, na fabricação de uma placa de circuito, é importante determinar a melhor ordem na qual um laser fará milhares de furos. Uma solução eficiente para este problema reduz os custos de produção para o fabricante.
Dificuldade
Em geral, o problema do vendedor ambulante é difícil de resolver. Se houver uma maneira de dividir este problema em problemas de componentes menores, os componentes serão pelo menos tão complexos quanto o original. Isto é o que os cientistas da computação chamam de problemas NP-duros.
Muitas pessoas têm estudado este problema. A solução mais fácil (e mais cara) é simplesmente tentar todas as possibilidades. O problema com isto é que para N cidades você tem (N-1) possibilidades fatoriais. Isto significa que para apenas 10 cidades há mais de 180 mil combinações para tentar (desde que a cidade inicial esteja definida, pode haver permutações nas nove restantes). Contamos apenas a metade, já que cada rota tem uma rota igual em marcha à ré com o mesmo comprimento ou custo. 9! / 2 = 181 440
- Soluções exatas para o problema podem ser encontradas, usando algoritmos de ramo e de limite. Isto é possível atualmente para até 85.900 cidades.
- As abordagens heurísticas utilizam um conjunto de regras de orientação para a seleção do próximo nó. Mas como a heurística resulta em aproximações, nem sempre dará a solução ótima, embora a heurística admissível de alta qualidade possa encontrar uma solução útil em uma fração do tempo necessário para uma força bruta total do problema. Um exemplo de uma heurística para um nó seria uma soma de quantos nós não visitados estão "perto" de um nó conectado. Isto poderia encorajar o vendedor a visitar um grupo de nós próximos agrupados juntos antes de passar para outro agrupamento natural no gráfico. Ver algoritmos de Monte Carlo e algoritmos de Las Vegas
