第3章(搜索推理技术2图启发搜索)课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人 工 智 能,Artificial Intelligence(AI),人 工 智 能,1,第,3,章 搜索推理技术,3.1 图的搜索策略,3.2,盲目搜索,3.,3,启发式搜索,3.,4,与或树搜索（,补充,）,3.,5,博弈树搜索（,补充,）,3.,6,消解原理,第3章 搜索推理技术 3.1 图的搜索策略,2,3.,3,启发式搜索,宽度和深度优先搜索的,缺点,：,扩展节点的顺序是人为规定的，要扩展节点的数目可能非常大，占用大量的计算时间和内存空间，使得搜索效率低,3.3 启发式搜索宽度和深度优先搜索的 缺点：,3,等代价搜索技术的,缺点,选取已经搜索到的代价最小的节点来扩展，但是没有考虑目标状态，不知道离目标状态还有多远，还需要付出多大的代价,等代价搜索技术的 缺点,4,提高搜索效率的,思路,：,利用更多的与问题有关的信息来选取待扩展的节点,提高搜索效率的 思路：,5,3.,3.1,启发式搜索策略和估价函数,启发信息（背景知识）,：与具体问题特性有关的一些信息。（在具体的使用过程中，还与使用人、算法有关）,启发式搜索方法,：利用启发信息的搜索方法,3.3.1 启发式搜索策略和估价函数启发信息（背景知识）：,6,用于决定要扩展的下一个节点,，避免宽度优先或深度优先搜索中的盲目（人为规定）地选择扩展节点,在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，避免盲目地同时生成所有可能的后继节点,用于决定某些应该从搜索树中抛弃或修剪的节点,搜索技术中启发信息的用途,：,用于决定要扩展的下一个节点，避免宽度优先或深度优先搜索中,7,本节的关注点,：,利用启发信息来决定下一个要扩展的节点,本节的关注点：,8,有序搜索,：,在搜索过程总是选择“,最有希望,”的节点作为下一个被扩展节点的搜索技术,估价函数,：用来估算节点“,希望,”程度的函数,有序搜索：在搜索过程总是选择“最有希望”的节点作为下一个,9,一般情况下，估计函数值越大，希望程度就越低,根据搜索过程、问题的启发信息来定义的，对搜索效率会产生较大的影响,希望,估价函数,估价函数的基本特性,：,一般情况下，估计函数值越大，希望程度就越低希望估价函数估价函,10,用,f,(,n,),表示节点,n,的估价函数值，并且期望，它是从起始节点、通过节点,n,、,到达目标节点的最小代价的一个,估计值,起始节点,节点,n,目标节点,用 f(n)表示节点 n 的估价函数值，并且期望,11,计算一个节点的“,估价函数,”，可以分成两个部分：,已经付出的代价（,起始节点到当前节点,）,将要付出的代价（,当前节点到目标节点,）,估价函数的计算,起始节点,当前节点,目标节点,计算一个节点的“估价函数”，可以分成两个部分：估价函数,12,节点,n,的估价函数,f,(,n,),定义为从初始节点、经过,n,、,到达目标节点的路径的最小代价的估计值，即,f,(,n,)=,g,(,n,)+,h,(,n,),g,(,n,),是从初始节点到达当前节点,n,的,实际代价,h,(,n,),是从节点,n,到目标节点的最佳路径的,估计代价,节点,n,目标节点,起始节点,g,(,n,),h,(,n,),节点 n 的估价函数 f(n)定义为从初始节点,13,h,(,n,),体现出搜索过程中采用的启发式信息（背景知识），称之为,启发函数,g,(,n,),所占的比重越大，越趋向于宽度优先或等代价搜索；反之，,h,(,n,),的比重越大，表示启发性能就越强,f,(,n,)=,g,(,n,)+,h,(,n,),h(n)体现出搜索过程中采用的启发式信息（背景知识）,14,对于具体问题来说，根据问题的本质及解的性质，可以定义多种估价函数。,用不同的估价函数指导搜索，其效果可能会相差很远。,因此，必须尽可能选择最能体现问题特性的、最佳的估价函数,对于具体问题来说，根据问题的本质及解的性质，可以定义多种估价,15,例：,八数码问题的估价函数,f,(,n,)=,g,(,n,)+,h,(,n,),g,(,n,),定义为搜索树中,n,的深度,h,(,n,),可以定义成不同形式,例：八数码问题的估价函数,16,节点,n,的状态与目标状态之间数字不在位的个数（错放棋子的个数，不记空格）,目标状态,当前状态,节点 n 的状态与目标状态之间数字不在位的个数（错放棋,17,节点,n,中每一个数字与目标位置最短距离（每一个数字走到目标位置的要走的最少步数）之和,目标状态,当前状态,节点 n 中每一个数字与目标位置最短距离（每一个数字走到,18,把中心位置除掉，沿顺时针方向，如果一个数字的跟随数字是目标状态中的数字，则记,0,分，否则记,2,分。中心位置有数字记,1,分，无数字记,0,分。所有的总和为,h,(,n,),目标状态,当前状态,例：数字,2,的跟随数字是,1,，而目标状态的数字应该是,8,把中心位置除掉，沿顺时针方向，如果一个数字的跟随数字是目,19,有序搜索算法（方法、技术）,在搜索过程中，,OPEN,表中节点按照其估价函数值以递增顺序排列，选择,OPEN,表中具有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为,有序搜索,有序搜索算法（方法、技术）,20,这里，介绍尼尔逊,(,Nilsson),提出的有序搜索的基本算法：,有序状态空间搜索算法,3.,3.2,有序搜索,这里，介绍尼尔逊(Nilsson)提出的有序搜索的基本算法：,21,(1),把起始节点,S,放到,OPEN,表中，并计算节点,S,的,f,(S),(2),如果,OPEN,是空表，则失败退出（无解）,有序状态空间搜索算法,：,(1)把起始节点 S 放到 OPEN 表中，并计算节点 S,22,(3),从,OPEN,表中选择一个,f,值最小的节点,i,。,如果有几个节点值相同，当其中有一个为目标节点时，则选择目标节点；否则就选择其中任一个节点作为节点,i,(3)从 OPEN 表中选择一个 f 值最小的节点 i,23,(4),把节点,i,从,OPEN,表中移出，并把它放入,CLOSED,的已扩展节点表中,(5),如果,i,是个目标节点，则成功退出（有解）,(6),扩展节点,i,，,生成其全部后继节点。对于,i,的每一个后继节点,j,：,(4)把节点 i 从 OPEN 表中移出，并把它放入 CL,24,说明：,节点,j,可以分成三种情形,：,新产生的节点，即不属于,OPEN,表又不属于,CLOSED,表（6-1、6-2步）,已经产生过的节点，且属于,OPEN,表，其已经有父节点（6-1、6-3、6-3-1、6-3-2步）,已经产生过的节点，且属于,CLOSED,表，其已经有父节点和后继节点（6-1、6-3、6-3-1、6-3-2、6-3-3步),说明：节点 j 可以分成三种情形：,25,CLOSED,表,OPEN,表,有父节点,既父节点又有子节点,CLOSED表OPEN表有父节点既父节点又有子节点,26,(6-1),计算,f,(,j,),(6-2),如果,j,既不在,OPEN,表中，又不在,CLOSED,表中，则用估价函数,f,把它加入,OPEN,表相应位置。从,j,加一个指向其父辈节点,i,的指针，以便于反向追踪解的路径,(6-1)计算 f(j),27,(6-3),如果,j,已在,OPEN,表（,处理与父节点的关系,）或,CLOSED,表（,处理与父节点和子节点的关系,）中，则比较新的,f,(,j,),值和前面计算出来的,f,(,j,),值。如果新的,f,(,j,),值较小，则,(6-3)如果 j 已在 OPEN 表（处理与父节点的关,28,(6-3-1),用新的值取代旧的值,(6-3-2),改变指针，从,j,指向,i,，,删除原来的父辈节点指针,(6-3-3),如果节点,j,在,CLOSED,表中，则把它移回,OPEN,表,(7),转向,(2),(6-3-1)用新的值取代旧的值,29,旧,CLOSED,表,OPEN,表,新,新,新小旧大,X,X,移回,旧CLOSED表OPEN表新新新小旧大XX移回,30,对于图的搜索，一个节点可能有多个父节点，这一步可以保证具有最小估价函数值的节点当作父节点，同时使得搜索得到的子图总是一棵树,对于树的搜索，任何节点（除起始节点）只有一个父节点，则可以省略这一步,步骤6-3的说明,对于图的搜索，一个节点可能有多个父节点，这一步可以保证具有最,31,后继节点,j,新,节点,在,Open？,在,Closed？,新,f,值小,调整父节点,新,f,值小,调整父节点,移回,Open,自动删除子节点,后继节点 j新在在新 f 值小新 f 值小,32,如果,f,(,i,),取节点,i,的深度，这时就是宽度优先搜索,如果,f,(,i,),取从起始节点到当前节点,i,之间路径的代价，这时就是等代价搜索,有序搜索算法的特例,：,如果 f(i)取节点 i 的深度，这时就是宽度优先搜,33,例：,八数码问题,估价函数为：,f,(,n,)=,d,(,n,)+W(,n,),其中:,d,(,n,),：,节点,n,的深度,W(,n,),：,即,h,(,n,),节点,n,中错放的棋子个数,例：八数码问题,34,2,8,3,1,6,4,7,5,4,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,8,3,1,6,4,7,5,6,4,6,空,1,2,3,4,2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,8,3,1,4,7,6,5,6,5,5,8,3,2,1,4,7,6,5,2,8,3,7,1,4,6,5,6,7,2,3,1,8,4,7,6,5,2,3,1,8,4,7,6,5,5,7,2,3,1,8,4,7,6,5,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,5,7,5,目标节点,283164754283164752831476528316,35,带圆圈的数字表示估价函数的值,不带圆圈的数字表示扩展顺序,相同值时，同一次扩展按先后顺序排放，否则后扩展的节点放在前面,深度,带圆圈的数字表示估价函数的值相同值时，同一次扩展按先后顺序排,36,第3章(搜索推理技术2图启发搜索)课件,37,每一个状态的存储形式,：,状态空间法,：长度为9的一维数组,父,符,1,2,3,8,0,4,7,6,5,盲目搜索中,：长度为11的一维数组,1,2,3,8,0,4,7,6,5,启发搜索中,：长度为14的一维数组,父,符,1,2,3,8,0,4,7,6,5,d,(,n,)+W(,n,)=,f,(,n,),每一个状态的存储形式：状态空间法：长度为9的一维数组父符12,38,例：,迷宫,人,4,3,2,1,代价,：关键位置点之间的水平与垂直距离之和,g,:,起始位置到当前位置之间的已经走过的距离,h,:,当前位置到目标位置的水平与垂直距离之和,例：迷宫人4321代价：关键位置点之间的水平与垂直距离之和,39,人,4,S,3E,2,N,1,W,(1,1),0,+,6,N3,(2,3),3,+,3,(2,4),4,+,2,N1,S1,(2,2),4,+,4,(1,4),5,+,3,(3,4),5,+,1,W1,E1,(3,3),6,+,2,(4,4),6,+,0,E1,S1,人4S3E2N1W(1,1)0+6N3(2,3)3+3(,40,思考题,对于下列迷宫，用,有序搜索算法,寻找出从入口到出口的一条路径,代价,：,关键位置之间的路程，其中,=3.0,g,:,起始位置到当前位置的已经走过的距离,思考题对于下列迷宫，用有序搜索算法寻找出从入口到出口的一条路,41,假设,：通道是放射状的直线和圆弧,h,:,当前位置到目标位置的直线和圆弧距离之和的最小值,假设：通道是放射状的直线和圆弧,42,3.,3.3,A*,算法,特殊的估价函数（对估价函数作出某些规定）,h,(,n,),h,*(,n,),最佳的启发函数值,有序算法的