我读到经典的旅行商问题（TSP）是 NP 难问题。并且有一些近似算法以及在 O(N^2 * 2^N) 时间内运行的特定算法。但据我所知，这些是针对一般图表中的 TSP 的。
所以我的问题是，是否有更好的（优选多项式时间）算法来求解 M x N 网格中的 TSP？
例如，假设有一个 3x4 的网格，从一个单元格到 2 个相邻（底部和右侧）单元格中的每一个单元格的移动成本不同。所以我想找到访问所有单元格的最小成本，从单元格 (0, 0) 开始并返回到单元格 (0, 0)。
编辑：为了澄清事情，我很确定这不是欧几里得 TSP。为简单起见，请考虑以下示例。一个矩形被分成M行和N列。推销员位于单元格 0, 0（左上角单元格）。他必须访问所有单元格并仍然返回到起始单元格 (0, 0)。但他只能从一个单元格移动到其 4 个相邻单元格（上、左、下、右）中的每一个。并且从一个小区到其任何一个相邻小区的成本可能并不相同。
谢谢。
hel*_*elb -2
TSP 的复杂性是由于两个节点之间可能的路由数量是指数级的。
网格具有固定的节点度（每个节点具有例如 4 个邻居），但是对于具有 4 个邻居的 M*N 网格，两个行驶节点之间的可能路线数量仍然是 O(4^(M*N))。
算法在网格上可能运行得更快，但问题仍然是 NP 困难的。
编辑：您可以省略访问顶点的路径，然后路径直接返回到最后一个顶点，因为这些路径不必要地长。这意味着总是有 3 个可能的邻居可供选择（而不是 4 个）。因此复杂度可以表示为O(3^(M*N))。这也对应于 Vikrams 答案中描述的暴力方法。