O Problema do Caixeiro Viajante
1 Introdução; é NP-Completo
2 Tipos de Problema;
2.1
2.2
2.2
2.2
A
A
A
A
Classe
Classe
Classe
Classe
P de problemas;
NP de problemas;
NP-Completo de problemas;
NP-Difícil de problemas.
3 Problema do caixeiro viajante;
3.1 Algoritmos de força bruta;
3.2 Implementação.
4 O Problema do caixeiro viajante é NPCompleto;
5 Conclusão;
6 Referências.
Copyright
1. Introdução
O problema do caixeiro viajante é um
problema que tenta determinar a menor rota para percorrer uma série de cidades, retornando à cidade de origem. Ele é um problema de otimização NPCompleto inspirado na necessidade dos vendedores em realizar entregas em diversos locais percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível.
2
1. Introdução
Nos anos de 1800, problemas relacionados
com o PCV começaram a ser desenvolvidos por dois matemáticos: o escocês William
Rowan Hamilton e o britânico Thomas
Penyngton Kerkman. A forma geral do PCV parece ter sido, pela primeira vez, estudada por matemáticos nos anos de 1930 em Harvard e Viena. O problema foi posteriormente estudado por Hassler
Whitney e Merril Flood em Princeton.
3
2. Tipos de Problemas
Para compreender o problema abordado
neste trabalho, é necessário conhecer a classe de problemas NP-Completos. Para melhor compreender essa classe e também as classes P e NP, segue uma definição básica de cada uma delas.
fig 1.
4
2. Tipos de Problemas
2.1 A Classe P de problemas A
classe P engloba todos os problemas decisórios que podem ser resolvidos por um algoritmo de tempo polinomial.
Um problema cujo algoritmo é de ordem O()
com uma constante k muito grande é considerado eficiente, pois é provável, pelo que se vê ao longo da história dos algoritmos, que logo sejam encontrados novos algoritmos mais eficientes que resolvam tal problema com uma complexidade menor.
5
2. Tipos de Problemas
2.2 A Classe NP de problemas
A classe