人工智能与或图搜索

ArtificialIntelligence4.1问题归约法•当问题复杂时，可把初始问题分解成若干简单的子问题，若子问题仍复杂，可再进一步分解，直到这些子问题的解可直接得到。这种问题的描述和求解方法，称为问题归约法。•可直接解答的问题称为本原问题，它是不必证明的、自然成立的。•归约法的问题表示可由下列三部分组成：–1）一个初始问题的描述；–2）一组把问题变成子问题的算子；–3）一组本原问题的描述•问题归约由问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的一些子问题，……，一直进行到产生的子问题都为本原问题，则问题得解。由于一问题所产生的若干子问题内的关系是并列的、同时的，所以，用与或图便能表示问题归约的状态空间。即对问题归约的描述可以很方便地用一个与或图的结构来表示它。ArtificialIntelligence4.2与或图•与节点：一个归约算子能够把单个问题变为几个子问题组成的集合，这时只有当所有子问题都有解，该父辈节点才有解。这种关系称为“与”关系，对应的节点称为与节点。•或节点：几个算子适用于同一个问题，从而产生不同的后继问题集合。这时只要有一个后继集合有解，则意味该父辈问题有解，此时关系是“或”关系，对应节点称为或节点。(a)PRQ(b)PRQ•与节点由与运算连接，如图（a）中Q和R，并用一条弧线将相关的边连接起来，这种弧线及所相关的边被称为超弧。•或节点由或运算连接，如图4-1（b）中Q和R。ArtificialIntelligence•与或图是一种普遍图，这种图被称为超图。也就是说，超图是存在超弧的图。一超弧所相关的边数（K）被称为该超弧的度，实现的连接为K-连接。•K—连接符：假设节点N被某个算子归约为一个包含K个子问题的替换集合，K1，我们用一个叫做K—连接符的超弧线把它们和节点N连接起来。每个K—连接符从一个父节点指向一个含有K个后继节点的集合，并说N有一个外向连接符K。•问题归约描述对应的结构就是一个与或图，原始问题描述对应于起始节点（或根节点），本原问题所对应的节点叫做叶节点。在某些特殊情况下，不出现任何与节点（所有超弧的度都为1），此时的图成了普通图，问题归约描述也就成为状态空间描述。ArtificialIntelligence•从图4-2所示的与或图中，节点n0有两个连接符：1-连接符指向节点n1；2-连接符指向节点集合{n4、n5}；对于节点n0来讲，n1可称为或节点，n4、n5可称为与节点。n0n4n1n3n2n5n6n8n7图4-2、与或图ArtificialIntelligence4.3与或图搜索•在与或图上执行搜索的过程，其目的在于表明起始节点是有解的，也就是说，搜索不是去寻找目标节点，而是寻找一个解图。•一个节点被称为是能解节点(SOLVED)，其递归定义为：–1．终节点是能解节点（直接与本原问题相关联）；–2．若非终节点有“或”子节点时，当且仅当其子节点至少有一个能解，该非终节点才能解；–3．若非终节点有“与”子节点时，当且仅当其子节点均能解，该非终节点才能解。•一个节点被称为是不能解节点(UNSOLVED)，其递归定义为:–1．没有后裔的非终节点是不能解的节点；–2．若非终节点有“或”子节点时，当且仅当所有子节点均不能解时，该非终节点才不能解；–3．若非终节点有“与”子节点时，当至少有一子节点不能解时，该非终节点才不能解。ArtificialIntelligence•一个解图就是那些能解节点的子图，是包含一节点（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不存在解图。ArtificialIntelligence•如果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)。ArtificialIntelligence•解图的求法是：从节点n开始，正确选择一个外向连接符，如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止。图4-3给出了上图所示与或图中n0{n7，n8}的三个解图（解图的耗散值分别为8，7，5）。n0n1n3n5n6n8n7n4n5n8n7n4n5n8n7871222226100n072200231n052200211图4-3、三个解图ArtificialIntelligence与或图搜索与状态空间图搜索的不同：•搜索目的是证明起始节点是否可解，而可解节点是递归定义的，取决于后继节点是否可解，即搜索是否找到可解的叶节点。因此，搜索有可解标示过程和不可解标示过程。•初始节点被标示为可解，则搜索成功结束，初始节点被标示为不可解，则搜索失败。•一旦发现不可解节点，应把该节点从图中删去。ArtificialIntelligence4.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的子节点为终节点则加能解标记。ArtificialIntelligence7、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、endArtificialIntelligence•AO*搜索算法可以理解为两个主要过程的重复。首先，是一个自上而下的图生长过程（4-6步），先通过有标记的连接符，找到目前为止最好的一个局部解图，然后对其中一个非终节点进行扩展，并对其后继节点赋估计耗散值和加能解标记。•第2过程是一个自下而上的估价函数值的修正、连接符的标记和SOLVED的标注过程。•耗散值的修正从刚被扩展的节点n开始，其修正耗散值q(n)取对h*(n)的所有估计值中最小的一个，然后根据耗散值递归计算公式逐级向上修正其先辈节点的耗散值，只有下层节点耗散值修正后，才可能影响到上一层节点的耗散值，因此必须自底向上一直修正到初始节点。ArtificialIntelligencen0n4n1n3n2n5n6n8n7h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n8)=0h(n7)=0假设各节点的启发函数值分别为：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，此时，通过向下跟踪有标记的连接符，便获得了此状态空间的解图。ArtificialIntelligencen0n4n1n3n2n5n6n8n7n0n1(3)211n5n4n0n1(4)(5)11n5n444n3n2n0n4n1n3n2n5n6n8n7(5)(5)441200(2)(5)(5)44002(2)(1)一次循环后二次循环后三次循环后四次循环后图4.4、AO*搜索过程每个节点旁边标记的是启发函数h(n)值（不带括号）或估价函数q（n）的修正值（带括号）；短箭头用来标记连接符，标明侯选局部解图；已经标注SOLVED的节点用实心圆来表示。ArtificialIntelligence4.5博弈树的搜索•博弈一直是启发式搜索的一个重要应用领域，早在20世纪60年代就已经出现若干个博弈系统，美国IBM公司的“深蓝”系统已达到了国际特级大师级的水平（97年胜了卡斯帕罗夫）。2001年，德国的“更弗里茨”软件击败了世界排名10位中的9位。本节所指博弈问题是指二人完备博弈：–1．由二人对垒，二人严格地轮流走步，自己的走步自己选择，–2．任何一方都完全知道对方过去的走步情况和今后可能的走步，不包括碰运气的情况。•由于在决定自己走步时只需考虑对自己有利的一步——或，而考察对方时，则应考虑对方所有可能的走步——与，因此，能够利用与或图搜索算法来解决博弈问题。另外，由于两人严格地轮流走步，使博弈状态图呈现出严格的与或图的交替层次，所以，可设计特殊的与或图搜索算法——博弈树搜索算法，使搜索更有效。ArtificialIntelligence4.5.1Grundy博弈•例：假设桌上放有一堆（7个）钱币，由两人轮流进行分堆，要求每人每次只把其中某堆钱币分成数目不相等的两小堆，最后不能分下去的人为负。•该问题的描述：–综合数据库：用无序数字序列x1，x2，…，xn表示n堆钱币不同的个数，再用两个说明符号MIN方和MAX方代表选手，无序数列和符号M组合（x1，x2，…，xn，M）就代表该由某个选手走步的状态。MAX方代表努力赢的一方，或尽力将其赢的几率最大化的一方；而MIN方代表力图使MAX方偏离取胜目标的另一方。博弈双方总是偏向最有利于自己的状态前进，反过来说，也就是MIN方和MAX方总是移向最不利于对方的状态。–规则：),,,,,,,,(),(),,,(1111MxxzyxxthenzyzyxMxxifniiinArtificialIntelligence图4-5、Grundy博弈问题状态空间图设初始状态为（7，MIN），则该问题的状态空间图