AI 导论3:搜索
搜索:在知识库中寻找可利用的知识,从而构建一条代价较小的路径
- 盲目搜索:预定策略,中间信息不用
- 启发式搜索:加入启发性信息
状态空间:状态 + 算符
- 状态:
- 算符:使状态改变的操作
- 举例
OPEN - CLOSE 表:搜索策略中常用数据结构
- OPEN 表:存放活结点(刚生成的节点)
- CLOSE 表:存放将要扩展的节点 (从 OPEN 表中取)& 扩展完成的节点
1. 广度优先搜索
- 从初始节点 S₀ 开始,逐层地对节点进行扩展并考察它是否为目标节点。在第 n 层的节点没有全部扩展并考察之前,不对第 n+1层的节点进行扩展
- OPEN 表中节点按照 FIFO 排序
搜索过程
- OPEN <- S0
- 若 OPEN 为空,无解退出,否则继续执行
- CLOSE <- (n = OPEN[0])
- 考察节点 n
- n 为目标节点,返回解退出
- n 不可扩展,转 2
- n 可扩展,继续执行
- 扩展 n,OPEN <- 未在 OPEN 和 CLOSE 中出现的子节点,子节点的父节点标记为 n,转 2
2. 深度优先搜索
基本思想
- 从初始节点 S₀ 开始,深度遍历
- OPEN 表中节点按照 LIFO 排序
搜索过程
- S0 -> OPEN
- 若 OPEN 为空,无解退出,否则继续执行
- CLOSE <- (n = OPEN[0])
- 考察节点 n
- n 为目标节点,返回解退出
- n 不可扩展,转 2
- n 可扩展,继续执行
- 扩展 n,未在 OPEN 和 CLOSE 中出现的子节点 -> OPEN,子节点的父节点标记为 n,转 2
3. 有界深度优先搜索
基本思想:深度优先搜索 + 深度界限 dm,搜索深度到达 dm 后,转换分支进行搜索
搜索过程
- S0 -> OPEN,d(S0) = 0
- 若 OPEN 为空,无解退出,否则继续执行
- CLOSE <- (n = OPEN[0])
- 考察节点 n
- n 为目标节点,返回解退出
- d(n) = dm,转 2
- n 不可扩展,转 2
- n 可扩展,继续执行
- 扩展 n,未在 OPEN 和 CLOSE 中出现的子节点 -> OPEN,子结点深度为 d(n) + 1,转 2
4. 代价树搜索
可深度可广度
代价树
代价树广度优先搜索
- OPEN <- S0
- 若 OPEN 为空,无解退出,否则继续执行
- CLOSE <- (n = OPEN[0])
- 考察节点 n
- n 为目标节点,返回解退出
- n 不可扩展,转 2
- n 可扩展,继续执行
- 扩展 n,OPEN <- 未在 OPEN 和 CLOSE 中出现的子节点,对整个 OPEN 表排序,按照代价从小到大排序,子节点的父节点标记为 n,转 2
代价树深度优先搜索
- S0 -> OPEN
- 若 OPEN 为空,无解退出,否则继续执行
- CLOSE <- (n = OPEN[0])
- 考察节点 n
- n 为目标节点,返回解退出
- d(n) = dm,转 2
- n 不可扩展,转 2
- n 可扩展,继续执行
- 扩展 n,未在 OPEN 和 CLOSE 中出现的子节点按代价从小到大排序 -> OPEN,子节点的父节点标记为 n,转 2
5. 启发式搜索
启发性信息:可用于指导搜索过程,且与具体问题有关的信息
估价函数:用于评估节点重要性的函数
-
g(x):代价函数,就是代价树搜索中的代价
-
h(x):启发函数,估计当前状态到最终状态还需要的代价
- 举例
全局择优搜索
广度优先、代价树广度优先也是全局择优搜索
- OPEN <- S0
- 若 OPEN 为空,无解退出,否则继续执行
- CLOSE <- (n = OPEN[0])
- 考察节点 n
- n 为目标节点,返回解退出
- n 不可扩展,转 2
- n 可扩展,继续执行
- 扩展 n,OPEN <- 未在 OPEN 和 CLOSE 中出现的子节点,对整个 OPEN 表排序,按照 f(x) 从小到大排序,子节点的父节点标记为 n,转 2
局部择优搜索
深度优先、代价树深度优先也是局部择优搜索
当一个节点被扩展后,选择 f(x) 最小的子结点作为下一个考察节点:
- S0 -> OPEN
- 若 OPEN 为空,无解退出,否则继续执行
- CLOSE <- (n = OPEN[0])
- 考察节点 n
- n 为目标节点,返回解退出
- d(n) = dm,转 2
- n 不可扩展,转 2
- n 可扩展,继续执行
- 扩展 n,未在 OPEN 和 CLOSE 中出现的子节点按 f(x) 从小到大排序 -> OPEN,子节点的父节点标记为 n,转 2
6. A* 搜索
是启发式搜索的终极进阶版,当估价函数 f(x) = g(x) + h(x) 中的 h(x) 可以代表所有 h(x) 的下界时(也就是 h(x) 代表从当前节点到目标节点的最小代价),启发式搜索就能进化为 A* 搜索:
- S0 -> OPEN
- 若 OPEN 为空,无解退出,否则继续执行
- CLOSE <- (n = OPEN[0])
- 考察节点 n
- n 为目标节点,返回解退出
- n 不可扩展,转 2
- n 可扩展,继续执行
- n 扩展出一堆子结点,这些子结点中不是 n 先辈的节点集合记为 M
- 针对 M 中所有节点,进行如下判定:
- 不在 OPEN、CLOSE 表中:完全的新节点,直接放入 表,父节点记为 n
- 在 OPEN 表中:待扩展的节点,如果将父节点修改为 n 能够减小其 g(x),则修改父节点为 n
- 在 CLOSE 表中:已经扩展的节点,如果将父节点修改位 n 能够减小其 g(x),则修改父节点为 n,同时更新其所有后续结点
- 对 OPEN 表中的节点按 h(x) 从小到大进行排序,转 2
可以看到,在步骤 6 中有可能需要更新大量节点的信息,这在结构复杂的网络中是不可承受的代价,影响搜索效率,而只要 h(x) 满足单调性限制,就能免除子结点更新:
h(x) 的单调性限制
设节点 xj 是节点 xi 的 子结点,c(xi, xj) 是节点 xi 到节点 xj 的花费,若满足:
则称 h(x) 具备单调性限制
一旦 h(x) 具备单调性限制,而每次选择扩展的节点又子节点中 f(x) 最小的,则 g(x) 就一定是最小的,所以不会存在子节点更新的问题,同时,A* 算法扩展的节点序列中 f 的值是递增的

原文链接:AI 导论3:搜索
nightmorning的博客 版权所有,转载请注明出处。
还没有任何评论,你来说两句吧!