Menu
I'm trying to solve a slightly modified version of the Hamiltonian Path problem. It is modified in that the start and end points are given to us and instead of determining whether a solution exists, we want to find the number of solutions (which could be 0).
The graph is given to us as a 2D array, with the nodes being the elements of the array. Also, we can only move horizontally or vertically, not diagonally. Needless to say, we can't go from one city to two cities because to do that we would need to visit a city twice.
I wrote a brute force solution that tries all 4 (3 or 2 for nodes on the edges) possible moves at each node and then counts the number of solutions (which is when it reaches goal and has seen all the other nodes too), but it ran for ridiculous amounts of time on inputs of modest size (like, say a 7x7 array).
I also thought of using bidirectional search since we know the goal, but this didn't really help, since we don't just want the fringes to meet, we want to also ensure that all the nodes have been visited. Moreover, it could be that when all nodes have been exhausted between the two fringes, they end in a way such that they can't be joined.
I feel like there is something I don't know that's leaving me with only a brute force solution. I know that the problem itself is NP-complete, but I'm wondering if there are any improvements over brute force. Can someone suggest something else?
--Edit--
I mentioned that using bidirectional search doesn't really help and I'd like to clarify why I thought so. Consider a 2x3 graph with the top left and bottom right nodes being the start and goal respectively. Let the fringes for bidirectional search move right from start and left from goal. After 2 moves, all the nodes would have been visited but there is no way to join the fringes, since we can only go in one direction from one node. However, it might be possible to make the algorithm work with some modifications, as David pointed out in his answer below.
403
Recall the way to find out how many Hamilton circuits this complete graph has. The complete graph above has four vertices, so the number of Hamilton circuits is: (N – 1)! = (4 – 1)!
In this paper a polynomial algorithm called the Minram algorithm is presented which finds a Hamiltonian Path in an undirected graph with high frequency of success for graphs up to 1000 nodes.
Depth first search and backtracking can also help to check whether a Hamiltonian path exists in a graph or not. Simply apply depth first search starting from every vertex v and do labeling of all the vertices. All the vertices are labelled as either "IN STACK" or "NOT IN STACK".
The number of different Hamiltonian cycles in a complete undirected graph on n vertices is (n – 1)!/2 and in a complete directed graph on n vertices is (n – 1)!. These counts assume that cycles that are the same apart from their starting point are not counted separately.
According to Wolfram Alpha,
... the only known way to determine whether a given general graph has a Hamiltonian path is to undertake an exhaustive search
I believe you would want to start by finding a single hamiltonian path, and then splitting it into two paths, making the split point one that clearly separates the two paths as much as possible. Then you can find the permutations in the subgraphs (and recurse, of course!)
I don't know the exact algorithm, but that sort of divide and conquer method is where I would start.
88
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
