Tamanho da fonte: 

O presente artigo tem como principal objetivo uma avaliação, com base em relato de experiência, da eficácia do uso de Programação Dinâmica em algoritmos solucionadores do Problema do Caixeiro Viajante na redução de seu custo computacional. Nesse sentido buscou-se comparar os desempenhos de um algoritmo solucionador com e sem o uso de programação dinâmica, como métrica para comparação foi utilizada a técnica de análise de algoritmos por meio do cálculo da complexidade computacional de cada uma das soluções, bem como testes de tempo de execução dos mesmos. O resultado obtido foi que o uso da programação dinâmica diminui a complexidade algorítmica do Problema de O(n!) para O(n² * 2n). Em linhas gerais, descobriu-se que é possível passar de um tempo que cresce em fatorial para um que cresce em exponencial, o que é um bom avanço, apesar de não resolver totalmente o problema de custo computacional para uma quantidade gigante de nós.