AI 导论3:搜索

正文索引 [隐藏]

搜索:在知识库中寻找可利用的知识,从而构建一条代价较小的路径

  • 盲目搜索:预定策略,中间信息不用
  • 启发式搜索:加入启发性信息

状态空间:状态 + 算符

  • 状态:image-20191210164610039
  • 算符:使状态改变的操作
  • 举例
    image-20191210164648851

OPEN - CLOSE 表:搜索策略中常用数据结构

  • OPEN 表:存放活结点(刚生成的节点)
  • CLOSE 表:存放将要扩展的节点 (从 OPEN 表中取)& 扩展完成的节点

1. 广度优先搜索

  • 从初始节点 S₀ 开始,逐层地对节点进行扩展并考察它是否为目标节点。在第 n 层的节点没有全部扩展并考察之前,不对第 n+1层的节点进行扩展
  • OPEN 表中节点按照 FIFO 排序

搜索过程

  1. OPEN <- S0
  2. 若 OPEN 为空,无解退出,否则继续执行
  3. CLOSE <- (n = OPEN[0])
  4. 考察节点 n
    • n 为目标节点,返回解退出
    • n 不可扩展,转 2
    • n 可扩展,继续执行
  5. 扩展 n,OPEN <- 未在 OPEN 和 CLOSE 中出现的子节点,子节点的父节点标记为 n,转 2

2. 深度优先搜索

基本思想

  • 从初始节点 S₀ 开始,深度遍历
  • OPEN 表中节点按照 LIFO 排序

搜索过程

  1. S0 -> OPEN
  2. 若 OPEN 为空,无解退出,否则继续执行
  3. CLOSE <- (n = OPEN[0])
  4. 考察节点 n
    • n 为目标节点,返回解退出
    • n 不可扩展,转 2
    • n 可扩展,继续执行
  5. 扩展 n,未在 OPEN 和 CLOSE 中出现的子节点 -> OPEN,子节点的父节点标记为 n,转 2

3. 有界深度优先搜索

基本思想:深度优先搜索 + 深度界限 dm,搜索深度到达 dm 后,转换分支进行搜索

搜索过程

  1. S0 -> OPEN,d(S0) = 0
  2. 若 OPEN 为空,无解退出,否则继续执行
  3. CLOSE <- (n = OPEN[0])
  4. 考察节点 n
    • n 为目标节点,返回解退出
    • d(n) = dm,转 2
    • n 不可扩展,转 2
    • n 可扩展,继续执行
  5. 扩展 n,未在 OPEN 和 CLOSE 中出现的子节点 -> OPEN,子结点深度为 d(n) + 1,转 2

4. 代价树搜索

可深度可广度

代价树

image-20191210171207813

代价树广度优先搜索

  1. OPEN <- S0
  2. 若 OPEN 为空,无解退出,否则继续执行
  3. CLOSE <- (n = OPEN[0])
  4. 考察节点 n
    • n 为目标节点,返回解退出
    • n 不可扩展,转 2
    • n 可扩展,继续执行
  5. 扩展 n,OPEN <- 未在 OPEN 和 CLOSE 中出现的子节点,对整个 OPEN 表排序,按照代价从小到大排序,子节点的父节点标记为 n,转 2

代价树深度优先搜索

  1. S0 -> OPEN
  2. 若 OPEN 为空,无解退出,否则继续执行
  3. CLOSE <- (n = OPEN[0])
  4. 考察节点 n
    • n 为目标节点,返回解退出
    • d(n) = dm,转 2
    • n 不可扩展,转 2
    • n 可扩展,继续执行
  5. 扩展 n,未在 OPEN 和 CLOSE 中出现的子节点按代价从小到大排序 -> OPEN,子节点的父节点标记为 n,转 2

5. 启发式搜索

启发性信息:可用于指导搜索过程,且与具体问题有关的信息

估价函数:用于评估节点重要性的函数

image-20191210172441302

  • g(x):代价函数,就是代价树搜索中的代价

  • h(x):启发函数,估计当前状态到最终状态还需要的代价

    • 举例

    image-20191210172626621

全局择优搜索

广度优先、代价树广度优先也是全局择优搜索

  1. OPEN <- S0
  2. 若 OPEN 为空,无解退出,否则继续执行
  3. CLOSE <- (n = OPEN[0])
  4. 考察节点 n
    • n 为目标节点,返回解退出
    • n 不可扩展,转 2
    • n 可扩展,继续执行
  5. 扩展 n,OPEN <- 未在 OPEN 和 CLOSE 中出现的子节点,对整个 OPEN 表排序,按照 f(x) 从小到大排序,子节点的父节点标记为 n,转 2

局部择优搜索

深度优先、代价树深度优先也是局部择优搜索

当一个节点被扩展后,选择 f(x) 最小的子结点作为下一个考察节点:

  1. S0 -> OPEN
  2. 若 OPEN 为空,无解退出,否则继续执行
  3. CLOSE <- (n = OPEN[0])
  4. 考察节点 n
    • n 为目标节点,返回解退出
    • d(n) = dm,转 2
    • n 不可扩展,转 2
    • n 可扩展,继续执行
  5. 扩展 n,未在 OPEN 和 CLOSE 中出现的子节点按 f(x) 从小到大排序 -> OPEN,子节点的父节点标记为 n,转 2

6. A* 搜索

是启发式搜索的终极进阶版,当估价函数 f(x) = g(x) + h(x) 中的 h(x) 可以代表所有 h(x) 的下界时(也就是 h(x) 代表从当前节点到目标节点的最小代价),启发式搜索就能进化为 A* 搜索:

  1. S0 -> OPEN
  2. 若 OPEN 为空,无解退出,否则继续执行
  3. CLOSE <- (n = OPEN[0])
  4. 考察节点 n
    • n 为目标节点,返回解退出
    • n 不可扩展,转 2
    • n 可扩展,继续执行
  5. n 扩展出一堆子结点,这些子结点中不是 n 先辈的节点集合记为 M
  6. 针对 M 中所有节点,进行如下判定:
    • 不在 OPEN、CLOSE 表中:完全的新节点,直接放入 表,父节点记为 n
    • 在 OPEN 表中:待扩展的节点,如果将父节点修改为 n 能够减小其 g(x),则修改父节点为 n
    • 在 CLOSE 表中:已经扩展的节点,如果将父节点修改位 n 能够减小其 g(x),则修改父节点为 n,同时更新其所有后续结点
  7. 对 OPEN 表中的节点按 h(x) 从小到大进行排序,转 2
    可以看到,在步骤 6 中有可能需要更新大量节点的信息,这在结构复杂的网络中是不可承受的代价,影响搜索效率,而只要 h(x) 满足单调性限制,就能免除子结点更新:

h(x) 的单调性限制

设节点 xj 是节点 xi 的 子结点,c(xi, xj) 是节点 xi 到节点 xj 的花费,若满足:

    \[h(x_i) \leq h(x_j) +c(x_i,x_j)\]

则称 h(x) 具备单调性限制

一旦 h(x) 具备单调性限制,而每次选择扩展的节点又子节点中 f(x) 最小的,则 g(x) 就一定是最小的,所以不会存在子节点更新的问题,同时,A* 算法扩展的节点序列中 f 的值是递增的