用于查找遍历图中所有顶点的路径的更好算法是什么？

Question

所以我有以下问题:

给定一个x乘y维的网格,计算从一个角落(比如左上角)开始到另一个角落(右下角)并穿过每个顶点的路径数量.

因此,我现在的方法只是通过尝试每个可能的路径并计算到达终点并遍历每个节点的路径来强制它.当它工作时,它是O(n ^ 2)并且速度极快得令人难以置信.由于要求路径遍历每个顶点,我不确定如何组合地进行组合.

我查找了更复杂的算法,并且Hierholzer用于计算欧拉路径的算法似乎有些相关但不完美,因为节点不能多次遍历.

事实上,我的程序有效,但很糟糕,我想让它更有效率.我可以使用更好的算法吗？

编辑感谢您的答案到目前为止.为了澄清,2d网格中的所有节点都通过n/e/s/w连接

此外,网格不必是正方形

Answer 1

你无能为力，因为这是哈密顿路径问题，是 NP 完全问题。

然而，您实际上可能会搜索其他内容并对您要解决的问题添加一些限制......

编辑：

正如@JanDvorak 指出的，您的具体限制是您使用的是方形网格。到目前为止我的发现：

如果x是偶数，则无法遍历从左上角开始到右下角结束的所有顶点。证明：

让我们计算沿轴的定向运动，例如向上-1、向下1、向左-1、向右-1。因此，如果有 x × x 网格，您的总移动量将为2*x。在每个顶点（最后一个顶点除外！），您仅选择一个方向。因此，如果您需要经过偶数个顶点，则您的总运动将为偶数，反之亦然。如果x是偶数，则顶点数为奇数，但总运动仍然是偶数=>您无法找到任何方法。