查找图中的哈密顿路径数的算法

Question

我正在尝试解决汉密尔顿路径问题的稍微修改的版本。对其进行了修改，因为已将起点和终点提供给我们，而不是确定解决方案是否存在，我们希望找到解决方案的
数量 （可以为0）。

该图以二维数组的形式提供给我们，节点是数组的元素。另外，我们只能水平或垂直移动，而不能对角移动。不用说，我们不能从一个城市到两个城市，因为要做到这一点，我们将需要两次访问一个城市。

我写了一个蛮力解决方案，尝试在每个节点上尝试所有4个（边缘节点为3或2）可能的移动，然后计算解决方案的数量（达到目标并看到所有其他节点时），但是它在大小适中的输入（例如7x7阵列）上运行了可笑的时间。

我也考虑过使用双向搜索，因为我们知道目标，但这并没有真正的帮助，因为我们不仅希望满足这些要求，而且还希望确保已访问所有节点。而且，可能是当两个条纹之间的所有节点都用尽时，它们以无法连接的方式结束。

我觉得有些事情我不知道，这使我只能解决蛮力问题。我知道问题本身是NP完全的，但是我想知道在蛮力方面是否有任何改进。有人可以提出其他建议吗？

- 编辑 -

我提到使用双向搜索并没有真正的帮助，我想阐明为什么会这样。考虑一个2x3图，左上角和右下角分别是起点和目标。让双向搜索的边缘从目标向右移动，从目标向左移动。经过2步移动后，所有节点都将被访问，但是无法加入边缘，因为我们只能从一个节点沿一个方向前进。但是，正如大卫在下面的回答中指出的那样，可能可以对算法进行一些修改。

Answer 1

根据Wolfram Alpha的说法，

…确定给定一般图是否具有哈密顿路径的唯一已知方法是进行详尽搜索

我相信您会想从找到一条哈密顿路径开始，然后将其分为两条路径，使分割点尽可能清楚地将两条路径分开。然后，您可以在子图中找到排列（当然还有递归！）

我不知道确切的算法，但是那种分而治之的方法就是我要开始的地方。