参考Russel和Norvig的第3.5节:在网格中，每个状态有4个后继状态，因此包含重复状态的搜索树有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 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的所有单元格，正如你可以看到的-可到达状态的数量，通过计算它们，看到它符合公式:
#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