人工智能及应用-ch5-2ppt课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,.,*,搜索方法,启发式搜索,.,启发式搜索,前面讨论的搜索策略中没有考虑问题本身的特性信息，而只是按事先规定的路线进行搜索。,如果在搜索过程中使用在搜索过程中获得的问题自身的一些特性信息来指导搜索显然会有利于搜索。我们将利用问题自身特性信息来引导搜索过程的搜索方法称为启发式搜索。,.,启发性信息的作用,启发性信息对搜索的指导作用可归纳为3个方面。,选择下一个要被扩展的结点。,在结点扩展时，选择有用的结点。,修剪掉某些不可能导致搜索成功的结点。,.,估价函数,启发信息在搜索过程中的主要作用是对结点的重要性进行评估，通过这个评估来实现OPEN表中结点的排序,这个评估一般是通过估价函数实现的。,.,估价函数,估价函数f(n)的一般形式为：,f(n)=g(n)+h(n),其中：,结点n是搜索图中当前被扩展的结点。,f(n)是从初始状态经由结点n到达目标结点的所有路径中最小路径代价的估计值。,g(n)是从初始结点到结点n的实际代价。,h(n)是从结点n到达目标结点的最优路径的估计代价。,.,估价函数示例,例：八数码问题。设初始状态和目标状态如下图，且估价函数为：f(n)=d(n)+w(n),其中：d(n)表示结点的结点深度；w(n)表示结点n不在位的数码个数。请计算初始状态的估价函数值。,2 3,1 8 4,7 6 5,2 3,8 4,7 6 5,S,0,S,g,.,估价函数示例,解：此例估价函数中有,g(n)=d(n)-路径的深度代表实际代价；,h(n)=w(n)-不在位数码说明结点与目标的差距。,f(,S,0,)=d(,S,0,)+w(,S,0,)=0+4=4,.,A算法,在一般图搜索算法中，如果每一步都利用估价函数f(n)=g(n)+h(n)对OPEN表中的结点进行排序，则称该搜索算法为A算法。,由于估价函数带有问题自身的启发性信息，所以A算法也是启发式搜索算法。,.,A算法-全局择优搜索,产生一个仅有初始结点,S,0,的,OPEN,表，建立一个,仅有初始结点,S,0,的图,G,置,S,0,的估价函数,f(S,0,)=g(S,0,)+h(S,0,),；,产生一个空的,CLOSED,表；,如果,OPEN,表为空，则失败退出；,在,OPEN,表的首部取一个结点,n,，将其放入,CLOSED,表，在,OPEN,表删除结点,n,；,.,A算法-全局择优搜索,考察结点,n,是否为目标结点，若是，则得到问题的解，成功退出；,若结点不可扩展，则转第,3,步；,扩展结点,n,，计算子结点的,f(ni,),并为每一个子结点指定父结点,将子结点放入,OPEN,表中；,按估价函数为,OPEN,表中的结点排序，转第,3,步。,.,A算法-全局择优搜索,例：八数码问题。设初始状态和目标状态如下图，且估价函数为：f(n)=d(n)+w(n),其中：d(n)表示结点的结点深度；w(n)表示结点n不在位的数码个数。请使用全局择优搜索求解问题。,2 3,1 8 4,7 6 5,2 3,8 4,7 6 5,S,0,S,g,.,A算法-全局择优搜索,解：搜索图为,2 3,1 8 4,7 6 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,1 2 3,8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,1 2 3,8 4,7 6 5,S,0,S,g,S,1,S,2,S,3,S,4,S,5,S,6,S,7,S,8,4,4,4,6,4,6,7,7,1 2 3,7 8 4,6 5,6,3,.,A算法-局部择优搜索,产生一个仅有初始结点,S,0,的,OPEN,表，建立一个,仅有初始结点,S,0,的图,G,置,S,0,的估价函数,f(S,0,)=g(S,0,)+h(S,0,),；,产生一个空的,CLOSED,表；,如果,OPEN,表为空，则失败退出；,在,OPEN,表的首部取一个结点,n,，将其放入,CLOSED,表，在,OPEN,表删除结点,n,；,.,A算法-局部择优搜索,考察结点,n,是否为目标结点，若是，则得到问题的解，成功退出；,若结点不可扩展，则转第,3,步；,扩展结点,n,，计算子结点的,f(ni,),并为每一个子结点指定父结点,按估价函数将子结点排序，并放入,OPEN,表的首部，转第,3,步。,.,关于A算法,全局择优搜索：当f(n)=g(n)，算法退化为代价树广度优先搜索；f(n)=d(n)，算法退化为广度优先搜索。,局部择优搜索：当f(n)=g(n)，算法退化为代价树深度优先搜索；f(n)=d(n)，算法退化为深度优先搜索。,.,A*算法,设f*(n)是从初始状态经由结点n到达目标结点的所有路径中最小路径代价值，f(n)是它的估计值。则f*(n)应由两部分组成：,g,(n)是从初始结点到结点n的最小代价。,h(n)是从结点n到达目标结点的最优路径的代价值，有多个目标结点时取其代价最小者。,所以 f*(n)=,g,(n)+h(n),.,A*算法,对A算法-全局择优搜索中的增加如下限制：,g(n,),是对,g*(n),的估计，并且,g(n,)0,h(n,),是,h*(n),的下界，即对任意结点都有,h(n,)h1(n),则被A2*扩展的结点一定被A1*扩展。,.,A*算法的最优性,如果启发函数满足以下两个条件：,h(,目标结点,)=0,对任意结点,n,和它的子结点,m,，都有,0,h(n)-h(m),C(n,m,),C(n,m,),是结点到其子结点的边代价，则称,h(n,),满足单调限制。,.,A*算法的最优性,结论：如果h满足单调条件，则当A*算法扩展结点n时，该结点就已经找到通往它的最佳路径，即g(n)=g*(n),.,A*算法-示例,例：八数码问题。设初始状态和目标状态如下图，且估价函数为：f(n)=d(n)+w(n),其中：d(n)表示结点的结点深度；w(n)表示结点n不在位的数码个数。请使用A*算法求解问题。,2 3,1 8 4,7 6 5,2 3,8 4,7 6 5,S,0,S,g,.,A*算法-示例,解：在前一个例中取,h(n)=w(n),w(n)表示结点n不在位的数码个数,显然有 w(n)h*(n),即例中的A算法也是A*算法。,.,A*算法-示例,还可以选择h(n)=P(n)，其中是每一个数码与其目标位置的距离之和，则有：,P(n)h*(n),.,2 3,1 8 4,7 6 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,1 2 3,8 4,7 6 5,1 2 3,8 4,7 6 5,S,0,S,g,S,1,S,2,S,3,S,4,S,5,S,8,3,3,6,5,3,1 2 3,7 8 4,6 5,3,5,.,