7

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.

efficiencyIsBliss
  • 3,043
  • 7
  • 38
  • 44

6 Answers6

3

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.

corsiKa
  • 81,495
  • 25
  • 153
  • 204
1

You could still use a bidirectional search, just add a constraint to the search so that previously seen nodes will not be candidates for searching.

Another approach you could take which would lend itself to a paralellizable solution is to break the search into smaller searches.

For example, try to solve your original problem by solving:

For each node, n, which is not a start or end node, find all paths from the start to n (set1) and from n to the end (set2).

After you find set1 and set2, you can discard all elements of their cross product which have a common node other than node n.

David Weiser
  • 5,190
  • 4
  • 28
  • 35
  • that wasn't the problem. Even if we aren't visiting nodes that have been visited, we still want the fringes to visit all the nodes in the graph. Also, it could be that the fringes can't be joined in a legal way. For example, consider a graph 3x2 graph with the top right and lower left nodes being start and goal. Let the fringes move right/left. After two moves, all nodes would have been visited, but there's no way to join them in a legal way bringing us back to a brute force search. – efficiencyIsBliss Mar 16 '11 at 23:55
  • Would you add that to the question description please? Also, why not just modify the search so that it will not stop until all nodes have been explored? – David Weiser Mar 17 '11 at 00:01
  • I had thought of a solution on similar lines before I thought of bidirectional search, but I'd given up on it. Using it along with bidirectional search makes it more useful though. +1 – efficiencyIsBliss Mar 17 '11 at 00:05
  • Because we want to reach the goal at the very end. Also, could you tell me what you think I should add to the description? The example that I used in my first comment? – efficiencyIsBliss Mar 17 '11 at 00:08
  • The example in your first comment, I think, would add greatly to your question. You asked an interesting question, good job!:) – David Weiser Mar 17 '11 at 16:22
1

Someone asked a question very similar to yours over on Math Overflow at https://mathoverflow.net/questions/36368/efficient-way-to-count-hamiltonian-paths-in-a-grid-graph-for-a-given-pair-of-vert and (1) they didn't get a deluge of "here's how to do it efficiently" responses (which probably means there isn't an easy way), (2) Mathematica apparently takes 5 hours to count the paths between opposite corners on a 7x7 grid, so you may well not be doing anything very wrong, and (3) there are a few interesting pointers among the answers.

Community
  • 1
  • 1
Gareth McCaughan
  • 19,888
  • 1
  • 41
  • 62
  • I let my code run for about 98 minutes before giving up, in hopes that I'd made some stupid mistake. I guess this completely douses any hopes. Thanks for saving me a lot of trouble though. – efficiencyIsBliss Mar 16 '11 at 23:59
0

On a 7x7 array (i.e. a total of 7*7=49 nodes), having either a O(n!) algorithm or a O(2^n*n^2) algorithm will both take way too much time.

Perhaps there is some way speeding this up taking into account the special characteristics of this particular graph (e.g. each node has at most 4 edges), but a fast solution seems improbable (unless someone incidentally finds a polynomial time algorithm for the Hamiltonian Path problem itself).

MAK
  • 26,140
  • 11
  • 55
  • 86
0

It can be solved using DP with bitmasking for values of n upto 20 or a few more i guess. Create a 2d dp table. dp[i][j] represents the answer of case that you are on ith vertex and j stores the information about visited vertices.Here's a C++ code.

Macros used:

#define    oncnt    __builtin_popcount
typedef    vector<int>   vi;

Outside Main:

vi ad[21];
 int n,m;

 int dp[20][(1<<19)+1];

int sol(int i,int mask)
{
    //cout<<i+1<<" "<<oncnt(mask)<<"\n";

    if(i==n-1)
    return 1;

    if(mask&(1<<i))
    return 0;

    int &x=dp[i][mask];
    if(x!=-1)
    return x;

    x=0;

    for(int j=0;j<ad[i].size();j++)
    {
        int k=ad[i][j];
        if(mask&(1<<k))
        continue;
        if(k==n-1&&oncnt(mask)!=n-2)
        continue;
        if(k!=n-1&&oncnt(mask)==n-2)
        continue;
// The above two pruning statements are necessary.
        x=madd(x,sol(k,mask|(1<<i)));

    }

    return x;

}

Inside Main:

cin>>n>>m;

for(int i=0;i<=n-1;i++)
 {
    for(int j=0;j<=(1<<(n-1));j++)
    dp[i][j]=-1;
 }


int a,b;
for(int i=1;i<=m;i++)
{
    cin>>a>>b;
    a--;
    b--;
    ad[a].pb(b);
}


 cout<<sol(0,0);
kkdrummer
  • 1
0

I found this approach to be extremely fast, and I was able to generalize it to work on a hexagonal grid: https://hal.archives-ouvertes.fr/hal-00172308/document. The trick is to push a frontier through the grid while keeping track of the possible paths. My implementation handles 20x20 grids in a few seconds.

DavidErb
  • 1
  • 1
  • 1