4
$\begingroup$

Here is my situation. I have a grid-type graph with obstacles. Every move (horizontally, vertically or diagonally with a range of 1) has a cost of exactly 1 (the graph is not weighted) provided that neither the source or the destination is an obstacle.

I need to, provided a starting node (a square), find any path that visits every single node that is reachable, without visiting any node twice. If there is no such path, then any path that would visit as many nodes as possible. In other words, I'm looking for an algorithm to find a Hamiltonian path in such a graph.

I am not looking for the shortest path.

The most important factor is the time the algorithm takes to complete (complexity).

I have searched Google and this site, and I only find variants of the travelling salesman, or algorithms for shortest path visiting all nodes, which won't work in my situation. My algorithm needs to find a path of any length visiting as many nodes as possible while never visiting a node twice. The path can end anywhere.

Does anyone have any tips? I've tried to do this with a variant of A*, but I couldn't make it work. I've succesfully done it by brute-forcing, but as the graph can be rather large, I need something a faster than O(n!).

It would be even better if the algorithm was non-deterministic, which means that if there are multiple possible solutions, we wouldn't always get the same one with the same graph and starting location. I have no idea how to do this without slowing it down though, and speed is more important.

$\endgroup$
  • $\begingroup$ @D.W. Hello! Yes, I looked at a few hamiltonian algorithms, and I mentioned in the post that it could never visit a node twice. I also had put the hamiltonian-path in the tags, although I didn't know if in the end the answer would come in that form, so I left it more open ended. Of course it could be the answer, but I didn't want to limit the scope as I was really unsure of what exactly I needed to make it work. $\endgroup$ – Kaito Kid Jan 12 '17 at 2:36
3
$\begingroup$

Since an exact algorithm is most likely off the table, I'll propose the following heuristic: Start at any vertex (though a vertex with no vertices above it would be best), and always move to the first neighbour in the following list that exists and has not yet been visited: UPLEFT, LEFT, DOWNLEFT, DOWN, DOWNRIGHT, RIGHT, UPRIGHT, UP. This should cause you to quickly travel to the top-left part of the graph, and thereafter alternatingly "snake" down and then up adjacent columns, "bending" around any obstacles but always hugging as close to the left border of the graph as possible, and thus gradually covering the graph from left to right.

There are probably many ways for this algorithm to get stuck -- that is, to make a move that leads to the subgraph induced by the unvisited vertices becoming disconnected, meaning that at most one of the resulting components can be visited. One way to ameliorate this somewhat is to first test whether the next valid move will lead to such a disconnection by checking whether there is a path through unvisited vertices from the vertex we would get to at the move after that to the next valid move from current vertex -- this can be done with BFS (or DFS, but BFS will terminate faster in the common case where a short path does exist). If no such path would then exist, and if a heuristic estimating the length of the path reachable from the first move is small (for example: the size of the connected component of unvisited vertices you would find yourself in), try the next move.

$\endgroup$
  • $\begingroup$ I will accept your answer even though I didn't use it in the end, because reading it gave me an idea for a solution and it worked. Thank you very much! $\endgroup$ – Kaito Kid Jan 14 '17 at 14:33
  • 1
    $\begingroup$ I just move from node to node with the following priority. The node with the fewest possible moves on the next action provided that it is at least one, and if there are none, then any node available that has no moves on the next turn. This has the side effect of sticking to the (ever growing) edges and therefore won't "split" the available field unless the circumstances are very unlucky, so about 95% of the time if there exists a path visiting all, it finds one. and if not, the path found visits as many nodes as possible. $\endgroup$ – Kaito Kid Jan 14 '17 at 14:34
  • $\begingroup$ That sounds like a good heuristic. Glad I could help :) $\endgroup$ – j_random_hacker Jan 14 '17 at 15:25
4
$\begingroup$

There isn't going to be a fast algorithm for this problem.

The class of graphs you're dealing with is, in some of the literature, called grid graphs. That is, they're finite induced subgraphs of the infinite graph with vertices $\mathbb{Z}\times\mathbb{Z}$ with an edge from $(x,y)$ to $(x',y')$ if, and only if, $|x-x'|+|y-y'|=1$.

Itai, Papadimitriou and Szwarcfiter (Hamiltonian Paths in Grid Graphs, SIAM Journal on Computing, 11(4):676–686, 1982) showed that it's NP-complete to determine whether a grid graph has a Hamiltonian path. Your problem is NP-hard (under Cook reductions, and possibly also under the more usual Karp reductions): if you can determine the length of the longest path from a vertex, just do that for each vertex in turn and see if any of the longest paths is Hamiltonian.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.