algorithm - 网格中旅行商的多项式时间算法

Question

我看过经典travelling salesman problem (TSP)是NP-Hard。并且有一些近似算法以及在 O(N^2 * 2^N) 时间内运行的特定算法。但是 AFAIK，这些是针对一般图表中的 TSP。

所以我的问题是，是否有更好的(优选多项式时间)算法来求解 M x N 网格中的 TSP？

例如，假设有一个 3x4 的网格，从一个单元格到 2 个相邻(底部和右侧)单元格中的每一个单元格的行进成本不同。所以我想找到访问所有单元格的最小成本，从单元格 (0, 0) 开始并返回到单元格 (0, 0)。

编辑:澄清一下，我很确定这不是欧几里得 TSP。为简单起见，请考虑以下示例。一个长方形被分成M行N列。推销员位于单元格 0, 0(左上角的单元格)。他必须访问所有单元格并仍然回到他的起始单元格 (0, 0)。但是他只能从一个单元格移动到它的 4 个相邻单元格(顶部、左侧、底部、右侧)中的每一个。并且从一个单元格到它的任何一个相邻单元格的成本可能不相同。

谢谢。

Answer 1

这是一个很老的帖子，但似乎所有的答案都不准确，所以我会尽量澄清一下(主要是为了 future 的读者)。

确实(AFAIK)当输入被限制为网格时，没有已知的 TSP 多项式解。

从这里开始，说一下 NP-Hard 中的问题——这个跳跃是不合理的，可能是不正确的。

节点的度数大于 2 的事实使得朴素算法确实以指数时间复杂度运行。正如@Eyal Schneider 所提到的，这并不能证明它是 NP-Hard。

证明 NP-Hard 中的 TSP(根据我知道的方法)是使用哈密顿路径是 NP-Hard 的事实完成的。在网格图上，Hamiltonian-Path 在 P 中，因此同样的方法证明它是 NP-Hard 是行不通的。

我在这里也提供了一个例子，为什么如果问题很难，每个节点的度数不一定是一个很好的指示。

在 2 层网格图上取 TSP，所有大小为 2 * n 的网格图都有一些 n。在这个问题中(在网格上 TSP 的一般情况下更容易)所有节点的度数(角点除外)都是 3，这意味着这里的大多数答案意味着朴素算法的时间复杂度仍然是 n 的指数(因为有O(n) 个度数大于 2 的节点。

事实上，对于 2 * n 个网格，恰好有 2 条哈密顿路径(相同的圆在相反的方向)。因此，存在一个多项式算法来解决 2 * n 网格上的 TSP - 检查 2 个圆，如果它们的最小值小于 k(给定图 G 的输入和最大值 k)，则返回 True。

总而言之——没有证据表明网格上的 TSP 是 NP-Hard (AFAIK)。也没有任何已知的多项式算法来解决网格上的 TSP(AFAIK)。如我所见，网格上的 TSP 可能在 NP-intermediate 中, 但是这门课有点棘手，要证明某些东西在 NP 中间是不可能的(这等同于证明 P 不等于 NP)。

最好的，

沙哈尔