Enumerating all hamiltonian paths from start to end vertex in grid graph

Posted by Eric on Stack Overflow See other posts from Stack Overflow or by Eric
Published on 2010-04-15T18:49:29Z Indexed on 2010/04/15 18:53 UTC
Read the original article Hit count: 220

Filed under:

hamiltonian-path

|

graph

|

graph-theory

Hello, I'm trying to count the number of Hamiltonian paths from a specified start vertex that end at another specified vertex in a grid graph. Right now I have a solution that uses backtracking recursion but is incredibly slow in practice (e.g. O(n!) / 3 hours for 7x7). I've tried a couple of speedup techniques such as maintaining a list of reachable nodes, making sure the end node is still reachable, and checking for isolated nodes, but all of these slowed my solution down. I know that the problem is NP-complete, but it seems like some reasonable speedups should be achievable in the grid structure.

Since I'm trying to count all the paths, I'm sure that the search must be exhaustive, but I'm having trouble figuring out how to prune out paths that aren't promising.

Does anyone have some suggestions for speeding the search up? Or an alternate search algorithm?

© Stack Overflow or respective owner

Related posts about hamiltonian-path

Using Traveling Salesman Solver to Decide Hamiltonian Path

as seen on Stack Overflow - Search for 'Stack Overflow'
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… >>> More
Variation on Hamiltonian path problems

as seen on Stack Overflow - Search for 'Stack Overflow'
Thinking about if we modify the definition of Hamiltonian path as we need to go through every edge once,but can pass vertex any times,is there still an algorithm available? How should I modify the original Hamiltonian algorithm to account for this? >>> More
Implementation of any Hamiltonian Path Problem algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi all ! Here is my problem : I have an array of points, the points have three properties : the "x" and "y" coordinates, and a sequence number "n". The "x" and "y" are defined for all the points, the "n" are not. You can access and write them calling points[i]-x, points[i]-y, points[i]-n. i.e.… >>> More
Enumerating all hamiltonian paths from start to end vertex in grid graph

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I'm trying to count the number of Hamiltonian paths from a specified start vertex that end at another specified vertex in a grid graph. Right now I have a solution that uses backtracking recursion but is incredibly slow in practice (e.g. O(n!) / 3 hours for 7x7). I've tried a couple of speedup… >>> More
Finding the shortest path through a digraph that visits all nodes

as seen on Programmers - Search for 'Programmers'
I am trying to find the shortest possible path that visits every node through a graph (a node may be visited more than once, the solution may pick any node as the starting node.). The graph is directed, meaning that being able to travel from node A to node B does not mean one can travel from node… >>> More

Related posts about graph

C++: Error in Xcode; "Graph::Coordinate::Coordinate()", referenced from: ...

as seen on Stack Overflow - Search for 'Stack Overflow'
In a program I am writing, I wrote for two classes (Coordinate, and Graph), with one of them taking the other as constructor arguments. When I try to compile it I get the following error for Graph.cpp: Undefined symbols: "Graph::Coordinate::Coordinate(double)", referenced from: Graph::Graph()… >>> More
How to create Line Graph and Bar graph on same parameters in asp.net

as seen on C# Corner - Search for 'C# Corner'
We can use GDI+ to draw chart components in C# or VB.NET language in memory and once the components are drawn in memory, we can save the drawing in an image on the Web server. Once the image is saved, we can display this image in an ASP.NET page using any Image tag or image control. >>> More
Display Graph using Boost Graph Library

as seen on Stack Overflow - Search for 'Stack Overflow'
Can anyone please tell me that once I've created a graph using Boost Graph library, how can I display that graph? My biggest concern is that the edge weights are coming from an exernal data source over the network. And I need to be able to display the edgeweights live as they get updated. >>> More
Matlab multiple graph types inside one graph

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have a task to draw electrostatic field between two electrodes( at given sizes and shape ), what i have now is that i draw the electrodes with area plot (area(elect_x,elect_y)) the graph looks like this: ------------------.--- |.. .---. |.. |...| |… >>> More
[C++] Write connected components of a graph using Boost Graph

as seen on Stack Overflow - Search for 'Stack Overflow'
I have an file that is a long list of weighted edges, in the following form node1_id node2_id weight node1_id node3_id weight and so on. So one weighted edge per line. I want to load this file into boost graph and find the connected components in the graph. Each of these connected components… >>> More