3
$\begingroup$

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.

enter image description here

$\endgroup$
1
2
$\begingroup$

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).

$\endgroup$
5
  • $\begingroup$ Relevant: cs.stackexchange.com/a/12242/683. $\endgroup$ Mar 23 '20 at 22:22
  • 1
    $\begingroup$ Perhaps you can emphasize that this holds for general (and also planar and certain types of grid graphs)? I think you're presenting it as an all hope is lost scenario when that might not be the case. $\endgroup$
    – Pål GD
    Mar 24 '20 at 10:48
  • $\begingroup$ @PålGD, isn't this type of graph exactly the type that is covered by the NP-completeness result that Yuval Filmus links to? Am I missing something? Can you elaborate on where the room for hope lies? $\endgroup$
    – D.W.
    Mar 24 '20 at 16:59
  • $\begingroup$ The answer that the link in the comment refers to may give pointers, but your answer doesn't answer the question. The OP asks for longest path specifically in grid graphs, whereas you answer the question for general graphs. The answer in the link seems to be about Hamiltonian Path, not longest path. $\endgroup$
    – Pål GD
    Mar 25 '20 at 13:26
  • $\begingroup$ I'd also add that I am looking for an algorithm that will find ONE of the longest paths in a short amount of time, I don't care about absolutely getting THE longest path. An algorithm that might suit my need could potentially be quite different than the ones commonly used to solve the "longest path" or "hamiltonian path" problems. $\endgroup$ Mar 26 '20 at 19:47
1
$\begingroup$

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.

$\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.