我最近试图提出哈密顿路径的总数（基本上从起始顶点开始，准确地访问每个节点一次并到达结束顶点）。蛮力 dfs 在 7x8 的中等大小的网格上走了很长一段路。我想出了一些修剪策略。这些修剪技术的目标是不应该进一步扩展不能是哈密顿路径的部分路径。
DFS算法：从起始顶点开始，访问其邻居节点并递归。记录访问过的节点数，一旦到达结束顶点，检查访问过的节点总数是否与网格中的总节点数相同。这将是指数复杂度，因为对于每个顶点，您可以在 4 个方向上进行，这将是 O(4^n)。所以重点应该是尽快拒绝一条路径，而不是等到到达终点。
修剪技巧：
1）对于给定的部分路径，检查剩余的图是否连通。如果不是，那么这条部分路径就不能成为哈密顿路径。
2) 对于给定的部分路径，每个尚未访问的节点必须具有至少 2 度，以便一个邻居节点可以用于进入该节点，而另一个其他邻居用于退出。
我想知道这些修剪技术可以节省多少时间。我是否还缺少一些非常重要的修剪技术，因为我的加速并不显着。
提前致谢 ！！！