优化网格中所有路径的回溯算法,从左上角到右下角只访问每个方块一次
Optimisation of the backtracking algorithm for all paths in a grid from top left to bottom right visiting each square just once
问题陈述:计算nxn中的路径数
从左上角到右下角的网格使得路径访问
每个方块恰好一次。例如,在一个7£7的格子中,有111712个这样的
路径。
算法和优化:我们从简单的回溯算法开始,然后
使用对如何修剪搜索的观察逐步优化它。
这是我不明白的部分:
Optimisation 1: In any solution, we first move one step down or right. There are always two
paths that are symmetric about the diagonal of the grid after the first step. Hence, we can decide that we always first move one step down (or right), and
finally multiply the number of solutions by two.
我知道会有对称的解决方案,所以我们可以只找到其中的一半并将数字乘以 2。但是我们如何实现呢?
这句话是什么意思?:
Hence, we can decide that we always first move one step down (or right)
这是否意味着第一步总是向下(或向右)?基本上调节基本递归的第一步?或者这是否意味着对每个递归步骤都这样做?或者这意味着完全不同的东西。我在理解上遇到了很多麻烦。请详细说明。
对于每条路径(例如“RDDRRD”)都有一个镜像路径,您可以在其中交换 D 和 R(“例如 DRRDDR”)。
文中说,如果你找到所有以 D 开头的路径,你可以通过执行反转简单地生成所有以 R 开头的路径。
因此,您可以简单地假设第一个字母是 D,然后将得到的路径数乘以 2。
对于涉及动态规划的解决方案,这不会产生太大影响,但对于朴素的回溯解决方案,这是一个因素 2!
问题陈述:计算nxn中的路径数 从左上角到右下角的网格使得路径访问 每个方块恰好一次。例如,在一个7£7的格子中,有111712个这样的 路径。
算法和优化:我们从简单的回溯算法开始,然后 使用对如何修剪搜索的观察逐步优化它。
这是我不明白的部分:
Optimisation 1: In any solution, we first move one step down or right. There are always two paths that are symmetric about the diagonal of the grid after the first step. Hence, we can decide that we always first move one step down (or right), and finally multiply the number of solutions by two.
我知道会有对称的解决方案,所以我们可以只找到其中的一半并将数字乘以 2。但是我们如何实现呢?
这句话是什么意思?:
Hence, we can decide that we always first move one step down (or right)
这是否意味着第一步总是向下(或向右)?基本上调节基本递归的第一步?或者这是否意味着对每个递归步骤都这样做?或者这意味着完全不同的东西。我在理解上遇到了很多麻烦。请详细说明。
对于每条路径(例如“RDDRRD”)都有一个镜像路径,您可以在其中交换 D 和 R(“例如 DRRDDR”)。 文中说,如果你找到所有以 D 开头的路径,你可以通过执行反转简单地生成所有以 R 开头的路径。
因此,您可以简单地假设第一个字母是 D,然后将得到的路径数乘以 2。
对于涉及动态规划的解决方案,这不会产生太大影响,但对于朴素的回溯解决方案,这是一个因素 2!