Sobre a questão do Algoritmo para o Problema do Caixeiro Viajante

Sabemos que há problemas para os quais se demonstrou que não existem algoritmos que os resolvam (como o Problema da Paragem - Turing 193G, ou o 10.° Problema de Hilbert - Matijasevic, 1970), enquanto outros há que, apesar de ser possível construir algoritmos para a sua resolução, esses algoritmos possuem "ordens de complexidade" tão grandes que originam a denominação de "ineficientes".


PDF do Artigo | PDF integral
Gazeta nº 138, pág. nº 29 | Categoria: Artigos | Palavras-Chave: algoritmos
Autor(es): Ana Maria de Almeida | Maria Rosália Dinis Rodrigues |