人工智能 第四章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 与或图搜索,4.1问题归约法,当问题复杂时，可把初始问题分解成若干简单的子问题，若子问题仍复杂，可再进一步分解，直到这些子问题的解可直接得到。这种问题的描述和求解方法，称为问题归约法。,可直接解答的问题称为本原问题。,归约法的问题表示可由下列三部分组成：,1）一个初始问题的描述,2）一组把问题变成子问题的算符,3）一组本原问题的描述,4.2 与或图,对问题归约的描述可以很方便地用一个与或图的结构来表示它。,与节点：,一个归约算符能够把单个问题变为几个子问题组成的集合，这时所有子问题都有解，该父辈节点才有解。这种关系称为“与”关系，对应的节点成为与节点。,或节点：,几个算符适用于同一个问题，从而产生不同的后继问题集合。这时只要有一个后继集合有解，则意味该父辈问题有解，此时关系是“或”关系，对应节点为或节点。,在图4.1中,N，M，H,是或节点，,B，C，D，E，F,分别是与节点。,A,N M H,B C D E F,图4.1 与节点和或节点,与或节点是针对与或树而言，对于一般的与或图有歧义,n,0,n,1,n,2,n,4,n,3,n,5,n,6,n,8,n,7,图4.2 与或图,K,连接符：,假设节点,N,被某个算符归约为一个包含,K,个子问题的替换集合，,K,1，,我们用一个叫做,K,连接符的超弧线把它们和节点,N,连接起来。每个,K,连接符从一个父节点指向一个含有,K,个后继节点的集合，并说,N,有一个外向连接符,K。,这种图称为超图，但我们仍把这种结构叫与或图。,问题归约描述对应的结构就是一个与或图，原始问题描述对应于起始节点（或根节点），本原问题所对应的节点叫做叶节点。在某些特殊情况下，不出现任何与节点，此时的图成了普通图，问题归约描述也就成为状态空间描述。,4.3 与或图搜索,在与或图上执行搜索的过程，其目的在于表明起始节点是有解的，也就是说，搜索不是去寻找目标节点，而是寻找一个解图。,定义：,一个与或图,G,中，从节点,n,到节点集,N,的解图记为,G,，G,是,G,的子图。,1若,n,是,N,的一个元素，则,G,由一节点组成；,2若,n,有一个指向节点,n,1,n,k,的外向连接符,K，,使得从每一个,n,i,到,N,有一个解图(,i=1,k)，,则,G,由节点,n，,连接符,K，,及,n,1,n,k,中的每一个节点到,N,的解图所组成；,3否则,n,到,N,不存在解图。,在搜索解图的过程中，还需要进行耗散值的计算。设连接符的耗散值规定为：,k-,连接符的耗散值=,k，,若解图的耗散值记为,k(n,N)，,则可递归计算如下：,1,若,n,是,N,的一个元素，则,k(n,N)=0；,2,若,n,有一个外向连接符指向后继节点(,n,1,n,i,)，,并设该连接符的耗散值为,C,n,，,则,k(n,N)=,C,n,+k(n,1,N)+k(,n,i,N),具有最小耗散值的解图称为最佳解图，其值也用,h*(n),标记。,搜索过程还要标记能解节点(,SOLVED)，,为此给出如下定义：,能解节点(,SOLVED):,1,终结点是能解节点；,2若非终结点 有“或”子节点时，当且仅当其子节点至少有一能解，该非终结点才能解；,3若非终结点有“与”子节点时，当且仅当其子节点均能解，该非终结点才能解。,不能解节点(,UNSOLVED):,1,没有后裔的非终结点是不能解节点；,2若非终结点有“或”子节点时，当且仅当所有子节点均不能解时，该非终结点才不能解；,3若非终结点有“与”子节点时，当至少有一子节点不能解时，该非终结点才不能解。,不过与或图搜索与状态空间图搜索有几点不同，说明如下：,1）搜索目的是证明起始节点是否可解，而可解节点是递归定义的，取决于后继节点是否可解，即搜索是否找到叶节点。因此，搜索有可解标示过程和不可解标示过程。初始节点被标示为可解，则搜索成功结束，初始节点被标示为不可解，则搜索失败。,2）一旦发现不可解节点，应把该节点从图中删去。,下面我们讨论一般与或图的启发式搜索算法,AO*,算法。与,A*,算法不同，其评价函数,f(n)=h(n)，,只考虑,h(n),这个分量，,h(n),作为,h*(n),的一个估计。,过程,AO*:,1,建立一个搜索图,G，G:=s，,计算,q(s)=h(s)，IF GOAL(s)THEN M(s,SOLVED)；,开始时图,G,只包括,s，,耗散值估计为,h(s)，,若,s,是终节点,则标记上能解。,2,Until s,已标记上,SOLVED,do:,3 begin,4 G,:=FIND(G)；,根据连接符标记（指针）找出一个待扩展的局部解图,G,，,指针后面步骤有说明。,5,n:=G,中的任一非终节点;选一个非终结点作为当前节点。,6,EXPAND(n),生成子节点集(,n,i,)，G:=ADD(,n,j,),G),计算,q(,n,j,)=h(,n,j,)，,其中,n,j,G，,IF GOAL(,n,j,)THEN M(,n,j,SOLVED);,把,n,的子节点添加到,G,中,对,G,中未出现的子节点计算耗散值，若有终节点则加能解标记。,7,S:=(n);,建立含,n,的单一节点集合,S.,8,Until S,为空,do:,9,begin,10,REMOVE(m,S),m,c,(S);,这个,m,的子节点,m,c,应不在,S,中。,11,修改,m,的耗散值,q(m):,对,m,指向节点集(,n,1i,，n,2i,n,ki,),的每一个连接符,i,分别计算,q,i,q,i,(m)=,C,i,+q(n,1i,)+q(,n,ki,),q(m):=min,q,i,(m);,对,m,的,i,个连接符,取计算结果最小的那个耗散值为,q(m)。,加指针到,min,q,i,(m),的连接符上,或把指针修改到,min,q,i,(m),的 连接符上,即原来指针与新确定的不一致时应删去.,IF M(,n,ji,SOLVED)THEN M(m,SOLVED);,若该连接符的所有子节点都是能解的,则,m,也标上能解.,12,IF M(m,SOLVED),(q(m),q(m,0,),THEN ADD(m,a,S);m,能解或修正的耗散值与原先估算,q,0,不同,则把,m,的所有先辈节点,m,a,添加到,S,中.,13,end,14,end,我们使用图4.2的与或图，并假设：,h(n,0,)=2，h(n,1,)=2，h(n,2,)=4，h(n,3,)=4，h(n,4,)=1，h(n,5,)=1，h(n,6,)=2，h(n,7,)=h(n,8,)=0，k-,连接符的耗散值=,k,应用,AO*,算法，经过四个循环，可找到解图。如图4.3,3,n,0,4 n,0,2,n,1,5,n,1,1,n,5,1,n,4,1,n,5,1,n,4,4 n,3,4 n,2,(a)(b),5,n,0,5 n,0,5,n,1,5,n,1,2,n,5,1,n,4,2,n,5,1,n,4,4 n,3,4 n,2,4 n,3,4 n,2,2,n,6,0 n,7,0 n,8,2,n,6,0 n,7,0 n,8,(c)(d),图4.3,AO*,算法的搜索图,4.4 博弈树的搜索,本节所指博弈问题是指二人完备博弈：,1由二人对垒，二人轮流走步，自己的走步自己选择,2任何一方都完全知道对方过去的走步情况和今后可能的走步，不包括碰运气的情况。,4.4.1博弈树的极大极小搜索法,对简单的博弈问题，我们可用类似与或图的搜索技术求出解图,。,极大极小搜索法是考虑双方对弈若干步之后，选一步好的走步。,这需定义一个评价函数,f,。,f(n):=,，,表示,MAX,方获胜，,f(n):=-,，,表示,MIN,方获胜，,f(n):=0,，,势力相同。,下面说明极大极小过程,MINLMAX：,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);,4.IF n,可直接判定为赢,输或平局,THEN f(n):=,-,0，GO LOOP1,ELSE EXPAND(n),n,i,，ADD(,n,i,，T),IF d,n,i,k THEN ADD(,n,i,OPEN),GO LOOP1,ELSE,计算,f(,n,i,),GO LOOP1;,n,i,达到深度,k,计算各端节点,f,值.,5.,LOOP2：IF CLOSED=NIL,THEN GO LOOP3,ELSE,n,d,=FIRST(CLOSED);,6.IF(,n,d,MAX),(f(,n,ci,MIN),有值),THEN f(,n,d,):=maxf(,n,ci,),REMOVE(,N,d,，CLOSED);,若,MAX,所有子节点均有值,则该,MAX,取其极大值.,IF(,n,d,MIN),(f(,n,ci,MAX),有值),THEN f(,n,d,):=minf(,n,ci,),REMOVE(,N,d,，CLOSED);,若,MIN,所有子节点均有值，则该,MIN,取其极小值.,7.,GO LOOP2;,8.LOOP3:IF f(s)NIL THEN EXIT(END,M(Move,T);s,有值,或则结束或标记走步。,下面我们以井字棋为例，说明极大极小搜索法。,如图4.4 有一井字形棋盘，甲乙二人轮流在空格中放入自己的棋子，谁先使三子成一线则胜，设甲先走用,表示，乙用,表示，,p,表示某种格局，,e(p),表示对格局的评价值。,e(p),定义如下：,1）甲胜，,e(p)=+,2）,乙胜，,e(p)=-,图4.4 井字棋,3）若,p,不是可定胜负的格局，则,e(p)=e,+,(p)-e,-,(p),其中，,e,+,(p),表示当前棋局所有空格都放上甲的棋子后，甲构成的行、列和对角线的个数。同理，,e,-,(p),表示当前棋局所有空格都放上乙的棋子后，乙构成的行、列和对角线的个数。对于图4.4，,e(p)=6-4=2,例：,(-1)(-2)(1),6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 5-4=1,4.4.2,-,搜索过程,在极大极小过程中，把生成树和棋局估值两个过程完全分离，使效率大大降低，若同时进行，再根据一定的条件判断，有可能尽早剪掉一些无用的分支，则可能减少搜索工作量，这是,-,搜索过程的基本思想。下面我们用井字棋说明,-,剪枝方法。,假设以深度优先方法生成了部分搜索树，则可使用终止搜索规则,-,剪枝：,1,剪枝：若任何极小节点的,值小于或等于任何它的极大父节点的,值，则可以终止该极小节点以下的搜索，并设置这个极小节点的最终倒推值为,。,2,剪枝：若任何极大节点的,值大于或等于它的极小父节点的,值，则可以终止该极大节点以下的搜索，并设置这个极大节点的最终倒推值为,。,-,过程：保存,和,值，并且当可能时便进行剪枝的整个过程，当初始节点的全部后继节点的最终倒推值都给出时，过程即结束，而最好的优先走步就是走向具有最高倒推值的那个后继节点。,例：,MAX,=-1,MIN,(,=,-1)(,=-1,)(,=1),6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 5-4=1 6-4=2,例:,A,B,C,D,E F,G,H I,J,K,L M N O P Q R S T U V W X Y,2,3 8 5 7 6 0 1 5 2,8 4 10 2,