一、搜索问题的形式化

1. 搜索问题通常可以被形式化为五个部分：

状态空间（state space）

初始状态（initial state）

动作/行动（action）

转移模型（transition model）：用来描述每个动作的作用

目标状态（goal state）

动作代价（action cost function）

一个动作序列形成一条路径（path），而解（solution）是一条 从初始状态到某个目标状态的路径。我们假设动作代价是可累加的； 也就是说，一条路径的总代价是各个动作代价的总和。最优解 （optimal solution）是所有解中路径代价最小的解。

二、搜索求解 

1. 树搜索（Tree Search）

树搜索函数返回：解，或者失败

使用问题的初始状态初始化搜索树的边界

循环执行：

-如果边界为空，返回失败

-选择一个叶结点，并将其从边界移除

-如果这个结点包括一个目标状态（当它被移除边界后），返回相应的解

-扩展所选结点，将结果结点添加到边界

边界已生成但尚未到达

2. 图搜索（Graph Search）

图搜索不允许重复访问结点，即OPEN表 ∩ CLOSED表 = ø，此处重复的结点不一定是父节点。

树搜索允许重复访问结点。

3. 树结点的结构

4. 搜索算法的评估

完备性

最优性

复杂性

三、搜索策略

边界中的结点顺序决定了搜索策略

1. 宽度优先搜索BFS（树搜索）

先扩展根节点，然后扩展根节点的所有后继节点，再扩展后继节点的后继。

对内存要求高，生成的结点数是指数级的。

BFS的最优性完备性复杂性

最优性：单步代价相同时

完备性：分支因子b有限

复杂性：1+b+…+b^d=O(b^d)

2. 一致代价搜索UCS（图搜索）/ Dijkstra算法

不同于广度优先搜索在深度一致的波（首先是深度1，然后是深度2，以此类推）中展开，一致代价搜索算法的思想是在路径代价一致的波中展开。

算法只在扩展节点时测试其是否为目标节点，而不是在生成节点时测试。

UCS的最优性、完备性、复杂性

最优性：最优

完备性：有0代价行动可能会陷入死循环

复杂性：所有动作代价相同时，这时一致代价搜索类似于广度优先搜索