产生式系统的搜索策略讲义课件(PPT 68页).ppt

08 03 2020 1 第三章产生式系统的搜索策略 状态空间 由给定问题的所有可能的状态组成的空间 相当于全集G 搜索空间 按某种策略在状态空间中选取的部分空间 G的子集 解路径 解空间 求解问题的一条有效路径 搜索策略的基本思路 搜索空间必须包含解路径 如果问题有解 且尽量缩小搜索空间 搜索策略的评价准则 总体费用最低 08 03 2020 2 费用的划分 a规则应用的费用 执行规则时所花的费用b控制费用 选择规则所花的费用 08 03 2020 3 第三章目录 3 1回溯策略3 2图搜索策略3 3启发式图搜索策略1 A算法2 爬山算法3 分支界限算法4 动态规划算法5 A 算法 08 03 2020 4 6 h函数与A 的关系7 关于单调性限制8 A 算法示例 08 03 2020 5 3 1回溯算法 08 03 2020 6 08 03 2020 7 例四皇后问题 08 03 2020 8 定义综合数据库 设 DATA ij 1 i j 4 其中 ij表示棋子所在行列如 24表示第二行第四列有一枚棋子因为棋盘上可放入的棋子数为0 4个所以集合中元素数位0 4个 即length DATA 0 4 08 03 2020 9 08 03 2020 10 08 03 2020 11 08 03 2020 12 08 03 2020 13 08 03 2020 14 08 03 2020 15 3 2图搜索策略 08 03 2020 16 图搜索策略 图搜索的实质是从问题空间中找出一张包含目标节点的子图 图搜索的结果 1 一个完整的搜索图G 2一个解路径 用指针表示的解路径 ProcedureGraphSearch1G G0 G0 s open s s 初始状态2closed 3Loop ifopen thenexit fall 4n first open remove n open add n closed 5ifgoal n thenexit success 6 mj expand n mj不含n的先辈节点7open add open mj mj不在open closed中 08 03 2020 17 标记mj每个到n节点指针确定是否需要修改已在open closed中的每个节点到n的指针确定是否需要修改已在closed中的每个节点的后继节点原来的指针 8按照某种方式排列open表中的节点 goloop 08 03 2020 18 08 03 2020 19 08 03 2020 20 深度优先算法 Procedruedepth First Search1G G0 G0 s open s closed s 初始状态2Loop ifopen thenexit fall 3n first open 4ifgoal n thenexit success 5remove n open add n closed 6 mj expand n mj不含n的先辈节点7open add open mj mj不在open closed中标记mj每个到n节点指针 按照节点深度递减顺序排列open中的节点8goloop 08 03 2020 21 讨论1 如果问题有解 有深度优先搜索算法 是否能够找到解 不一定 解空间是否有限 讨论2 本算法的改进之处是open中节点按照深度优先排列 但是没有对深度加以控制 可能造成搜索代价太大 08 03 2020 22 宽度优先算法 Procedruebreadth First Search1G G0 G0 s open s closed s 初始状态2Loop ifopen thenexit fall 3n first open 4ifgoal n thenexit success 5remove n open add n closed 6 mj expand n mj不含n的先辈节点7open add open mj mj不在open closed中 08 03 2020 23 标记每个到n节点指针 按照节点深度递增顺序排列open中的节点8goloop理论上可以利用宽度优先搜索能够找到解 如果问题有解的话 讨论 宽度优先算法和深度优先算法可能出现组合爆炸 都没有利用任何启发式信息 所以称为无信息搜索策略 08 03 2020 24 宽度优先例题 由一张桌子T 三个积木A B C组成一个积木世界 初始状态是A在B上 B在桌子上 C在桌子上 目标状态是 A B C依次从上到下排列在桌子上 如图 08 03 2020 25 解 1 状态描述 P1 P2 P3 表示按A B C顺序依次分别在P1 P2 P3上其中Pi是积木或者桌子 初始状态时 B T T 目标状态可以表示 B C T 2 定义操作 move x y 表示将积木x移到Y上 约束条件 aX顶部必须是空的b如果Y是积木 Y的顶部必须是空的c同一种状态出现不得多于一次 08 03 2020 26 1 解题过程2 open表和closed表3 节点样子画出整个图G和解路径4 程序何时结束5 改用深度优先如何 08 03 2020 27 3 3启发式图搜索策略 基本概念启发式图搜索的实质是利用启发信息有目的地进行搜索 减少搜索的盲目性 降低搜索空间找到最佳解启发式信息用于解决open表中节点的排列次序问题 方法是利用一个评价函数计算open表中节点的评价函数值 按照函数值从小到大排列所有节点 08 03 2020 28 评价函数的目的 把最有希望得到最佳解或者解的排列在前面 路径 给定节点序列 n0 n1 nk 如果该序列中的任一节点ni 1都有后继节点ni 则该节点序列为从n0到nk的一条路径 路径长度为K路径耗散值 路径耗散值等于该路径上所有相邻节点间耗散值的总和 08 03 2020 29 设 路径山任两点间的耗散值为才C ni nj 则从ni到nk的路径耗散值为C ni nj C ni nj C nj nk 最佳路径耗散值 最佳路径上的实际耗散值 记为 K ni nj K ni nj C ni nj 08 03 2020 30 定义几个函数1 g n k s n 从初始节点s到当前节点n的最佳路径的耗散值 2 h n k n t 从当前节点n到目标节点t的最佳路径的好三者 3 f n g n h n 从初始节点s通过当前节点n到目标节点t的最佳路径的耗散值 08 03 2020 31 4 评价函数 f n g n h n 其中f g h分别是f g h 的估计值 通常约定 f n 按照升序排列 讨论 有上述定义 得 1 g n g n 2 当h 0且g n d n 时 f n d n 既宽度优先策略 d n 节点深度 3 h n 称为启发函数 08 03 2020 32 3 1 1A算法 1G G0 G0 s open s closed f s g s h s s 初始状态2Loop ifopen thenexit fall 3n first open h 4ifgoal n thenexit success 5remove n open add n closed 6 mj expand n mj不含n的先辈节点计算f n mi g n mi h mi 自s经过n mi到目标节点的耗散值 08 03 2020 33 open add open mj 标记mj到n的指针 mj不在open closed中 iff n mk f mk thenf mk f n mk 标记mk到n的指针 mk在open中 iff n mL f mL thenf mL f n mL 标记mL到n的指针 mL在closed中 add mL open 把mL放回到open中7Open中的节点按f值升序排列8goloop 08 03 2020 34 08 03 2020 35 例八数码问题令 g n d n 节点深度h n w n 不在位的数码个数 启发函数 则f n d n w n 如初始节点s的f值f 0 d 0 w 0 0 4 4有4个数码不在位 08 03 2020 36 08 03 2020 37 对于f n g n h n 如果单独考虑g n 或者h n 即 1 f n g n 只考虑搜索过的路径已经耗费的费用 分支界限算法2 f n h n 只考虑未来的发展趋势 爬山算法那么可以得到两种特殊的算法 爬山算法和分支界限算法 08 03 2020 38 3 3 2爬山算法 ProcedureHill Climbing1n s2Loop ifgoal n thenexit success 3 mi expangd n 计算每个h mi nextn h mi 最小值的节点4ifh n h nextn thenexit fail 5n nextn6goloop优点 缺点 08 03 2020 39 3 3 3分支界限算法f n g n ProcedureBranch Bound1queue s s g s 0 queue中保存的是从s出发的路径 2Loop ifqueue 0thenexit fail 3path FIRST queue n LAST pATH 取第一条路径 及该路径的最后节点n4ifgoal n thenexit success 5 mj expand n 计算g mj g n mj remove s n queue add s mj queue 删除原来的路径 添加长度加一的路径 08 03 2020 40 6queue队列中分支按g值升序排列7GOLOOP例下图右八城市 城市间的耗散值已经给出 利用分支界限算法给出从S到t的最佳路径 08 03 2020 41 08 03 2020 42 3 3 4动态规划算法 Proceduredynamic Programming1queue s s g s 0 queue中保存的是从s出发的路径 2Loop ifqueue 0thenexit fail 3path FIRST queue n LAST pATH 取第一条路径 及该路径的最后节点n4ifgoal n thenexit success 5 mj expand n 计算g mj g n mj remove s n queue add s mj queue 08 03 2020 43 删除原来的路径 添加长度加一的路径 6仅保留queue中到达某一公共节点路径中耗散值最小的路径 余者删除 queue队列中分支按g值升序排列7GOLOOP 08 03 2020 44 08 03 2020 45 讨论a动态规划与分支界限差别在于去掉公共路径的冗余部分 提高效率 b如果问题空间是树结构 动态规划与分支界限相同 因为对于树结构不存在到达同一节点有多重路径的情况 C动态规划改进的代价 比如上例中 增加一个城市 08 03 2020 46 A算法总结 1初始状态 open s 2正常情况下 非成功非失败 取open中的第一个节点n 将n由open转移到closed 3扩充节点n 将新节点加入到open中4修改某些节点的路径5open中节点按照升序排列值得重视的一点 A算法失败的唯一原因是open表为空 08 03 2020 47 思考题 图中 s是起始点t是目标节点 如果存在从s到t的一条最佳路径 而n是最佳路径上的一点 1 f s f n f t 的关系2 如果f s 10 g n 4问h n 08 03 2020 48 3 3 5A 算法 最佳图搜索算法 A 算法定义 对于算法A 如果有h n h n 即h n 以h n 为上界 则称该算法称为A 算法 如果令h n 0 则满足h n h n 这就是分支界限算法和动态规划算法 再令g n d n d n 是节点深度 则f n d n A 算法就是宽度优先算法 宽度优先算法能找到最佳解 例 第二章中八数码问题令h n w n 不在位数字个数 08 03 2020 49 算法可采纳性 给定任意图 设存在从开始节点s到目标节点t的路径 如果算法能够结束在s到t的最佳路径上 则称该算法是可采纳的 A 是具有可采纳性 定理1对于有限图 如果从s到t存在路径 则A算法一定成功结束 08 03 2020 50 推论1 1因为A 算法是A算法的一个特例 所以在有限图上如果如果从s到t存在路径 则A 算法一定成功结束 定理2对于无限图 如果存在s到t路径 则A 算法一定成功结束 08 03 2020 51 推论2 1open表中任一满足f n f s 的节点n最终都将被A 选作扩展节点 定理3如果存在节点s到目标节点t路径 则A 算法一定能找到最佳解结束 推论3 1A 选来扩展的节点都有f n f s 08 03 2020 52 小结1如果存在节点s到目标节点t路径 则A 算法一定能找到最佳解结束 2open表中所有满足f n f s 的节点n最终都将被A 选作扩展节点 3A 选来扩展的节点都有f n f s 4f s 作为A 的一个衡量上限 08 03 2020 53 3 3 6h函数和A 算法的关系 本节重点来讨论h函数 即启发信息量 对A 算法搜索效率的影响总结 定义 给定两个A 算法A1和A2 都有f n1 g n1 h n1 f n2 g n2 h n2 如果对于所有非目标节点n 有h n1 h n2 则算法A2比算法A1有较多启发信息 讨论 启发信息与h函数值成正比 极端情况下 完全没有启发信息时h 0 则此时A 算法就是宽度优先算法 08 03 2020 54 定理 给定两个A 算法A1和A2如果A2的启发式信息比A1多 则在任何存在节点s到目标节点t的路径上 搜索结束时 由A2扩展的每一个节点必定被A1扩展 A1扩展的节点多 注意搜索空间小 不代表能够找到最佳解 08 03 2020 55 当h 0时 除最下面一层节点外 所有节点都进入closed表 求解路径如图红线所示 当考虑到h时 被扩充的节点只有s c j 解路径相同 08 03 2020 56 3 37h函数单调性限制 单调性限制的作用是 避免重复计算某些节点的f值 主要对连通图而言 以便减少搜索代价 单调性定义 给定一个启发函数h 如果对于所有节点ni和nj nj是ni的子节点 如果满足h ni h nj c ni nj h t 0 则称h满足单调性限制 上式可以写成h ni h nj c ni nj 可以理解为三角不等式 08 03 2020 57 定理5如果好h n 满足单调性限制条件 则A 算法扩展了节点n之后 就找到了到达节点n的最佳路径 即 如果A 选中节点n 在单调性限制条件下 有g n g n 08 03 2020 58 3 38A 算法示例 迷宫问题给定迷宫图如下 找出从入口到出口的最短路径 08 03 2020 59 解1 综合数据库定义状态集 x y 1 x y 4 其中 x y 表示任意节点的坐标所以问题表示为求解从 1 1 到 4 4 的最短路径 2规则集 定义4条移动规则 右移R1 if x y then x