Implementação do problema euclidiano bitônico do caixeiro-viajante para a disciplina de "Projeto e Análise de Algoritmos", no curso de Ciência da Computação na Universidade Federal Rural de Pernambuco - Unidade Acadêmica de Garanhuns. Estruturas desenvolvidas conforme orientação do Prof. Tiago B. A. de Carvalho, atividade retirada do livro "Algoritmos: Teoria e Prática".
O problema euclidiano do caixeiro-viajante é o problema de determinar o percurso fechado mais curto que conecta um dado conjunto de n pontos no plano. A Figura 15.9(a) mostra a solução para um problema de 7 pontos. O problema geral é NP-completo, e então se considera que sua solução exige mais do que o tempo polinomial (ver Capítulo 34).
J. L. Bentley sugeriu que simplificássemos o problema restringindo nossa atenção a percursos bitônicos, isto é, percursos que começam no ponto mais à esquerda, seguem estritamente da esquerda para a direita até o ponto da extremidade direita, e depois seguem estritamente da direita para esquerda, voltando ao ponto de partida. A Figura 15.9(b) mostra o percurso bitônico mais curto dos mesmos 7 pontos. Nesse caso, é possível um algoritmo de tempo polinomial.
Descreva um algoritmo de tempo O(n²) para determinar um percurso bitônico ótimo. Considere por hipótese que não existem dois pontos com a mesma coordenada x. (Sugestão: Desloque-se da esquerda para a direita, mantendo possibilidades ótimas para as duas partes do percurso.)
(Imagem retirada do livro "Algoritmos: Teoria e Prática")
Autores:
 |
 |
|---|---|
| Antônio A. S. N. | Armstrong L. M. G. Q. |
| @AntonioAdelino | @lohhans |