3.6 知情搜索第二部分——找到最优解《人工智能》第3版 学习笔记 · 第06篇上一节3.5介绍的爬山法、束搜索等知情搜索策略往往只能找到某个解本节讨论如何在知情搜索框架下系统地找到最优解分支定界法3.6.1、使用低估启发值的分支定界法3.6.2、采用动态规划的分支定界法3.6.3以及 A* 搜索3.6.4。3.6.1 分支定界法Bounded Branch-and-Bound核心思想普通分支定界法不使用启发信息只根据节点已经付出的代价来扩展节点g(n)从根节点到达节点 n 已付出的代价open 表存放待扩展节点每次取出 g(n) 最小的节点扩展类似一致代价搜索closed 表存放已扩展过的节点避免重复扩展界 bound当前找到的最优最小目标路径代价。一旦找到目标就更新 bound之后所有 g(n) ≥ bound 的分支一律剪掉。首次到达目标节点时得到的路径代价并不一定最优因此算法继续搜索直到 open 表为空或所有剩余分支的 g 值都不小于当前 bound最终保留的路径即为最优解。搜索树示例图 3.13下图是一棵典型的搜索树根节点 A 通过边已付代价连接各子节点其中 G₁、G₂ 为目标节点。各边代价A–B4、A–C11、B–D15、B–E13、C–F4、C–H3、D–I12、D–J10、E–G₁18、E–K16、F–L6、F–M3、H–N1、H–G₂7。分步扩展过程图 3.14 a–e分支定界按 g(n) 从小到大扩展(a)初始根节点 Ag(A)0(b)扩展 A生成 Bg4、Cg11©扩展 Bg4 最小生成 Dg41519、Eg41317open 中现有 C(g11)、D(19)、E(17)(d)扩展 Cg11 最小生成 Fg11415、Hg11314(e)扩展 Hg14 最小生成 Ng14115、G₂g14721。叶子节点总开销图 3.14 g当所有叶子目标节点都被扩展后可比较它们的总开销取最小者作为最优解各叶子总开销I29、K33、L21、M18、N15、G₂21G₁ 已作为目标被剪枝/不计。可见最小总开销为N 的 15对应路径 A→C→H→N。注意分支定界会在搜索过程中不断用更小的 bound 剪掉更差的分支从而缩小搜索空间。伪代码function BRANCH-AND-BOUND(problem): open [初始节点] closed [] bound ∞ best None while open 非空: n open 中 g(n) 最小的节点 从 open 移除 n加入 closed if n 是目标节点: if g(n) bound: bound g(n); best 路径(n) continue # 继续找更优解 for m in Expand(n): # 生成子节点 if g(m) bound: # 超界分支直接剪枝 open.append(m) return best应用旅行商问题TSP分支定界法最经典的应用之一是旅行商问题TSP给定若干城市及两两距离寻找一条从某城市出发、恰好经过所有城市一次并返回出发城市的最短回路。图 3.15 给出一个 5 城市网络实例西安、成都、北京、哈尔滨、杭州边上标注的是城市间距离km部分距离西安–成都 606、西安–北京 914、西安–杭州 1150、哈尔滨–北京 1061、哈尔滨–杭州 1822、北京–成都 1518、北京–杭州 1134、成都–杭州 1539 等。将 TSP 转化为搜索树根节点为出发城市每层扩展决定下一个访问的城市路径代价为累计行驶距离当形成完整回路时即得到一个界再用分支定界剪枝排除更差的部分路线。图 3.16 展示了以西安为起点的分支定界搜索过程(a)根节点西安分出四条边成都 606、北京 914、杭州 1150、哈尔滨 1975(b)先扩展最小的成都606从成都继续访问北京60615182124等©继续扩展北京北京→哈尔滨91410611975等逐层累计路径长度并更新界。通过不断更新界并剪掉代价已超界的分支最终得到最短回路。3.6.2 使用低估启发值的分支定界法核心思想普通分支定界只用已付代价 g(n) 决定扩展顺序效率偏低。引入启发式估计后定义估价函数f(n) g(n) h(n)g(n)从起点到 n 的已付代价h(n)从 n 到目标的启发式估计剩余代价的下界估计f(n)经过 n 的完整路径总代价的估计值。低估条件可采纳性h(n) 必须不高估真实剩余代价即h(n) ≤ h*(n)其中 h*(n) 是从 n 到目标的最小真实代价。当 h 满足低估条件时f(n) 是经过 n 的最优路径总代价的乐观估计从而保证第一个被扩展/找到的目标节点就是全局最优解且剪枝不会误剪最优分支。启发式搜索树图 3.18下图在 3.6.1 的树结构上为每个节点标注了启发值 h节点标注格式为节点: h 值A:18、B:14、C:4叶子节点灰色框h 值为 0。边上仍标注已付代价。由于 f©g©h©11415f(B)g(B)h(B)41418因此先扩展 C而不再像普通分支定界那样先扩展 B——启发值把搜索导向更有希望的方向。分步演示图 3.19图 3.19 展示了按 f 值扩展并剪枝的细节f(B) g(B)h(B) 414 18f© 114 15故先扩展 C扩展 C 后生成 F、Hf(F) g(F)h(F) (114)1 16f(H) (113)3 17均小于当前界 18继续扩展扩展 F 得到 Mf 值超界剪枝扩展 H 得到 N超界剪枝与 G₂沿 H→G₂f(G₂) (1137)0 21即路径 A→C→H→G₂ 总开销 21同时 f(D)(415)92821D 分支被剪掉其他超界分支f21同样剪枝。最终找到路径A→C→H→G₂总开销 21且由于 h 低估该解即最优解。对比普通分支定界 vs 低估启发值解 3 拼图3 拼图8 拼图的小规模版本是理解两种策略差异的经典例子。图 3.20 用普通分支定界h0此时 fg求解搜索树规模爆炸、展开大量节点图 3.21 使用低估启发值h 为各数字牌到目标位置的曼哈顿距离搜索树显著缩小图中每个节点是一个 2×2 拼图状态数字 1、2、3 加一个空格边上标注 f 值。普通分支定界按深度盲目扩展fg而低估启发值按 fgh 优先扩展更接近目标的节点从而大幅减少搜索节点数。3.6.3 采用动态规划的分支定界法最优性原理Principle of Optimality动态规划的基础是最优性原理最优路径的任意子路径也是最优的。即若 S→…→G 是起点 S 到终点 G 的最优路径则其中任意两节点之间的片段也是这两节点间的最优路径。图 3.22 用示意图说明从 S 到 G 的最优路径可以经由中间节点 I₁ 或 I₂S 到 I₁ 的开销开销1与 S 到 I₂ 的开销开销2各自独立、互不影响只需分别求解并取优图中上半部分为图 3.21 © 的环路剪枝演示出现重复状态的节点标*直接剪枝不再扩展。动态规划与分支定界的结合在分支定界搜索中利用最优性原理可以剪除冗余的中间状态如果到达同一节点的两条路径中后者的代价不小于前者则后者一定不可能出现在最优解中直接丢弃。同时以递归/迭代方式保存子问题的最优解避免重复计算。这样动态规划分支定界既能像分支定界一样用界剪枝又能像动态规划一样复用子问题最优解进一步压缩搜索空间。3.6.4 A* 搜索核心思想A* 搜索是在分支定界基础上结合启发函数的最优搜索算法f(n) g(n) h(n)每次从 open 表中取出f(n) 最小的节点扩展。与 3.6.2 的分支定界相比A* 显式维护 closed 表并做环路检测与剪枝已扩展节点若以更小 f 值重新出现则更新否则剪掉保证每个状态至多扩展一次。可采纳性Admissibility若启发函数满足可采纳性h(n) ≤ h*(n)永远不高估到目标的真实代价则 A* 是可采纳的第一次扩展目标节点时得到的路径就是最优路径。这是 A* 最重要的理论保证。h 越接近 h*A* 扩展的节点越少h≡0 时退化为一致代价搜索。示例A* 解 3 拼图图 3.23搜索树中每个节点标注f(n)g(n)h(n)根节点状态3 1 / 空格 2f gh 04 4按 f 最小优先扩展生成左子3 空格 / 2 1f156与右子3 1 / 空格 2f134扩展右子继续扩展 f4 的节点出现重复状态时标*剪枝环路检测最终到达目标状态1 2 / 3 空格f 40 4路径即最优解。A* 正是通过按 f 最小扩展 环路剪枝 可采纳启发三者结合既保证最优性又控制搜索规模。要点总结分支定界法只按已付代价 g(n) 扩展节点用界 bound剪掉 g ≥ bound 的分支首次找到目标后继续搜索以逼近最优对应 open/closed 表机制。低估启发值分支定界法估价函数 f(n)g(n)h(n)h 满足低估条件 h(n) ≤ h*(n) 时f 是乐观估计保证首次找到的目标即最优解。动态规划分支定界法利用最优性原理最优路径的子路径也是最优的剪除冗余中间状态保存并复用子问题最优解压缩搜索空间。A* 搜索按 fgh 扩展 f 最小节点配合 closed 表与环路检测标*剪枝当 h 可采纳时 A* 必然找到最优路径是知情搜索中兼顾最优性与效率的代表算法。
从基础理论开始学习人工智能（五）知情搜索（第二部分）——找到最优解
3.6 知情搜索第二部分——找到最优解《人工智能》第3版 学习笔记 · 第06篇上一节3.5介绍的爬山法、束搜索等知情搜索策略往往只能找到某个解本节讨论如何在知情搜索框架下系统地找到最优解分支定界法3.6.1、使用低估启发值的分支定界法3.6.2、采用动态规划的分支定界法3.6.3以及 A* 搜索3.6.4。3.6.1 分支定界法Bounded Branch-and-Bound核心思想普通分支定界法不使用启发信息只根据节点已经付出的代价来扩展节点g(n)从根节点到达节点 n 已付出的代价open 表存放待扩展节点每次取出 g(n) 最小的节点扩展类似一致代价搜索closed 表存放已扩展过的节点避免重复扩展界 bound当前找到的最优最小目标路径代价。一旦找到目标就更新 bound之后所有 g(n) ≥ bound 的分支一律剪掉。首次到达目标节点时得到的路径代价并不一定最优因此算法继续搜索直到 open 表为空或所有剩余分支的 g 值都不小于当前 bound最终保留的路径即为最优解。搜索树示例图 3.13下图是一棵典型的搜索树根节点 A 通过边已付代价连接各子节点其中 G₁、G₂ 为目标节点。各边代价A–B4、A–C11、B–D15、B–E13、C–F4、C–H3、D–I12、D–J10、E–G₁18、E–K16、F–L6、F–M3、H–N1、H–G₂7。分步扩展过程图 3.14 a–e分支定界按 g(n) 从小到大扩展(a)初始根节点 Ag(A)0(b)扩展 A生成 Bg4、Cg11©扩展 Bg4 最小生成 Dg41519、Eg41317open 中现有 C(g11)、D(19)、E(17)(d)扩展 Cg11 最小生成 Fg11415、Hg11314(e)扩展 Hg14 最小生成 Ng14115、G₂g14721。叶子节点总开销图 3.14 g当所有叶子目标节点都被扩展后可比较它们的总开销取最小者作为最优解各叶子总开销I29、K33、L21、M18、N15、G₂21G₁ 已作为目标被剪枝/不计。可见最小总开销为N 的 15对应路径 A→C→H→N。注意分支定界会在搜索过程中不断用更小的 bound 剪掉更差的分支从而缩小搜索空间。伪代码function BRANCH-AND-BOUND(problem): open [初始节点] closed [] bound ∞ best None while open 非空: n open 中 g(n) 最小的节点 从 open 移除 n加入 closed if n 是目标节点: if g(n) bound: bound g(n); best 路径(n) continue # 继续找更优解 for m in Expand(n): # 生成子节点 if g(m) bound: # 超界分支直接剪枝 open.append(m) return best应用旅行商问题TSP分支定界法最经典的应用之一是旅行商问题TSP给定若干城市及两两距离寻找一条从某城市出发、恰好经过所有城市一次并返回出发城市的最短回路。图 3.15 给出一个 5 城市网络实例西安、成都、北京、哈尔滨、杭州边上标注的是城市间距离km部分距离西安–成都 606、西安–北京 914、西安–杭州 1150、哈尔滨–北京 1061、哈尔滨–杭州 1822、北京–成都 1518、北京–杭州 1134、成都–杭州 1539 等。将 TSP 转化为搜索树根节点为出发城市每层扩展决定下一个访问的城市路径代价为累计行驶距离当形成完整回路时即得到一个界再用分支定界剪枝排除更差的部分路线。图 3.16 展示了以西安为起点的分支定界搜索过程(a)根节点西安分出四条边成都 606、北京 914、杭州 1150、哈尔滨 1975(b)先扩展最小的成都606从成都继续访问北京60615182124等©继续扩展北京北京→哈尔滨91410611975等逐层累计路径长度并更新界。通过不断更新界并剪掉代价已超界的分支最终得到最短回路。3.6.2 使用低估启发值的分支定界法核心思想普通分支定界只用已付代价 g(n) 决定扩展顺序效率偏低。引入启发式估计后定义估价函数f(n) g(n) h(n)g(n)从起点到 n 的已付代价h(n)从 n 到目标的启发式估计剩余代价的下界估计f(n)经过 n 的完整路径总代价的估计值。低估条件可采纳性h(n) 必须不高估真实剩余代价即h(n) ≤ h*(n)其中 h*(n) 是从 n 到目标的最小真实代价。当 h 满足低估条件时f(n) 是经过 n 的最优路径总代价的乐观估计从而保证第一个被扩展/找到的目标节点就是全局最优解且剪枝不会误剪最优分支。启发式搜索树图 3.18下图在 3.6.1 的树结构上为每个节点标注了启发值 h节点标注格式为节点: h 值A:18、B:14、C:4叶子节点灰色框h 值为 0。边上仍标注已付代价。由于 f©g©h©11415f(B)g(B)h(B)41418因此先扩展 C而不再像普通分支定界那样先扩展 B——启发值把搜索导向更有希望的方向。分步演示图 3.19图 3.19 展示了按 f 值扩展并剪枝的细节f(B) g(B)h(B) 414 18f© 114 15故先扩展 C扩展 C 后生成 F、Hf(F) g(F)h(F) (114)1 16f(H) (113)3 17均小于当前界 18继续扩展扩展 F 得到 Mf 值超界剪枝扩展 H 得到 N超界剪枝与 G₂沿 H→G₂f(G₂) (1137)0 21即路径 A→C→H→G₂ 总开销 21同时 f(D)(415)92821D 分支被剪掉其他超界分支f21同样剪枝。最终找到路径A→C→H→G₂总开销 21且由于 h 低估该解即最优解。对比普通分支定界 vs 低估启发值解 3 拼图3 拼图8 拼图的小规模版本是理解两种策略差异的经典例子。图 3.20 用普通分支定界h0此时 fg求解搜索树规模爆炸、展开大量节点图 3.21 使用低估启发值h 为各数字牌到目标位置的曼哈顿距离搜索树显著缩小图中每个节点是一个 2×2 拼图状态数字 1、2、3 加一个空格边上标注 f 值。普通分支定界按深度盲目扩展fg而低估启发值按 fgh 优先扩展更接近目标的节点从而大幅减少搜索节点数。3.6.3 采用动态规划的分支定界法最优性原理Principle of Optimality动态规划的基础是最优性原理最优路径的任意子路径也是最优的。即若 S→…→G 是起点 S 到终点 G 的最优路径则其中任意两节点之间的片段也是这两节点间的最优路径。图 3.22 用示意图说明从 S 到 G 的最优路径可以经由中间节点 I₁ 或 I₂S 到 I₁ 的开销开销1与 S 到 I₂ 的开销开销2各自独立、互不影响只需分别求解并取优图中上半部分为图 3.21 © 的环路剪枝演示出现重复状态的节点标*直接剪枝不再扩展。动态规划与分支定界的结合在分支定界搜索中利用最优性原理可以剪除冗余的中间状态如果到达同一节点的两条路径中后者的代价不小于前者则后者一定不可能出现在最优解中直接丢弃。同时以递归/迭代方式保存子问题的最优解避免重复计算。这样动态规划分支定界既能像分支定界一样用界剪枝又能像动态规划一样复用子问题最优解进一步压缩搜索空间。3.6.4 A* 搜索核心思想A* 搜索是在分支定界基础上结合启发函数的最优搜索算法f(n) g(n) h(n)每次从 open 表中取出f(n) 最小的节点扩展。与 3.6.2 的分支定界相比A* 显式维护 closed 表并做环路检测与剪枝已扩展节点若以更小 f 值重新出现则更新否则剪掉保证每个状态至多扩展一次。可采纳性Admissibility若启发函数满足可采纳性h(n) ≤ h*(n)永远不高估到目标的真实代价则 A* 是可采纳的第一次扩展目标节点时得到的路径就是最优路径。这是 A* 最重要的理论保证。h 越接近 h*A* 扩展的节点越少h≡0 时退化为一致代价搜索。示例A* 解 3 拼图图 3.23搜索树中每个节点标注f(n)g(n)h(n)根节点状态3 1 / 空格 2f gh 04 4按 f 最小优先扩展生成左子3 空格 / 2 1f156与右子3 1 / 空格 2f134扩展右子继续扩展 f4 的节点出现重复状态时标*剪枝环路检测最终到达目标状态1 2 / 3 空格f 40 4路径即最优解。A* 正是通过按 f 最小扩展 环路剪枝 可采纳启发三者结合既保证最优性又控制搜索规模。要点总结分支定界法只按已付代价 g(n) 扩展节点用界 bound剪掉 g ≥ bound 的分支首次找到目标后继续搜索以逼近最优对应 open/closed 表机制。低估启发值分支定界法估价函数 f(n)g(n)h(n)h 满足低估条件 h(n) ≤ h*(n) 时f 是乐观估计保证首次找到的目标即最优解。动态规划分支定界法利用最优性原理最优路径的子路径也是最优的剪除冗余中间状态保存并复用子问题最优解压缩搜索空间。A* 搜索按 fgh 扩展 f 最小节点配合 closed 表与环路检测标*剪枝当 h 可采纳时 A* 必然找到最优路径是知情搜索中兼顾最优性与效率的代表算法。
