Using a Sales Traveling Salesman Solution to Solve the Hamiltonian Way

Question

This is for a project where I am asked to introduce a heuristic for the task of optimizing a traveling salesman, as well as the problem of solving Hamiltonian paths or solving a cycle. I don’t need help with the implementation itself, but I have a question about the direction I'm going.

I already have a genetic algorithm based TSP heuristic: it assumes a complete schedule, starts with a set of random decisions as a population, and works to improve the population over several generations. Can I also use it to solve a Hamilton problem or a cycle? Instead of optimizing to get the shortest path, I just want to check if there is a path.

Now any complete graph will have a Hamiltonian path in it, so the TSP heuristic should be expanded to any graph. This can be done by setting the edges to a certain value of infinity if there is no path between the two cities and the first path is returned, which is an acceptable Hamiltonian path.

Is this right? Or should I use a different heuristic for the Hamiltonian trajectory? My main problem is whether this is a viable approach, since I can be sure that TSP optimization works (because you start with solutions and improve them), but not if the Hamiltonian solution to the path finds any either way in a fixed number of generations.

I guess the best approach is to test it myself, but I was limited in time and thought I would ask before I go down this path ... (I could find another heuristic for the Hamiltonian path)

Answer 1

I don’t know if you have ever received an answer to this question. A simple trick is to add one dummy point, which has a zero value for all of your other points. Solve the TSP and get rid of the dummy point - the Hamiltonian path remains. Plain!

Answer 2

Both are NP-tasks, so by definition you can transform the input and use the same algorithm; -)

. , .

EDIT: : : http://en.wikipedia.org/wiki/Hamiltonian_path_problem