人工智能与或图搜索.ppt

第四章与或图搜索 4 1问题归约法4 2与或图4 3与或图搜索4 4AO 算法4 5博弈树的搜索 4 1问题归约法 当问题复杂时 可把初始问题分解成若干简单的子问题 若子问题仍复杂 可再进一步分解 直到这些子问题的解可直接得到 这种问题的描述和求解方法 称为问题归约法 可直接解答的问题称为本原问题 它是不必证明的 自然成立的 归约法的问题表示可由下列三部分组成 1 一个初始问题的描述 2 一组把问题变成子问题的算子 3 一组本原问题的描述问题归约由问题出发 运用操作算子产生一些子问题 对子问题再运用操作算子产生子问题的一些子问题 一直进行到产生的子问题都为本原问题 则问题得解 由于一问题所产生的若干子问题内的关系是并列的 同时的 所以 用与或图便能表示问题归约的状态空间 即对问题归约的描述可以很方便地用一个与或图的结构来表示它 4 2与或图 与节点 一个归约算子能够把单个问题变为几个子问题组成的集合 这时只有当所有子问题都有解 该父辈节点才有解 这种关系称为 与 关系 对应的节点称为与节点 或节点 几个算子适用于同一个问题 从而产生不同的后继问题集合 这时只要有一个后继集合有解 则意味该父辈问题有解 此时关系是 或 关系 对应节点称为或节点 与节点由与运算连接 如图 a 中Q和R 并用一条弧线将相关的边连接起来 这种弧线及所相关的边被称为超弧 或节点由或运算连接 如图4 1 b 中Q和R 与或图是一种普遍图 这种图被称为超图 也就是说 超图是存在超弧的图 一超弧所相关的边数 K 被称为该超弧的度 实现的连接为K 连接 K 连接符 假设节点N被某个算子归约为一个包含K个子问题的替换集合 K 1 我们用一个叫做K 连接符的超弧线把它们和节点N连接起来 每个K 连接符从一个父节点指向一个含有K个后继节点的集合 并说N有一个外向连接符K 问题归约描述对应的结构就是一个与或图 原始问题描述对应于起始节点 或根节点 本原问题所对应的节点叫做叶节点 在某些特殊情况下 不出现任何与节点 所有超弧的度都为1 此时的图成了普通图 问题归约描述也就成为状态空间描述 从图4 2所示的与或图中 节点n0有两个连接符 1 连接符指向节点n1 2 连接符指向节点集合 n4 n5 对于节点n0来讲 n1可称为或节点 n4 n5可称为与节点 图4 2 与或图 4 3与或图搜索 在与或图上执行搜索的过程 其目的在于表明起始节点是有解的 也就是说 搜索不是去寻找目标节点 而是寻找一个解图 一个节点被称为是能解节点 SOLVED 其递归定义为 1 终节点是能解节点 直接与本原问题相关联 2 若非终节点有 或 子节点时 当且仅当其子节点至少有一个能解 该非终节点才能解 3 若非终节点有 与 子节点时 当且仅当其子节点均能解 该非终节点才能解 一个节点被称为是不能解节点 UNSOLVED 其递归定义为 1 没有后裔的非终节点是不能解的节点 2 若非终节点有 或 子节点时 当且仅当所有子节点均不能解时 该非终节点才不能解 3 若非终节点有 与 子节点时 当至少有一子节点不能解时 该非终节点才不能解 一个解图就是那些能解节点的子图 是包含一节点 n 到目的节点集合 N 的 连通的能解节点的子图 其定义如下 一个与或图G中 从节点n到节点集N的解图记为G G 是G的子图 1 若n是N的一个元素 则G 由单个节点n组成 2 若n有一个指向节点集 n1 nk 的外向连接符K 使得从每一个节点ni到N有一个解图 i 1 k 则G 由节点n 连接符K 以及 n1 nk 中的每一个节点到N的解图所组成 3 否则n到N不存在解图 如果n s为初始节点 则此解图即为所求解问题的解图 在对普通图的解路求解或搜索中 一般须计算或估计其路径代价 同样地 在搜索与或图解图的过程中 也需要进行耗散值的计算 设连接符的耗散值规定为 k 连接符的耗散值 k 若解图的耗散值记为k n N 则可递归计算如下 1 若n是N的一个元素 则k n N 0 2 若n有一个外向连接符指向后继节点集合 n1 ni 并设该连接符的耗散值为Cn 则k n N Cn k n1 N k ni N 具有最小耗散值的解图称为最佳解图 其值也用h n 标记 求解问题的解图的值为h s 解图的求法是 从节点n开始 正确选择一个外向连接符 如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止 图4 3给出了上图所示与或图中n0 n7 n8 的三个解图 解图的耗散值分别为8 7 5 图4 3 三个解图 与或图搜索与状态空间图搜索的不同 搜索目的是证明起始节点是否可解 而可解节点是递归定义的 取决于后继节点是否可解 即搜索是否找到可解的叶节点 因此 搜索有可解标示过程和不可解标示过程 初始节点被标示为可解 则搜索成功结束 初始节点被标示为不可解 则搜索失败 一旦发现不可解节点 应把该节点从图中删去 4 4AO 算法 假设 估价函数q n h n G为当前扩展生成的与或图 G 为一后选局部解图 是G的一个子图 h n 是节点n的启发函数 而q n 是节点n的估价函数 是从节点n到一组终叶节点的一个最优解图的一个代价估计 过程AO 1 建立一个搜索图G G s 计算q s h s IFGOAL s THENM s SOLVED 开始时图G只包括s 耗散值估计为h s 若s是终节点 则标记上能解 2 Untils已标记为SOLVED do 3 Begin4 G FIND G 根据连接符标记 指针 找出一个待扩展的局部解图G G的连接符将在第11步中标记 5 n G 中的任一非终节点 选一个非终节点作为当前节点 6 EXPAND n 生成子节点集 ni G ADD ni G 计算q ni h ni 如果ni G IFGOAL ni THENM ni SOLVED 对G中原未出现的n的子节点添加到G中 并计算其耗散值 若n的子节点为终节点则加能解标记 7 S n 建立含n的单一节点集合S 待修正的节点集合 8 UntilS为空 do 9 begin10 REMOVE m S 当mc S 从集合S中移出一节点m 要求这个m在图G中的子节点mc 不出现在S中 从底层开始修正 11 根据下面方法修改m的耗散值q m 对m指向节点集 n1i n2i nki 的每一个连接符i分别计算qi qi m Ci q n1i q nki q m minqi m 对m的i个k 连接符 取计算结果最小的那个连接符的耗散值为节点m的q m 加指针到minqi m 的连接符上 或把指针修改到minqi m 的连接符上 即原来指针与新确定的不一致时应删去 IFM nji SOLVED THENM m SOLVED j 1 2 k 若该连接符的所有子节点都是能解的 则m也标上能解 12 IFM m SOLVED q m q0 m THENADD ma S m能解或修正的耗散值与原先估算q0不同 则把m的所有先辈节点ma 添加到S中 修正向上传递 13 end14 end AO 搜索算法可以理解为两个主要过程的重复 首先 是一个自上而下的图生长过程 4 6步 先通过有标记的连接符 找到目前为止最好的一个局部解图 然后对其中一个非终节点进行扩展 并对其后继节点赋估计耗散值和加能解标记 第2过程是一个自下而上的估价函数值的修正 连接符的标记和SOLVED的标注过程 耗散值的修正从刚被扩展的节点n开始 其修正耗散值q n 取对h n 的所有估计值中最小的一个 然后根据耗散值递归计算公式逐级向上修正其先辈节点的耗散值 只有下层节点耗散值修正后 才可能影响到上一层节点的耗散值 因此必须自底向上一直修正到初始节点 假设各节点的启发函数值分别为 h n0 3 h n1 2 h n2 4 h n3 4 h n4 1 h n5 1 h n6 2 h n7 h n8 0 目标节点 k 连接符的耗散值 k 应用AO 算法 经过四个循环 可找到解图 在第一次循环中 扩展节点n0 下一次循环扩展节点n1 接着扩展节点n5 最后扩展节点n4 在节点n4被扩展之后 节点n0便被标注SOLVED 此时 通过向下跟踪有标记的连接符 便获得了此状态空间的解图 图4 4 AO 搜索过程每个节点旁边标记的是启发函数h n 值 不带括号 或估价函数q n 的修正值 带括号 短箭头用来标记连接符 标明侯选局部解图 已经标注SOLVED的节点用实心圆来表示 4 5博弈树的搜索 博弈一直是启发式搜索的一个重要应用领域 早在20世纪60年代就已经出现若干个博弈系统 美国IBM公司的 深蓝 系统已达到了国际特级大师级的水平 97年胜了卡斯帕罗夫 2001年 德国的 更弗里茨 软件击败了世界排名10位中的9位 本节所指博弈问题是指二人完备博弈 1 由二人对垒 二人严格地轮流走步 自己的走步自己选择 2 任何一方都完全知道对方过去的走步情况和今后可能的走步 不包括碰运气的情况 由于在决定自己走步时只需考虑对自己有利的一步 或 而考察对方时 则应考虑对方所有可能的走步 与 因此 能够利用与或图搜索算法来解决博弈问题 另外 由于两人严格地轮流走步 使博弈状态图呈现出严格的与或图的交替层次 所以 可设计特殊的与或图搜索算法 博弈树搜索算法 使搜索更有效 4 5 1Grundy博弈 例 假设桌上放有一堆 7个 钱币 由两人轮流进行分堆 要求每人每次只把其中某堆钱币分成数目不相等的两小堆 最后不能分下去的人为负 该问题的描述 综合数据库 用无序数字序列x1 x2 xn表示n堆钱币不同的个数 再用两个说明符号MIN方和MAX方代表选手 无序数列和符号M组合 x1 x2 xn M 就代表该由某个选手走步的状态 MAX方代表努力赢的一方 或尽力将其赢的几率最大化的一方 而MIN方代表力图使MAX方偏离取胜目标的另一方 博弈双方总是偏向最有利于自己的状态前进 反过来说 也就是MIN方和MAX方总是移向最不利于对方的状态 规则 图4 5 Grundy博弈问题状态空间图 设初始状态为 7 MIN 则该问题的状态空间图如图4 5所示 图中所有终节点均表示要走步的选手必输的情况 取胜方的目标是设法使棋局发展为结束在对方走步时的终节点上 因此节点A是MAX的搜索目标 而节点B C则为MIN的搜索目标 搜索策略要考虑的问题是 以MAX方的角度 对MIN走步后的每一个MAX节点 该状态由MIN控制 必须证明MAX对MIN所有可能走的每一个棋局对弈后都能够获胜 即MAX必须考虑应付MIN的所有招法 这是一个与的含义 因此含有MAX符号的节点可看成与节点 对MAX走步后的每一个MIN节点 该状态由MAX控制 只需要证明MAX有一步能走赢就可以 即MAX只要考虑能走出一步棋使MIN无法招架就成 因此含有MIN符号的节点可看成或节点 于是对弈过程的搜索图就呈现出与或图表示的形式 从搜索图可以看出 MAX方存在完全取胜的策略 图中所示部分就代表了这种策略 这时不论MIN怎么走 MAX方均可取胜 因而寻找MAX的取胜的策略便和求与或图的解图 能解 能胜 一致起来 即MAX要获胜 必须对所有与节点取胜 但只需对一个或节点取胜 这就是一个解图 因此实现一种取胜的策略就是搜索一个解图的问题 解图就代表一种完整的博弈策略 4 5 2博弈树的极大极小搜索法 极大极小搜索法是考虑双方对弈若干步之后 从可能的走步中选一步相对好的走步来走 即在有限的搜索深度范围内进行求解 这需定义一个评价函数f 以便对棋局的势态 节点 作出优劣估值 一般规定有利于MAX的势态 f n 取正值 有利于MIN的势态 f n 取负值 势均力敌 f n 0 若f n 表示MAX方获胜 若f n 表示MIN方获胜 假定开始由MAX选择走一步棋 如何选择一步好棋 首先 对给定的格局MAX给出可能的走法 然后MIN对MAX的每一步走法 又给出可能的走法 这样进行若干次 一定深度 得到一组端节点 每个端节点有相应的静态函数值 然后由底向上逐级计算倒推估值 在MIN处取其下层估值中最小者 在MAX处取其下层估值最大者 一直到MAX的开始棋局 取其下层估值中最大的格局作为要走的第一步 图4 6是一个表示考虑两步棋的例子 图中端节点的数字是用静态函数f n 计算得到 其他节点应用倒推的方法取值 图中A B C是MIN方要走步的节点 MAX方应考虑其最坏的情况 故其估值应分别取其子节点估值中最小者 而s是MAX走步的节点 可考虑最好的情况 故其估值应取A B C值中最大者 这样 确定了f s 2 也就是说 相对较优的走步是走向B 因为从B出发 对手不可能产生比f s 2更差的效果 当用端节点的静态估计函数值求倒推值时 两位选手应采用不同的策略 从下往上逐层交替使用极大和极小的选值方法 故称为极大极小过程 图4 6 f n 求值过程 下面说明极大极小过程MINLMAX 思维过程 1 T s MAX OPEN s CLOSED 开始时树由初始节点构成 OPEN表只含有S 2 LOOP1 IFOPEN THENGOLOOP2 3 n FIRST OPEN REMOVE n OPEN ADD n CLOSED 将n放到CLOSED表的前面 使第5步操作时深度大的节点优先被取出 OPEN表先进先出 CLOSED表后进先出 4 IFn可直接判定为赢 输或平局THENf n 0 GOLOOP1ELSEEXPAND n ni ADD ni T IFd ni kTHENADD ni OPEN GOLOOP1ELSE计算f ni ni达到深度k 计算各端节点f值 5 LOOP2 IFCLOSED NIL THENGOLOOP3ELSEnd FIRST CLOSED 6 IF nd MAX f nci MIN 有值 THENf nd max f nci REMOVE nd CLOSED GOLOOP2 若MAX所有子节点均有值 则该MAX取其极大值 ELSEIF nd MIN f nci MAX 有值 THENf nd min f nci REMOVE nd CLOSED GOLOOP2 若MIN所有子节点均有值 则该MIN取其极小值 7 ELSEGOLOOP1 若有子节点的值待确定 进入其它分支继续进行节点的扩展 8 LOOP3 IFf s NILTHENEXIT END M Move T s有值 或则结束或标记走步 例 在九宫格棋盘上 甲乙 MAX和MIN 二人轮流在空格中放入自己的棋子 一次一枚 谁先使自己的三子成一线就获胜 设甲先走用 表示 乙用 表示 p表示某种格局 f p 表示对格局的评价值 为便于讨论 将棋盘的整行 整列或整条对角线称为赢线 如果一条赢线上只有 方的棋子或为空 而没有对方的棋子 那么这条赢线就称为 方的赢线 f p 定义如下 1 MAX胜 f p 2 MIN胜 f p 3 若p不是可定胜负的格局 则f p fMAX p fMIN p 其中 fMAX p 表示当前棋局所有空格都放上MAX的棋子后 MAX的三个棋子成线的总数 同理 fMIN p 表示当前棋局所有空格都放上MIN的棋子后 MIN的三个棋子成线的总数 设考虑走两步的搜索过程 利用棋盘对称性的条件 则第一次调用算法产生的搜索树如图4 7所示 图中端节点下面是计算的f p 值 非端节点的倒推值标记在圆圈内 为了使初始节点具有最大的倒推值 可以看出第1步的最好走法是把棋子下到中央位置 图4 7 一字棋第1阶段的搜索树 设MAX走完第一步后 MAX的对手是在 上的格子下子 这时MAX就要在新的格局下调用算法 第2次产生的搜索树如图4 8所示 图4 8 一字棋第2阶段的搜索树 类似地第3次的搜索树如图4 9所示 至此MAX走完最好的走步后 不论MIN怎么走 都无法挽回败局 因此只好认输了 否则还要进行下面的搜索 图4 9 一字棋第3阶段的搜索树 4 5 3 搜索过程 在极大极小过程中 把生成树和棋局估值两个过程完全分离 即先生成全部的搜索树 然后再进行端节点静态估值和倒推值计算 这使效率大大降低 如图4 9中 其中一个MIN节点要全部生成A B C D四个节点 然后还要逐个计算其静态估值 最后在求倒推值阶段 才赋给这个MIN节点的倒推值 若两个过程同时进行 再根据一定的条件判断 有可能尽早剪掉一些无用的分支 那么就可能减少搜索工作量 这是 搜索过程的基本思想 如 生成节点A后 马上进行静态估值 得知f A 后 就可以断定再生成其余节点及进行静态计算是多余的 可以马上对MIN节点赋倒推值 丝毫不会影响MAX的最好优先走步的选择 为了使生成和估值过程紧密结合 采用有界深度优先策略进行搜索 这样当生成达到规定深度的节点时 就立即计算其静态估值函数 而一旦某个非端节点有条件确定其倒推值时就立即计算赋值 图4 10 一字棋第1阶段 剪枝方法 从图4 10中标记的节点生成顺序号 也表示节点编号 看出 生成并计算完第6个节点后 第1个节点倒推值完全确定 可立即赋给倒推值 1 这时对初始节点来说 虽然其他子节点尚未生成 但由于S属极大值层 可以推断其倒推值不会小于 1 我们称极大值层的这个下界值为 即可以确定S的 1 这说明S实际的倒推值绝不会比 1更小 具体的取值还取决于其他后继节点的倒推值 因此继续生成搜索树 当第8个节点生成出来并计算得静态估值为 1后 就可以断定第7个节点的倒推值不可能大于 1 我们称极小值层的这个上界值为 即可确定节点7的 1 有了极小值层的 值 很容易发现若 时 节点7的其他子节点不必再生成 这不影响高一层极大值的选取 因S的极大值不可能比这个 值还小 再生成无疑是多余的 因此可以进行剪枝 于是 在搜索过程中通过记录并比较倒推值的上下界并进行比较 就可以实现修剪操作 称这种操作为 剪枝 类似的还有 剪枝 统称为 剪枝技术 在实际修剪中 还可以随时修正 但极大值层的倒推值下界值 永不下降 实际的倒推值取其后继节点最终确定的倒推值中最大的一个倒推值 而极小值层的倒推值上界值 永不上升 其倒推值取其后继节点最终确定的倒推值中最小的一个倒推值 总结上述叙述 在一个分支上进行 剪枝的规则描述如下 1 剪枝 若任一极小值层节点的 值小于或等于它任一先辈极大值层节点的 值 即 先辈层 后继层 则可以终止该极小值层中这个MIN节点以下的搜索 并设置这个MIN节点的最终的倒推值为 极小值层节点的剪枝 2 剪枝 若任一极大值层节点的 值大于或等于它任一先辈极小值层节点的 值 即 后继层 先辈层 则可以终止该极大值层中这个MAX节点以下的搜索过程 并设置这个MAX节点的最终倒推值为 极大值层节点的剪枝 过程 保存 和 值 并且当满足条件时便进行剪枝 当初始节点的全部后继节点的最终倒推值都给出时 过程即结束 而最好的优先走步就是走向具有最高倒推值的那个后继节点 显然剪枝后选得的最好优先走步 其结果与不剪枝的MAXMIN方法所得的完全相同 因而 过程具有较高的效率 比较是在极大值层节点和极小值层节点间进行的 比较时是与先辈层节点 已经有了值的那些节点 不仅限于父辈 只有一个节点的值固定以后 其值才能够向其父节点传递 剪枝搜索得到的最佳走步与极大极小方法得到的结果一致 但效率会提高 生成搜索图和剪枝过程同时进行 注意几个问题 图4 11给出了d 4的博弈树的 搜索过程 其中括号中的数字表示求静态估值及倒推值过程的次序编号 该图详细表示出 剪枝过程的若干细节 初始节点的最终倒推值是1 该值等于某一个端节点的静态估值 图4 11 搜索过程的博弈树 剪枝 剪枝 剪枝 剪枝