CODEWITHSUNDEEP
algorithmgraphpath-findingnp-completehamiltonian-cycle
Abhinav Bhadoria
Abhinav Bhadoria

Reputation: 61

Hamiltonian path generator algorithm

I have been playing with Hamiltonian paths for some time and have found some cool uses of it. One being a sort of puzzle where the goal is to connect all the nodes to form a hamiltonian path.

So, being a novice programmer I am, I created a very basic brute force graph generator that creates graphs having a hamiltonian path. But the problem arises when I try to increase the graph size to 10x10. Needless to say, by brute force does not works there.

I understand Hamiltonian path is an NP-Complete problem, but is there a method to optimize the graph generation process. Any sort of trick that can create 15x15 grids in reasonable time.

Thank you very much.

Upvotes: 2

Views: 2106

Answers (1)

David Schilling
David Schilling

Reputation: 31

You're looking for what's called the "Backbite algorithm" - start with any Hamiltonian path, a trivial one will do (zig-zag back and forth across your grid, or have a spiral).

Then loop a random number of times:

  1. Select either end point

  2. There are at least two and at most four neighboring vertices; randomly select one that is not already the Hamiltonian neighbor of the end point you started with

  3. If the second point was not the other endpoint

    a. connect the two points you picked - this will produce a graph that looks like a loop with a tail

    b. Find the edge that causes the loop (not the edge you just added, rather one of its neighbors), and delete it (this is the 'backbite' step)

  4. If in step 3 the second point was the other endpoint, join the two (you will now have a Hamiltonian cycle), and delete any other random edge

At each step, the new graph is still a Hamiltonian path.

Upvotes: 3

Related Questions