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

Presentation on theme: "人工智能原理 第 2 章 搜索技术 （下）. 本章内容 本章内容 2.1 搜索与问题求解 2.2 无信息搜索策略 2.3 启发式搜索策略 2.4 局部搜索算法 2.5 约束满足问题 2.6 博弈搜索 参考书目 附录 A* 算法可采纳性的证明 第2章 搜索技术."— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

39 39 2.5.4 变量约束的启发式 在搜索中尽可能早地考虑某些约束，以便 减少搜索空间 前向检验 — 如果 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 40 前向检验 地图染色问题中的前向检验 前向检验与 MRV 启发式相结合 — 实际上， MRV 要做的就是向前找合适的变量 赋值 V=blue 引起矛盾，此时 SA 赋值为空， 不满足问题约束 — 算法就要立刻回溯 注意这里只是检验一步，即和当前节点是否 矛盾 / 至于被检验节点之间的约束检验还不 能进行 — 改进：约束传播 第2章 搜索技术

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

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

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

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

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

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

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

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

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

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

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

52 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

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

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

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

56 56 极大极小值 (3) 第2章 搜索技术 3 12 8 2 4 6 14 5 2 A BDC 322 3 MAX MIN MAX

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

59 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章 搜索技术

60 60 2.6.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 61 博弈树的剪枝 (1) 第2章 搜索技术 3 [-∞, +∞] A B [-∞,3] (a) [-∞, +∞] 12 A B 3 [-∞,3] (b)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

82 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 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章 搜索技术