O problema do caixeiro viajante

O Problema do Caixeiro Viajante (PCV), ou Traveling Salesman Problem (TSP), é um caso típico de otimização combinatória, freqüentemente utilizado em computação para demonstrar problemas de difícil resolução. A sua definição formal é: encontrar um caminho através de um grafo valorado que inicie e termine no mesmo vértice, passe por todos os demais vértices do grafo uma única vez e minimize o custo total. O problema do caixeiro viajante é um problema de otimização associado ao da determinação dos caminhos hamiltonianos em um grafo qualquer. O objetivo do PCV é encontrar, em um grafo G = (N, A), o caminho hamiltoniano de menor custo.

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.