人工智能讲义AI02N..ppt

第二章 状态空间法及搜索 2 0引言 问题求解是个大课题 如求解智力测验难题 求证逻辑或数学定理 求解最短路径 求解能够取胜的博奕走步序列等 常用的求解方法是试探搜索法 即在可能的解答空间中寻找一个合理的解 例 八数码难题 283283283164141647576575 28316475 12384765 初始状态 目标状态 2 1状态空间法的基本概念和基本系统结构 1 基本概念状态与操作状态 表示问题求解过程中每一步问题状况的数据结构初始状态 由问题已知的前提 初始条件的原始描述所构成的状态目标状态 问题解决时应该到达的状态操作 算符 把一种状态变成另一种状态的运算 状态空间法状态空间 问题求解过程中由初始状态可能到达的所有状态的集合状态空间法 建立初始状态 在状态空间中进行搜索 以找到一条从初始状态到达目标状态的 最佳 路径 这条路径 即达到目标状态的操作步骤 就是问题的解 基本系统结构产生式系统的组成综合数据库 初始数据库 目标数据库 中间数据库产生式规则 IFATHENBA 条件B 操作 结果控制策略 选择可使用的规则和搜索算法等 控制策略产生式规则综合数据库产生式系统的组成 八数码难题综合数据库可用3X3的二维数组表示一个状态 棋局 初始数据库 283164705目标数据库 123804765产生式规则R1 IF空格上方有棋THEN空格上移 R2 IF空格右方有棋THEN空格右移R3 IF空格下方有棋THEN空格下移R4 IF空格左方有棋THEN空格左移旅行商问题A5721E3B2434D1C 综合数据库可用线性并列表 List 表示状态 表中放有旅行商经过的城市 表中最后一个元素就是旅行商当前所在的城市初始数据库 A 目标数据库 A A 产生式规则R1 IF没有去过BTHEN下一步去BR2 IF没有去过CTHEN下一步去CR3 IF没有去过DTHEN下一步去DR4 IF没有去过ETHEN下一步去ER5 IF都去过了THEN下一步去A 2 2状态空间的搜索策略 搜索过程概述用图来描述状态空间节点 对应于状态描述扩展节点 把适用于某个节点状态的产生式规则运用到该节点而产生其后继节点指针 从每个后继节点指向其父节点 状态空间的搜索 图搜索搜索过程 从起始节点开始扩展节点 设置指针并检查各后继节点是否为目标节点 如果没有找到目标节点 则继续进行扩展节点和设置指针的过程 当找到目标节点时 沿着有关指针可以从目标节点回朔到起始节点 产生一条解答路径 由于扩展节点的顺序不同 及搜索的顺序不同 形成了各种不同的搜索方法 爬山法 PP20 23 回溯法 习题1P42第2题2P42第3题3P43第6题 更正 图2 8 应为 图2 9 从 2M 2C 节点开始继续原图的搜索 贪心法贪心法与爬山法类似 也是一种不可撤回搜索法 算法思想 从起始节点出发 每一步都选从当前来看对达到目标最有利的操作 举例 A B E D C 5721 3 2 4 4 3 1 在旅行商的例子中 若在任何一个城市 总是选一个路程最短的未到过的城市先去 则为贪心法 这样得到的解为 A B E C D A 14 不可撤回搜索法效率较高 但不能保证找到 最佳 解 如上例的最佳解为 A C D E B A 10 图搜索的一般算法 GRAPHSEARCH 1 建立一个只含有起始节点S的搜索图G 图中每个节点有一个指向其父节点的指针 S的这一指针为一特殊值 如0 并把S放入未扩展节点表OPEN中 2 建立已扩展的节点表CLOSED 初始时该表为空 3 LOOP 若OPEN表为空 则失败退出 4 把OPEN表中的第一个节点移出 放入CLOSED表中 称其为n节点 5 若n为目标节点 则成功退出 问题的解是沿指针追踪G中从n到S的路径而得到的 图搜索算法举例 八数码难题初始状态 283目标状态 123164804705765 6 扩展节点n 生成不是n的祖先的那些后继节点的集合M 如果没有后继节点 则转LOOP 7 把那些不在G中的M的成员作为n的后继节点加入G 并设置一个通向n的指针 把它们加入OPEN表 对已在G中的M的成员 调整有关指针 8 按某种方式 重排OPEN表 9 转LOOP OPENCLOSEDn283164 705283283164164705705283283283283164104164164075765750705283283283283283104164164164164765750705075075283283283283283104164064164164765750175705075 OPENCLOSEDn283283283283283283164064164164104104750175705075765765283283283203283283283283164064014184140164164104750175765765765705075765283283203283283283283283283064014184140164164104164164175765765765705075765750750283283203283283283283283283064014184140160164164104164175765765765754705075765750 283164705 283164075 283104765 283164750 283064175 283014765 203184765 283140765 283160754 283164705 283164075 283104765 283164750 283064175 283014765 203184765 283140765 283160754 083264175 283604175 283714055 023184765 230184765 280143765 283145760 283106754 083214765 280163754 803264175 203684175 283640175 803214765 208143765 283145706 283016754 203186754 283156704 283674105 208163754 830264175 863204175 230684175 830214765 813204765 283704615 283714650 123804765 023684175 123784065 283714605 280643175 283645170 283674150 283674015 123084765 234180765 CLOSED 26OPEN 21 讨论OPEN表中节点的排序对算法的影响先进先出 宽度优先后进先出 深度优先启发函数 启发式搜索第七步搜索图的扩充与指针的调整 S 1 2 6 4 5 3 CLOSED表中的节点 OPEN表中的节点 每条弧的费用为1 要搜索到达目标节点的最少费用路径 搜索图的弧 搜索树的指针 指向父节点 注意 因为节点1的后继已在CLOSED表中 已扩展 所以调整指针时 不仅要调整自己的指针 还要调整其后裔的指针 节点4 5 若其自身的指针未调整 则不必考虑其后裔节点 对其在CLOSED表中的后裔 也要同样处理 此算法不仅生成一个搜索图G 而且也生成了一棵由指针联接起来的搜索树 搜索树能给出从起始节点到目标节点的唯一路径 问题的解 2 3启发式图搜索法 引言盲目搜索的缺点启发信息用于决定要扩展的下一个节点在扩展一个节点时 用于决定要生成哪一个或哪几个后继节点用于决定某些应该从搜索树中抛弃或修剪的节点 估价函数估价函数 用来估算节点处于最佳求解路径上的希望程度的函数有序搜索法 按估价函数值来排OPEN表顺序的图搜索算法单值有序搜索法只有一个估价函数 多值有序搜索法有n个估价函数第一类多值有序搜索 先按f1排序 f1相同时 再按f2排序 P31八数码难题之例 第二类多值有序搜索 每个估价函数fi有一定的前提条件pi pn true 对条件满足的估价函数按第一类多值有序搜索方法处理 第一类多值有序搜索的讨论当n 1时 就是普通的单值有序搜索 令n 2 f1为搜索的深度 f2为另一和问题有关的估价函数 则多值有序搜索变成优化的广度优先搜索 即在广度优先的前提下 在同一层深度中优先选择希望较大的节点 令n 2 f1为接近目标状态的程度估计 f2为接近最佳路径的程度估计 则可以在尽快到达目标的前提下求最佳可能的路径 令n 2 f1 depth m 为整除运算 f2为另一个估价函数 则为广义的优化广度优先算法 即按深度计算 以每m层为一个阶梯 搜索优先在低阶的阶梯内进行 在每一层阶梯内部 优先展开那些希望大的节点 每一层阶梯实验完毕后 再向高一层阶梯过渡 令n 3 f1为多空格的N数码难题中被移动棋子所在的行数 f2为被移动棋子所在列数的负数 f3为被移动棋子将要去的行数的负数 则搜索的规则为 1 优先移动行数小的棋子 2 对同一行棋子 优先移动列数大的 3 对相同行列的棋子 优先移动向行数大的方向走的棋子 第二类多值有序搜索的讨论当p1 p2 true时 退化为第一类多值有序搜索 令n 2 p1 freecell m f1 depth f2 depth 算法的意思是 当还有相当数量的存储空间 m 时 用广度优先搜索 一旦存储空间数量减少到某种限度以内 即采用深度优先搜索 令n 2 p1 pending m f1 depth f2 depth 当已生成而未处理完的节点数小于某个限度时 采用宽度优先搜索 一旦超过这个限度 即采用深度优先搜索 与上例的异同 令n 3 p1 all 对方士象全 p2 pair 对方有一对士或一对象 f1 a H b K f2 a b H K 2 f3 b H a K 其中H表示我方马的个数 K为我方炮的个数 a和b为常数 0 a b 此时算法表示处理中国象棋残局的一种原则 当对方士象都全时 主要根据我方炮的多少来判断局势优劣 对方有一对士或一对象时 我方马 炮的作用大体相等 对方士象都不成对时 则主要根据我方有几匹马来判断棋势 由以上例子可知 多值有序搜索算法可以在多种优化目标指导下利用多种启发信息 是非常灵活的 举例 八数码难题估价函数 f n d n w n 其中 d n 为n的深度w n 为不在位的棋子数应用规则的顺序 左 上 右 下 如起始节点283164705其f值为0 4 4 283164705 283 283 283164104164075765750 283 203 283014184140765765765 083 283 023 230214714184184765015765765 123084765 123 123804784765065 CLOSED 6OPEN 8 估价函数的重要性习题P43第11题 题中的BOUND为搜索深度的限制 参见P28迷宫问题 注意由状态图可看出 迷宫的结构与P28所示的不同 2 4A 算法 引言A 算法是N Nillson于1971年提出的一种有序搜索算法估价函数f 对任意节点n f n 是从起始节点S经过节点n到达目标节点的最小费用的估计 实际耗散值K ni nj 节点ni和nj之间最佳路径的实际耗散值g n K s n 起始节点s到节点n的最佳路径的实际耗散值h n min K n ti ti T T为从n所能到达的目标节点集合 从n到目标节点最佳路径的实际耗散值f n g n h n 起始节点s经过节点n到目标节点最佳路径的实际耗散值 性质f s h s n在最佳路经上 则f n g n h n f s f n f s A算法估价函数 f n g n h n 其中g n 是对g n 的估价 h n 是对h n 的估价 g n 通常选择为当前所找到的从初始节点S到节点n的 最佳 路径的耗散值 显然有g n g n A算法 采用估价函数f n 来排列OPEN表的GRAPHSEARCH算法 1 建立一个只含有起始节点S的搜索图G 图中每个节点有一个指向其父节点的指针 S的这一指针为一特殊值 如0 并把S放入未扩展节点表OPEN中 计算f S 2 建立已被扩展的节点表CLOSED 初始时表为空 3 LOOP 若OPEN表为空 则失败退出 4 把OPEN表中的第一个节点移出并放入CLOSED表中 称此节点为n节点 5 若n为目标节点 则成功退出 6 扩展节点n 对其每个后继子节点m a 计算f m b 若m不在G中 将其作为n的后继节点加入G 设置一个通向n的指针 并把它加入OPEN表 c 若m已在G中 则比较刚计算的f值与原先的f值 如新值较小 则以新值代替旧值 并调整有关指针 此时 若m在CLOSED表中 则把它移回OPEN表 7 按f值由小到大重排OPEN表 8 转LOOP A 算法f n g n h n 其中g n 同上 且对于每个节点n有 h n h n A 算法 采用具有上述性质的估价函数的A算法例 八数码难题f n d n w n 2 5A 算法的讨论 A 算法的可纳性可纳性 对任一个搜索图 如果从起始节点S到目标节点存在一条或一条以上的路径 搜索算法总是结束在一条从S到目标节点的最佳路径上 则称此搜索算法是可纳的 A 算法可纳性的证明 1 A 搜索结束前 已进入CLOSED表的节点的f值均满足f n f S 先证明 在最佳路径上的所有节点的f n f S 设n在最佳路径上有f n g n h n f S 且g n g n 又h n h n f n g n h n g n h n f S 在搜索结束前的任何时候 OPEN表中至少有一个节点在最佳路径上我们对所扩展的节点数m用数学归纳法证 i m 0时 OPEN表中只有S 显然在最佳路径上ii 设在m k时 OPEN表中至少有一个节点在最佳路径上 则当扩展第k 1个节点后 a若所扩展的节点不在最佳路径上 显然OPEN表中仍然有处在最佳路径上的节点 b若所扩展的节点在最佳路径上 则其后继节点至少有一个是在最佳路径上 设该节点为n 若n既不在OPEN表也不在CLOSED表中 则应将n加入OPEN表 若n已在OPEN表中 则在调整其指针和重新计算f之后 仍将其保留在OPEN表中 283164705 283 283 283164104164075765750 283 203 283014184140765765765 083 283 023 230214714184184765015765765 123084765 123 123804784765065 n n 若n已在CLOSED表中 则在调整其指针后重新将其放入OPEN表中由I ii 可知 结论 成立 由于每次扩展的节点都是OPEN表中f值最小的节点 而OPEN表中总有f值小于等于f S 的处在最佳路径上的节点 故所扩展的节点的f n f S 2 当目标节点t排在OPEN表的第一位时 在最佳路径上的其他所有节点均已进入CLOSED表 反证法 设目标节点t在OPEN表中 它的父节点是n 且n 不在最佳路径上 t也不在 此时 f t g n K n t g n K n t 由于n 不在最佳路径上 g n K n t f S 故f t f S 由 1 的证明可知OPEN表中总有处在最佳路径上的节点n而f n f S 故n一定排在t之前 可见 只有当最佳路径上的所有中间节点均被扩展后 处于最佳路径上的目标节点才可能排在OPEN表的第一位 3 由上可知 当目标节点进入CLOSED表时 它一定处在最佳路径上 且该路径上的所有节点均已在CLOSED表中 只要追踪指针 就可以得到问题的最优解 h函数的启发能力设A1和A2是求解同一个问题的采用不同h函数的两个A 算法 其估价函数分别为f1 n g1 n h1 n f2 n g2 n h2 n 其中h1和h2都是h 的下界 如果对所有非目标节点n都有h2 n h1 n 则在搜索终止时 A1扩展的节点数不会比A2少证明 我们对搜索树中扩展节点的深度采用数学归纳法进行证明 1 深度为0时 当前节点n S 若S为目标节点 两个算法都不必扩展任何节点 否则 两个算法都要扩展S 故深度为0时 结论成立 2 设A1扩展了A2搜索树中所扩展的深度小于等于k的所有节点 若A2扩展深度为k 1的任一节点n 由归纳假设 A2搜索树中n的父节点 深度为K 也会由A1扩展 故节点n也必在A1的搜索树中 且g1 n g2 n 若A1不能扩展n 则在A1终止时 n必在其OPEN表中 而A1没有扩展n 说明 f1 n f S 即g1 n h1 n f S 我们已经知道g1 n g2 n 且h1 n g1 n h1 n f S 但A2扩展了节点n 说明f2 n f S 矛盾 故A1也一定会扩展节点n 例如 在八数码难题中 令p n 为不在位的牌与其目标位置的距离之和 而f n d n p n 283164705 283 283 283164104164075765750 283 203 283014184140765765765 023 230184184765765 123084765 123 123804784765065 p n w n CLOSED 5OPEN 7 以上结论说明h值越大 启发功能越强 搜索效率越高 特别地 1 h n h n 此时f n g n h n f S 而只有在最佳路径上的节点才有f n f S 故搜索仅沿最佳路径进行 效率最高 2 h n 0无启发信息 盲目搜索 效率低 3 h n h n 是一般的A算法 效率高 但不能保证找到最佳路径 有时为求解难题取h n h n 以提高效率 思考题 八数码难题的初始状态和目标状态分别为 216048753 123804765 取h n P n 3S n 其中P n 是每只棋子离开其应在位置的距离的总和 S n 是每只棋子排列顺序的计分值的总和 计分方法是中心方格上的棋子计1分 非中心方格中的棋子如其后面跟的棋子和目标顺序不同则计2分 若相同则计0分 试比较使用这样的h函数的A算法和用h n W n 的A 算法解此题的效率 g函数的作用如我们只考虑找到目标节点所需的剩余工作量 是否可以不要把g函数包括在f中 如八数码难题取f n w n 当h函数不是一个理想的估计时 搜索过程可能会误入歧途 不断向纵深发展 而总不能达到目标 g函数使搜索增加了一个宽度优先分量 因而确保了隐含图中没有那一部分会永远搜索不到 h的单调限制调整指针的代价h的单调限制如果对所有节点ni及其后继节点nj 有0 h ni h nj K ni nj 且h t 0其中K ni nj 表示ni到nj弧线上标记的实际耗散值 t为目标节点 则称h函数满足单调限制 满足单调限制的h函数必取h 的下界 习题P44第13题在P34图2 19的旅行商问题中 设h n 目标状态表的元素总数 现行状态表的元素数 X7 f1 n g n h n f2 n d n 请画出第一类多值有序算法的搜索图 思考题在h函数启发能力的讨论中 能否证明若h2 n 大于等于h1 n A1扩展的节点数不会比A2少 试用数学归纳法证明满足单调限制的h函数必取h 的下界 H满足单调限制 则在任一搜索路径上 h函数单调下降 f函数单调上升 P38 h满足单调限制 所有已扩展的节点必处在从S到该节点的最佳路径上 证明 设n是当前要扩展的任一节点 对从S到n的最佳路径的长度l进行归纳 1 l 0时 n S 显然n已在 从S到n的 最佳路径上 2 设l k时 结论成立 在l k 1时 令从S到n的最佳路径为S n0 n1 nk nk 1 n 且该序列中已扩展的最后一个节点为ni n 由归纳假设n0 ni均已扩展 即ni 1在OPEN表中 且已处在最 佳路径上 i k 即当前要扩展的节点nk 1 n已在最佳路径上 若ig n h n 于是 f ni 1 f n 而当前要扩展的节点是n 应有f n f ni 1 矛盾 2 6B算法 举例 设所搜索的状态空间如图所示 n0 n5 n1 n2 n4 n3 11961 32 3 1 1 4 1 6 0 0 4 8 16 36 其中n5为起始节点 n0为目标节点 任意两节点间的实际耗散值为 2 i 2 2 j 1 i j1 j i 52 5i 1 j 0 K ni nj h函数 00 i 1h ni 2 I1 i 52 5 4i 5 n5n4n3n2n1n036 3617141311 36171413114336171413104336171413104236171411942361714119413617141184136171411840 n5n4n3n2n1n0361710974036171097393617109639361710963836171075383617107537361710743736171074363617107436 B算法设置一个动态的全局变量F 其值为至目前为止所搜索到的节点的最大f值 在GRAPHSEARCH第8步排OPEN表时 对节点n 若f n F 则按f值排序 若f n F 则令f n g n 再按新的f值排序 总共扩展节点次数 红变白 2 0 2 0 2 1 2 2 2