algorithm - 网格上的最长路径，无需重新访问网格单元

Question

我正在寻找一种算法来找到网格上两点之间的最长路径，并增加了您不能重新访问网格上的单元格的限制。 (此外，您只能上下左右移动)。

考虑到这些限制，我认为走最长的路与尝试尽可能多地填充空间是一样的。但是，我很难弄清楚如何做到这一点。

Answer 1

这是二维网格的线性时间算法:http://www.sciencedirect.com/science/article/pii/S0166218X11003088

如果网格不是矩形，那么问题就是 NP-hard 问题，您应该使用一些算法变体来解决旅行商问题 - 例如一个使用整数线性规划。