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

Question

我正在寻找一种算法来确定网格上两点之间的最长路径，并增加了您无法重新访问网格上的单元格的限制。（此外，您只能向上、向下、向左和向右移动）。

考虑到这些限制，我想走最长的路径与试图填满尽可能多的空间是一样的。但是，我在弄清楚如何做到这一点时遇到了一些困难。

Answer 1

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

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

Answer 2

在一般网格图（您所描述的那种）上，最长路径问题仍然是 NP-hard。

这是因为哈密顿路径在一般网格图上是 NP 完全的。然后减少是相同的：快速最长路径求解器将立即为您提供快速哈密顿路径求解器，只需将每对节点之间的最长路径长度与 进行比较n-1。