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

Z时代
2024-01-10
分类：问答

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

数量（可以为0）。

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

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

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

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

- 编辑 -

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