Usando Caixeiro Viajante Solver decidir Caminho Hamiltoniano

Question

Este é um projeto onde eu estou pediu para implementar uma heurística para o problema de otimização caixeiro-viajante e também o caminho ou decisão ciclo problema hamiltoniano. Eu não preciso de ajuda com a própria implementação, mas tenho uma pergunta sobre a direção que eu vou entrar.

Já tenho uma heurística TSP baseado em um algoritmo genético: ele assume um grafo completo, começa com um conjunto de soluções aleatórias como uma população, e trabalha para melhorar a população para um número de gerações. Posso também usá-lo para resolver os problemas de caminho ou ciclo hamiltoniano? Em vez de otimização para obter o caminho mais curto, eu só quero verificar se existe um caminho.

Agora, qualquer grafo completo terá um caminho hamiltoniano nele, assim que a heurística TSP teria que ser estendido para qualquer gráfico. Isso poderia ser feito através da definição das bordas para algum valor infinito se não houver um caminho entre duas cidades, e retornando o primeiro caminho que é um caminho Hamiltoniano válido.

É esse o caminho certo para abordá-lo? Ou devo usar uma heurística diferente para caminho hamiltoniano? A minha principal preocupação é se é uma abordagem viável desde que eu posso ser um pouco certeza de que as obras de otimização TSP (porque você começar com soluções e melhorá-los), mas não se um decisor caminho hamiltoniano iria encontrar qualquer caminho em um número fixo de gerações.

Presumo que a melhor abordagem seria para testá-lo eu mesmo, mas eu estou limitado por tempo e pensei que eu ia perguntar antes de ir por esse caminho ... (eu poderia encontrar uma heurística diferente para caminho hamiltoniano vez)

Answer 1

Não sei se você já tem uma resposta para isso. O truque simples é adicionar um ponto fictício que tem uma distância de zero a todos os seus outros pontos. Resolver o TSP e livrar-se do ponto fictício - o que resta é o caminho hamiltoniano. Simples!

Answer 2

Ambos são NP problemas completos, então, por definição, você pode converter a entrada e usar o mesmo algoritmo; -)

Mas a idéia básica deve funcionar. Claro que você pode precisar alterar a geração de novos caminhos e os critérios de sucesso.

EDIT: BTW: Há uma sugestão para um algoritmo aleatório: http://en.wikipedia.org/wiki/Hamiltonian_path_problem