eff*_*iss 6 algorithm path np-complete
我正在尝试解决哈密顿路径问题的略微修改版本.修改它的起点和终点是给我们的,而不是确定是否存在解,我们想找到解的数量(可能是0).
该图作为2D数组提供给我们,其中节点是数组的元素.此外,我们只能水平或垂直移动,而不是对角移动.毋庸置疑,我们不能从一个城市到两个城市,因为要做到这一点,我们需要两次访问一个城市.
我写了一个强力解决方案,尝试在每个节点上所有4个(边缘上的节点为3或2个)可能的移动,然后计算解决方案的数量(当它达到目标并且已经看到所有其他节点时),但是它在适度大小的输入上运行了大量的时间(例如7x7阵列).
我也想过使用双向搜索,因为我们知道了目标,但这并没有真正帮助,因为我们不仅希望条纹满足,我们还希望确保所有节点都已被访问过.此外,可能是当所有节点在两个条纹之间耗尽时,它们以不能连接的方式结束.
我觉得有些东西我不知道只留给我一个蛮力的解决方案.我知道这个问题本身就是NP完全的,但我想知道是否有任何有关蛮力的改进.有人可以提出别的建议吗？
- 编辑 -
我提到使用双向搜索并没有真正帮助,我想澄清为什么我这么认为.考虑一个2x3图,左上角和右下角节点分别是起点和目标.让双向搜索的条纹从开始向左移动,从目标开始向左移动.在2次移动之后,所有节点都将被访问但是没有办法加入条纹,因为我们只能从一个节点向一个方向移动.但是,正如David在下面的回答中指出的那样,也许可以使算法有一些修改.
根据沃尔夫勒姆·阿尔法的说法，
...确定给定的一般图是否具有哈密顿路径的唯一已知方法是进行详尽的搜索
我相信您会首先找到一条哈密顿路径，然后将其分成两条路径，使分割点尽可能清晰地分隔两条路径。然后你可以在子图中找到排列（当然还有递归！）
我不知道确切的算法，但我将从这种分而治之的方法开始。