避免重复状态的搜索算法 [英] Search algorithm with avoiding repeated states

问题描述

参考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 步骤至（0,0）（索引（ d，d）），所以我们可以得到更严格的界限。

方法1：组合

如果我们说我们只能移动向上和向右，我们可以遍历的可到达单元的数量是 sum {CC（i，2） | i = 0,1，...，d} 。在这里， CC 代表 stars and bars 解决方案，并定义为：

  CC（n，k）=选择（n + k-1，k-1）=（n + k-1）！/ / code> 

分配公式时，我们得到：

pre> 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 步骤的唯一单元格的数量是任何此类矩形上的单元格数量。 / p>

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



  #reachable_cells（d）= sum {4i | i = 1，...，d} = 4 sum {i | i = 1，...，d} 
  

这是算术级数的总和（并添加我们得到：

pre $ lt; code> #reachable_cells（d）= 4 * d（d + 1）/ 2 + 1 = 2d（d + 1）+ 1〜= 2d ^ 2


strong>

  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 
  

With reference to Section 3.5 of Russel and Norvig : On a grid, each state has four successors, so the search tree including repeated states has 4^d leaves; but there are only about 2d^2 distinct states within d steps of any given state.

What is the meaning of distinct states here. Can someone explain me by considering various values of d, say 1,2,3,4.

解决方案

What is the meaning of distinct states here.

The meaning of distinct state is a unique cell, you count each cell in the grid only once.

Crude upper bound to number of distinct states:

First, look at a subgrid of size 2d+1 X 2d+1, and you start from the node at the middle. It is easy to see that there are no cells outside of this subgrid that are reachable (from the center) within d steps. In addition, number of cells in this subgrid is (2d+1)*(2d+1) ~= 4d^2, so we found a simple upper bound which is significantly better than naive 4^d.

But there are many cells which are still unreachable (for example, you cannot get within d steps to (0,0) from the middle (which is index (d,d)), so we can get a tighter bound.

Approach 1: Combinatorics:

If we say we can move only "up and right", the number of reachable cells we can traverse through are sum { CC(i,2) | i=0,1,...,d }. In here, CC stands for stars and bars solution, and defined as:

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

When assigning the formula, we get:

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

The above is sum of arithmetic progression that sums to (d)(d+1)/2

However, note that by allowing only "up and right" moves, we allowed reaching only to the upper-right quarter of the grid, and we want to allow it for the other quarters as well. From symmetry, for each quarter the number of attainable cells is identical to the above, and in addition - add the origin cell (one we started from) so at total we get:

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

Approach 2 Geometrical:

Have a look on the following example matrix of size 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

This matrix contains all nodes of distance at most 3 from the center.
If you look carefully, you can see that each distance is actually forming a square around the center, with an edge of length d. (so for d=1, there is a square around 0 with edges of length 1, for d=2, there is a square with edged of length 2, and so on)

In a square, the perimeter is 4a - where a is the length of the edge.
So, the number of unique cells which are reachable from the center with at most d steps, is the number of cells on any such rectangle.

Number of cells on a rectangle with edge length of i is 4i, and we need to sum that up for each possible rectangle where i<d, and we get:

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

This is sum of arithmetic progression again (and add the origin again), and we get:

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

Examples:

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

In the above, you have 7X7 matrix, it contains all cells of of distance up to 3 from the center, as you can see - the number of reachable states by counting them and see it fits the 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

这篇关于避免重复状态的搜索算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！