避免重复状态的搜索算法

Question

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

这里不同的状态是什么意思。有人可以通过考虑 d 的各种值来解释我，比如 1,2,3,4。

Answer 1

What is the meaning of distinct states here.

distinct state的意思是一个唯一的cell，你对grid中的每个cell只计算一次。

不同状态数的粗略上限：

首先，查看大小为 2d+1 X 2d+1 的子网格，然后从中间的节点开始。很容易看出，在 d 步内（从中心）可以到达此子网格之外的任何单元格。此外，此子网格中的单元格数量为 (2d+1)*(2d+1) ~= 4d^2，因此我们找到了一个简单的上限，该上限明显优于原始 4^d.

但是还有很多单元格仍然无法访问（例如，您无法在 d 步内从中间（即索引 (d,d)）到达 (0,0)，所以我们可以获得更严格的约束。

方法一：组合学：

如果我们说我们只能移动"up and right"，我们可以遍历的可达单元格数是sum { CC(i,2) | i=0,1,...,d }。这里CC代表stars and bars解，定义为：

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

但是，请注意，通过只允许 "up and right" 次移动，我们只允许到达网格的右上四分之一，我们希望其他四分之一也允许。从对称性来看，每个季度可获得的单元格数量与上述相同，此外 - 添加原始单元格（我们从中开始的单元格）所以总共得到：

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

方法 2 几何：

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

6 5 4 3 4 5 6
5 4 3 2 3 4 5
4 3 2 1 2 3 4
3 2 1 0 1 2 3
4 3 2 1 2 3 4
5 4 3 2 3 4 5
6 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 6
5 4 3 2 3 4 5
4 3 2 1 2 3 4
3 2 1 0 1 2 3
2 3 2 1 2 3 4
5 4 3 2 3 4 5
6 5 4 3 4 5 6

在上面，你有 7X7 矩阵，它包含距离中心最多 3 的所有单元格，如你所见 - 通过计算可到达状态的数量并查看它是否符合 forumla:

#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

Search algorithm with avoiding repeated states