Finding a hamiltonianISH path in a graph

Question

Problem statement

Given a graph of all the blue squares in the following image where each blue square is connected to other blue squares in all 4 cardinal directions.

Given any starting node.

What algorithm will allow for finding the longest(ish) path.

Considering that each node can only be visited once.

Considering that we don't care where the path ends.

Considering that speed is more important than necessarily visiting each node.

Example

I have traced an example of the desired result in the image below. As you can see, the path does not visit each node and that is fine. I'm looking for a fast algorithm that will give me one of the longest possible path on this graph. 80% coverage or more is what I'm shooting for.

Answer 1

I ended up using the UCT (MCTS with UCB1) algorithm but with a twist.

Normally, in UCT, the simulation phase is a simulated play-through of a game with moves chosen at random. If the simulated game ends in a win, the node's score, from where the simulation was played out, and all it's parents' scores all the way back to the root, are incremented by 1.

In my implementation, the simulated "play-through" is actually just a random walk down the tree of neighboring tiles that haven't been visited yet. Once the simulation reaches a terminal-node (dead-end) it assigns a score of s = d / m where d is the terminal node's depth in the tree and m is the maximum possible depth.

On a 15 x 15 grid with no obstacles, you would set m to 225 as the longest path would visit every tile. I've set mine slightly lower than that as I need the algorithm to be generalized and work on randomly generated maps that usually have 10-30 tiles occupied by obstacles.

Instead of incrementing the parents' score, the backtracking algorithm sets each parent's score to the newly computed score, if it is higher than their current score. In other words, a node's score always represents the length of the longest path reached so far from this node.

UCT uses UCB1 in order to select which node to exploit or explore once every children of the current node have been expanded and I have largely kept with that. The only modification I have made is to the exploitation term. In UCB1, the exploitation term is w / v where w is the node's accumulated score and v is the number of time the node was visited. This works great in a game where you want to select the move that maximizes your chances of winning. In my case, since the score reflects not a binary function of win = 1 and lose = 0 but rather a scale of 0 = super short path vs 1 = the longest path possible and I want to go down the longest path found by the algorithm, I have simply set the exploitation term to s = score = longest path reachable from this node.

The context in which I'm using this algorithm allows me about 40 ms of compute time in a NodeJS environment before I have to select a move. This usually affords around 785 tree traversals on my machine. On average, in that time, and on the map showed in OP, this algorithm will find a path that is 70 nodes deep. Which is more than enough for my purposes seeing as I get to run the algorithm again the next turn. In practice, when using this algorithm to select next moves, I end up travelling a path that is 100-110 steps long before hitting a dead-end and I cover a very large portion of the blue tiles.

For fun I have ran the algorithm for much longer and at around 300 000 traversals (30 secs on my machine), on average, again on the map shown in OP, it finds a path that is 125 nodes deep which is pretty close to the max depth on this map.

Answer 2

This is the longest path problem. It's NP-hard to find the longest path in a general graph. You can try applying any standard algorithm for finding longest paths. Search on this site for "longest path" and "Hamiltonian path" to find many references. Since you're willing to accept suboptimal solutions, you might look for a heuristic or approximation algorithm (e.g., using a local search algorithm).