Fiz um programa em Java que implementou o algoritmo Depth-First Search (busca em profundidade) para encontrar a solução ótima do problema do caixeiro viajante. Quem quiser pode fazer o download do programa. O algoritmo implementado é de força-bruta, ou seja, testa todas as possibilidades possíveis. Assim, como a complexidade do programa é da ordem de n!, logo a execução do programa torna-se inviável. Em meus testes, para n=14, o tempo de execução foi de 42,73 minutos. A estimativa de tempo para n=15 é de 15 vezes esse tempo, ou seja, 641 minutos.
Ao executar o programa, deve ser informada a matriz de adjacência do grafo, indicando as distâncias entre os vértices. A figura acima ilustra a execução do problema do caixeiro viajante com n=4. Para n=5, deve-se incluir uma uma nova linha e uma nova coluna em todas as linhas. O resultado apresentará o menor caminho que saia da cidade 0, passe por todas as outras cidades e retorne para 0.
Atualizado em 14/02/2011: O link para download do programa foi corrigido.