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 的值是递增的