《人工智能-与或图搜索.ppt》由会员分享，可在线阅读，更多相关《人工智能-与或图搜索.ppt（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章 与或图搜索,1 问题归约法 2 与或图 3 与或图搜索 4 AO*算法 5 博弈树的搜索,问题: 在边长为 2 的正方形内，任意放置 5 个点，求证其中必存在两个点，它们之间的距离不大于2。 问题可转化为：在四个单位正方形内，任意放置5个点，至少有两个点在同一正方形内。,1 问题归约法,问题: 假定我们已经会求矩形的面积，现在要求如图所示的五边形的面积。 方法分析: 五边形的面积转化为矩形面积。,II,III,1,2,3,I,求解步骤：,求五边形面积,求 1面积,求 2面积,求 3面积,求 I面积,求 II面积,求 III面积,求面积,求面积,求面积,1,2,3,I,II,III,问题
2、归约法: 当问题复杂时，可把初始问题分解成若干简单的子问题，若子问题仍复杂，可再进一步分解，直到这些子问题的解可直接得到。这种问题的描述和求解方法，称为. 本原问题: 可直接解答的问题称为 ，它是不必证明的、自然成立的. 归约法的组成： 1）一个初始问题的描述； 2）一组把问题变成子问题的算子 (分解或转换)； 3）一组本原问题的描述 不同的算子对应不同的关系,从而使问题归约的描述可用一个与或图的结构来表示.,小结:,2 与或图,与节点：把单个问题分解为几个子问题来求解。只有当所有子问题都有解，该父辈节点才有解。表示一种 “与” 关系。 或节点：同一问题被转换为几种不同的后继问题。只要有一个后
3、继问题有解，则原问题有解。表示一种 “或” 关系。,与节点由与运算连接（超弧），如图（a）. 或节点由或运算连接，如图（b）.,定义：与或图就是包含与节点和或节点的图，即存在超弧的图，也称为超图. 超图与状态空间图有什么区别？ 与或图是一种更一般的图. 定义：一超弧所相关的边数（K）被称为该超弧的度，实现的连接称为K-连接. K连接符：从一个父节点指向一组含有K个后继节点的节点集.,在与或图中，节点 n0 有两个连接符：1-连接符指向节点 n1；2-连接符指向节点集合n4、n5； 对于节点 n0 来讲，n1 可称为或节点，n4、n5 可称为与节点。,与或图,3 与或图搜索,含义：在与或图上执行
4、搜索的过程，其目的在于标明起始节点是有解的，即，搜索不是去寻找到目标节点的一条路径，而是寻找一个解图。 定义：一个节点被称为能解节点，其递归定义为： 1终节点是能解节点（直接与本原问题相关联）； 2若非终节点 有 “或” 子节点时，当且仅当其子节点至少有一个能解 ，该非终节点才能解； 3若非终节点有 “与” 子节点时，当且仅当其子节点均能解，该非终节点才能解。,定义：不能解节点的递归定义为: 1没有后裔的非终节点是不能解的节点； 2若非终节点有 “或” 子节点时，当且仅当所有子节点均不能解时，该非终节点才不能解； 3若非终节点有 “与” 子节点时，当至少有一子节点不能解时，该非终节点才不能解.
5、,是由能解节点构成的一个子图，是包含一节点（n）到目的(终)节点集合（N）的、连通的能解节点的子图. 在一个与或图 G 中，从节点 n 到节点集 N 的解图记为 G， G 是 G 的子图. 1若 n 是N的一个元素，则G由单个节点n组成； 2若 n 有一个指向节点集 n1,nk 的外向连接符 K，使得从每一个节点 ni (i=1,k) 到 N 有一个解图 ，则 G由节点 n，连接符 K，以及 n1 ,nk中的每一个节点到 N 的解图所组成； 3否则 n 到 N 不存在解图. 如果 n=s 为初始节点，则解图为所求解问题的解图.,解图的定义：,若解图的耗散值记为 k(n, N)，则可递归计算如下
6、： 若 n 是 N 的一个元素，则 k(n, N)=0； 若 n 有一个外向连接符指向其后继节点集合n1,ni，并设该连接符的耗散值为 Cn（一般k-连接符的耗散值=k ），则 k(n, N)= Cn+ k(n1, N)+ k(ni, N) 具有最小耗散值的解图称为最佳解图，其值也用 h*(n) 标记。,解图耗散值的计算：,例：从节点 n 开始，正确选择一个外向连接符，一直进行下去直到产生的每一个后继节点成为集合N中的一个元素为止。下图给出了 n0 n7，n8的三个解图（耗散值分别为 8，7，5）.,解图的求法,与或图搜索与状态空间图搜索的区别：,搜索目的不同：是证明起始节点是否可解，而可解节
7、点是递归定义的，取决于后继节点是否可解，即搜索过程是能否找到可解的叶节点. 结果不同：若初始节点被标示为可解，则搜索成功结束；若初始节点被标示为不可解，则搜索失败. 节点处理不同：一旦发现不可解节点，应把该节点从图中删去.,4 与或图启发式搜索算法 AO*,假设：G；G；h(n)是从节点 n 到一组终叶节点的一个最优解图的一个代价估计，评价函数q(n)=h(n) AO*过程: 1.建立初始搜索图，G:=s，计算 q(s)=h(s)，IF GOAL(s) THEN M(s,SOLVED)； 2. Until s 已标记为 SOLVED, do: 3. Begin 4. G := FIND(G)；
8、根据连接符标记（指针）找出一个待扩展的侯选局部解图G（连接符在11步标记） 5. n := G 中的任一非终节点; 选一个当前节点 6. EXPAND(n),生成子节点集ni，如果 ni G， G:= ADD(ni,G),计算 q(ni)=h(ni)，IF GOAL(ni) THEN M(ni, SOLVED);,7 S:=n; 建立含 n 的节点集合S.（已扩展待修正） 8 Until S为空, do: 9 Begin (m为S中任一节点) 10 REMOVE(m, S),当 mcS;（mmc ,从底层开始修正） 11 修改 m 的耗散值 q(m): 对 m 指向节点集 (n1i，n2i,
9、nki) 的每一个连接符 i 分别计算qi, qi(m)=Ci+q(n1i)+q(nki), 并取 q(m):= min qi (m); 加(或修正)指针到 min qi (m) 的连接符上. IF M(nji, SOLVED) THEN M(m, SOLVED);（j=1，2，k）若该连接符的所有子节点都是能解的,则m也能解. 12 IF M(m, SOLVED) (q(m) q0(m) THEN ADD(ma, S); m 能解或修正的耗散值与原先估算q0不同,则把m的所有先辈节点ma添加到S中. （能解或修正向上传递） 13 end (与8匹配) 14 end (与2匹配),两个过程的重
10、复: 自上而下的图生长过程（4-6步）: 先通过有标记的连接符，找到目前为止最好的一个局部解图，然后对其中一个非终节点进行扩展，并对其后继节点赋估计耗散值和加能解标记. 自下而上的估价函数值的修正、连接符的标记和SOLVED的标注过程(7-12): 耗散值的修正从刚被扩展的节点n开始，其修正耗散值q(n)取所有估计值中最小的一个，然后根据耗散值递归计算公式逐级向上修正其先辈节点的耗散值.只有下层节点耗散值修正后，才可能影响到上一层节点的耗散值，如此一直修正到初始节点.,AO*搜索算法过程分析,例: 各节点启发值如图，k-连接符的耗散值= k, 求最佳解图. 应用 AO* 算法，经四个循环，可找
11、到解图. 在第一次循环扩展节点 n0；然后,依次扩展节点 n1、n5、n4。 在节点 n4 被扩展之后，节点 n0 便被标注SOLVED，此时，通过向下跟踪有标记的连接符，便获得了解图.,主要步骤 第4步(G) 第5步(n) 第6步 第7步(S) 第11步 第12步,AO*搜索算法的过程,第1循环 (n0) (n0) (n1,n5,n4) (n0) 比较,选n0n1; n1不可解; 无,第2循环 n0n1 (n1) (n2,n3) (n1) 1) 比较,选n1n3; n3不可解; 2)比较,选n0n5, n4; n5, n4不可解; 1) 加n0 S; 2)无;,第3循环 n0n5, n4 (
12、n5) (n6,n7,n8) (n5) 比较,选n5n7, n8; 改指针; n7, n8可解, n5可解 1)加n0 S; 2) 无;,第4循环 n0n5, n4; (n4) (n5,n8) (n4) 1)比较,选n4 n8; n8可解, n4可解; 2) n4 , n5可解; n0可解. 1)加n0 S; 2) 无;,n0,n1,n4,n5,2,1,1,3,4,4,6,5,4,2,0,0,2,5,n6,n3,n2,n7,n8,不带括号的数是启发函数h(n)值,带括号数是估价函数q（n）的修正值；短箭头用来标记连接符，标明侯选局部解图；已经标注SOLVED的节点用黑心圆来表示。,讨论,当节点
13、n无后继节点? 在第11步中对 m (n)赋一个高的 q 值(会传递到s), 从而排除了含有n的子图被当作候选局部解图的可能性. 在 G 中存在多个非终节点时,选择什么样的节点先扩展? 一般选择最能导致该局部解图耗散值发生较大变化的节点先进行扩展, 可促使及时修改局部解图的标记. 同A算法类似,若 sN 存在解图,当 h(n) h*(n)且h(n)满足单调限制条件时(对n到其子节点的每一连接符均需要满足),则 AO* 一定能找到最佳解图.,与A*算法的区别,评价函数只考虑 h(n): 理由: 算法有自下而上的修正费用的的操作, 实际上局部解图费用值的估计是在起始节点S 比较, 计算 g 既无必
14、要也不可能. 不能优先扩展具有最小费用的节点: 理由: K-连接符连接的有关子节点对父节点的可解性及费用值的估计都会产生影响. 仅适用于无环图,否则耗散值递归计算不收敛: 方法: 当新生成的节点已在图中时,判断是否为正被扩展节点的先辈节点. 控制策略不同: 没有 OPEN 表和 CLOSED 表, 只用生成的解图结构 G, h(n) 是最佳解图的费用估计.,5 博弈树的搜索,问题: 二人完备博弈： 1由二人对垒，轮流走步，自己的走步自己选择 2信息完备: 任何一方都完全知道对方过去的走步情况和今后可能的走步，不包括碰运气的情况 表示方法: 利用与或图表示来描述博弈问题. 理由: 由于在博弈中,
15、决定自己走步时只需考虑对自己有利的一步或，而考察对方时，则应考虑对方所有可能的走步与. 求解方法: 特殊的与或图搜索算法博弈树搜索. 理由: 由于两人严格地轮流走步，使博弈状态图呈现出严格的与或图的交替层次.,1) Grundy 博弈,例：假设桌上放有一堆（7个）钱币，由两人轮流进行分堆，要求每人每次只把其中某堆钱币分成数目不相等的两小堆，最后不能分下去的人被判负. 综合数据库： （x1，x2，xn，M）表示某个选手走步的状态. 其中, x1，x2，xn 表示 n 堆钱币不同的个数，M 代表选手( MIN 或 MAX ). 规则：,控制策略: 博弈双方总是偏向最有利于自己的状态前进，己方会尽力
16、将赢的几率最大化,而使对手方偏离取胜目标.,(5,1,1,MIN),(6,1,MAX),(5,2,MAX),(4,3,MAX),(3,2,2,MIN),(4,2,1,MIN),(7,MIN),(3,3,1,MIN),(4,1,1,1,MAX),(3,2,1,1,MAX),(2,2,2,1,MAX),(2,1,1,1,1,MAX),(3,1,1,1,1,MIN),(2,2,1,1,1,MIN),A,B,C,搜索策略分析（以MAX方的角度） 对 MAX 节点(MIN控制)， MAX 必须都能够获胜，即MAX必须考虑应付MIN的所有招法，故它为与节点. 对 MIN 节点(MAX控制)， MAX 只需
17、证明有一步能走赢就可以，即MAX只要考虑有一步棋使MIN无法招架就成，故它为或节点. 因此,对弈过程的搜索图就呈现出与或图表示的形式，从图可见，MAX方存在完全取胜的策略. 于是,寻找MAX方取胜的策略便和求与或图的解图(能解能胜)一致起来，即MAX要获胜，在各层必须对所有与节点取胜，但只需对一个或节点取胜.,2) 博弈树的极大极小搜索法,思想：预先考虑双方对弈若干步之后的局势，从当前侯选的走步中选一个相对好的走步来走，即在有限搜索深度范围内进行求解. 方法：定义一个评价函数 f，以便对棋局的势态（节点）作出优劣估值. 一般规定: 有利于 MAX(我) 的势态，f(n)取正值; 有利于 MIN
18、(敌) 的势态，f(n)取负值; 势均力敌，f(n):=0. 若 f(n):= ，表示MAX方获胜; 若 f(n):=-，表示MIN方获胜.,选步的过程:,假定开始由 MAX 选择走一步棋，如何选择一步好棋？ 首先，对给定的格局MAX给出可能的走法，接着, MIN对MAX的每一步走法，又给出可能的走法，这样进行若干次（规定深度），得到一组端节点.此时,计算每个端节点相应的静态函数值; 然后由底向上逐级计算倒推估值，在MIN处(与节点)取其下层估值中最小者，在MAX处(或节点)取其下层估值最大者。一直到MAX的开始棋局，取其下层估值中最大的格局作为要走的第一步.,当用端节点的静态估计函数值求倒推
19、值时，针对两位选手的控制力应采用不同的策略，从下往上逐层交替使用极大和极小的选值方法，故称为极大极小过程.,9,-6,0,0,-2,-4,-3,-6,-2,-4,-2,MAX取极大值,MIN取极小值,端节点,例. 向前看两步时f(n)的求值过程,极大极小过程 MIN-MAX： 1. T:=(s, MAX)，OPEN:=(s)，CLOSED:=( ); 开始时树由初始节点构成，OPEN表只含有s. 2. LOOP1: IF OPEN =( ) THEN GO LOOP2; 3. n:=FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED); 将n放到CLOSED表的前面
20、，使第5步操作时深度大的节点优先被取出.(OPEN表先进先出, CLOSED表后进先出) 4. IF n 可直接判定为赢, 输或平局 THEN f(n):= -0，GO LOOP1 ELSE EXPAND(n)ni， ADD (ni ，T) IF dni k THEN ADD(ni, OPEN) ,GO LOOP1 ELSE 计算 f(ni) GO LOOP1 ; ni达到深度k,计算端节点f值.,5. LOOP2：IF CLOSED=NIL,THEN GO LOOP3 ELSE nd=FIRST(CLOSED); 6.IF(nd MAX) (f(nci MIN)有值) THEN f(nd):
21、=maxf(nci),REMOVE(nd，CLOSED); 若MAX所有子节点均有值,则该MAX取其极大值. ELSE IF(nd MIN) (f(nci MAX)有值) THEN f(nd):=minf(nci),REMOVE(nd，CLOSED); 若MIN所有子节点均有值，则该MIN取其极小值. 7. GO LOOP2; 8. LOOP3:IF f(s)NIL THEN EXIT(END M(Move,T) ; s有值,或则结束或标记走步.,例：在九宫格棋盘上，甲乙（MAX和MIN）二人轮流在空格中放入自己的棋子（一次一枚），谁先使自己的三子成一线就获胜，设甲先走用（）表示，乙用（ ）表
22、示，p表示某种格局，f (p)表示对格局的评价值。 赢线定义: 将棋盘的整行、整列或整条对角线称为赢线。如,一条赢线上只有（或 ）方的棋子或为空，而没有对方的棋子，那么这条赢线就称为（或 ）方的赢线。 f (p)定义： 1）MAX胜，f (p)=+ 2）MIN胜，f (p)=- 3）若 p 不是可定胜负的格局，则 f (p) = fMAX(p) - fMIN(p),考虑走两步的搜索过程,并兼顾棋盘对称性条件 第一次调用算法产生的搜索树如下图所示，图中端节点下面是计算的f (p)值，非端节点的倒推值标记在圆圈内. 结论: 第1步的最好走法是把棋子下到中央位置. (为了使初始节点具有最大的倒推值)
23、,fMAX(p)=4,fMIN(p)=6,f (p)=4-6=-2,一字棋第1阶段的搜索树,一字棋第2阶段的搜索树,一字棋第3阶段的搜索树,3) -搜索过程,极大极小搜索缺陷: 把生成树和棋局估值两个过程完全分离，即先生成全部的搜索树，然后再进行端节点估值和倒推值计算，这导致效率降低. 例: 一个 MIN 节点要全部生成A、B、C、D 节点，然后逐个计算其静态估值，最后在求倒推值阶段，才赋给这个 MIN 节点的倒推值-. 如何改进?,改进思路: 若两个过程同时进行，再依一定的条件判断，有可能尽早剪掉一些无用的分支，那么就可能减少搜索量，这是-搜索的思想. 例：生成节点A后，马上进行静态估值，得
24、知f（A）=-后，便可断定再生成其余节点并进行估值计算是多余的，故可马上对MIN节点赋倒推值-，不会影响MAX的最好优先走步的选择. 实现方法: 采用有界深度优先策略进行搜索，这样当生成达到规定深度的节点时，就立即计算其静态估值函数，而一旦某个非端节点有条件确定其倒推值时就立即计算赋值.,一字棋第1阶段-剪枝方法,1-6f(1)=-1 初始S,f(S)=-1,此时该MAX层下界值=-1; 7-8 f(7)=-1,此时该MIN层上界值 =-1 ,节点7的其他子节点不必再生成，因S的极大值不可能比这个值还小，再生成是多余的，故可剪枝.,在搜索过程中,通过记录并比较倒推值的上、下界并进行比较，就可以
25、实现修剪操作，这种技术统称为-剪枝技术. 在实际修剪中，、的值可以随时修正，但满足如下条件： 极大值层的倒推值下界值永不下降，实际的倒推值取其后继节点最终确定的倒推值中最大的一个倒推值. 极小值层的倒推值上界值永不上升，其倒推值取其后继节点最终确定的倒推值中最小的一个倒推值.,在一个分支上进行-剪枝的判断规则： 剪枝：若任一极小值层节点的值小于或等于它任一先辈极大值层节点的值，即 （先辈层）（后继层），则可终止该MIN层中这个MIN节点以下的搜索，并设置这个MIN节点的最终的倒推值为.(位置：MIN层的剪枝) 剪枝：若任一极大值层节点的值大于或等于它任一先辈极小值层节点的值，即 （后继层）（先
26、辈层），则可终止该MAX层中这个MAX节点以下的搜索，并设置这个MAX节点的最终倒推值为.(位置：MAX层的剪枝),-过程：保存和值，且满足条件时便进行剪枝，当初始节点的全部后继节点的最终倒推值都给出时，过程即结束，而最好的优先走步就是走向具有最高倒推值的那个后继节点.,比较是在极大值层节点和极小值层节点间进行的(非直系). 比较时是与先辈层节点(已经有了值的那些节点),不仅限于父辈. 只有一个节点的值固定以后,其值才能够向其父节点传递. -剪枝搜索得到的最佳走步与极大极小方法得到的结果一致,但效率会提高. 生成搜索图和剪枝过程同时进行.,注意几个问题:,0,0,(2),(3),5,(4)=0
27、,(5) 0,(6),-3,(7) -3,(8) =0,(9) 0,(10),3,(11) =3,(12) 3,(13) =0,(14) 0,(15),5,(16) 5,(17),4,(18) 4,(19),1,(20) =1,(21) 1,(22),-3,(23) -3,(24) =1,(25) 1,(26),6,(27) 6,(28),8,(29) =6,(30) 6,(31) =1,(32) =1,最佳走步,MAX,MIN,-剪枝, -剪枝,-剪枝, -剪枝,d=4,括号中的数字表示次序,小结,博弈树搜索的目标：找到当前棋局的一步走法,所以剪枝搜索的结果是得到了一个最佳走步,而不是象一般
28、的图搜索或者与或图搜索那样,得到的是从初始节点到目标节点(集)的一条路径或者解图. -剪枝的效率问题：当搜索树深度为D,分枝因数为B时，端节点数Nd为： Nd =BD （不剪枝）； Nd=2BD/2-1 (剪枝，D为偶数); Nd=B(D+1)/2+B(D-1)/2-1(剪枝，D为奇数). 在同样资源限制下,使用剪枝技术可以向前考虑更多的走步数,这样选取当前的最好优先走步,将带来更大的取胜优势.,改进策略,等候状态平稳后中止搜索的方法：不严格限制搜索的深度，当到达深度限制时,如出现博弈格局有较大变化时(如出现兑子),则应多搜索几层,使格局进入较稳定状态后再中止,这样可使结果更合理. 增添辅助搜索的方法：当算法给出所选的走步后,不要马上停止搜索,而是在原先估计可能的路径上再往前试探搜索几步,再次检验会不会出现意外. 知识利用：对某些博弈的开局阶段和残局阶段,往往总结了一些固定的对弈模式,因此可以利用这些知识编好走步表,以便在开局和结局时使用查表法，加快算法运行，只是在进入中盘阶段后,再调用搜索算法,来选择最优的走步.,第四章 与或图搜索,理解能解节点的定义， 通过事例掌握AO* 搜索过程；了解博弈问题的产生式描述；掌握博弈树的极大极小、 -搜索过程. 思考习题: 1.P75页 2.5题. 2.P75页 2.6题.,