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

| 我正在尝试解决汉密尔顿路径问题的稍微修改的版本。对其进行了修改，因为已将起点和终点提供给我们，而不是确定解决方案是否存在，我们希望找到解决方案的数量（可以为0）。 该图以二维数组的形式提供给我们，节点是数组的元素。另外，我们只能水平或垂直移动，而不能对角移动。不用说，我们不能从一个城市到两个城市，因为要做到这一点，我们将需要两次访问一个城市。 我编写了一个蛮力解决方案，尝试在每个节点上尝试所有4个（边缘节点为3或2个）可能的移动，然后计算解决方案的数量（达到目标时也看到了所有其他节点），但是它在大小适中的输入（例如7x7阵列）上运行了可笑的时间。 我也考虑过使用双向搜索，因为我们知道目标，但这并没有真正的帮助，因为我们不仅希望满足这些要求，而且还希望确保已访问所有节点。此外，可能是当两个条纹之间的所有节点都用尽时，它们以无法连接的方式结束。 我觉得有些事情我不知道，只剩下蛮力解决方案了。我知道问题本身是NP完全的，但是我想知道在蛮力方面是否有任何改进。有人可以提出其他建议吗？ - 编辑 - 我提到使用双向搜索并没有真正的帮助，我想阐明为什么会这样。考虑一个2x3图，左上角和右下角分别是起点和目标。让双向搜索的边缘从目标向右移动，从目标向左移动。经过2次移动后，所有节点都将被访问，但是由于我们只能从一个节点向一个方向前进，因此无法加入边缘。但是，正如大卫在下面的回答中指出的那样，可能可以对算法进行一些修改。