计算二维网格中哈密顿路径总数的剪枝策略
我最近试图计算出哈密顿路径的总数（基本上从起始顶点开始，访问每个节点一次并到达结束顶点）。蛮力 dfs 在 7x8 的中等大小的网格上进行长时间的行走。我想出了其中一些修剪策略。这些修剪技术的目标是不应该进一步扩展不能是哈密顿路径的部分路径。
DFS算法： 从起始顶点开始，访问其邻居节点并递归。记录访问的节点数，一旦到达结束顶点，检查访问的节点总数是否与网格中的节点总数相同。这将是指数复杂度，因为对于每个顶点，您可以朝 4 个方向移动，其复杂度为 O(4^n)。因此，重点应该是尽快拒绝一条路径，而不是等到到达终点顶点。
剪枝技巧：
1）对于给定的部分路径，检查剩余图是否连通。如果不是，那么该部分路径最终不能成为哈密顿路径。
2) 对于给定的部分路径，每个尚未访问的节点必须至少具有2度，使得一个邻居节点可以用于进入该节点，而其他邻居节点可以用于退出。
我想知道这些修剪技术可以节省多少时间。另外，我是否缺少一些非常重要的修剪技术，因为我的速度提升并不显着。
提前致谢 ！！！
I was recently trying to come up with the total number of hamiltonian paths (basically starting for start vertex, visit each node exaactly once and reach the end vertex). Brute force dfs goes for a long walk on a moderate sized grid of 7x8. I came up with some of these prunning strategies. The goal of these pruning techniques is that a partial path which cannot be a hamiltonian path should not be extended further.
DFS Algorithm:
Start for the start vertex, visit its neighbor nodes and recurse. Keep a count of the number of nodes visited and once reaching the end vertex, check if the totla visited nodes is same as the total nodes in the grid. This is going to be exponential complexity as for each vertex you can go in 4 directions, which will be of O(4^n). So focus should be to reject a path as soon as possible and not wait until reaching the end vertex.
Pruning Techniques:
1) For a given partial path, check if the remaining graph is connected. If it is not, then this partial path cannot end up to be a hamiltonian path.
2) For a given partial path, each yet-to-be-visited node must have atleast 2 degree such that one neighbor node could be used to enter this node and other other neighbor is used to exit.
I was wondering how much these pruning techniques could save time. Also am I missing some very improtant pruning techinque because my speed up is not significant.
Thanks in Advance !!!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
有一个适用于一般图的 O(n^2 * 2^n) 解决方案。该结构与此处描述的 O(2^n * n^2) 算法相同，
http:// /www.algorithmist.com/index.php/Traveling_Salesperson_Problem
除了记录最小距离之外，您还记录计数。
除此之外，你可以做的任何修剪仍然会有帮助。
There is an O(n^2 * 2^n) solution that works for general graphs. The structure is identical to the O(2^n * n^2) algorithm described here,
http://www.algorithmist.com/index.php/Traveling_Salesperson_Problem
Except rather than recording minimum distances, you are recording counts.
Any pruning you can do on top of that will still help.