避免重复状态的搜索算法

参考Russel和Norvig的第3.5节：在一个网格上，每个状态有四个后继状态，因此包括重复状态的搜索树有4^d个叶子节点；但在任何给定状态的d步之内，只有大约2d^2个不同的状态。

这里的不同状态是什么意思？能否通过考虑d的不同值，例如1,2,3,4来解释一下？

回答：

这里的不同状态是什么意思？

不同状态的含义是一个独特的单元格，你只计算网格中的每个单元格一次。

不同状态数量的粗略上限：

首先，查看一个大小为2d+1 X 2d+1的子网格，并从中间的节点开始。很容易看出，在d步之内，从中心无法到达这个子网格之外的任何单元格。此外，这个子网格中的单元格数量是(2d+1)*(2d+1) ~= 4d^2，所以我们找到了一个比简单的4^d显著更好的上限。

但仍有许多单元格是无法到达的（例如，从中间（索引为(d,d)）无法在d步之内到达(0,0)），所以我们可以得到一个更紧密的上限。

方法1：组合学：

如果我们说只能向上和向右移动，我们可以通过的可达单元格数量是sum { CC(i,2) | i=0,1,...,d }。这里的CC代表星和条解法，定义为：

CC(n,k) = Choose(n+k-1,k-1) = (n+k-1)!/(n!*(k-1)!)

当应用公式时，我们得到：

sum{ (i+1)!/(i)!1! | i=1,...,d} = sum { (i+1) | i=1,...,d}

以上是等差数列的和，合计为(d)(d+1)/2

然而，请注意，通过只允许向上和向右移动，我们只能到达网格的右上角，我们还希望允许到达其他角。从对称性来看，每个角的可达单元格数量与上述相同，并且还需加上起始单元格（我们开始的那个），所以总共我们得到：

#reachable_cells(d) = 4* (d)(d+1)/2 = 2d(d+1) + 1 ~= 2d^2

方法2：几何学：

看一下以下大小为7 X 7的示例矩阵：

6 5 4 3 4 5 65 4 3 2 3 4 54 3 2 1 2 3 43 2 1 0 1 2 34 3 2 1 2 3 45 4 3 2 3 4 56 5 4 3 4 5 6

这个矩阵包含了距离中心最多3步的所有节点。
如果你仔细观察，你会发现每个距离实际上在中心周围形成了一个边长为d的正方形。（所以对于d=1，在0周围有一个边长为1的正方形，对于d=2，有一个边长为2的正方形，以此类推）

在一个正方形中，周长是4a – 其中a是边的长度。
因此，从中心最多d步可达的唯一单元格数量，就是任何这样的矩形上的单元格数量。

边长为i的矩形上的单元格数量是4i，我们需要对每个可能的矩形进行求和，其中i<d，我们得到：

#reachable_cells(d) = sum { 4i | i=1,....,d } = 4 sum{ i | i=1,...,d}

这再次是等差数列的和（再加上起始点），我们得到：

#reachable_cells(d) = 4 * d(d+1)/2 + 1 = 2d(d+1) + 1 ~= 2d^2

示例：

6 5 4 3 4 5 65 4 3 2 3 4 54 3 2 1 2 3 43 2 1 0 1 2 32 3 2 1 2 3 45 4 3 2 3 4 56 5 4 3 4 5 6

在上面，你有一个7X7的矩阵，它包含了距离中心最多3步的所有单元格，正如你所见 – 通过计数可达状态的数量并验证它符合公式：

#reachable_cells(0) = 2*0*1 + 1 = 1#reachable_cells(1) = 2*1*2 + 1 = 5#reachable_cells(2) = 2*2*3 + 1 = 13#reachable_cells(3) = 2*3*4 + 1 = 25

学技术