'Longest path on a grid, without revisiting grid cells
I am looking for an algorithm to fidn the longest path between two points on a grid, with the added restriction that you cannot revisit a cell on the grid. (Also, you can only move up, down, left, and right).
Given these restrictions, I imagine that walking the longest path is the same as trying to fill as much of the space as possible. However, I have some difficulting in figuring out how to do this.
Solution 1:[1]
Here is linear time algorithm for 2D grid: http://www.sciencedirect.com/science/article/pii/S0166218X11003088
If the grid is not rectangular, then the problem is NP-hard and you should use some variation of algorithm for solving travelling salesman problem - e.g. one using integer linear programming.
Solution 2:[2]
The longest-path problem is still NP-hard on general grid-graphs (the kind which you are describing).
This is due to the fact that Hamiltonian path is NP-complete on general grid graphs. The reduction is then the same: a fast longest-path solver would immediately give you a fast Hamiltonian path solver, simply by comparing the length of the longest path between every pair of nodes to n-1.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | usamec |
| Solution 2 | Martin |