人工智能与或图搜索23

,#,人工智能,吉林大学珠海学院计算机科学与技术系,2.1 与或图(AND/OR Graph)的搜索,为严格描述AND/OR图，我们先推广弧的概念。在有向图中的弧是从一个父亲节点指向它的儿子节点的。在AND/OR图中使用的弧叫做超弧，一个超弧可以把一个父亲节点和k个儿子节点同时连接起来，这样的弧也叫做k连弧，在AND/OR图中，k连弧用弧线连接起来。当k=1时，k连弧退化成通常的有向图中的弧。,k连弧,一般的,弧,弧,n7,n6,n3,n0,n1,n4,n2,n5,n8,与或图,n,5,n,1,n,3,n,6,n,7,n,8,n,5,n,0,n,7,n,8,n,4,n,0,三个解,图,图,n,5,n,7,n,8,n,4,n,0,在定义,中,中假定AND,/,/OR图不含,回,回路，,即,即是说,，,，图,中,中不存,在,在一个,节,节点的,后,后裔也,是,是这个,节,节点的,祖,祖先的,情,情形。,不,不含,回,回路保,证,证了节,点,点间具,有,有部分,序,序关系,，,，从,而,而保证,了,了下面,定,定义的,合,合理性,。,。,设N是AND,/,/OR图G的目标,节,节点集,合,合，,从,从图中,任,任意一,个,个节点n出发到N的一个,解,解图是AND,/,/OR图G的一个,子,子图，,用,用G表示，,递,递归,定,定义如,下,下：,如果n是N中的一,个,个节点,，,，则G只包括n.,如果n有一条,从,从n出发的k连弧ai,这个k连弧连,接,接的儿,子,子节点,是,是n1,n2,.,.,nk,则解图G由节点n,k连弧ai,和由n1,n2,.,.,.,nk出发的,解,解图构,成,成。,否则，G没有从n出发到N的解图,。,。,与或图,设从节,点,点n到,目,目标节,点,点集合N的费,用,用用c,(,(n,N),表,表示，,则,则c,(,(n,N),定,定义如,下,下：,如果n,是,是N中,的,的一个,节,节点，,则,则c,(,(n,N),=,=0，,如果n,有,有一条,从,从n出,发,发的k,连,连弧ai,这,这个k,连,连弧连,接,接的儿,子,子节点,是,是n1,n2,.,.,.,.,nk,则,解,解图G,由节,点,点n,k连,弧,弧ai,和,由,由n1,n2,.,.,nk出发,的,的解图,构,构成。,这,这时，,解,解图G,的费,用,用定义,为,为,c(n,N,),)=c(ai)+c(n,n1),+,+c(n,nk),其,中,中c(ai),是,是k连,弧,弧ai,的,的费用,.,.,否则，G没,有,有从n,出,出发到N的解,图,图。设,其,其费用,为,为无穷,大,大.,。,。,例如，,如,如果假,定,定k连,弧,弧的费,用,用是k,则,图,图3.4 所,示,示的AND,/,/OR,图,图的两,个,个解图,中,中，左,图,图的费,用,用是8,，,，右,图,图的费,用,用是7,。,。,2.2与或图,的,的启发,式,式搜索,AND,/,/OR,图,图的启,发,发搜索,过,过程AO*,1.,建,建立一,个,个只由,根,根节点s构成,的,的搜索,图,图G,设,设从s 出,发,发的解,图,图的费,用,用为q,(,(s),=,=h(s),如,如果s是目,标,标节点,，,，用SOLVED,标,标记s,.,.,2.untils 被,标,标上SOLVED,do,:,:,3.begin,4.,通,通过,跟,跟踪从s出发,的,的有标,记,记的超,弧,弧计算,候,候选解,图,图G,(,(这些,标,标记在,后,后 面,的,的步骤11中,给,给出),5.,在,在G,中选,一,一个不,是,是目标,节,节点的,叶,叶节点n,6.,扩,扩展,节,节点n,产,生,生节点n的所,有,有儿子,n1,n2,.,.,nk,并,并把,这,这些儿,子,子连到,图,图G上,对于,每,每一个,不,不曾在G中出,现,现的儿,子,子nj,设q(nj)=h(nj),如,如果,这,这些儿,子,子节点,中,中的某,些,些节点,是,是目标,节,节点,则,则把这,些,些节点,标,标记为SOLVED,.,.,7.建立一,个,个由n构成的,单,单元素,集,集合S.,8.直到S变空,do:,9.begin,10.从S中删除,其,其儿子,节,节点不,在,在S中的节,点,点,记此节,点,点为m.,按以下,步,步骤修,改,改m的费用q(m),对于每,一,一个从m出发的,指向节,点,点集合ni1,ni2,.,.,.,nik超弧ai，计算qi(m)=c(ai)+q(ni1),+,+q(nik),这里的q(nij)或者是,在,在本循,环,环内部,的,的前面,步,步骤计,算,算出的,值,值，或,者,者是在,步,步骤6中指定,的,的值。,设,设q(m)是所有qi(m)的最小,者,者，,标,标记实,现,现这个,最,最小值,的,的超弧,，,，如果,本,本次标,记,记与以,前,前的标,记,记不同,，,，擦,去,去以前,的,的标记,，,，如,果,果这些,超,超弧指,向,向的所,有,有儿子,节,节点都,标,标记了SOLVED,则把m也标上SOLVED,.,.,12.如果m标记了SOLVED或者m修改后,的,的费用,与,与以前,的,的费用,不,不同，,则,则把m通过标,记,记的超,弧,弧连接,的,的父亲,节,节点加,入,入到S中，,13end,14.end,算法分,为,为两个,阶,阶段,1.4-6 步,.,.自,顶,顶向下,的,的产生,候,候补解,图,图,并,并扩展,候,候补解,图,图的过,程,程.,2.7,-,-12,自,底,底向上,修,修正费,用,用值,标,标记,弧,弧及的,过,过程.,例,H(n0)=3,H(n1)=2,H(n2)=4,H(n3)=4,H(n4)=1,H(n5)=1,H(n6)=2,H(n7)=0,H(n8)=0,n1,n5,n4,1,2,1,5,n0,n1,n5,n4,5,1,n2,4,n7,0,3,n0,4,n8,0,n6,2,5,n0,n1,n5,n4,5,1,n2,4,n7,0,n8,0,n6,2,n3,4,2,2,一次循,环,环后,二次循,环,环后,三次循,环,环后,四次循,环,环后,图3.5AO*搜索算,法,法的例,子,子,n1,n5,n4,1,2,1,3,n0,n3,4,n2,4,5,n0,n5,n4,1,n7,0,n8,0,2,搜索得,到,到的解,图,图,2.3,博,博弈,树,树的搜,索,索,穷尽的,极,极大极,小,小过程,。,。两个游戏者分别为MAX和MIN,MAX想取得,高,高的分,数,数，,而,而MIN想取得,低,低的分,数,数，把,整,整个棋,的,的状态,以,以及所,有,有可能,的,的移动,都,都用一,个,个有与,或,或图表,示,示出来,，,，对,于,于某一,游,游戏者,求,求出他,的,的解图,，,，就是,为,为游戏,者,者制定,的,的赢的,策,策略。Nim游戏，,桌,桌子上,有,有 7,枚,枚硬,币,币，,由,由MAX和MIN两个人,分,分别把,一,一堆硬,币,币分成,不,不相等,的,的两堆,，,，谁不,能,能继续,做,做下去,，,，谁就,算,算输，,为,为MAX制定一,个,个赢的,策,策略。知识表,示,示，,二,二元组s,p,其中s为一集,合,合，,表,表示桌,面,面上各,堆,堆的硬,币,币数，p表示对,当,当前状,态,态应该,移,移动的,游,游戏者,。,。例如（2，3，2,，,，MAX）表示现,在,在桌面,上,上有3 堆,硬,硬币，,分,分别,为,为2，3，2个,，,，此,时,时应抡,到,到MAX移动。,1,固定深,度,度的极,大,大极小,过,过程。实际的,游,游戏的,状,状态空,间,间是非,常,常大的,，,，例,如,如国际,象,象棋有10120个状态,，,，要,想,想把所,有,有状态,都,都列出,来,来，,实,实际上,是,是做不,到,到的，,改,改进,的,的处理,方,方法是,在,在当前,状,状态下,把,把游戏,扩,扩展到,某,某一固,定,定的深,度,度，,对,对这个,深,深度的,树,树的叶,节,节点进,行,行状态,估,估值，,然,然后分,别,别逐层,地,地以取,极,极大和,取,取极小,的,的方式,上,上传，,最,最终,给,给出对,游,游戏者,移,移动的,最,最佳建,议,议,例,例；,九,九宫游,戏,戏,估,估,值,值函数,：,：MAX所能占,据,据的行,，,，列,和,和对角,线,线数,-,-MAX所能占,据,据的行,，,，列,和,和对角,线,线数,如果MAX赢，,为,为无穷,大,大,如果MIN赢，,为,为0,5-4,=,=1,两步棋,的,的例子,S,J,I,H,G,F,E,D,A,B,C,MAX取极大,值,值,MIM取极小,值,值,MAX,(-2,),),(-2,),),(0),(0),(-6,),),(9),(-4,),),(-3,),),(-4,),),(-2,),),(-6,),),MAX的移动,过程MINMAX,:,:,算法分,为,为两个,阶,阶段,第一阶,段,段用宽,度,度优先,产,产生给,定,定深度,内,内的所,有,有节点,然后对,所,所有叶,节,节点进,行,行状态,估,估值.第二阶,段,段自低,向,向上倒,推,推估计,值,值,一层取,极,极小,一层去,极,极大.直至求,出,出初始,节,节点的,估,估值.,MIN,MAX,6-5,=,=1,5-5=0,6-5,=,=1,5-5,=,=0,4-5,=,=-1,5-6,=,=-1,5,-,-5=0,5-6=-1,6,-,-6=0,4-6,=,=-2,5-4,=,=16-4,=,=2,Alpha-beta过程在固定,深,深度的,极,极大极,小,小过程,中,中，,对,对于一,个,个给定,的,的节点,，,，需,要,要先扩,展,展到给,定,定的深,度,度，,然,然后对,叶,叶节点,进,进行估,值,值，在,一,一层一,层,层地向,上,上返回,值,值，,决,决定最,佳,佳移动,。,。为,提,提高效,率,率，,我,我们可,以,以按深,度,度优先,方,方式，,从,从左,边,边开始,，,，先,对,对最左分支扩,展,展到给,定,定深度,，,，定,出,出极大,和,和极小,的,的取值,界,界限，,即,即alpha值和beta值，,然,然后一,边,边扩展,一,一边估,值,值，,并,并把估,值,值同alpha值和beta值相比,较,较，这,样,样就可,以,以省掉,许,许多节,点,点的估,值,值，,当,当然这,些,些节点,也,也不必,产,产生了,，,，因,此,此提高,了,了算法,的,的效率,，,，这,就,就是Alpha-beta过程。,Alpha-beta剪枝的,原,原则1。在,任,任一个MIN节点，,如,如果,发,发现了,其,其beta值小于,或,或者等,于,于它的,一,一个MAX祖先节,点,点的alpha值，则,可,可以剪,枝,枝2。在,任,任一个MAX节点下,，,，如,果,果发现,了,了其alpha值大于,或,或者等,于,于它的,一,一个MIN祖先节,点,点的bata值，则可,以,以剪枝,2,5,3,1,2,0,3,3,3,MAX,MIN,MAX,0,2,MIN,图3.8alpha,-,-beta剪枝过,程,程,05,-,-333,-,-3022,-,-30,-,-23541,-,-30689,-,-3,MAX,最佳移,动,动,=0,=0,=0,=0,=0,=1,=-3,=1,=6,=1,