搜索算法中的不同状态

Question

在 AI- 现代方法一书中以及 link 中的答案：

我有一个问题。我有点理解我们如何得到 2 d² 作为不同状态的数量。我没有得到的是几何方法。供大家参考，我给出了矩阵和解。

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

在上面，你有 7×7 矩阵，它包含距离中心不超过 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

Google 的工程师 Amit 回答了这个问题。

Answer 1

想法是相同距离的细胞形成菱形（45°的正方形）。

当您查看 3 次出现时，您有 4 个面，总共 4*3=12 个单元格：

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

对于其他距离，我们得到：

  distance   occurrences
  ----------------------
     0            1
     1            4
     2            8
     3           12
     ..
     n           4n

公式4n对所有n都成立，除了n=0，当它是 1.

现在，要知道距离到 n 的不同单元格的数量，我们得到这个 table:

  distance   occurrences
  ----------------------
     0            1
     1            1+4
     2            1+4+8
     3            1+4+8+12
     ..
     n            1 + ∑4i, for i in [1..n]

现在1 + ∑4i = 1+4∑i，而∑i就是triangular number，意味着我们可以简化为：

1+4( ½n(n+1) ) = 1+2n(n+1)，这是你在例子中给出的公式：

#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
  ...
#reachable_cells(n) = 2*n*(n+1) + 1

搜索算法中的不同状态

distinct states in search algorithm

algorithm

search

artificial-intelligence