人工智能 第三章 基本的问题求解方法

《人工智能 第三章 基本的问题求解方法》由会员分享，可在线阅读，更多相关《人工智能 第三章 基本的问题求解方法（87页珍藏版）》请在装配图网上搜索。

1、,,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,第三章,基本的问题求解方法,问题求解的过程：1）知识表示；2）针对问题，分析特征，选择合适的方法来求解（包括搜索和推理）,方法：,1）基于状态图方法-搜索；,2）基于谓词逻辑方法-推理；,3）基于结构化的知识表示方法来求解问题；,本章介绍,搜索技术,,,搜索,技,技术,是,是人,工,工智,能,能的,基,基本,技,技术,之,之一,,在,在人,工,工智,能,能各,应,应用,领,领域,中,中被,广,广泛,地,地使,用,用。,早期,的,的人,工,工智,能,能程,序,序与,搜,搜索,技,技术,联,联系,就,就

2、更,为,为紧,密,密，,几,几乎,所,所有,的,的早,期,期的,人,人工,智,智能,程,程序,都,都是,以,以搜,索,索为,基,基础,的,的。,A.Newell,和,和H,·,·A,·,·Simon-LT程,序,序,A·Newell,和,和H,·,·A,·,·Simon-GPS(GeneralProblemSolver),R.Fikes和N.Nilsson-STRIPS(StanfordResearchInstituteProblemSolver),现在,,搜,搜索,技,技术,渗,渗透,在,在各,种,种人,工,工智,能,能系,统,统中,,在,在专,家,家系,统,统、,自,自然,语,语言,理,理

3、解,、,、自,动,动程,序,序设,计,计、,模,模式,识,识别,、,、机,器,器人,学,学、,信,信息,检,检索,和,和博,奕,奕都,广,广泛,使,使用,。,。,,,搜索(search),路径,状态序列,搜索,寻找从初始状态,到,到目标状态的路,径,径;,S0,Sg,,,搜索的必要性,AI为什么要研,究,究search?,问题没有直接的,解,解法;,解方程组;,定理证明;,需要探索地求解;,,,搜索与检索的区,别,别,状态是否动态生,成,成;,检索: 静态;,在数据库中检索,某,某人的纪录;,搜索: 动态生,成,成;,下棋,,,几个问题,目标状态是否确,定,定?,确定: 定理证,明,明, ei

4、ght-puzzle,不确定: 求积,分,分, 下棋;,确定目标的性质;,问题的解: 路,径,径(解路径)/,目,目标状态;,需要路径:,下棋,不需要路径:,电路设计,需要/不需要:,诊,诊病,约束条件,目标状态不确定,时,时, 用来约束,目,目标状态的性质;,X+Y=4:,非,非整数解/整数,解,解,,,几个问题(续1),多解性;,X+Y=4:整,数,数解,最优解,评价标准/判断,准,准则;,min(x*y),北京->上海:,时,时间最短/费,用,用最少,最优解是否唯一?,下棋,,,,搜索问题,状态空间,2,,3,,7,,,,5,,1,,4,,8,,6,,1,,2,,3,,8,,,4,,7,

5、,6,,5,,,,搜索不是检索,2,,3,,7,,,,5,,1,,4,,8,,6,,1,,2,,3,,8,,,4,,7,,6,,5,,,,难点,2,,3,,7,,,,5,,1,,4,,8,,6,,1,,2,,3,,8,,,4,,7,,6,,5,,,,启发式方法,2,,3,,7,,,,5,,1,,4,,8,,6,,1,,2,,3,,8,,,4,,7,,6,,5,,,,搜索方法的评价,标,标准,搜索问题是AI,核,核心理论问题之,一,一。一般一个问,题,题可以用好几种,搜,搜索技术解决,,选,选择一种好的,搜,搜索技术对解决,问,问题的效率很有,关,关系, 甚至关,系,系到求解问题有,没,没有解。

6、 搜,索,索方法好的标准, 一般认为有,两,两个：(1)搜索空,间,间小;(2)解最佳,。,。,,,搜索分类,搜索从问题性质,上,上来看, 可分,为,为一般搜索和博,奕,奕搜索, 从处,理,理方法上来看,,可,可分为盲目搜,索,索和启发式搜索,。,。还可以分得更,细,细。,到目前为止,AI领域中已提,出,出许多具体的搜,索,索方法, 概括,起,起来有：(1)求任,一,一解路的搜索策,略,略,回溯法；爬山法(Hill Climbing)；,宽度优先法(Breadth-first)；,深,深度优先法(Depth-first),(2)求最佳解,路,路的搜索策略,大英博物馆法(BritishMuse

7、um)；最佳图搜索,法,法(A*),(3)求与或关,系,系解图的搜索法,一般与或图搜索,法,法(AO*)；,极,极小极大法(Minimax),剪,剪枝法(Alpha-beta Pruning)；启发式,剪,剪枝法(HeuristicPruning),,,,,TOPICS,回溯策略（,Backtracking,）,图搜索（GRAPHSEARCH）,无信息搜索,启发式搜索,,,TOPIC1,Backtracking,N,1,N,0,N,2,N,3,N,4,N,5,回溯策略,,,例：四皇后问题,,,( ),,,( ),Q,((1,1)),,,( ),Q,Q,((1,1)),((1,1)(2,3)),

8、,,( ),Q,((1,1)),((1,1) (2,3)),,,( ),Q,Q,((1,1)),((1,1) (2,3)),((1,1) (2,4)),,,( ),Q,Q,((1,1)),((1,1) (2,3)),((1,1) (2,4)),Q,((1,1) (2,4)(3.2)),,,( ),Q,Q,((1,1)),((1,1) (2,3)),((1,1)(2,4)),((1,1)(2,4)(3.2)),,,( ),Q,((1,1)),((1,1)(2,3)),((1,1)(2,4)),((1,1)(2,4)(3.2)),,,( ),((1,1)),((1,1)(2,3)),((1,1)(

9、2,4)),((1,1)(2,4)(3.2)),,,( ),((1,1)),((1,1)(2,3)),((1,1)(2,4)),((1,1)(2,4)(3.2)),Q,((1,2)),,,( ),((1,1)),((1,1)(2,3)),((1,1)(2,4)),((1,1)(2,4)(3.2)),Q,((1,2)),Q,((1,2)(2,4)),,,( ),((1,1)),((1,1)(2,3)),((1,1)(2,4)),((1,1)(2,4)(3.2)),Q,((1,2)),Q,((1,2)(2,4)),Q,((1,2)(2,4)(3,1)),,,Q,Q,Q,Q,( ),((1,1)),

10、((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)),,,存在问题及解,决,决办法,问题和解决方,法,法：,深度问题,对搜索深度加,以,以限制,死循环问题,状态重复:A→B,，,B→C, C,→,→A,记录从初始状,态,态到当前状态,的,的路径,,,TOPIC2GRAPHSEARCH,图搜索策略,问题的引出,回溯搜索：只,保,保留从初始状,态,态到当前状态,的,的一条路径。,图搜索：保留,所,所有已经搜索,过,过的路径

11、。,,N,5,N,1,N,0,N,2,,N,3,,N,4,,,一些基本概念,图：一个节点,的,的集合。节点,由,由弧连接起来,。,。,有向图：弧是,一,一个节点指向,另,另一个节点的,图,图，称为有向,图,图。,后继,/,父亲：如果有,一,一条弧从,n,i,指向,n,j,，则,n,j,称为,n,i,的后继，,n,i,称为,n,j,的父辈（父亲,）,）；,,,一些基本概念(续1),路径：如果存,在,在一个节点序,列,列（,n,i0,，,n,i1,，,……,，,n,ik,），,n,ij,是,n,ij-1,是的后继，,j=1,，,……,，,k,，则称这个,序,序列是从节,点,点,n,i0,到节点,n

12、,ik,的一条路径,，,，长度为,k,。,祖先/后裔,：,：如果存在,一,一条从n,i,到n,j,的路径，则,称,称n,j,是n,i,的后裔，n,i,称为n,j,的祖先。,树：每个节,点,点最多只有,一,一个父辈。,没,没有父辈的,节,节点称为根,节,节点。没有,后,后继的节点,称,称为叶节点,。,。,,,一些基本概,念,念(续2),节点深度：,根节点深度=0,其它节点深,度,度=父节点,深,深度+1,0,1,2,3,,,一些基本概念（,续,续3）,扩展一个节点,生成出该节点的,所,所有后继节点。,弧的费用,有一条弧连接n,i,和n,j,两个节点, 用C(n,i,, n,j,),表示使用规则从

13、n,i,到n,j,的费用(耗散值)。,玉泉路---天,安,安门,路径的耗散值,一条路径的耗散,值,值等于连接这条,路,路径各节点间所,有,有耗散值的总和,。,。用C(n,i,, n,j,),表示从n,i,到n,j,的路径的耗散值,。,。,,,,GRAPHSEARCH,的思路,OPEN,表,已经生成但未扩,展,展节点,CLOSED,表,已扩展节点,扩展节点,i,生成节点,j,指针,调整指针,,,图搜索（,Graph Search,）的一般过程,1、建立一个只,有,有起始节点S的,搜,搜索图G，把S,放,放入一个叫open的未扩展节,点,点表；,2、  建立已,扩,扩展节点表closed，初始,为

14、,为空；,3、  LOOP；若open,为,为空，则失败退,出,出；,4、  选open表中的第一,个,个节点，设为n,，,，移入closed表；,5、若n为目标,节,节点，则成功退,出,出，该问题的解,即,即是G中沿S指,向,向n的路径；,6、若不是目标,节,节点，则扩展n,，,，生成不是n的,祖,祖先的那些后继,节,节点的集合m，,把,把m的成员作为n的后继加入G,中,中；,7、对未曾在G,中,中出现过的m成,员,员，设一通向n,的,的指针，把它们,加,加入open表,。,。对已在closed或open表上的m成员,，,，确定是否要更,改,改到n的指针方,向,向，对已在closed上的m,

15、成,成员，确定是否,要,要更改G中通向,每,每个后裔节点的,指,指针方向。,8、按某一方式,（,（深度优先、宽,度,度优先、A,*,算法）重排open表,9、GO LOOP,,,例子,S,OPEN,CLOSE,{S},{},1,2,3,{},{S},{1,2,3},{S},{2,1,3},{S},4,5,{1,3},{S,2},{1,3,4,5},{S,2},{3,1,4,5},{S,2},{1,4,5},{S,2,3},6,{1,4,5,6},{S,2,3},,,例：右图中黑节,点,点表示已扩展，,白,白节点表示未扩,展,展，问题：先扩,展,展6号节点生成m1={4，7}，然后扩展节,点,点

16、1，生成m2={2}，按算,法,法第七步重新修,改,改原图。,6,1,2,4,5,3,难点！,！,！！算,法,法中第,七,七步,7,,,扩展节,点,点6生,成,成m1={4,，,，7},的,的调整,6,1,2,4,5,3,7,,1,2,3,5,4,6,7,×,,,再扩展,节,节点1,生,生成m2={2}的,调,调整,,1,2,3,5,4,6,7,,1,2,3,5,4,6,7,×,×,,,最终结,果,果,6,1,2,4,5,3,7,,1,2,3,5,4,6,7,,,图搜索,与,与回溯,算,算法的,区,区别,扩展节,点,点,:,回溯算,法,法:,生,生成一,个,个儿子,节,节点.,图搜索:,扩,扩

17、,展,展节点,,,生成所,有,有儿子,节,节点.,候选节,点,点:,回溯算,法,法:,一,一个.,图搜索:,多,多,个,个.,回溯:,回溯算,法,法,:,返回父,亲,亲节点.,图搜索:,不,不一定,返,返回父,亲,亲节点.,,,TOPIC3,无,无信,息,息搜索,如果在,GRAPHSEARCH,中，对,节,节点的,排,排序不,使,使用与,问,问题相,关,关的信,息,息，则,称,称为无,信,信息图,搜,搜索（,盲,盲目搜,索,索）,宽度优,先,先和深,度,度优先,,,1、breadth-firstsearch,宽度优,先,先搜索,：,：如果,搜,搜索是,以,以接近,起,起始节,点,点的程,度,度

18、依次,扩,扩展节,点,点的,。,。,搜索逐,层,层进行,；,；在对,下,下一层,的,的任一,节,节点进,行,行搜索,之,之前，,必,必须搜,索,索完本,层,层的所,有,有节点,。,。,,,(1),把,把起,始,始节点,放,放到OPEN,表,表中(,如,如果该,起,起始节,点,点为一,目,目标节,点,点，则,求,求得一,个,个解答)。,(2),如,如果OPEN是个,空,空表，,则,则没有,解,解，失,败,败退出,；,；否则,继,继续。,(3),把,把第,一,一个,节,节点(节,点,点n)从OPEN,表,表移,出,出，,并,并把,它,它放,入,入CLOSED的,扩,扩展,节,节点,表,表中,。,。

19、,(4),扩,扩展,节,节点n。,如,如果,没,没有,后,后继,节,节点,，,，则,转,转向,上,上述,第,第(2),步,步。,(5),把,把n的所,有,有后继节,点,点放到OPEN表,的,的末端，,并,并提供从,这,这些后继,节,节点回到n的指针,。,。,(6),如,如果n的,任,任一个后,继,继节点是,个,个目标节,点,点，则找,到,到一个解,答,答，成功,退,退出；否,则,则转向第(2)步,。,。,算法,,,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,★,21,22,23,24,★,26,27,28,29,30,31,1,2,3,4,5

20、,6,7,8,9,10,11,12,13,14,15,16,17,18,19,★,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,,,,,,,,,,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,搜索,演示,★,已扩展,节,节点,正,正在扩,展,展节点,扩展的,子,子节点,未,未扩,展,展节点,目标,,,宽度优,先,先法应,用,用示例,宽度优,先,先法求,九,九宫重,排,排问题,2 3,1 8 4,7 6 5,1 2 3,8 4,7 6 5,,,23,184,7

21、65,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

22、 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,,,宽度优,先,先搜索,是,是图搜,索,索一般,过,过程的,特,特殊情,况,况，将,图,图搜索,一,一般过,程,程中的,第,第8步,具,具体化,为,为本算,法,法中的,第,第6步,，,，这实,际,际是将OPEN表作,为,为“先,进,进先出,”,”的队,列,列进行,操,操作。,一定能,找,找到解,找到

23、的,解,解一定,是,是最佳,解,解,(在每个,路,路径消,耗,耗是同,样,样的意,义,义上),搜索的,空,空间大,、,、慢。,分析,,,深度优,先,先搜索,：,：首先,扩,扩展最,新,新产生,的,的(即,最,最深的)节点,。,。深度,相,相等的,节,节点可,以,以任意,排,排列。,特点：,扩,扩展最,深,深的节,点,点,使,得,得搜索,沿,沿着状,态,态空间,某,某条单,一,一的路,径,径从起,始,始节点,向,向下进,行,行下去,；,；只有,当,当搜索,到,到达一,个,个没有,后,后裔的,状,状态时,，,，它才,考,考虑另,一,一条替,代,代的路,径,径。,算法：,与,与宽度,优,优先相,似,

24、似，不,同,同在于,：,：(5),把,把n,的,的所有,后,后继节,点,点放到OPEN表的,前,前端,2、depth-first search,,,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,★,23,24,★,26,27,28,29,30,31,1,2,活结点,表,表,1,1,2,1,1,2,4,2,2,4,8,4,4,8,16,8,8,16,16,,8,17,8,8,17,17,,8,8,,4,9,4,4,9,18,9,9,18,18,,9,19,9,19,19,,,4,4,,2,5,2,2,5,10,5,5,10,20,9,9,9,

25、10,10,20,20,,10,21,10,10,21,21,,10,10,,5,11,5,5,11,★,演示,,,例,九宫重排问,题,题,8 3,6 4,7 ■5,初始状态,1 23,8 ■4,765,目标状态,,应用示例,,,23,1 84,7 65,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

26、 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,2 8 3,6 4,1 7 5,2 8 3,1 6,7 5 4,8 3,2 1 4,7 6 5

27、,2 8 3,7 1 4,6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1,2,3,4,5,6,7,8,9,a,b,d,1 2 3,8 4,7 6 5,目标,,,分析,①不一定能,找,找到解。,②解不一定,是,是最佳解。,,,3、其他方,法,法,含有深度界,限,限的深度优,先,先搜索算法,：,：,基于代价树,的,的搜索算法,：,：,,,TOPIC4,heuristicsearch,盲目搜索效,率,率低，耗费,过,过多的计算,空,空间与时间,，,，这是组合,爆,

28、爆炸的一种,表,表现形式。,利用知识来,引,引导搜索，,达,达到减少搜,索,索范围，降,低,低问题复杂,度,度的目的。,启发式方法的本质是部,分,分地放弃算,法,法"一般化, 通用化"的概念,,把,把所要解,的,的问题的具,体,体领域 的,知,知识加进算,法,法中去,,以,以提高算法,的,的效率。,,,启发式搜索：就是利用,与,与问题有关,的,的启发信息,进,进行搜索,启发信息：,与,与具体问题,有,有关的特性,信,信息,启发信息的,强,强度,强：降低搜,索,索工作量，,但,但可能导致,找,找不到最优,解,解,弱：一般导,致,致工作量加,大,大，极限情,况,况下变为盲,目,目搜索，但,可,可能

29、可以找,到,到最优解,难点：,获取；,强度的确定,；,；,,,启发信息的,用,用途,a、用于决,定,定要扩展的,下,下一节点（,避,避免盲目扩,展,展）,b、在扩展,过,过程中，用,于,于决定生成,哪,哪一个或哪,几,几个后继（,以,以免太多无,用,用节点）,C、用于决,定,定被抛弃or被修剪的,节,节点（博羿,中,中常用，其,它,它不常见）,。。。,,,基本,思,思想,启发,式,式搜,索,索过,程,程中,,要,要对OPEN,表,表进,行,行排,序,序,,这,这,就,就需,要,要有一,种,种方,法,法来,计,计算,待,待扩,展,展节,点,点有,希,希望,通,通向,目,目标,节,节点,的,的不,

30、同,同程,度,度,,我,我们,总,总是,希,希望,能,能找,到,到最,有,有希,望,望通,向,向目,标,标节,点,点的,待,待扩,展,展节,点,点优,先,先扩,展,展。,希望,的,的量,度,度就,是,是通,过,过估,价,价函,数,数f,（,（n,）,）来,描,描述,的,的,,,,估价,函,函数,：,：定,义,义为,从,从初,始,始节,点,点经,过,过n,节,节点,到,到达,目,目的,节,节点,的,的路,径,径的,最,最小,代,代价,的,的估,计,计值,，,，,X,W,Z,g(X),h,(X),估价,函,函数,的,的形,式,式为f(n)=g(n)+h(n),g（n）,—,—是到目,前,前为,止,

31、止,,从,从s,到,到n,的,的最,小,小路,径,径（实,际,际值,）,）,h（n）,—,—n节,点,点到,目,目标,节,节点,最,最佳,路,路径,的,的估,计,计值,，,，体,现,现了,启,启发,信,信息,通常f（n）,由,由经,验,验和,直,直觉,得,得到,的,的，,有,有很,多,多种,取,取法,，,，关,键,键在,于,于h,（,（n,）,）。,,,e．g．八数码,难,难题的估价函数,f（n）=g（n）+h（n）,d（n）：节点n的深度,w（n）：不在,位,位的数字个数,p（n）：不在,位,位的数字离目标,的,的距离之和,例：右图（a）,中,中2、8、1、6不在位，w（n）=4 ，p,（,

32、（n）=1+2+1+1=5；,（,（b）6、8、2、1不在位，w（n）=4,，,，p（n）=3+2+2+2=9,2 8 3,1 6 4,7 5,6 8 3,2 1 4,7 5,a b c,8 1 2,6 3,7 5 4,,,s（n）：沿着,周,周围那些非中心,方,方格上依顺时针,方,方向检查n格局,中,中每一将牌，如,果,果其后紧跟的将,牌,牌正好是目标格,局,局中该将牌的后,续,续者，则该将牌,得,得0分，否则得2分；在中中方,格,格上有将牌得1,分,分

33、，无得0分；,将,将所有将牌得分,之,之和即为s（n,）,）。图（c）中s（a）=6。,2 8 3,1 6 4,7 5,6 8 3,2 1 4,7 5,a b c,8 1 2,6 3,7 5 4,,,例子:eight-puzzle,评价函,数,数,f(n) =d(n)+ W(n),d(n):,节,节点n,的,的深度;,W(n):与,目,目标相,比,比,,错,错位的,数,数字数,目,目，即,不,不在位,的,的数字,个,个数;,1,,2,,3,,8,,4,,7,

34、,6,5,,2,,8,,3,,1,6,,4,,7,,,,5,,初始状,态,态,目标状,态,态,,,283,164,75,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 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 3,1 8 4,7

35、6 5,2 3,1 8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3,7 8 4,6 5,s(4),A(6),B(4),C(6),D(5),E(5),F(6),G(6),H(7),I(5),J(7),K(5),L(5),M(7),目标,1,2,3,4,5,6,,,由前例,看,看出,,与,与深,度,度优先,搜,搜索和,宽,宽度优,先,先搜索,相,相比较, 启,发,发式搜,索,索大大,减,减少了,搜,搜索范,围,围,,大,大大减,少,少了扩,展,展的节,点,

36、点,,大,大大减,少,少了生,成,成的节,点,点,,从,从而达,到,到降低,问,问题复,杂,杂度,,提,提高,算,算法的,效,效率的,目,目的。,,,估价函,数,数的进,一,一步说,明,明,n,S,g*(n),h*(n),g,f*(n)=g*(n)+h*(n)：,从s经,过,过n到g的最,短,短路径,g*(n),：,：从s到n,的,的最短路径,h*(n),：,：从n到g,的,的最短路径,f（n）=g（n）+h（n）：,从,从s经过n,到,到g的最短,路,路径的估计,值,值,g(n)、h(n),分别是g*(n)、h*(n),的,的估计值,,,g(n),一般,取实际走过,的,的路径的费,用,用和.

37、,g(n),,g*(n),随着算法的,执,执行，由于指针的,变,变动，,g(n),会下降.,h,,0,没有启发式,信,信息;,,,启发式搜索,算,算法,A算法,A*算法,,,A,算法,在Graphsearch过程中,，,，如果第8,步,步的重排open表是,依,依据f（n,）,）=g（n,）,）+h（n,）,）进行的，,则,则称该过程,为,为A算法。,g(n)取,实,实际走过的,路,路径的费用,和,和;,节点排序是,按,按照f(n)从小到大,排,排;,如前例-九,宫,宫重排问题,,,算法A*,在A算法中,，,，如果满足,条,条件：,0≤h(n)≤h*(n),则A算法称,为,为A*算法,。,

38、。,称h（x）,为,为h*（x,）,）的下界，,它,它表示某种,偏,偏于保守的,估,估计。,启发式搜索,算,算法A*又,称,称为最佳图,搜,搜索算法(Optimal Search),。,。,,,,5、经典例,题,题（八数码,难,难题）：,设有八数码,难,难题，起始,状,状态如右图,，,，要求找出,九,九宫重排的,最,最终解路径,，,，并画框图,。,。,2 83,1 64,75,,,解法一：,第一步：取,估,估价函数为f（n）=d（n）+w（n），,则,则显然按照,定,定义1它是A算法；,第二步：因,为,为w（n）,指,指的是不在,位,位的个数，,所,所以w（n,）,）=4，即,估,估计

39、只需要,走,走4步即可,到,到达目标状,态,态，而实际,上,上要到达目,标,标状态肯定,要,要大于3步,，,，即w（x,）,）≤w,*,（x），满,足,足定义，所,以,以是A,*,算法；,第三步：画,图,图，并计算,各,各个状态f,（,（n）的值,，,，取f（n,）,）值最小的,节,节点进行扩,充,充。,(图见前),,,解法二：取,估,估价函数为f（n）=d（n）+P（n），,同,同理也是A*算法；,如图,,,,,TipsA算法,与,与A*算,法,法区别,区别在于,在,在A*算,法,法中，0≤h(n)≤h*(n),示例：,八数码难,题,题中,h(n),的,的三种定,义,义,h(n)=w(n),

40、 h(n)=p(n)-A*算,法,法,h(n)=p(n)+3s(n)-A算法,,,A*算法,具,具有可采,纳,纳性,一般地说,对,对任意一,个,个图,,当,当s到目,标,标节点有,一,一条路径,存,存在时,,如,如果搜,索,索算法总,是,是在找到,一,一条从s,到,到目标节,点,点的最佳,路,路径上结,束,束, 则,称,称该搜索算法是可,采,采纳的(Admissibility)。,A*就具,有,有可采纳,性,性,即当问题,有,有解时,A*一,定,定能找到,一,一条到达,目,目标节点,的,的最佳路,径,径。（why？）,证明见参,考,考资料-A*算法,具,具有可采,纳,纳性,考虑h(n)≡0,的

41、,的情况！,！,！！！,,,A*算法,的,的理论意,义,义,A*算法,的,的理论意,义,义在于给,出,出了求解,最,最佳解的,条,条件,h(n),≤,≤ h*(n),对给定的,问,问题,函,数,数h*(n)在问,题,题有解的,条,条件下客,观,观上是存,在,在的。但,在,在问题求,解,解过程中,不,不可能都,明,明确知道,。,。因此,,对,对实际,问,问题,,能,能不能使,所,所定义的,启,启发函数,满,满足下界,范,范围条件? 这是,个,个问题。,如,如果困难,很,很大,,那,那未A*,算,算法的实,际,际应用就,会,会受到限,制,制。,,,以前面-八数,码,码难题为例,定义h(n),为,为

42、任意节点与,目,目标之间的差,异,异,若取= w(n)(将牌不,在,在位个数),,那,那未很容易,看,看出, 尽管,我,我们对具体的h*(n)是,多,多少很难确切,知,知道, 但根,据,据“不在位”,将,将牌个数这个,估,估计, 就能,得,得出至少要移动W(n)步才能到达目标, 显然有h(n) =W(n)≤h*(n)。,进一步考虑任,意,意节点与目标,之,之间距离的信,息,息, 即取h(n) =p(n),p(n)定义,为,为每一个将牌,与,与其目标位置,之,之间距离(不,考,考虑夹在其间,的,的将牌)的总,和,和,那未同样,能,能断定至少也要移动p(n)步才能达到目标,，,，仍然有P(n)≤

43、h*(n)。,,,启发信息的强,度,度的进一步分,析,析,强：降低搜索工作,量,量，但可能导致,找,找不到最优解,弱：一般导致工作,量,量加大，极限,情,情况下变为盲,目,目搜索，但可能可以,找,找到最优解,,,h(n)取不,同,同函数时的八,数,数码难题求解,情,情况进行比较, 比较h(n) = 0,、,、h(n)= W(n),和,和h(n)= p(n),三,三种情况的求,解,解结果。,①,①h(n) = 0: 即启发函,数,数启发信息为0, f(n) = h(n) + g(n) =g(n)＝,d(n)(搜,索,索深度),,此,此实际上是宽,度,度优先搜索。,②,② h(n) = W(n):

44、 即启,发,发函数取将牌,不,不在位的信息, f(n)= h(n) + g(n) = W(n) +d(n) (,搜,搜索深度)。,③,③ h(n)= p(n): 即启发,函,函数取每一个,将,将牌与其目标,位,位置之间距离,的,的总和的信息,,,实际上①中h(n) =0,≤,≤h*(n)，,②和③均已证,明,明W(n)≤h*(n)，P（n）≤h*(n)，即3种算法都是A*算法。,比较搜索空间,，,，分析启发信息,强,强弱的效果：,启发函数,h(n) = 0,h(n) = W(n),h(n) = p(n),扩展节点数,26,6,5,生成节点数,46,13,11,,,附：评价搜索,算,算法的指标,

45、1、外显率（Penetrance）,P=L/T,L — 从初,始,始状态到目标,状,状态的长度；,T — 从初,始,始状态到目标,状,状态所产生的,所,所有状态的个,数,数；,显然P=1时,，,，说明有效路,径,径所经历的节,点,点都有用,,,2、有效分支,数,数（EffectiveBranching Factor）,B —搜索过,程,程中，平均每,个,个节点产生的,分,分支数目；,因为每个节点,产,产生的平均分,支,支数为B，所,以,以从初始到目,标,标状态产生的,总,总分支数T为,：,：,,,本章回顾,教学内容：本,章,章在上一章知,识,识表示的基础,上,上研究问题求,解,解的方法，是,人,人工智能研究,的,的又一核心问,题,题。本章主要,介,介绍基本的搜,索,索技术,教学重点：图,搜,搜索策略、启,发,发式搜索,教学难点：启,发,发式搜索,教学方法：课,堂,堂教学为主，,辅,辅以恰当的实,验,验。注意结合,前,前面所学知识,表,表示的基础内,容,容，将其与问,题,题求解方法融,为,为一体。,教学要求：重,点,点掌握一般图,搜,搜索策略，掌,握,握各种搜索方,法,法，尤其是启,发,发式搜索中的A*算法。,,,homework,选做：利用,A*算法求解,九,九宫重排问题,。,。,要求：同前,---- THE END ----,,,