O Problema do Caixeiro Viajante

1455 palavras 6 páginas
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

Relacionados

  • Problema do Caixeiro Viajante
    2130 palavras | 9 páginas
  • Problema do caixeiro viajante
    840 palavras | 4 páginas
  • Problema do caixeiro viajante
    2533 palavras | 11 páginas
  • Problema Caixeiro Viajante
    385 palavras | 2 páginas
  • Resumo da origem e no que conssiste o problema do caixeiro-viajante
    607 palavras | 3 páginas
  • Otimização por Colônia de Formigas Distribuído do Problema do Caixeiro Viajante.
    1037 palavras | 5 páginas
  • Resolução do problema do caixeiro viajante utilizando metaheurística vnsvnd com programação distribuída socket tcp
    2618 palavras | 11 páginas
  • Heurística de Inserção em Grafos na resolução do Problema do Caixeiro Viajante Critérios: mais próximo, mais distante e randômico Implementação e Testes
    1241 palavras | 5 páginas
  • modeloPCV Caixeiro Viajante
    1786 palavras | 8 páginas
  • CAIXEIRO VIAJANTE 1
    1506 palavras | 7 páginas