O Problema do Caixeiro Viajante

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