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

Question

我正在尝试解决 Hamiltonian Path 的略微修改版本问题。它被修改为起点和终点给了我们，而不是确定解决方案是否存在，我们想要找到解决方案的数量(可能是 0)。

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

我写了一个蛮力解决方案，尝试在每个节点上进行所有 4 次(边上的节点为 3 或 2 次)可能的移动，然后计算解决方案的数量(这是当它达到目标并且也看到所有其他节点时)，但它在适度大小的输入(比如 7x7 数组)上运行了荒谬的时间。

我也想到了用bidirectional search因为我们知道目标，但这并没有真正帮助，因为我们不只是希望边缘相遇，我们还想确保所有节点都被访问过。此外，可能是当两个边缘之间的所有节点都用完时，它们以无法连接的方式结束。

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

--编辑--

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

Answer 1

根据 Wolfram Alpha ,

... the only known way to determine whether a given general graph has a Hamiltonian path is to undertake an exhaustive search

我相信您会希望从找到一条哈密尔顿路径开始，然后将其拆分为两条路径，使拆分点尽可能清楚地将两条路径分开。然后你可以在子图中找到排列(当然是递归!)

我不知道确切的算法，但我会从那种分而治之的方法开始。