资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.1,图搜索策略,3.2,盲目搜索,3.3,启发式搜索,3.4,消解原理,3.5,规则演绎系统,1,第三章 搜索推理技术,3.6,产生式系统,3.7,非单调推理,3.8,小结,问题,：知识表示有那些方法？知识表示的目的是什么？构建智能系统的关键是什么？,3.1,图搜索策略,思考：状态空间法的基本特点？基本推理方法？其求解结果是什么？简单回顾实例：猴子与香蕉。,2,用一个四元表列,（,W,，,x,，,Y,，,z,）,表示这个问题状态,W,猴子的水平位置,x,当猴子在箱子顶上时取,x = 1,；否则取,x = 0,Y,箱子的水平位置,z,当猴子摘到香蕉时取,z=1,；否则取,z=0,算符：,Goto,（,U,），,（,W,，,0,，,Y,，,z,）,goto,（,U,）,（,U,，,0,，,Y,，,z,）,Pushbox,（,V,），,（,W,，,0,，,W,，,z,）,pushbox,（,V,）,（,V,，,0,，,V,，,z,）,Climbbox,，,（,W,，,0,，,W,，,z,）,climbbox,（,W,，,1,，,W,，,z,）,Grasp,，,（,c,，,1,，,c,，,0,）,grasp,（,c,，,1,，,c,，,1,）,3,3.1,图搜索策略,4,(b,，,1,，,b,，,0),（,U,，,0,，,b,，,0,）,（,V,，,0,，,V,，,0,）,（,c,，,1,，,c,，,0,）,（,U,，,0,，,V,，,0,）,（,c,，,1,，,c,，,1,）,（,a,，,0,，,b,，,0,）,U=b,，,climbbox,猴子和香蕉问题的状态空间图,提问：人工搜索求解的解答？,目标状态,goto,（,U,）,goto,（,U,）,goto,（,U,）,U=b, pushbox,（,V,）,pushbox,（,V,）,goto,（,U,）,V,c,，,climbbox,V,=,c,，,climbbox,3.1,图搜索策略,5,猴子和香蕉问题自动演示：,猴子,香蕉,箱子,猴子,香蕉,箱子,Ha!Ha!,3.1,图搜索策略,思考：计算机的搜索策略？,图搜索控制策略,:,一种在图中寻找路径的方法。,图中每个节点对应一个状态,;,每条连线对应一个操作符。,图搜索过程,（,GraphSearch,）,6,3.1,图搜索策略,7,开始,把,S,放入,OPEN,表,OPEN,表为空表？,把第一个节点,(n),从,OPEN,表移至,CLOSED,表,n,为目标节点吗？,把,n,的后继节点放入,OPEN,表的末端，提供返回节点,n,的指针,修改指针方向,重排,OPEN,表,失败,成功,图,3.1,图搜索过程框图,是,是,否,否,3.1,图搜索策略,(1),(3),(4),(5),(6),(7),(7),(8),(9),OPEN,CLOSED,(1),(2),宽度优先,图搜索的一般过程如下：,1,）建立一个只含有起始节点,S,的搜索图,G,，把,S,放到一个叫做,OPEN,的,未扩展节点表,中。,2,）建立一个叫做,CLOSED,的,已扩展节点,表，其初始为空表,.,3,）,LOOP,：若,OPEN,表是空表，则失败退出。,4,）选择,OPEN,表上的第一个节点，把它从,OPEN,表移出并放进,CLOSED,表中。称此节点为节点,n,5,）若,n,为一目标节点，则有解并成功退出，此解是追踪图,G,中沿着指针从,n,到,S,这条路径,而得到的,(,指针将在第,7,步中设置,),。,8,3.1,图搜索策略,6,）扩展节点,n,，同时生成不是,n,的祖先的那些后继节点的集合,M,。把,M,的这些成员作为,n,的后继节点添入图,G,中。,7,）对那些未曾在,G,中出现过的,M,成员设置一个通向,n,的指针。把,M,的这些成员加进,OPEN,表。对已经在,OPEN,或,CLOSED,表上的每一个,M,成员，确定是否需更改通到,n,的指针方向。对已在,CLOSED,表上的每个,M,成员，确定是否需要更改图,G,中通向它的每个后裔节点的指针方向。,8,）按某一任意方式或按某个探试值，重排,OPEN,表。,9,）,GO LOOP,。,9,3.1,图搜索策略,图搜索策略,图搜索的实质是,从问题空间中找出一张包含目标节点的子图。,图搜索的结果：,1,，一个完整的搜索图,G,。,2,一个解路径,，用指针表示的解路径。,Procedure Graph Search,1 G=G,0,(G,0,=s),open=(s) /s:,初始状态,2 closed=(),3Loop:if open=() then exit(fall),4 nfirst(open) remove(n,open), add(n,closed),5 if goal(n) then exit(success),6m,j, expand(n), /m,j,不含,n,的先辈节点,7 openadd(open,，,m,j,) / m,j,不在,open,，,closed,中,2024/9/17,10,标记,m,j,每个到,n,节点指针,确定是否需要修改已在,open,，,closed,中的每个节点到,n,的指针,确定是否需要修改已在,closed,中的每个节点的后继节点原来的指针。,8,按照某种方式排列,open,表中的节点，,go loop,2024/9/17,11,2024/9/17,12,2024/9/17,13,思考：,（,1,）结果路径的形成中，为什么其节点顺序是明确的？,（,2,）,OPEN,表中的节点具有什么特点？,（,3,）,CLOSED,表中的节点具有什么特点？,（,4,）对,OPEN,表节点的排序有何意义？,提出：盲目搜索与启发式搜索。,14,3.1,图搜索策略,3.2,盲目搜索,盲目搜索又叫做,无信息搜索,，一般只适用于求解比较简单的问题。,特点：不需重排,OPEN,表；,种类：宽度优先、深度优先、等代价搜索等。,15,3.2.1,宽度优先搜索（,Breadth-first,）,定义：,以接近起始节点的程度逐层扩展节点的搜索方法。,特点：,一种高代价搜索，但若有解存在，则必能找到它。,16,S,L,O,M,F,P,Q,N,F,F,F,宽度优先搜索示意图,1,）把起始节点放到,OPEN,表中,(,如果该起始节点为一目标节点，则求得一个解答,),。,2,）如果,OPEN,是个空表，则没有解，失败退出；否则继续。,3,）把第一个节点,(,节点,n),从,OPEN,表移出，并把它放入,CLOSED,的扩展节点表中。,4,）扩展节点,n,。如果没有后继节点，则转向上述第,(2),步。,5,）把,n,的所有后继节点放到,OPEN,表的末端，并提供从这些后继节点回到,n,的指针。,6,）如果,n,的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第,(2),步。,17,宽度优先搜索算法：,3.2,盲目搜索,18,开始,把,S,放入,OPEN,表,OPEN,表为空表？,把第一个节点,(n),从,OPEN,表移至,CLOSED,表,是否有后继节点,为目标节点？,扩展,n,，把,n,的后继节点放入,OPEN,表的,末,端，提供返回节点,n,的指针,失败,成功,图,3.2,宽度优先算法框图,是,否,是,否,3.2,盲目搜索,思考：与原始算法比较异同，宽度优先的体现？,2024/9/17,19,宽度优先算法,Procedrue breadth-First-Search,1 G=G,0,(G,0,=s),open=(s),closed=() /s:,初始状态,2 Loop: if open=() then exit(fall),3 nfirst(open),4 if goal(n) then exit(success),5remove(n,open), add(n,closed),6m,j, expand(n), /m,j,不含,n,的先辈节点,7 openadd(open,，,m,j,) / m,j,不在,open,，,closed,中,2024/9/17,20,标记每个到,n,节点指针，按照节点深度递增顺序排列,open,中的节点,8 go loop,理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。,讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索策略。,2024/9/17,21,：,宽度优先例题：,由一张桌子,T,、三个积木,A,、,B,、,C,组成一个积木世界，初始状态是,A,在,B,上，,B,在桌子上，,C,在桌子上；目标状态是：,A,、,B,、,C,依次从上到下排列在桌子上。如图,2024/9/17,22,解：,1,）状态描述,（,P1,，,P2,，,P3,）表示按,A,、,B,、,C,顺序依次分别在,P1,P2,P3,上其中,Pi,是积木或者桌子。初始状态时（,B,、,T,、,T,）,目标状态 可以表示（,B,、,C,、,T,）,2,）定义操作,:move(x,y),表示将积木,x,移到,Y,上 ；,约束条件,:a X,顶部必须是空的,b,如果,Y,是积木，,Y,的顶部必须是空的,c,同一种状态出现不得多于一次。,2024/9/17,23,1,）解题过程,2,）,open,表和,closed,表,3,）节点样子画出整个图,G,和解路径,4,）程序何时结束,5,）改用深度优先如何？,例子,八数码难题（,8-puzzle problem,）,24,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,（目标状态）,（初始状态,）,规定：,将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展,26,个节点，共生成,46,个节点之后才求得解（目标节点）。,3.2,盲目搜索,25,3.2,盲目搜索,3.2.2,深度优先搜索,(Dephth-first),26,定义：,首先扩展最新产生的,(,即最深的,),节点。,特点：,防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度,深度界限。,与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在,OPEN,表的前端,。,3.2,盲目搜索,深度优先搜索示意图,27,S,L,O,M,F,P,Q,N,F,F,F,3.2,盲目搜索,28,开始,把,S,放入,OPEN,表,OPEN,表为空表？,把第一个节点,(n),从,OPEN,表移至,CLOSED,表,是否有后继节点,为目标节点？,扩展,n,，把,n,的后继节点放入,OPEN,表的,前,端，提供返回节点,n,的指针,失败,成功,图,3.6,深度优先算法框图,是,否,是,否,3.2,盲目搜索,节点,n,的深度等于最大深度？,否,2024/9/17,29,深度优先算法,Procedrue depth-First-Search,1 G=G,0,(G,0,=s),open=(s),closed=() /s:,初始状态,2 Loop:if open=() then exit(fall),3 nfirst(open),4 if goal(n) then exit(success),5remove(n,open), add(n,closed),6m,j, expand(n), /m,j,不含,n,的先辈节点,7 openadd(open,，,m,j,) / m,j,不在,open,，,closed,中,标记,m,j,每个到,n,节点指针，按照节点深度递减顺序排列,open,中的节点,8 go loop,示范：有界深度,(4),优先的八数码问题深度优先搜索树？,30,3.2,盲目搜索,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,（目标状态）,（初始状态,）,31,3.2,盲目搜索,2024/9/17,32,讨论,1,：如果问题有解，用深度优先搜索算法，是否能够找到解？,不一定,.,解空间是否有限？,讨论,2,：本算法的改进之处是,open,中节点按照深度优先排列，但是没有对深度加以控制，可能造成搜索代价太大,3.2.3,等代价搜索,33,定义,是,宽度优先搜索,的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。,搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。,算法,在等价搜索算法中，把从节点,i,到其后续节点,j,的连接弧线记为,c(I,j),把从起始节点,S,到任一节点,I,的路径代价记为,g(i),。在搜索树上，假设,g(i),也是从起始节点,S,到节点的最少代价路径上的代价。,3.2,盲目搜索,思考：如何动态计算,g,(,i,)?,34,开始,把,S,放入,OPEN,表,OPEN,表为空表？,把,具有最小,g,(,i,),值的节点,i,从,OPEN,表移至,CLOSED,表,是否有后继节点,为目标节点？,失败,成功,图,3.8,等代价搜索算法框图,是,否,是,否,令,g(s)=0,S,是否目标节点,？,是,成功,否,3.2,盲目搜索,扩展,i,，计算其后继节点,j,的,g(j),，并把后继节点放入,OPEN,表,课后例题讲解,1.,设有如图所示的一棵与,/,或树，请用与,/,或树的,宽度优先搜索,及与,/,或树的,深度优先搜索,求出解树。,35,解：（,1,）与,/,或树的宽度优先搜索,先扩展节点,A,，得到节点,B,和,C,；,再扩展节点,B,得节点,t1,、,t2,，因为,t1,、,t2,为可解节点，故节点,B,可解，从而可节点,A,可解。,所以,求得解树为：,36,（,2,）与,/,或树的深度优先搜索,先扩展节点,A,得到节点,B,和,C,；,再,扩展节点,C,得节点,D,和,t5,；,t5,为可解节点，再扩展节,D,，得节点,t3,、,t4,；,t3,、,t4,为可解节点，故节点,D,可解，因为节点,D,和,t5,可,解故,节点,C,可解，从而可节点,A,可解,。,所以求得解树为：,37,2.,下图是,5,个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从,A,城出发，经过其它各城市一次且仅一次，最后回到,A,城，请找出一条最优线路。,等代价搜索,38,3.3,启发式搜索,启发式信息：,用来加速搜索过程的问题领域信息，一般与有关问题具体领域背景有关，不一定具有通用性。,启发式搜索：,利用启发式信息的搜索方法,特点：,重排,OPEN,表，选择最有希望的节点加以扩展,种类：有序搜索、,A,*,算法等,39,基本步骤：,初始化，判断,OPEN,表是否为空，选择节点,n,，判断,n,是否目标节点，扩展节点,n,，重排,OPEN,表、调整指针，循环。,各自特点：,重排,OPEN,表的依据不同。,盲目搜索可能带来组合爆炸。,思考,： （,1,）图搜索方法的基本步骤？,（,2,）宽度优先、深度优先、等代价方法的特点？,（,3,）盲目搜索的缺点？,有序搜索（,Ordered Search,）,总是选择,“,最有希望,”,的节点作为下一被扩展节点,估价函数（,Evaluation Function,）,为获得某些节点,“,希望,”,的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上 。,f,(,n,),表示节点,n,的估价函数值,应用节点,“,希望,”,程度（估价函数值）重排,OPEN,表；有序搜索也称为,最佳优先搜索,；,估价函数举例：,（,1,）棋局的得分；,（,2,）距离目标状态的距离量度；,（,3,）,TSP,问题中的路径；,思考：,f,函数的计算，重排序的方法？,40,3.3.1,启发式搜索策略和估价函数,3.3,启发式搜索,41,3.3.2,有序搜索（,Ordered Search,；,Best,first Search,）,实质：,选择,OPEN,表上具有最小,f,值的节点作为下一个要扩展的节点,。,3.3,启发式搜索,Nilsson,（尼尔逊）方法：,一个节点的,“,希望,”,越大，则其,f,值越小。被选择的节点是估价函数最小的节点。,思考：如果把宽度优先、深度优先、等代价搜索方法作为有序搜索的特例，那么它们的,f,函数如何计算？,举例示范。,42,开始,把,S,放入,OPEN,表，计算估价函数,f,(s),OPEN,表为空表？,选取,OPEN,表中,f,值最小的节点,i,放入,CLOSED,表,i,为目标节点吗？,扩展,i,，得后继节点,j,，计算,f,(,j,),，提供返回节点,i,的指针，利用,f,(,j,),对,OPEN,表重新排序，调整亲子关系及指针,失败,成功,图,3.9,有序搜索算法框图,是,否,是,否,3.3,启发式搜索,算法,八数码难题,43,（,2,）如下的八数码难题（,8-puzzle problem,）,1,2,3,8,4,5,6,7,（目标状态）,1,2,3,8,4,5,6,7,（初始状态）,（,3,）,八数码难题的有序搜索树见下图,：,3.3,启发式搜索,（,1,）估价函数设置：,f,(,n,) =,d,(,n,) +,W,(,n,),d,(,n,),:,节点,n,的深度；,W,(,n,),:,错放的棋子数,44,3.3,启发式搜索,f,函数的重要性,有序搜索的有效性直接取决于,f,是提高搜索效率的关键；,如果,f,不准确，可能失去最佳解，也可能失去全部解；,f,一般选择策略,搜索时间与空间的折衷；,保证有解或有最佳解；,f,选择的三种典型情况：,（,1,）最优解答：状态空间中有多条解答路径，求解最优解答，如,A*,算法；,（,2,）搜索代价与解答质量的综合：问题类似于（,1,），但搜索过程可能超出时间与空间的界限。在适当的搜索实验中找到满意解答，并限制满意解答与最优解答的差异程度；如：,TSP,问题；,（,3,）最小搜索代价：不考虑解答的最优化（只有一个解答或多个解答间无差异），尽量使搜索代价最小；如：定理证明。,思考,： （,1,）,f,不能识别某些节点的真实“希望”值会怎么样？,（,2,）,f,过多估计了全部节点又会怎么样？,45,3.3,启发式搜索,3.3.3 A*,算法,思考：经过节点,n,的最佳路径，怎么表示？,怎么求解最优解答,路径,。,估价函数,f*,：对节点,n,定义,f,*,(,n,)=,g*,(,n,)+,h*,(,n,),表示从,S,开始通过节点,n,的一条最佳路径的代价。其中,g*,(,n,),表示从起始节点,S,到,n,的最佳路径，,h*,(,n,),表示从,n,到某目标节点的最佳路径。,估价函数,f,：,f,(,n,)=,g,(n)+,h,(,n,),；,其中,g,是,g*,的估计 ，,h,是,h*,的估计；,g,的一个选择就是搜索树中从,S,到,n,的这段路径的代价；显然有,g,(n),g*,(,n,),；,h,的依赖于领域的启发信息，比如八数码问题中的,W,(,n,),h,称为启发式函数；,46,3.3,启发式搜索,A,*,算法：,定义,1,在,GRAPHSEARCH,过程中，如果第,8,步的重排,OPEN,表是依据,f,(,x,)=,g,(,x,)+,h,(,x,),进行的，则称该过程为,A,算法,。,定义,2,在,A,算法中，如果对所有的,x,存在,h(x)h*(x),则称,h(x),为,h*(x),的,下界,，它表示某种偏于保守的估计。,定义,3,采用,h*(x),的下界,h(x),为启发函数的,A,算法，称为,A*,算法,。当,h=0,时，,A*,算法就变为,等代价搜索算法,。,47,A*,算法总框图,48,开始,把,S,放入,OPEN,表，记,f,=,h,OPEN=NIL?,失败,BESTNODE,是目标节点？,成功,扩展,BESTNODE,，产生,后续节点,SUCCESSOR,否,否,是,是,A*,子过程,选取,OPEN,表上未设置过的具有最小,f,值,的节点,BESTNODE,放入,CLOSED,表中,
展开阅读全文