搜搜算法的核心

• state，状态，状态对应了搜索过程中的节点（node）
• action，动作

状态可以是一个数，可以是一个数组，可以是任何一系列能够描述事物的参数。比如对于迷宫而言，我们会将迷宫的每个位置有什么作为状态。

动作存在于两个状态之间，比如我有一个动作是交换相邻元素。那么对于状态

[1, 2, 3] -> [1, 3, 2]

以上就是交换后两个元素的动作。

• 相邻状态，就是能从一个状态，执行一步动作就能到达的状态集合

  [1, 2, 3] -> [2, 1, 3]
  [1, 2, 3] -> [1, 3, 2]
  

  状态123，经过一次交换动作，只能到达状态213，132，无法到达状态321，312，231

• fringe，边界（状态）集合，边界就是我已经枚举到了这个状态，但还没有从这个状态出发，考虑这个状态能够通过动作扩展出其他状态的状态集合（还没扩展）。

搜索时这样的一个过程：从一个状态开始，枚举所有可能的动作，找到该动作的相邻状态，然后从相邻状态继续出发，枚举所有可能的动作，得到相邻状态的相邻状态，……如此重复，从一个状态可以达到相邻状态的相邻状态的相邻状态的相邻状态……，将所有可能的状态按照这种方式枚举出来的过程，就叫做搜索。

搜索往往时有目标的，当我们枚举到一个满足条件的内容时，就可以停下的，这个目标一般称为 goal。

搜索算法的分类

Lecture3: uninformed search，也就是没有额外信息的搜搜，常见算法 DFS，BFS，DLS，IDS

• DFS：Depth first search，深度优先搜索，简称深搜：

  深搜就是在边界集合 fringe 中，优先扩展深度最深的节点（深度就是从初始状态 init state 开始，需要多少个 action 才能到达该状态）

• BFS：Breath first search，广度优先搜索，简称广搜：

  广搜就是在边界集合 fringe 中，优先扩展深度最浅的节点

Lecture4 ：informed search

• A*：BFS和DFS是两个极端，一个最深一个最浅，但都不够智能，而且仅仅使用了深度作为判断的依据。我们将深度称为 g，当前状态到终止状态的估计步数称为 h，定义新的价值为 f=g + h，然后优先扩展 f 最小的节点。f 最小意味着，这一个节点在目前所有见过的节点中，估计能够最快搜索到终点 goal