Using Traveling Salesman Solver to Decide Hamiltonian Path
- by Firas Assaad
This is for a project where I'm asked to implement a heuristic for the traveling salesman optimization problem and also the Hamiltonian path or cycle decision problem. I don't need help with the implementation itself, but have a question on the direction I'm going in.
I already have a TSP heuristic based on a genetic algorithm: it assumes a complete graph, starts with a set of random solutions as a population, and works to improve the population for a number of generations. Can I also use it to solve the Hamiltonian path or cycle problems? 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 would have to be extended to any graph. This could be done by setting the edges to some infinity value if there is no path between two cities, and returning the first path that is a valid Hamiltonian path.
Is that the right way to approach it? Or should I use a different heuristic for Hamiltonian path? My main concern is whether it's a viable approach since I can be somewhat sure that TSP optimization works (because you start with solutions and improve them) but not if a Hamiltonian path decider would find any path in a fixed number of generations.
I assume the best approach would be to test it myself, but I'm constrained by time and thought I'd ask before going down this route... (I could find a different heuristic for Hamiltonian path instead)
