人工智能一般搜索原理

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,*,搜索技术,问题提出,：有了知识表示方法之后，就需要有解决问题的方法，也就是搜索技术。所谓搜索，就是寻找一条从初始问题到问题解的路径,本章内容,：搜索技术有许多种，本章介绍一些早期的、比较简单的搜索原理：1，盲目搜索；2，启发式搜索；3，消解原理；4，通用问题求解技术,关键问题,：,如何利用知识，尽可能有效地找到问题的解(最佳解)。,第三章 一般搜索原理,10/3/2024,1,一般搜,索,索原理,搜索策,略,略可分,为,为三大,类,类,不可撤,回,回方式,、,、回朔,方,方式、,图,图搜索,方,方式,不可撤,回,回方式：每一,次,次搜索,时,时，利,用,用局部,知,知识根,据,据最优,评,评价，,选,选出下,一,一状态,，,，选定,后,后不能,撤,撤回，,只,只能继,续,续,回朔方,式,式：在搜,索,索过程,中,中，有,时,时会发,现,现所选,的,的路径,不,不适合,找,找到目,标,标，这,时,时允许,退,退回去,另,另选一,条,条路径,。,。,图搜索,方,方式：如果把,问,问题求,解,解过程,用,用图来,表,表示。,节,节点代,表,表问题,的,的状态,，,，弧代,表,表状态,变,变化的,方,方向，,则,则搜索,就,就变成,对,对图进,行,行从初,始,始节点,开,开始，,到,到目标,节,节点路,径,径的搜,索,索。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,2,回溯搜,索,索策略,例：皇,后,后问题,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,3,( ),皇后问,题,题搜索,过,过程（,一,一）,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,4,Q,( ),(1,1),皇后问,题,题搜索,过,过程（,二,二）,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,5,Q,Q,( ),(1,1),(1,1) (2,3),皇后问,题,题搜索,过,过程（,三,三）,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,6,Q,( ),(1,1),(1,1) (2,3),皇后问,题,题搜索,过,过程（,四,四）,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,7,Q,Q,( ),(1,1),(1,1) (2,3),(1,1) (2,4),皇后问,题,题搜索,过,过程（,五,五）,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,8,Q,Q,Q,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,皇后问,题,题搜索,过,过程（,六,六）,1/15/2020,9,Q,Q,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,皇后问,题,题搜索,过,过程（,七,七）,1/15/2020,10,Q,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,皇后问,题,题搜索,过,过程（,八,八）,1/15/2020,11,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,皇后问,题,题搜索,过,过程（,九,九）,1/15/2020,12,Q,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),(1,2),第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,皇后问,题,题搜索,过,过程（,十,十）,1/15/2020,13,Q,Q,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),(1,2),(1,2) (2,4),第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,皇后问,题,题搜索,过,过程（,十,十一）,1/15/2020,14,Q,Q,Q,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),(1,2),(1,2) (2,4),(1,2) (2,4) (3,1),第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,皇后问,题,题搜索,过,过程（,十,十二）,1/15/2020,15,Q,Q,Q,Q,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),(1,2),(1,2) (2,4),(1,2) (2,4) (3,1),(1,2) (2,4) (3,1) (4,3),第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,皇后问,题,题搜索,过,过程（,十,十三）,1/15/2020,16,递归的,思,思想,从前有座山,从前有座山,从前有座山,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,17,一个递,归,归的例,子,子,intListLenght(LIST *pList),if,(,(pList,=,=NULL)return 0,;,;,else returnListLength(pList-next)+1;,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,18,回溯搜,索,索算法,说,说明,BACKTRACK,（,（DATA）,DATA：当,前,前状态,。,。,返回值,：,：从当,前,前状态,到,到目标,状,状态的,路,路径,（以规,则,则表的,形,形式表,示,示）,或FAIL。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,19,回溯搜,索,索算法,（,（一）,递归过,程,程BACKTRACK(DATA,),),1,IFTERM(DATA)RETURNNIL;,2,IFDEADEND(DATA)RETURNFAIL;,3,RULES,:,:=APPRULES(DATA,),);,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,TERM:找目标,DEADEND:状态不,合,合法,无法继,续,续搜索,APPRULES:取可应,用,用规则,集,集,1/15/2020,20,回溯搜,索,索算法,（,（二）,4,LOOP:IFNULL(RULES)RETURN FAIL,;,;,5,R:=FIRST(RULES),;,;,6,RULES:,=,=TAIL(RULES),;,;,7,RDATA:,=,=GEN(R, DATA,),);,8,PATH:=BACKTRACK,(,(RDATA,),);,9,IFPATH=FAILGOLOOP;,10,RETURNCONS(R,PATH);,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,TAIL:删除头,条,条规则,GEN,:,:调用规,则,则作用,于,于当前,状,状态,CONS:获取解,路,路径规,则,则表,1/15/2020,21,存在问,题,题及解,决,决办法,问题：,深度问,题,题:如,果,果深度,太,太深,死循环,问,问题:,如,如果,状,状态出,现,现重复,解决办,法,法：,对搜索,深,深度加,以,以限制,记录从,初,初始状,态,态到当,前,前状态,的,的路径,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,22,增加约,束,束后的,回,回溯搜,索,索算法,BACKTRACK1（DATALIST）,DATALIST：,从,从初始,到,到当前,的,的状态,表,表（逆,向,向）,返回值,：,：从当,前,前状态,到,到目标,状,状态的,路,路径,（以规,则,则表的,形,形式表,示,示）,或FAIL。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,23,增加约,束,束后的,回,回溯搜,索,索算法,(,(一),1,DATA:,=,=FIRST,(,(DATALIST,),),2,IFMENBER(DATA, TAIL,(,(DATALIST,),),RETURNFAIL;,3,IFTERM(DATA)RETURNNIL;,4,IFDEADEND(DATA)RETURNFAIL;,5,IFLENGTH(DATALIST)BOUND,RETURNFAIL;,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,24,增加约,束,束后的,回,回溯搜,索,索算法,(,(二),6,RULES,:,:=APPRULES(DATA,),);,7,LOOP,:,: IF NULL,(,(RULES,),) RETURNFAIL;,8,R:,=,=FIRST,(,(RULES,),);,9,RULES,:,:=TAIL,(,(RULES,),);,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,25,增加约,束,束后的,回,回溯搜,索,索算法,(,(三),10,RDATA,:,:=GEN(R,DATA);,11,RDATALIST:=CONS(RDATA,DATALIST);,12,PATH:,=,=BACKTRCK1(RDATALIST),13,IFPATH=FAIL GO LOOP,;,;,14,RETURN CONS,(,(R,PATH),;,;,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,26,一些深,入,入的问,题,题,失败原,因,因分析,、,、多步,回,回溯,Q,Q,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,27,一些深,入,入问题,（,（续）,回溯搜,索,索中知,识,识的利,用,用,基本思,想,想：,尽可能,选,选取划,去,去对角,线,线上位,置,置数最,少,少的。,Q,Q,Q,Q,4 3 3 4,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,28,模式导,向,向搜索,这个算,法,法是将,递,递归搜,索,索应用,到,到谓词,演,演算的,通,通用搜,索,索算法,要判断,一,一个谓,词,词表达,式,式是某,个,个断言,集,集合的,逻,逻辑结,论,论,首先谓,词,词表达,式,式作为,目,目标，,使,使用合,一,一来选,择,择能与,其,其后件,匹,匹配的,蕴,蕴涵式,并把得,到,到的置,换,换运用,于,于该蕴,涵,涵式的,前,前件,这个前,件,件成了,新,新的目,标,标称,其,其为子,目,目标,应用递,归,归搜索,解,解这个,子,子目标,如果与,事,事实相,匹,匹配，,则,则搜索,结,结实,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,29,模式导,向,向搜索,算,算法描,述,述一,Functionpattern_search(current_goal,),),begin,ifcurrent_goalisinclosed thenreturn FAIL,else putcurrent_goalintoclosed,whileeveryrule andfactsdo,begin,case,current_goal,与,与,事,事实合,一,一,returnSUCCESS,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,30,模式导,向,向搜索,算,算法描,述,述二,current_goal,是,是合,取,取式,begin,forevery,合,合取项item do,ret,=,=pattern_search(item),ifret,=,=FAILthen returnFAIL,end,current_goal,与,与规,则,则的后,件,件合一,begin,对前件q应用,对,对应的,合,合一置,换,换,ret,=,=pattern_search(q),ifret,=,=FAILthen returnFAIL elseSUCCESS,end,end,returnFAIL,end,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,31,图搜索,策,策略,图搜索,策,策略就,是,是在图,中,中寻找,从,从起始,点,点到目,标,标点的,路,路径的,方,方法,图搜索,的,的一般,过,过程是,构,构造搜,索,索图的,过,过程。,令,令搜索,图,图开始,时,时只有,起,起始点S0，,然,然后逐,步,步扩展,节,节点，,直,直到将,目,目标点,扩,扩展到,搜,搜索图,里,里为止,。,。扩展,的,的过程,就,就是搜,索,索的过,程,程,扩展节,点,点的方,法,法不同,，,，就意,味,味着搜,索,索的方,法,法不同,，,，也就,是,是搜索,的,的路径,不,不同。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,32,图搜索,策,策略图,示,示,S0,Sg,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,33,节点扩,展,展,扩展一,个,个节点,生成出,该,该节点,的,的所有,后,后继节,点,点，并,给,给出它,们,们之间,的,的代价,值,值。这,一,一过程,称,称为“,扩,扩展一,个,个节点,”,”。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,34,路径,路径,设一节,点,点序列,为,为(n0, n1,nk)，对,于,于i,=,= 1,k，,若,若节点ni-1具有一,个,个后继,节,节点ni，则该,序,序列称,为,为从n0到nk的路径,。,。,路径的,代,代价值,一条路,径,径的代,价,价值等,于,于连接,这,这条路,径,径各节,点,点间所,有,有代价,值,值的总,和,和。用C(ni, nj)表示从ni到nj的路径,的,的代价,值,值。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,35,节点深,度,度,节点深,度,度：,根节点,深,深度=0,其它节,点,点深度,=,=父节,点,点深度,+,+1,0,1,2,3,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,36,图搜索,的,的一般,过,过程,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,成功,是,把第一个节点(n)从OPEN表移至CLOSED表,把n的后继节点放入OPEN表的末端，提供返回节点n的指针,修改指针方向,把S放入OPEN表,重排OPEN表,是,否,否,OPEN为空？,n为目标节点？,失败,开始,1/15/2020,37,图搜索,过,过程说,明,明,我们在,搜,搜索过,程,程中用,到,到了OPEN表和CLOSED表两个数据结,构,构,OPEN表中的,节,节点都,是,是搜索,树,树的端,节,节点，,即,即至今,尚,尚未被,选,选作为,扩,扩展的,节,节点,CLOSED表中的节,点,点或者,是,是已被扩展而,不,不能生,成,成后继,节,节点的,那,那些端,节,节点，,或,或者是,搜,搜索树,的,的非端,节,节点,重排OPEN表，实,际,际上就,是,是在选,择,择搜索,顺,顺序，,也,也就是,扩,扩展的,节,节点的,顺,顺序。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,38,节点类,型,型说明,.,.,.,mj,.,mk,.,.,.,ml,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,扩展的,节,节点OPEN表没有,的,的部分,扩展,的节点,在,在已在,close,表中的,部,部分,扩展的,节,节点已,在,在OPEN表中的,部,部分,选定的,扩,扩展节,点,点,1/15/2020,39,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,图搜索,过,过程的,图,图示（,一,一）,现要扩展它,1/15/2020,40,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,图搜索,过,过程的,图,图示（,二,二）,修改父,子,子关系,现要扩展它,1/15/2020,41,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,图搜索,过,过程的,图,图示（,三,三）,修改父,子,子关系,修改父,子,子关系,1/15/2020,42,盲目搜,索,索概述,盲目搜,索,索也叫,无,无信息,搜,搜索,盲目搜,索,索实际,上,上是对,解,解空间,的,的遍历,盲目搜,索,索包括,有,有：,宽度优,先,先搜索：搜索,以,以接近,起,起始节,点,点的程,度,度依次,扩,扩展节,点,点，在,对,对下一,层,层搜索,前,前，必,须,须搜索,完,完本层,的,的所有,节,节点。,深度优,先,先搜索：搜索,首,首先扩,展,展最新,产,产生的,节,节点。,等代价,搜,搜索：搜索,沿,沿最小,代,代价节,点,点进行,扩,扩展。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,43,宽度优,先,先搜索,成功,是,把第一个节点(n)从OPEN表移至CLOSED表,把n的后继节点放入OPEN表的末端，提供返回节点n的指针,把S放入OPEN表,是,否,否,OPEN为空？,是否有任何后继节点为目标节点？,失败,开始,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,44,目标,23,184,765,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,1,2,5,6,7,3,1 2 3,8 4,7 6 5,8,2 3 4,1 8,7 6 5,4,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,八数码,难,难题的,宽,宽度优,先,先搜索,树,树,按上下左,右,右序走,步,步,1/15/2020,45,宽度优,先,先搜索,的,的性质,当问题,有,有解时,，,，一定,能,能找到,解,解,当问题,为,为单位,代,代价值,，,，且问,题,题有解,时,时，一,定,定能找,到,到最优,解,解,方法与,问,问题无,关,关，具,有,有通用,性,性,效率较,低,低,属于图,搜,搜索方,法,法,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,46,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,深度优,先,先搜索,成功,是,把第一个节点(n)从OPEN表移至CLOSED表,把n的后继节点放入OPEN表的前端，提供返回节点n的指针,把S放入OPEN表,是,否,否,OPEN为空？,节点n的深度是否等于深度界限？,失败,开始,是否有任何后继节点为目标节点？,是,否,S是否为目标节点？,否,成功,1/15/2020,47,23,184,765,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,1 2 3,8 4,7 6 5,目标,。,。,。,。,。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,八数码,难,难题的,深,深度优,先,先搜索,树,树,1/15/2020,48,深度优,先,先搜索,的,的性质,一般不,能,能保证,找,找到最,优,优解,当深度,限,限制不,合,合理时,，,，可能,找,找不到,解,解，可,以,以将算,法,法改为,可,可变深,度,度限制,最坏情,况,况时，,搜,搜索空,间,间等同,于,于穷举,是一个,通,通用的,与,与问题,无,无关的,方,方法,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,49,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,等代价,搜,搜索,成功,是,把具有最小g(i)值的节点i从OPEN表移至CLOSED表,计算其后继节点j的g(j)值。把其后继节点放入OPEN表,把S放入OPEN表,否,否,OPEN为空？,失败,开始,i是否为目标节点？,是,S是否为目标节点？,否,成功,是,令g(s)=0,1/15/2020,50,什么是,启,启发式,搜,搜索,盲目搜,索,索的效,率,率低，,耗,耗费过,多,多的计,算,算时间,和,和空间,，,，容易,产,产生组,合,合爆炸,。,。,利用知,识,识来引,导,导搜索,，,，达到,减,减少搜,索,索范围,，,，降低,问,问题复,杂,杂度的,目,目的。,对搜索,产,产生帮,助,助的信,息,息称为,启,启发信,息,息,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,51,启发式,信,信息对,搜,搜索方,法,法的影,响,响,启发信,息,息的多,少,少用启,发,发信息,强,强度来,表,表示,不同的,启,启发信,息,息对搜,索,索方法,带,带来不,同,同的影,响,响：,强：降,低,低搜索,工,工作量,，,，但可,能,能导致,找,找不到,最,最优解,弱：一,般,般导致,工,工作量,加,加大，,极,极限情,况,况下变,为,为盲目,搜,搜索，,但,但可能,可,可以找,到,到最优,解,解,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,52,启发式,搜,搜索类,型,型,启发信,息,息按用,途,途可分,为,为3类,：,：,用于决,定,定要扩,展,展的下,一,一个节,点,点（这个节,点,点称为,最,最有希,望,望的节,点,点），以,免,免像在,宽,宽度优,先,先或深,度,度优先,搜,搜索中,那,那样盲,目,目地扩,展,展,在扩展,一,一个节,点,点的过,程,程中，,用,用于决,定,定要生,成,成哪些,其,其后继,节,节点，以免盲,目,目地生,成,成所有,节,节点。,用于决,定,定哪些,节,节点应,从,从搜索,树,树中抛,弃,弃或修,剪,剪。,用来估,算,算节点,希,希望程,度,度的方,法,法为估,价,价函数,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,53,对启发,式,式搜索,的,的认识,有些启,发,发信息,能,能够大,大,大减少,搜,搜索工,作,作量，,但,但不能,保,保证能,够,够得到,最,最小代,价,价路径,我们往,往,往希望,获,获得路,径,径代价,和,和求该,路,路径所,需,需的搜,索,索代价,的,的综合,为,为最小,由于计,算,算综合,代,代价很,困,困难，,因,因此，,比,比较两,种,种方法,的,的优劣,，,，依赖,使,使用的,经,经验,使用估,价,价函数,实,实际是,对,对OPEN表,进,进行排,序,序，再,按,按顺序,扩,扩展节,点,点，进,行,行搜索,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,54,有序搜,索,索,若按估,价,价函数,的,的增序,对,对OPEN表,进,进行排,序,序，这,种,种搜索,方,方法叫,做,做有序,搜,搜索或,最,最佳优,先,先搜索,有序搜,索,索的有,效,效性取,决,决于估,价,价函数,的,的选择,，,，否则,有,有可能,失,失去一,个,个最好,的,的解甚,至,至全部,的,的解,如果没,有,有合适,的,的选择,，,，可考,虑,虑两个,方,方面的,内,内容：,一个是,时,时间和,空,空间的,折,折中,保证有,一,一个解,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,55,有序搜,索,索框图,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,成功,是,选取f值最小的节点i，从OPEN表移至CLOSED表,扩展i，计算后继节点j的f(j)，对OPEN表重排序，调整亲子关系,把S放入OPEN表，计算f(s),是,否,否,OPEN为空？,i是目标节点？,失败,开始,1/15/2020,56,估价函,数,数：f(n,),)=d,(,(n),+,+w(n),其中，d(n,),):节点的,深,深度,w(n,),):节点放,错,错棋子,数,数目,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,八数码,难,难题的,有,有序搜,索,索树,2 8 3,1 6 4,7 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,1 2 3,8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,1 2 3,7 8 4,6 5,2 3,1 8 4,7 6 5,5,4,6,4,6,6,7,7,5,6,7,5,5,1 2 3,8 4,7 6 5,目标,5,估价函,数,数值,1/15/2020,57,A,算法,A算法,是,是一种,有,有序搜,索,索的启,发,发式搜,索,索算法,。,。它采,用,用估算,节,节点n,的,的两个,代,代价：,从起始,点,点s到n的最,小,小代价,路,路径的,代,代价,从n到,某,某个目,标,标节点,的,的最小,代,代价路,径,径的代,价,价,估价函,数,数的形,式,式：,f(n,),) =g(n),+,+ h,(,(n),其中：g(n,),)：是,对,对g*,(,(n),的,的估价,值,值,h(n,),)：是,对,对h*,(,(n),的,的估价,值,值,称,为,为启发,函,函数,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,58,A算法估价函,数,数的说,明,明,g*(n)：,从,从s到n的最,佳,佳路径,的,的代价,h*(n)：,从,从n到,某,某个目,标,标节点,的,的最佳,路,路径的,代,代价,f*(n)=g*(n)+h*(n)：从s经,过,过n到,某,某个目,标,标节点,的,的最佳,路,路径的,代,代价,g(n,),)、h,(,(n),、,、f(n)分,别,别是g,*,*(n,),)、h,*,*(n,),)、f,*,*(n,),)的估,计,计值,表明，,估,估价函,数,数f(n)是,对,对从起,始,始点s,经,经过n,到,到某个,目,目标节,点,点的最,佳,佳路径,的,的代价,的,的估计,值,值,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,59,A算法,流,流程,1,OPEN:=,(,(s), f,(,(s),:,:=g,(,(s),+,+h(s);,2,LOOP:IFOPEN=(,),)THEN EXIT,(,(FAIL),;,;,3,n:=FIRST(OPEN);,4,IFGOAL(n,),) THENEXIT(SUCCESS);,5,REMOVE,(,(n,OPEN), ADD(n,CLOSED,),);,6,EXPAND,(,(n),mi,计算f,(,(n,mi,),):=g(n, mi)+h(mi);,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,60,A算法,流,流程（,续,续）,ADD,(,(mj, OPEN,),),标,标记mj到n,的,的指针,；,；,IFf(n, mk)f(mk)THEN f,(,(mk,),):=f(n, mk),标记mk到n,的,的指针,；,；,IFf(n, ml),a,b,(z),(,(x)(,y),(P(x,),) Q(x,),), R,(,(y),U(z),2,移动否,定,定符,理论根,据,据：(a,b,),) =, a ,b,(a,b,),) =, a ,b,(x)P,(,(x),=,=(,x),P(x),(x)P,(,(x),=,=(,x),P(x),(z),(,(x)(,y),(P(x,),) ,Q(x),R(y,),)U(z),第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,76,化子句,集,集例（续1,）,）,3,变,变量标,准,准化,即：对,于,于不同,的,的约束,，,，对应,于,于不同,的,的变量,(x)A(x,),) ,(,(x)B,(,(x),=,=,(x)A(x,),) ,(,(y)B,(,(y),4,量词左,移,移,(x)A(x,),) ,(,(y)B,(,(y),=,=(x),(,(y),A(x), B,(,(y),5,消存在,量,量词,(,(skolem化）,原则：,对,对于一,个,个受存,在,在量词,约,约束的,变,变量，,如,如果他,不,不受全,程,程量词,约,约束，,则,则该变,量,量用一,个,个常量,代,代替，,如,如果他,受,受全程,量,量词约,束,束，则,该,该变量,用,用一个,函,函数代,替,替。,(z),(,(x)(,y),(,P(x),Q,(,(x),),) R(y),U,(,(z),=,(,(x,),),(P(x,),) ,Q(x),R(f(x,),),U(a),第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,77,化子句,集,集例（,续,续2）,6,化,化为合,取,取范式,即(a,b),(,(cd), (ef,),)的形式,(x,),),(,(P,(,(x),Q(x,),), R,(,(f(x),U,(,(a),=,(,(x,),)(,P(x),Q,(,(x),),) R(f(x,),)U(a,),),=,(,(x,),),P(x), R,(,(f(x),U(a),Q,(,(x),),)R(f,(,(x),),)U,(,(a),7,隐去全,程,程量词,P(x,),) R(f(x,),)U(a,),),Q(x,),)R(f(x,),)U(a,),),第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,78,化子句,集,集例（续3,）,）,8,表,表示为,子,子句集,P,(,(x),R(f,(,(x),),)U,(,(a), Q(x,),)R(f(x,),)U(a,),),9,变量标,准,准化（,变,变量换,名,名）,P,(,(x1,),) R(f(x1),U(a),Q,(,(x2,),)R(f(x2),U(a),第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,79,消解推,理,理规则,L1、L2,为,为任一,原,原子公,式,式，他,们,们具有,相,相同的,谓,谓词符,号,号，但,一,一般变,量,量名不,同,同,已知两,子,子句L1和L2,如果L1、L2具,有,有最一,般,般合一,者,者,那么可,得,得新子,句,句(),这个新子句,叫,叫做消,解,解式,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,80,命题逻,辑,辑的消,解,解推理,举,举例,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,假言推理：P PQ (PQ）,消解式,：Q,合并：PQ PQ,消解式,：QQ = Q,重言式：P Q PQ,消解式,：PP 或 QQ,空子句：P P,消解式,：NIL,三段论,：,：PQ,(,(PQ）,QR,(,(QR）,消解式：PR,(,(P,Q）,1/15/2020,81,谓词逻,辑,辑的消,解,解推理,举,举例,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,B(x) B(x)C(x）,消解式,：C(x),P(x)Q(x） Qf(y),消解式,：Pf(y),置换,：f(y)/x,Px,f(y)Q(x)Rf(a),y Pf(f(a),zR(z,w）,消解式,：Qf(f(a)Rf(a),yRf(y),w,置换,：f(f(a)/x, f(y)/z,1/15/2020,82,消解反,演,演求解,过,过程,消解反,演,演是利用消解原,理,理进行,命,命题证,明,明。,给定公,式,式集S和目,标,标公式L,证明公式L,的,的步骤,如,如下：,否定L，得L,把L添加到S中去,把新产,生,生的集,合,合L,S化成子,句,句集,应用消,解,解原理,力,力图推,导,导出一,个,个表示,矛,矛盾的,空,空子句,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,83,命题逻,辑,辑消解,反,反演的,例,例子,设公理,集,集：,P,(PQ),R,(ST),Q,T,求证：R,子句集,：,：,(1)P,(2),P,Q,R,(3),S,Q,(4),T,Q,(5)T,(6),R（目标求,反,反）,化子句,集,集：,(PQ),R,=,(P,Q),R,=,P,QR,(ST),Q,=, (ST,),)Q,=,(,(S,T,),)Q,=,(,(S,Q),(,TQ),=,S,Q,T,Q,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,84,命题逻,辑,辑消解,反,反演的,例,例子（,续,续）,子句集,：,：,(1)P,(2),P,Q,R,(3),S,Q,(4),T,Q,(5)T,(6),R（目标求,反,反）,归结：,(7)PQ,(,(2, 6,),),(8),Q,(,(1,7),(9),T,(,(4, 8,),),(10,),) nil,(,(5, 9,),),第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,85,谓词逻,辑,辑消解,反,反演的,例,例子,例：,已知：IfFidogoeswhereverJohn goesand if Johnisatschool,whereisFido ?,(x),AT,(,(John,x),AT(Fido, x,),),AT(John,School,),),求证：(x)AT(Fido, x,),),子句集,：,：,AT,(,(John,y),AT(Fido, y,),),AT(John,School,),),AT(Fido, x,),),(,( ,(,(x)AT(Fido, x,),) =, (, x,),) AT(Fido, x,),) ),第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,86,AT(Fido, x),AT(John, y),AT(Fido, y),子句集：AT(John, y) AT(Fido, y),AT(John, School),AT(Fido, x),AT(John, x),x/y,AT(John, School),nil,School/x,AT(Fido, School),第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,谓词逻,辑,辑消解,反,反演的,例,例子（,续