O Problema do caixeiro viajante (PCV) consiste em encontrar a rota mais curta que conecte cidades. Um algoritmo ingênuo tentaria todos as rotas . Um algoritmo Held–Karp melhoraria isso em aproximadamente passos. Mostre que e, portanto, que o algoritmo Held-Karp é mais rápido.
Ambos algoritmos mostram que a classe de complexidade do PCV não é pior que EXPTIME, que são problemas que podem ser resolvidos em tempo . Por exemplo, para qualquer , então o algoritmo Held-Karp tem tempo de execução exponencial.
Soluções aproximadas podem ser encontradas em tempo , então o PCV aproximado está na classe de complexidade P de problemas solúveis em tempo polinomial. Qualquer algoritmo polinomial é mais rápido que um exponencial, ou .

ISBN: 9789722408936 Edição: 04-1995 Editor: Livros Horizonte Idioma: Português Dimensões: 220 x 240 mm Páginas: 108 Tipo de Produto: Livro Coleção: Extra-Coleção Classificação Temática: Livros em Português > História > Etnografia