人工智能一般搜索原理

《人工智能一般搜索原理》由会员分享，可在线阅读，更多相关《人工智能一般搜索原理（94页珍藏版）》请在装配图网上搜索。

1、,,,,,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,‹#›,单击此处编辑母版标题样式,*,搜索技术,问题提出,：有了知识表示方法之后，就需要有解决问题的方法，也就是搜索技术。所谓搜索，就是寻找一条从初始问题到问题解的路径,本章内容,：搜索技术有许多种，本章介绍一些早期的、比较简单的搜索原理：1，盲目搜索；2，启发式搜索；3，消解原理；4，通用问题求解技术,关键问题,：,如何利用知识，尽可能有效地找到问题的解(最佳解)。,第三章 一般搜索原理,10/3/2024,1,,一般搜,索,索原理,搜索策,略,略可分,为,为三大,类,类,不可撤,回,回方式,、,、回朔,方,方式、,图,图

2、搜索,方,方式,不可撤,回,回方式：每一,次,次搜索,时,时，利,用,用局部,知,知识根,据,据最优,评,评价，,选,选出下,一,一状态,，,，选定,后,后不能,撤,撤回，,只,只能继,续,续,回朔方,式,式：在搜,索,索过程,中,中，有,时,时会发,现,现所选,的,的路径,不,不适合,找,找到目,标,标，这,时,时允许,退,退回去,另,另选一,条,条路径,。,。,图搜索,方,方式：如果把,问,问题求,解,解过程,用,用图来,表,表示。,节,节点代,表,表问题,的,的状态,，,，弧代,表,表状态,变,变化的,方,方向，,则,则搜索,就,就变成,对,对图进,行,行从初,始,始节点,开,开始，,到

3、,到目标,节,节点路,径,径的搜,索,索。,第三章,一,一般,搜,搜索原,理,理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)),

4、皇后问,题,题搜索,过,过程（,三,三）,第三章,一,一般,搜,搜索原,理,理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)

5、(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.

6、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

7、,,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盲目搜,索,索,皇后问,题,题搜索,

8、过,过程（,十,十二）,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,

9、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盲目

10、搜,索,索,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,;,;

11、,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,,存在问,题,题及解,决,决办法,问题：,深度问,题,题:如,果,果深度

12、,太,太深,死循环,问,问题:,如,如果,状,状态出,现,现重复,解决办,法,法：,对搜索,深,深度加,以,以限制,记录从,初,初始状,态,态到当,前,前状态,的,的路径,,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,22,,增加约,束,束后的,回,回溯搜,索,索算法,BACKTRACK1（DATALIST）,,DATALIST：,从,从初始,到,到当前,的,的状态,表,表（逆,向,向）,返回值,：,：从当,前,前状态,到,到目标,状,状态的,路,路径,（以规,则,则表的,形,形式表,示,示）,或FAIL。,,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,

13、索,索,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,R

14、ULES,:,:=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

15、,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

16、 3 4,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,28,,模式导,向,向搜索,这个算,法,法是将,递,递归搜,索,索应用,到,到谓词,演,演算的,通,通用搜,索,索算法,要判断,一,一个谓,词,词表达,式,式是某,个,个断言,集,集合的,逻,逻辑结,论,论,首先谓,词,词表达,式,式作为,目,目标，,使,使用合,一,一来选,择,择能与,其,其后件,匹,匹配的,蕴,蕴涵式,并把得,到,到的置,换,换运用,于,于该蕴,涵,涵式的,前,前件,这个前,件,件成了,新,新的

17、目,标,标—称,其,其为子,目,目标,应用递,归,归搜索,解,解这个,子,子目标,如果与,事,事实相,匹,匹配，,则,则搜索,结,结实,,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,29,,模式导,向,向搜索,算,算法描,述,述一,Functionpattern_search(current_goal,),),begin,ifcurrent_goalisinclosed thenreturn FAIL,else putcurrent_goalintoclosed,whileeveryrule andfactsdo,begin,case,current_goal

18、,与,与,事,事实合,一,一,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,=,=

19、=FAILthen returnFAIL elseSUCCESS,end,end,returnFAIL,end,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,31,,图搜索,策,策略,图搜索,策,策略就,是,是在图,中,中寻找,从,从起始,点,点到目,标,标点的,路,路径的,方,方法,图搜索,的,的一般,过,过程是,构,构造搜,索,索图的,过,过程。,令,令搜索,图,图开始,时,时只有,起,起始点S0，,然,然后逐,步,步扩展,节,节点，,直,直到将,目,目标点,扩,扩展到,搜,搜索图,里,里为止,。,。扩展,的,的过程,就,就是搜,索,索的过,程,程,扩展节,

20、点,点的方,法,法不同,，,，就意,味,味着搜,索,索的方,法,法不同,，,，也就,是,是搜索,的,的路径,不,不同。,,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,32,,图搜索,策,策略图,示,示,S0,Sg,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,33,,节点扩,展,展,扩展一,个,个节点,生成出,该,该节点,的,的所有,后,后继节,点,点，并,给,给出它,们,们之间,的,的代价,值,值。这,一,一过程,称,称为“,扩,扩展一,个,个节点,”,”。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/

21、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,其它节,点,点深度,=,=父节,点

22、,点深度,+,+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表中的,节,节点

23、都,是,是搜索,树,树的端,节,节点，,即,即至今,尚,尚未被,选,选作为,扩,扩展的,节,节点,CLOSED表中的节,点,点或者,是,是已被扩展而,不,不能生,成,成后继,节,节点的,那,那些端,节,节点，,或,或者是,搜,搜索树,的,的非端,节,节点,重排OPEN表，实,际,际上就,是,是在选,择,择搜索,顺,顺序，,也,也就是,扩,扩展的,节,节点的,顺,顺序。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2020,38,,节点类,型,型说明,…..,.,.,mj,…...,mk,…...,…...,…...,ml,第三章,一,一般,搜,搜索原,理,理3.1盲目搜

24、,索,索,扩展的,节,节点OPEN表没有,的,的部分,扩展,的节点,在,在已在,close,表中的,部,部分,扩展的,节,节点已,在,在OPEN表中的,部,部分,选定的,扩,扩展节,点,点,1/15/2020,39,,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,图搜索,过,过程的,图,图示（,一,一）,现要扩展它,1/15/2020,40,,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,图搜索,过,过程的,图,图示（,二,二）,修改父,子,子关系,现要扩展它,1/15/2020,41,,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,图搜索,过,过程的,图,

25、图示（,三,三）,修改父,子,子关系,修改父,子,子关系,1/15/2020,42,,盲目搜,索,索概述,盲目搜,索,索也叫,无,无信息,搜,搜索,盲目搜,索,索实际,上,上是对,解,解空间,的,的遍历,盲目搜,索,索包括,有,有：,宽度优,先,先搜索：搜索,以,以接近,起,起始节,点,点的程,度,度依次,扩,扩展节,点,点，在,对,对下一,层,层搜索,前,前，必,须,须搜索,完,完本层,的,的所有,节,节点。,深度优,先,先搜索：搜索,首,首先扩,展,展最新,产,产生的,节,节点。,等代价,搜,搜索：搜索,沿,沿最小,代,代价节,点,点进行,扩,扩展。,,第三章,一,一般,搜,搜索原,理,理

26、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

27、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

28、,7 6 5,8,2 3 4,1 8,7 6 5,4,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,八数码,难,难题的,宽,宽度优,先,先搜索,树,树,按上下左,右,右序走,步,步,1/15/2020,45,,宽度优,先,先搜索,的,的性质,当问题,有,有解时,，,，一定,能,能找到,解,解,当问题,为,为单位,代,代价值,，,，且问,题,题有解,时,时，一,定,定能找,到,到最优,解,解,方法与,问,问题无,关,关，具,有,有通用,性,性,效率较,低,低,属于图,搜,搜索方,法,法,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,1/15/2

29、020,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

30、 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,

31、7,8,9,a,b,c,d,1 2 3,8 4,7 6 5,目标,。。。,。,。。。。。,。,。。,第三章,一,一般,搜,搜索原,理,理3.1盲目搜,索,索,八数码,难,难题的,深,深度优,先,先搜索,树,树,1/15/2020,48,,深度优,先,先搜索,的,的性质,一般不,能,能保证,找,找到最,优,优解,当深度,限,限制不,合,合理时,，,，可能,找,找不到,解,解，可,以,以将算,法,法改为,可,可变深,度,度限制,最坏情,况,况时，,搜,搜索空,间,间等同,于,于穷举,是一个,通,通用的,与,与问题,无,无关的,方,方法,第三章,一,一般,搜,搜索原,理,理3.1

32、盲目搜,索,索,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,,什么是,启,启发式,搜,搜索,盲目搜,索,索的效,率,率低，,耗,耗费过,多,多的计,算,算时间,和,和空间,，,，容易,产,产生组,合,合爆炸,。,。,利用知,识,识来引,导,导搜索,，,，达

33、到,减,减少搜,索,索范围,，,，降低,问,问题复,杂,杂度的,目,目的。,对搜索,产,产生帮,助,助的信,息,息称为,启,启发信,息,息,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,51,,启发式,信,信息对,搜,搜索方,法,法的影,响,响,启发信,息,息的多,少,少用启,发,发信息,强,强度来,表,表示,不同的,启,启发信,息,息对搜,索,索方法,带,带来不,同,同的影,响,响：,强：降,低,低搜索,工,工作量,，,，但可,能,能导致,找,找不到,最,最优解,弱：一,般,般导致,工,工作量,加,加大，,极,极限情,况,况下变,为,为盲目,搜,搜索，,但,

34、但可能,可,可以找,到,到最优,解,解,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,52,,启发式,搜,搜索类,型,型,启发信,息,息按用,途,途可分,为,为3类,：,：,用于决,定,定要扩,展,展的下,一,一个节,点,点（这个节,点,点称为,最,最有希,望,望的节,点,点），以,免,免像在,宽,宽度优,先,先或深,度,度优先,搜,搜索中,那,那样盲,目,目地扩,展,展,在扩展,一,一个节,点,点的过,程,程中，,用,用于决,定,定要生,成,成哪些,其,其后继,节,节点，以免盲,目,目地生,成,成所有,节,节点。,用于决,定,定哪些,节,节点应,从,从搜索,

35、树,树中抛,弃,弃或修,剪,剪。,用来估,算,算节点,希,希望程,度,度的方,法,法为估,价,价函数,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,53,,对启发,式,式搜索,的,的认识,有些启,发,发信息,能,能够大,大,大减少,搜,搜索工,作,作量，,但,但不能,保,保证能,够,够得到,最,最小代,价,价路径,我们往,往,往希望,获,获得路,径,径代价,和,和求该,路,路径所,需,需的搜,索,索代价,的,的综合,为,为最小,由于计,算,算综合,代,代价很,困,困难，,因,因此，,比,比较两,种,种方法,的,的优劣,，,，依赖,使,使用的,经,经验,使用估,

36、价,价函数,实,实际是,对,对OPEN表,进,进行排,序,序，再,按,按顺序,扩,扩展节,点,点，进,行,行搜索,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,54,,有序搜,索,索,若按估,价,价函数,的,的增序,对,对OPEN表,进,进行排,序,序，这,种,种搜索,方,方法叫,做,做有序,搜,搜索或,最,最佳优,先,先搜索,有序搜,索,索的有,效,效性取,决,决于估,价,价函数,的,的选择,，,，否则,有,有可能,失,失去一,个,个最好,的,的解甚,至,至全部,的,的解,如果没,有,有合适,的,的选择,，,，可考,虑,虑两个,方,方面的,内,内容：,一个是

37、,时,时间和,空,空间的,折,折中,保证有,一,一个解,第三章,一,一般,搜,搜索原,理,理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,),):节点放

38、,错,错棋子,数,数目,第三章,一,一般,搜,搜索原,理,理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

39、,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

40、到,某,某个目,标,标节点,的,的最小,代,代价路,径,径的代,价,价,估价函,数,数的形,式,式：,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)+

41、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,LOO

42、P: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,,,

43、, mk)

44、*,*(n,),),则A算,法,法称为A*算,法,法。,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,62,,A*算法估价函,数,数举例,在问题,求,求解过,程,程中，,不,不可能,明,明确知,道,道h*,(,(n),，,，可,根,根据经,验,验估计,下,下界范,围,围条件,例如，8数码,问,问题,如取h,(,(n),=,=,“,“不在,位,位”的,牌,牌数，,可,可估计,出,出至少,要,要移动h(n,),) 步,，,，才能,达,达到目,标,标，因,此,此，有h(n,),) ≤h*,(,(n),如取h,(,(n,),) =,每,每个牌与目,标,标位置,的,的距

45、离,和,和，同,样,样可估,计,计出至,少,少要移,动,动h(n),步,步，才,能,能达到,目,目标，,因,因此，,有,有h(n),≤,≤ h,*,*(n,),),第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,2,,8,3,1,,6,4,7 5,1,,2,3,8,,,4,7 6 5,1/15/2020,63,,博弈中,的,的启发,式,式搜索,博弈空,间,间的极,小,小极大,搜,搜索:,假定对,手,手具有,相,相同的,关,关于状,态,态空间,的,的知识,,,,且用,该,该知识,以,以一致,方,方式比,赛,赛.,博弈中,的,的对手,分,分别称,为,为MI

46、N和MAX,一种余,一,一棋变,体,体：,博弈双,方,方要交,替,替地将,一,一堆牌,分,分成数,量,量不同,的,的两堆,牌,牌,最,先,先无法,分,分堆的,棋,棋手为,失,失败,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,64,,穷举式,的,的极小,极,极大搜,索,索,博弈过,程,程可以,用,用一个,树,树来表,示,示,标记叶,节,节点若MIN,获,获胜标0,MAX,获,获胜标1,,标记MIN节,点,点为其,子,子节点,值,值中的,最,最大值,标记MAX节,点,点为其,子,子节点,值,值中的,最,最小值,这样向,上,上传播,,,,直至,根,根节点,第三章,

47、一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,65,,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,一种余,一,一棋变,体,体树,4-3,4-2,-,-1,5-1,-,-1,7,5-2,2-2,-,-1-1-1,3-2,-,-1-1,6-1,4-1,-,-1-1,2-2,-,-2-1,3-1,-,-1-1-1,2-1,-,-1-1-1,-,-1,3-2,-,-2,0,0,1,1,0,1,1,1,1,1,1,0,0,3-3,-,-1,0,MIN,MAX,MIN,MAX,MIN,MAX,1/15/2020,66,,固定层,深,深的极,小,小极大,搜,搜索,这

48、种策,略,略称为n-层,预,预判,用于状,态,态空间,不,不可能,全,全部展,开,开的情,形,形，比,如,如国际,象,象棋的,状,状态数,大,大约是10120,n的值,由,由可用,的,的时间,和,和空间,资,资源而,定,定,由于叶,节,节点不,是,是博弈,的,的最终,状,状态,,不,不能用,胜,胜利或,失,失败来,标,标记,需用某,个,个启发,评,评估函,数,数的值,来,来标记,这个向,上,上传播,的,的值不,表,表示是,否,否可以,胜,胜利,,只,只表示,经,经过n,步,步可达,到,到的最,佳,佳状态,,,,也可,能,能是完,全,全误导,性,性的,大多数,博,博弈都,为,为设计,启,启发提,

49、供,供了无,限,限的想,象,象空间,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,67,,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,一种九,宫,宫游戏,的,的启发,函,函数,启发值,为,为对MAX来,说,说存在,的,的所有,可,可能胜,利,利路线,,,,减去,对,对MIN来说,存,存在的,所,所有可,能,能胜利,路,路线,X,O,X,O,X,O,X有6条,,O有5条,可能的,胜,胜利路,线,线,E(n)=6,-,-,5=1,X有4条,,O有6条,可能的,胜,胜利路,线,线,E(n)=4,-,-,6=,-,-2,X有5条,,O有4条,可能的,胜

50、,胜利路,线,线,E(n)=5,-,-,4=1,1/15/2020,68,,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,α-β,搜,搜索,单纯的,极,极小极,大,大搜索,需,需要对,搜,搜索空,间,间进行,两,两遍分,析,析,效,率,率低,α-β搜索对极小,极,极大搜,索,索进行,改,改进,基本思,想,想：不,搜,搜索预,判,判深度,的,的整个,空,空间，,对,对能判,断,断不起,作,作用的,分,分支则,去,去掉，,不,不搜索,以深度,优,优先方,式,式到达,预,预判层,，,，在不,断,断剪枝,的,的过程,中,中，向,上,上传播,评,评估值,α值是,与,与MAX节点,关,关联的

51、,不,不减小,值,值,β值是与MIN,节,节点关,联,联的不,增,增大值,1/15/2020,69,,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,α-β,搜,搜索举,例,例,MIN,MAX,MIN,MAX,2,3,5,9,0,7,4,2,1,5,6,3,9,0,7,2,6,3,0,2,3,≥2,≤3,≥5,≥2,≤0,≤2,×,×,≥,,3,×,1/15/2020,70,,双向搜,索,索,搜索可,以,以是从,初,初始状,态,态开始,向,向目标,状,状态的正向搜,索,索；,搜索也,可,可以是,从,从目标,状,状态开,始,始向初,始,始状态,的,的逆向搜,索,索,再可能,是,是同时

52、,从,从初始,状,状态向,目,目标状,态,态的正向搜,索,索和从目,标,标状态,向,向初始,状,状态的逆向搜,索,索，直至,这,这两条,路,路径在,中,中途某,处,处小结,接,接为止,，,，这种,搜,搜索策,略,略称为双向搜,索,索,第三章,一,一般,搜,搜索原,理,理3.2启发式,搜,搜索,1/15/2020,71,,消解原,理,理概述,消解原,理,理又称,为,为归结原,理,理是一,种,种重要,的,的推理,规,规则,它来源,于,于定理,证,证明：F1,∧,∧F2,∧,∧…,∧,∧Fn→W,用反证,法,法证：F=F1,∧,∧F2,∧,∧…,∧,∧Fn ∧～W为永假,等价于,证,证明：F对应,的

53、,的子句,集,集S为,不,不可满,足,足的,归结原,理,理的基,本,本思路,是,是：寻,找,找将S,扩,扩充后,的,的子句,集,集S1,，,，它可,满,满足性,与,与S相,同,同，且,容,容易判,断,断可满,足,足性，,从,从而知,道,道S的,可,可满足,性,性，则,定,定理得,证,证,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,72,,消解过,程,程,原子公,式,式和原,子,子公式,的,的否定,称,称为文,字,字,文字的,析,析取构,成,成的公,式,式称为,子,子句,若S中,存,存在空,子,子句，S为,不,不可满,足,足的,将F化,为,为对应,的,的子句,集

54、,集S,将S扩,充,充为可,满,满足性,相,相同的,子,子句集S1，,这,这个扩,充,充的过,程,程就是,归,归结的,过,过程,判断S1 是,否,否存在,空,空子句,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,73,,消解过,程,程举例,E2,∨,E1,（,（前提,）,）,～,E2,∨,E3,（,（前提,）,）,（消解,式,式）E1,∨,E3,（,（结论,）,）,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,74,,建立子,句,句集,消去蕴,涵,涵符号,：,：～P∨Q取代P,→,Q,减少否,定,定符号,的,的管辖,域,域,对变量

55、,标,标准化,消去存,在,在量词,化为前,束,束形,化为合取范,式,式：,如,如：PΛ(P∨Q）Λ(～P∨Q）,消去全,称,称量词,获得子句集,更换变,量,量名,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,75,,化子句,集,集例,例：(z),(,(x)(,,y),{,{[(P(x,),) Q(x,),)),,R(y)],,U,(,(z),},},1,,消,消蕴涵,符,符,理论根,据,据：ab,=,=>,~,~a,,b,(z),(,(x)(,,y),{,{[~(P(x,),) Q(x,),)),, R,(,(y),],]

56、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,,变,变量标,准,准化,即：对,于,于不同,的,的约束,

57、，,，对应,于,于不同,的,的变量,(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化）,原则：,对,对于一,个,个受存,在,在量词,约,约束的,变,变量，,如,如果他,不,不受全,程,程量词,约,约束，,则,则该变,量,量用一,个,个常量,代,代替，,如,如果他,受,受全程,量,量词约,束,束，则,该,该变量,用,用一个,

58、函,函数代,替,替。,(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),,,(,(cd),, (ef,),)的形式,(x,),){[,(,(~P,(,(x),,~Q(x,),)),, R,(,

59、(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,,化子句,集,

60、集例（续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,为,为任一,原,原子公,式,式，他,们,们具有,相,相同的,谓,谓词符,号,号，但,一,一般变,量,量名不,同

61、,同,已知两,子,子句L1∨α和～L2∨β,如果L1、L2具,有,有最一,般,般合一,者,者σ,那么可,得,得新子,句,句(α∨β),σ,σ,这个新子句,叫,叫做消,解,解式,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,80,,命题逻,辑,辑的消,解,解推理,举,举例,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,假言推理：P ～P∨Q (P→Q）,消解式,：Q,合并：P∨Q ～P∨Q,消解式,：Q∨Q = Q,重言式：P ∨Q ～P∨～Q,消解式,：P∨～P 或 Q∨～Q,空子句：P ～P,消解式,：NIL,三段论,：,：～P

62、∨Q,(,(P→Q）,～,～Q∨R,(,(Q→R）,消解式：～P∨R,(,(P,→,→Q）,1/15/2020,81,,谓词逻,辑,辑的消,解,解推理,举,举例,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,B(x) ～B(x)∨C(x）,消解式,：C(x),P(x)∨Q(x） ～Q[f(y)],消解式,：P[f(y)],置换,：f(y)/x,P[x,f(y)]∨Q(x)∨R[f(a),y] ～P[f(f(a)),z]∨R(z,w）,消解式,：Q[f(f(a))]∨R[f(a),y]∨R[f(y),w],置换,：f(f(a))/x, f(y)/z,1/15/20

63、20,82,,消解反,演,演求解,过,过程,消解反,演,演是利用消解原,理,理进行,命,命题证,明,明。,给定公,式,式集S和目,标,标公式L,证明公式L,的,的步骤,如,如下：,否定L，得～L,把～L添加到S中去,把新产,生,生的集,合,合{～L,S}化成子,句,句集,应用消,解,解原理,力,力图推,导,导出一,个,个表示,矛,矛盾的,空,空子句,第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,83,,命题逻,辑,辑消解,反,反演的,例,例子,设公理,集,集：,P,,(PQ),,R,,,,,(ST),,Q,,T,求证：R,子句集,：,：,(1)P,(

64、2),~,~P,,~Q,,R,(3),~,~S,,Q,(4),~,~T,,Q,(5)T,(6),~,~R（目标求,反,反）,化子句,集,集：,(PQ),,R,=>,~,~(P,,Q),,R,=>,~,~P,~,~QR,,(ST),,Q,=>,~,~ (ST,),)Q,=>,(,(~S,,~T,),)Q,=>,(,(~S,,Q),,(,~,~TQ),=>,{,{~S,,Q,,~,~T,,Q},第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,84,,命题逻,辑,辑消解,反,反演的,例,例子（,续,续）

65、,子句集,：,：,(1)P,(2),~,~P,,~Q,,R,(3),~,~S,,Q,(4),~,~T,,Q,(5)T,(6),~,~R（目标求,反,反）,归结：,(7)~P~Q,(,(2,,,, 6,),),(8),~,~Q,(,(1,7),(9),~,~T,(,(4,,,, 8,),),(10,),) nil,(,(5,,,, 9,),),第三章,一,一般,搜,搜索原,理,理3.3消解原,理,理,1/15/2020,85,,谓词逻,辑,辑消解,反,反演的,例,例子,例：,已知：IfFidogoeswhereverJohn goesand if Johnisatschool,

66、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消解原,理,理,谓词逻,辑,辑消解,反,反演的,例,例子（,续