人工智能原理 第 2 章 搜索技术 （下）

本章内容 本章内容 2.1 搜索与问题求解 2.2 无信息搜索策略 2.3 启发式搜索策略 2.4 局部搜索算法 2.5 约束满足问题 2.6 博弈搜索 参考书目 附录 A* 算法可采纳性的证明 第2章 搜索技术

2.4 局部搜索算法 局部搜索与最优化 爬山法搜索 模拟退火搜索 局部剪枝搜索 遗传算法 第2章 搜索技术

4 局部搜索算法 前面的搜索算法都是保留搜索路径的， 到达目标的路径就是问题的解 — 然而许 多问题中到达目标的路径是无关紧要的 与系统地搜索状态空间(保留各种路径) 相对，不关心路径的搜索算法就是局部 搜索算法 局部搜索从一个单独的当前状态出发，通常 只移动到相邻状态 典型情况下搜索的路径不保留 第2章 搜索技术

5 局部搜索算法的应用 集成电路设计 工厂场地布局 车间作业调度 自动程序设计 电信网络优化 车辆寻径 文件夹管理 第2章 搜索技术

局部搜索与最优化问题 局部搜索算法的优点： 只使用很少的内存(通常是一个常数) 经常能在不适合系统化算法的很大或无限的 状态空间中找到合理的解 最优化问题 — 根据一个目标函数找到最佳 状态 / 只有目标函数，而不考虑(没有) “ 目标测试 ” 和 “ 路径耗散 ” 局部搜索算法适用于最优化问题 第2章 搜索技术

7 状态空间地形图 (1) 第2章 搜索技术 山肩 目标函 数 全局最大 值 局部最大 值 “ 平坦 ” 局部最大值 状态空 间 当前状 态

8 状态空间地形图 (2) 在状态图中，既有 “ 位置 ” (用状态表示) 又有 “ 高度 ” (用耗散值或目标函数值表 示) 如果高度对应于耗散值，则目标是找到全局 最小值，即图中最低点 如果高度对应于目标函数，则目标是找到全 局最大值，即图中最高峰 如果存在解，则完备的局部搜索算法能够找 到解 而最优的局部搜索算法能够找到全局最大或 最小值 第2章 搜索技术

9 局部搜索算法 本节简要介绍以下4种局部搜索算法 / 介绍其算法思想 爬山法搜索 模拟退火搜索 局部剪枝搜索 遗传算法 从搜索的角度看遗传算法也是搜索假设空间 的一种方法(学习问题归结为搜索问题) — 生 成后继假设的方式 第2章 搜索技术

爬山法搜索 爬山法 (hill-climbing)— 就是向值增加的方向持 续移动 — 登高过程 / 如果相邻状态中没有比它 更高的值，则算法结束于顶峰 爬山法搜索算法思想： (1) 令初始状态 S 0 为当前状态 (2) 若当前状态已经达标，则算法运行结束，搜索成 功 (3) 若存在一个动作可以作用于当前状态以产生一个 新状态，使新状态的估计值优于当前状态的估计 值，则放弃当前状态，并令刚产生的新状态为当 前状态，转 (2) (4) 取当前状态为相对最优解，停止执行算法 第2章 搜索技术

11 爬山法搜索的局限 爬山法是一种局部贪婪搜索，不是最优解 算法 ( 或是不完备的 ) / 其问题是： 局部极大值 — 比其邻居状态都高的顶峰，但是 小于全局最大值 ( 参照状态空间地形图 ) 山脊 — 一系列的局部极大值 高原 — 评价函数平坦的一块区域 ( 或者山肩 ) 第2章 搜索技术

12 爬山法搜索的变形 爬山法的变形 随机爬山法 — 随机选择下一步 首选爬山法 — 随机选择直到有优于当前节点的 下一步 随机重新开始爬山法 — 随机生成初始状态，进 行一系列爬山法搜索 — 这时算法是完备的概率 接近 1 第2章 搜索技术

模拟退火搜索 将爬山法(停留在局部山峰)和随机行走 以某种方式结合，以同时获得完备性和 效率 模拟退火的思想 想象在不平的表面上如何使一个乒乓球掉到 最深的裂缝中 — 如果只让其在表面滚动，则 它只会停留在局部极小点 / 如果晃动平面， 可以使乒乓球弹出局部极小点 / 技巧是晃 动足够大使乒乓球弹出局部极小点，但又不 能太大把它从全局极小点中赶出 第2章 搜索技术

14 模拟退火的解决思路 (1) 思路 — 开始使劲晃动(先高温加热)然后 慢慢降低摇晃的强度(逐渐降温)[退火过 程] 算法的核心 — 移动选择 选择随机移动，如果评价值改善，则移动被 接受，否则以某个小于1的概率接受 概率按照移动评价值变坏的梯度ΔE而呈指 数级下降 / 同时也会随着作为控制的参 数 —“ 温度 ” T的降低(数值减小)而降低 接受概率 =e ΔE/T (注意此时ΔE <0) 第5章 搜索技术

15 模拟退火的解决思路 (2) 温度T是时间的函数，按照模拟退火的思 想，数值应该逐渐减小(降温) 因为接受概率 =e ΔE/T 且ΔE <0，所以当温 度高时，接受概率较大(接近1) / 而T越 来越低时，ΔE/T变大，因而接受概率降 低 可以证明，如果T下降得足够慢，则算法 找到全局最优解的概率接近1 第5章 搜索技术

局部剪枝搜索 基本思想 — 与只从一个单独的起始状态 出发不同，局部剪枝搜索从k个随机生成 的状态开始，每步生成全部k个状态的所 有后继状态 / 如果其中之一是目标状态， 算法停止；否则从全部后继状态中选择 最佳的k个状态继续搜索 在局部剪枝搜索过程中，有用的信息在k 个并行的搜索线程之间传递 — 算法会很 快放弃没有成果的搜索而把资源放在取 得最大进展的搜索上 第2章 搜索技术

17 随机剪枝搜索 如果k个状态缺乏多样性，则局部剪枝搜 索会受其影响，性能变差 算法的变种 — 随机剪枝搜索帮助缓解这 一问题 — 随机剪枝搜索不是选择最好的k 个后代，而是按照一定概率随机地选择k 个后继状态 / 选择给定后继状态的概率 是状态值的递增函数 类似于自然选择过程 — 状态对应生物体，其 值对应于适应性，后代就是后继状态 第2章 搜索技术

遗传算法 遗传算法 (generic algorithm/GA) 是随机剪 枝的变种 — 不是通过修改单一状态而是 通过把两个父状态结合以生成后继状态 与剪枝搜索一样，遗传算法也是从k个随机 状态开始 — 这k个状态称为种群，每个状态 称为个体 个体用有限长的字符串(通常为0/1串)表示 每个状态用其评价函数(适应度函数)给出评 价值(适应值) 随后的操作包括 — 选择/杂交/变异 第2章 搜索技术

19 遗传算法的操作 选择 ( 或者称繁殖 )— 按照一定概率随机地 选择两对个体进行繁殖 ( 即生成后继状态 ) 杂交 ( 或者称交叉 )— 杂交点是在表示状态 的字符串中随机选择的一个位置，以此 形成新状态 — 后代是父串在杂交点上进 行杂交 ( 各取一部分 ) 得来的 变异 — 在新生成的串中各个位置都会按 照一个独立的小概率随机变异 第2章 搜索技术

20 遗传算法简要描述 (1) 定义问题和目标函数 (2) 选择候选解作为初始种群，每个解作为个体用 二进制串表示 ( 个体相当于染色体，其中的元素 相当于基因 ) (3) 根据目标函数，对于每个个体计算适应函数值 (4) 为每个个体指定一个与其适应值成正比的被选 择概率 ( 繁殖概率 ) (5) 根据概率选择个体，所选个体通过交叉 / 变异 等操作产生新一代种群 (6) 如果找到了解或者某种限制已到，则过程结束； 否则转 (3) 第2章 搜索技术

21 遗传算法的特点 遗传算法也结合了 “ 上山 ” 趋势和随机 搜索，并在并行搜索线程之间交换信息 遗传算法的主要优势来自于杂交 数学上可以证明，如果基因编码的位置在初 始时就随机转换的话，杂交就没有优势 杂交的优势在于它能够将独立发展的若干个 相对固定的字符(能够执行有用的功能 — “ 砖块 ” )组合起来，提高了搜索的粒度 所谓有用的砖块，就是几个结合起来可以构 造问题的解 — 参见书中的八皇后问题举例 第2章 搜索技术

22 遗传算法的模式 遗传算法上述特点可以用模式 (schema) 来 解释 — 模式是某些位置上的数字尚未确 定的一个状态子串 能够匹配模式的字符串称为该模式的实例 如果一个模式的实例的平均适应值超过均值， 则种群内这个模式的实例数量会随时间而增 长 遗传算法在模式和解的有意义成分相对应时 才会工作得最好 遗传算法有很多应用，但是在什么情况 下它会达到好效果，还有很多研究要做 第2章 搜索技术

2.5 约束满足问题 约束满足问题的定义 CSP 的回溯搜索 变量赋值次序的启发式 变量约束的启发式 关于失败变量的启发式 第2章 搜索技术

约束满足问题的定义 约束满足问题 (Constraint Satisfying Problem, CSP) 由一个变量集合 {X 1 ~X n } 和一个约束集 合 {C 1 ~C m } 定义 每个变量都有一个非空可能值域 D i 每个约束指定了包含若干变量的一个子集内各 变量的赋值范围 CSP 的一个状态 — 对一些或全部变量的赋值 {X i =v i, X j =v j, …} 第2章 搜索技术

25 CSP 问题的解 一个不违反任何约束的对变量的赋值称 为相容赋值或合法赋值 对每个变量都进行赋值称为完全赋值 一个 ( 一组 ) 既是相容赋值又是完全赋值的 对变量的赋值就是 CSP 问题的解 CSP 问题常常可以可视化，表示为约束图， 更直观地显示问题，帮助思考问题的答 案 第2章 搜索技术

26 从搜索角度看待 CSP 问题 CSP 看作搜索问题的形式化 初始状态 — 空赋值集合，所有变量都是未赋 值的 后继函数 — 给未赋值的变量一个赋值，要求 该赋值与先前的变量赋值不冲突 目标测试 — 测试当前的赋值 ( 组 ) 是否是完全 赋值 路径耗散 — 每步耗散均为常数 (1) 每个解必须为完全赋值 / 如果有 n 个变量， 则解出现的深度为 n( 有限 ) / 常使用深度 优先搜索 第2章 搜索技术

27 例 1 ：澳大利亚地图染色问题 (1) 澳大利亚地图：用红绿蓝3色标出各省， 相邻者颜色不同 第2章 搜索技术 西澳大利 亚 北领地 南澳大利 亚 昆士兰 新南威尔 士 维多利亚 塔斯马尼亚

28 对应于澳大利亚地图的约束图,相互关联的节点 用边连接 第5章 搜索技术 例 1 ：澳大利亚地图染色问题 (2) WA NT SA NSW Q V T 西澳大利亚 – WA 北领地 – NT 南澳大利亚 – SA 昆士兰 – Q 新南威尔士 – NSW 维多利亚 – V 塔斯马尼亚 – T 一组满足约束的完全赋值 {WA=R, NT=G, Q=R, SA= B, NSW=G, V=R, T=R}

29 例 2 ：密码算术问题 (1) 算式 T W O +T W O ——————— F O U R 直观地求解此问题： F=1 如不考虑 O/U 有进位，则 R/U/O 为偶数 R={4,6,8} O={2?,3?,4!} R=8/O=4 则 T=7( 由 O/R/U/W 共同限制 ) T=7 则 U=6/W=3  由此得到一组解 {1468 | 734} 考虑 U 有进位： R={0,2,4,6,8} O={5,……} R=0/O=5( 有进位 )/T=7/W=6/U=3 解 ={1530 | 765} 第2章 搜索技术

30 各算式约束 四列算式约束 O+O=R+10*X1 X1+W+W=U+10*X2 X2+T+T=O+10*X3 X3=F 对应的约束超图如右 六个变量互不相等约 束可化为两两不等约 束 — 二元约束 第2章 搜索技术 例 2 ：密码算术问题 (2) FTWUOR X3X1X2 约束：互不相等，两两不等

31 CSP 问题的分类 变量 — 离散值域 有限值域 — 如地图染色问题 无限值域 — 如作业规划，要使用约束语言 ( 线性约束 / 非线性约束 ) 变量 — 连续值域 如哈勃望远镜实验日程安排 / 线性规划问题 约束的类型 一元约束 — 只限制一个变量的取值 二元约束与 2 个变量相关 高阶约束 — 涉及 3 个或更多变量 第2章 搜索技术

32 CSP 问题求解的复杂度 搜索相容的完全赋值，最朴素的想法是 依次取变量的赋值组合并检查其是否满 足约束条件  指数级计算量 若 CSP 问题的任何一个变量的最大值域为 d ，那么可能的完全赋值数量为 O(d n ) 有限值域 CSP 问题包括布尔 CSP 问题 — 其 中有一些 NP 完全问题，如 3SAT 问题 ( 命 题逻辑语句的可满足性 ) / 最坏情况下不 会指望低于指数级时间复杂性解决该问 题 第2章 搜索技术

CSP 的回溯搜索 CSP 问题具有一个性质：可交换性 — 变量 赋值的顺序对结果没有影响 / 所有 CSP 搜 索算法生成后继节点时，在搜索树每个 节点上只考虑单个变量的可能赋值 CSP 问题的求解使用深度优先的回溯搜索 算法思想： 每次给一个变量赋值，当没有合法赋值 ( 不 满足约束时 ) 就要推翻前一个变量的赋值， 重新给其赋值，这就是回溯 第2章 搜索技术

34 简单回溯法生成的搜索树 澳大利亚地图染色问题的搜索树 第2章 搜索技术 WA=red NT=green WA=Red NT=blue WA=red NT=green Q=red WA=red NT=green Q=blue WA=greenWA=blue

35 回溯搜索的通用算法 可以改善上述无信息搜索算法的性能， 这些改进是一些通用性的考虑： 变量赋值的次序对性能的影响 — 在若干变量 已经赋值的条件下，如果下一步赋值有多个 选择，该选择哪一个？ 当前变量的赋值会对其他未赋值变量产生什 么约束？怎样利用这种约束以提高效率？ 当遇到某个失败的变量赋值时，怎样避免同 样的失败？就是说找到对这种失败起到关键 作用的某个变量赋值 第2章 搜索技术

变量赋值次序的启发式 随机的变量赋值排序难以产生高效率的 搜索 如：在 WA=red/NT=green 条件下选取 SA 赋值 比 Q 要减少赋值次数 (1:2) / 并且一旦给定 SA 赋值以后， Q/NSW/V 的赋值只有一个选择 因此，选择合法取值最少的变量 — 或者 称为最少剩余值 (MRV) 启发式，或者称 为最受约束变量 / 失败优先启发式 称为失败优先启发式是因为它可以很快找到 失败的变量，从而引起搜索的剪枝，避免更 多导致同样失败的搜索 第2章 搜索技术

37 MRV 启发式 当有多个变量需要选择时 — 优先选择在 当前约束下取值最少的变量 当赋值的变量有多个值选择时 — 优先选 择为剩余变量的赋值留下最多选择的赋 值 如， WA=red/NT=green 时，如果给 Q 赋值， 则 Q=blue 的选择不好，此时 SA 没有一个可 选择的了 如果要找出问题的所有解，则排序问题 无所谓 第2章 搜索技术

38 度启发式 对于初始节点，选择什么变量更合适？ 度启发式 — 选择涉及对其他未赋值变量 的约束数量大 ( 与其他变量关联最多 ) 的变 量 地图染色例子中，度 (SA)=5 / 其他均为 2/3 实际上，一旦选择了 SA 作为初始节点，应 用度启发式求解本问题，则可以不经任何回 溯就找到解 SA=red  NT=green  Q=blue  NSW=green  WA=blue  V=blue 第2章 搜索技术

变量约束的启发式 在搜索中尽可能早地考虑某些约束，以便 减少搜索空间 前向检验 — 如果 X 被赋值，前向检验就是检 查与 X 相连的那些变量 Y ，看看它们是否满 足相关约束，去掉 Y 中不满足约束的赋值 第2章 搜索技术 WANTQNSWVSA RGB R GBRGB GB R BG R BRGB B R BG R B -- WA=red Q=green V=blue 蓝色字体为 赋值结果

40 前向检验 地图染色问题中的前向检验 前向检验与 MRV 启发式相结合 — 实际上， MRV 要做的就是向前找合适的变量 赋值 V=blue 引起矛盾，此时 SA 赋值为空， 不满足问题约束 — 算法就要立刻回溯 注意这里只是检验一步，即和当前节点是否 矛盾 / 至于被检验节点之间的约束检验还不 能进行 — 改进：约束传播 第2章 搜索技术

41 约束传播 — 弧相容 约束传播 — 将一个变量的约束内容传播 到其他变量 希望约束传播检验更多的变量 / 花费的 代价更少 — 快速 弧相容 — 依次检验约束图中各个相关节 点对 ( 这里弧是有向弧 ) 例如：给定 SA/NSW 当前值域，对于 SA 的每 个取值 x ， NSW 都有某个 y 和 x 相容，则 SA 到 NSW 的弧是相容的 / 反过来是 NSW 到 SA 的 弧相容 第2章 搜索技术

42 弧相容 (1) 在地图染色约束的前向检验图中：第三行 SA={blue}/NSW={red,blue} ，则 SA 的取值有 一个 NSW=red 与之相容 / 反过来 NSW=blue ， 则 SA 为空值，即不相容 — 通过删除 NSW 值域 中的 blue 可使其相容 同样，弧相容检测也能更早地发现矛盾 — 如 第二行 SA/NT 值域均为 {blue} ，如必须删去 SA=blue ，则发现不相容 保持弧相容 (MAC) 算法思想 — 反复检测某 个变量值域中的不相容弧，进行值删除， 直到不再有矛盾 第2章 搜索技术

43 弧相容 (2) 弧相容算法思想： 用队列记录需要检验不相容的弧 每条弧 [Xi, Xj] 依次从队列中删除并被检验， 如果任何一个 Xi 值域中的值需要删除，则每 个指向 Xi 的弧 [Xk, Xi] 都必须重新插入队列 进行检验 — 因为指向这个变量的弧可能产生 新的不相容 ( 因为原来可能就是因为这个值 产生了它们之间的相容 ) 时间复杂度 — 二元 CSP 约束至多有 O(n 2 ) 条弧 / 每条弧至多插入队列 d 次 (d 个取值 ) ，检验一 条弧为 O(d 2 ) / 算法最坏情况下为 O(n 2 d 2 ) 第2章 搜索技术

44 特殊约束 实际问题中出现的特殊约束，其效率要 比通用的约束高很多 变量取值各不相同 —AllDiff ，如果约束涉及 m 个变量，所有变量共有 n 个取值，如果 m>n 则此约束不能被满足 相应算法 — 删除约束中只有单值值域的变量， 将其取值从其余变量值域中删去；对单值变 量重复此过程；如果得到空值域或剩下的变 量数大于取值数，则产生矛盾 其他约束 — 资源约束 / 边界约束 第2章 搜索技术

关于失败变量的启发式 在回溯算法中，当发现不满足约束即搜 索失败时，则回到上一个变量并尝试下 一个取值 — 称为历时回溯 / 在很多情况 下这样做是效率很低的 — 因为问题并不 决定于上一个 ( 甚至几个 ) 变量的取值 所以，回溯应该倒退到导致失败的变量 集合中的一个变量 — 该集合称为冲突集 变量 X 的冲突集是通过约束与 X 相连接的 先前已赋值变量的集合 第2章 搜索技术

46 冲突集 对于地图染色问题，设有不完全赋值 {Q= red, NSW=green, V=blue, T=red} / 此时， SA 赋值将发现不满足任何约束 —SA 的冲 突集 ={Q, NSW, V} 对于前向检验算法，可以很容易得到冲 突集 基于 X 赋值的前向检验从变量 Y 的值域中删 除一个值时，说明 X 和 Y 存在冲突，则显然 X 是 Y 的冲突集中的一个变量 当到达 Y 时，可知回溯到哪个变量 第2章 搜索技术

47 后向跳转 回溯检验导致失败的变量的赋值 — 后向 跳转：回溯到冲突集中时间最近 ( 最后赋 值 ) 的变量 每个被后向跳转剪枝的分支在前向检验 算法中也被剪枝 — 简单的后向跳转在前 向检验 ( 弧相容性检验 ) 搜索中是多余的 因为都是做取值相容的检测，只要在弧 相容检验时增加一个变量集合记录即可 第2章 搜索技术

48 冲突指导的后向跳转 变量的冲突集更一般的情况 — 前面的变 量集合中全部变量 ( 不是其中一个变量 ) 使 得当前变量与之冲突 冲突指导的后向跳转处理 令 Xj 是当前变量， conf(Xj) 是其冲突集，如 果 Xj 每个可能取值都失败了，则后向跳转到 conf(Xj) 中最近的一个变量 Xi 令 conf(Xi)=conf(Xi)  conf(Xj)-{Xi} 从 Xi 向前是无解的 / 从 Xi 回到某个以前的变 量赋值 ( 参考 p116 例子 ) 第2章 搜索技术

2.6 博弈搜索 极大极小决策  -  剪枝 第2章 搜索技术

50 博弈搜索问题与方法 从智能体角度看，博弈是多智能体之间 的竞争和对抗 / 在竞争的环境中，每个 智能体的目的是冲突的，由此引出对抗 搜索问题 — 称为博弈 本节探讨两个问题 — 如何搜索到取胜的 路径 / 如何提高搜索效率 相应的方法 — 最优策略(极大极小决策)/  -  剪枝 第2章 搜索技术

51 博弈游戏的描述 两个游戏者的博弈可以定义为一类搜索 问题，其中包括： 初始状态 — 棋盘局面和哪个游戏者出招 后继函数 — 返回(招数,状态)对的一个列表， 其中每对表示一个合法招数和相应的结果状 态 终止测试 — 判断游戏是否结束 效用函数 — 或称目标函数，对终止状态给出 一个数值如输赢和平局(以-1/+1/0表示) 双方的初始状态和合法招数定义了游戏的博 弈树 — 此为博弈搜索 第2章 搜索技术

52 井字棋的博弈树 第2章 搜索技术 ………… … … X XX XX X XXX X O O XX O X O X X O X X O X X O X X O O X O O XX X XO O XX O X OO X … MAX(X) MIN(O) MAX(X) MIN(O) TERMINAL 效用效用 0 +1

极大极小决策 博弈搜索中，最优解是导致取胜的终止 状态的一系列招数 在井字棋搜索树中，因为 MAX 先行，所 以 MAX 的任务是利用搜索树确定最佳招 数 / 但是另一方 MIN 也有发言权 因此 MAX 制定取胜策略时必须不断地考 虑 MIN 应对条件下如何取胜 — 即 MAX 初 始状态下应该采取什么招数，然后是 MIN 应对造成的状态下 MAX 采取的招数， 接着继续考虑下一步应对后的招数... 第2章 搜索技术

54 极大极小值 (1) 假设一个两层的博弈树(因为即使是井字 棋的博弈树也太复杂了)，其中有 MAX 节点和 MIN 节点 博弈树中，每个单方的招数 ( 或称走步 ) 是 一层 / 双方各走一招称为一步 ( 博弈树的 深度是一步的 ) 给定一棵博弈树，最优策略可以通过检 查每个节点的极大极小值来决定 — 记为 MAX-MIN(n) ，所以也称为极大极小决策 第2章 搜索技术

55 极大极小值 (2) 如果博弈双方都按照最优策略进行，那 么一个节点的极大极小值就是对应状态 的效用值(对应MAX) 对于某个节点，极大极小函数如下定义 MAX 优先选择有极大值的状态 / MIN 则 选择有极小值的状态 第5章 搜索技术

56 极大极小值 (3) 第2章 搜索技术 A BDC MAX MIN MAX

57 极大极小值 (4) 图中 MAX 先行，有 3 个后继 MIN 节点，此 时 MAX 的取值必须看 MIN 如何取值 每个 MIN 节点亦有 3 个后继 MAX 节点，假 设其取值已知 因为 MIN 节点只取其后继节点中之最小 者 ( 让 MAX 效用最小 ) ，故 B=3/C=2/D=2 MAX 节点取 A/B/C 中最大者，故 A=3 最后根节点 A 的极大极小函数值 =3— 引向 具有最高极大极小值的后继 第2章 搜索技术

58 极大极小值算法说明 简单的递归算法 — 按照定义计算每个后继 节点的极大极小值 / 搜索是从目标到初始节 点的反向推导 算法对博弈树实行了深度优先搜索 如果博弈树的最大深度为 m ，每个节点的合 法招数为 b ，则 算法的时间复杂度是 O(b m ) 每次生成全部后继节点的空间复杂度是 O(bm) 每次只生成一个后继节点的空间复杂度是 O(m) 第2章 搜索技术

59 极大极小值算法 Function MAX-MIN-DECISION(state) returns an action inputs: state (current state in game) v← MAX-VALUE(state) return the action in SUCCESSORS(state) with value v Function MAX-VALUE(state) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v← - ∞ for a, s in SUCCESSORS(state) do v← MAX(v, MIN-VALUE(s)) return v(a=action 招数 ) Function MIN-VALUE(state) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v← +∞ for a, s in SUCCESSORS(state) do v← MIN(v, MAX-VALUE(s)) return v 第2章 搜索技术

 -  剪枝 极大极小值搜索的问题是状态数随着棋 局步数的数量而指数级增长 — 不幸的是 没有办法消除这种指数级增长，所幸的 是可以有效将其减半 — 剪枝技术 应用于极大极小值搜索树中 —  -  剪枝 剪掉那些不可能影响最后决策的分支，返回 和极大极小值算法同样的结果 例子的剪枝过程中 MAX-MIN(n)= max(min(3,12,8), min(2,x,y), min(14,5,2))= max(3,min(2,x,y),2)=max(3,z,2)=3 第2章 搜索技术

61 博弈树的剪枝 (1) 第2章 搜索技术 3 [-∞, +∞] A B [-∞,3] (a) [-∞, +∞] 12 A B 3 [-∞,3] (b)

62 博弈树的剪枝 (2) 第2章 搜索技术 12 A B [3, +∞] 3 8 [3,3] (c) 12 A B C [3, +∞] [-∞,2] [3,3] (d)

63 博弈树的剪枝 (3) 第2章 搜索技术 [-∞,14] 12 A B D C [3,14] [-∞,2] [3,3] (e) 12 A B D C [3,3] [-∞,2] [2,2] [3,3] (f )

64  -  剪枝算法 (1) 在极大极小值算法基础上增加了剪枝功 能，即在返回值基础上增加了判断 Function ALPHA-BETA-SEARCH(state) returns an action inputs: state (current state in game) v← MAX-VALUE(state, - ∞, +∞) return the action in SUCCESSORS(state) with value v 第2章 搜索技术

65  -  剪枝算法 (2) Function MAX-VALUE(state, ,  ) returns a utility value inputs: state , the value of the best alternative for MAX along the path to state , the value of the best alternative for MIN along the path to state if TERMINAL-TEST(state) then return UTILITY(state) v← - ∞ for a, s in SUCCESSORS(state) do v← MAX(v, MIN-VALUE(s, ,  )) if v≥  then return v  ← MAX( , v) return v 第2章 搜索技术

66  -  剪枝算法 (3) Function MIN-VALUE(state, ,  ) returns a utility value inputs: state , the value of the best alternative for MAX along the path to state  the value of the best alternative for MIN along the path to state if TERMINAL-TEST(state) then return UTILITY(state) v← +∞ for a, s in SUCCESSORS(state) do v← MIN(v, MAX-VALUE(s, ,  )) if v≤  then return v  ← MIN( , v) return v 第2章 搜索技术

67  -  剪枝算法的说明  -  剪枝可以应用树的任何深度，许多情 况下可以剪掉整个子树 / 其原则是 — 如果 在节点 n 的父节点或者更上层的节点有一 个更好的选择 m ，则在实际游戏 ( 搜索 ) 中 永远不会到达 n  =到目前为止在路径上任意点发现的MAX最 佳选择  =到目前为止在路径上任意点发现的MIN最 佳选择  -  搜索不断更新  /  值，当某个节点的值 分别比  /  值更差时剪掉该节点的剩余分支 第2章 搜索技术

68  -  剪枝的效率  -  剪枝的效率很大程度上取决于检查后 继节点的次序 — 应该先检查那些可能最 好的后继 如果能够先检查那些最好的后继，则  -  剪枝算法只需检查 O(b d/2 ) 个节点以决定最 佳招数 / 极大极小值算法为 O(b d )— 有效 分支因子 b 到 b 的平方根 — 效率大大提高 第2章 搜索技术

69 本章复习提示 尝试使用搜索方式求解问题 / 注意本章 的搜索算法都是通用算法，即没有考虑 具体任务的相关知识 具体搜索问题的形式化表示 ( 初始状态 / 后 继函数 / 搜索代价等 ) 了解各种搜索算法 ( 包括局部搜索和博弈 搜索 ) 的思想、相关性质和性能 尝试用启发式搜索算法 (A* 算法 ) 解决一 些游戏问题 约束满足问题的相关概念 第2章 搜索技术

70 参考书目 Stuart Russell / Peter Norvig: AIMA 第 3 章 / 第 4 章 / 第 5 章 / 第 6 章 陆汝钤 编著 : 人工智能 ( 上册 ) 第 5 章 / 第 6 章 / 第 8 章 / 第 9 章 田盛丰、黄厚宽，人工智能与知识工程， 中国铁道出版社， 1999 年 8 月第 1 版，第 4 章 / 第 9 章 第2章 搜索技术

附录 A* 算法可采纳性的证明 第2章 搜索技术

72 A* 算法可采纳性 定理： A* 算法是可采纳的，即若存在从初始节 点 S 0 到目标节点 Sg 的路径，则 A* 算法必 能结束在最佳路径上 证明的过程： 首先证明 A* 算法必定成功结束 其次证明 A* 算法结束时中止于最佳路径 第2章 搜索技术

73 证明的步骤 证明分为三步： (1)对于有限图，A*算法一定成功结束 (2)对于无限图，A*算法一定成功结束 (3)A*算法必定终止于最佳路径上 对于无限图情况的证明，引入2个引理 (1)如果A*算法不终止，则存在f值任意大的节 点 (2)A*算法结束前，仍有耗散值更小的节点待 扩展 第2章 搜索技术

74 定理 1 的证明 (1) 定理1 — 对于有限图，如果从初始节点S 0 到目标节点Sg有路径存在，则A*算法一 定成功结束 证明： 首先证明算法必定会结束 由于搜索图为有限图，如果算法能找到解， 则会成功结束；如果算法找不到解，则必然 会由于Open表变空而结束。因此，A*算法必 然会结束 第2章 搜索技术

75 定理 1 的证明 (2) 然后证明算法一定会成功结束 由于至少存在一条由初始节点到目标节点的 路径，设此路径为 S 0 = n 0 ，n 1 ， … ，n k =Sg 算法开始时，节点n 0 在Open表中，而且路径 中任一节点n i 离开Open表后，其后继节点 n i+1 必然进入Open表，这样，在Open表变为 空之前，目标节点必然出现在Open表中 / 因此，算法必定会成功结束★ 第2章 搜索技术

76 引理 1 的证明 (1) 引理 1— 对无限图，如果从初始节点 S 0 到 目标节点 Sg 有路径存在，且 A* 算法不终 止的话，则从 Open 表中选出的节点必将 具有任意大的 f 值 证明： 设 d*(n) 是 A* 算法生成的从初始节点 S 0 到节 点 n 的最短路径长度，由于搜索图中每条边 的代价都是一个正数，令这些正数中最小的 一个数是 e, 则有 第2章 搜索技术

77 引理 1 的证明 (2) 因为是最佳路径的代价，故有 又因为h(n)≥0，故有 如果A*算法不终止的话，从Open表中选出的 节点必将具有任意大的 d*(n) 值，因此，也将 具有任意大的f值 ★ 第2章 搜索技术

78 引理 2 的证明 (1) 引理 2— 在 A* 算法终止前的任何时刻， Open 表中总存在节点 n’ ，它是从初始节点 S 0 到目标节点的最佳路径上的一个节点， 且满足 证明： 设从初始节点 S 0 到目标节点 t 的最佳路径序列为 S 0 = n0 ， n1 ， … ， nk =Sg 算法开始时，节点 S 0 在 Open 表中，当节点 S 0 离 开 Open 进入 Closed 表时，节点 n 1 进入 Open 表 第2章 搜索技术

79 引理 2 的证明 (2) 因此， A* 没有结束以前，在 Open 表中必存在 最佳路径上的节点 设这些节点排在最前面的节点为 n’, 则有 f(n’)=g(n’)+h(n’) 由于 n’ 在最佳路径上，故有 g(n’)=g*(n’), 从而 f(n’)=g*(n’)+h(n’) 又由于 A* 算法满足 h(n’)≤h*(n’), 故有 f(n’)≤g*(n’)+h*(n’)=f*(n’) 因为在最佳路径上的所有节点的 f* 值都应相 等，因此有 f(n’)≤f*(S 0 ) ★ 第2章 搜索技术

80 定理 2 的证明 定理 2— 对于无限图，如果从初始节点 S 0 到目标节点 Sg 有路径存在，则 A* 算法必 然会结束 证明： ( 反证法 ) 假设 A* 算法不结束，由引理 1 知 Open 表中 的节点有任意大的 f 值，这与引理 2 的结论 相矛盾，因此， A* 算法只能成功结束 ★ 推论 1—Open 表中任一具有 f(n)≤f(S 0 ) 的节 点 n ，最终都被 A* 算法选作为扩展节点 第2章 搜索技术

81 定理 3 的证明 (1) 定理 3—A* 算法是可采纳的，即若存在从 初始节点 S 0 到目标节点 Sg 的路径，则 A* 算法必能结束在最佳路径上 证明： 证明过程分以下两步进行 先证明 A* 算法一定能够终止在某个目标节点 上 — 由定理 1 和定理 2 可知，无论是对有限图 还是无限图， A* 算法都能够找到某个目标节 点而结束 第2章 搜索技术

82 定理 3 的证明 (2) 再证明 A* 算法只能终止在最佳路径上 ( 反证法 ) 假设 A* 算法未能终止在最佳路径上，而是终 止在某个目标节点 Sg 处，则有 f(Sg)=g(Sg)>f*(S 0 ) 由引理 2 可知，在 A* 算法结束前，必有最佳 路径上的一个节点 n’ 在 Open 表中且有 f(n’)≤f*(S 0 )<f(Sg) 这时， A* 算法一定会选择 n’ 来扩展，而不可 能选择 Sg ，从而也不会去测试目标节点 Sg ， 这就与假设 A* 算法终止在目标节点相矛盾 / 因此， A* 算法只能终止在最佳路径上★ 第2章 搜索技术

83 推论 2 推论 2— 在 A* 算法中，对任何被扩展的任 一节点 n ，都有 f(n) ≤ f*(S 0 ) 证明： 令 n 是由 A* 选作扩展的任一节点，因此 n 不会 是目标节点，且搜索没有结束 / 由引理 2 可知， 在 Open 表中有满足 f(n’)≤f*(S 0 ) 的节点 n’ 若 n=n’, 则有 f(n)≤f*(S 0 ) 否则，算法既然选择 n 扩展，那就必有 f(n)≤f(n’) 所以有 f(n)≤f*(S 0 ) ★ 第2章 搜索技术