《启发式搜索ppt课件.ppt》由会员分享，可在线阅读，更多相关《启发式搜索ppt课件.ppt（37页珍藏版）》请在三一办公上搜索。
1、启发式搜索,启发式信息加速搜索,盲目搜索的缺陷改进：根据与问题相关的知识问题，引入启发式信息。策略：从初始结点S出发，选择离目标最近的子节点扩展。定义：f(n)为经过结点n的且从起点到目标的最短路径长度的估计函数。 f(n)的值越小，表示路径越短,引入f(n)的搜索过程,f(n),f(n)？,f(n) =g(n) + h(n) g(n)表示起始结点到n的最短路径长度的估计h(n)表示n到目标结点的最短路径长度的估计g=? h=?,引入g(n) 、h(n)的搜索过程,f(n)f*(n),八数码问题,启发式搜索算法A算法,定义g(n)为已发现的初始结点到结点n所有路径中的最短路径的代价。定义h(n
2、)为结点n到目标结点的最短路径长度的估计，也称启发式函数。f(n) =g(n)+ h(n)利用f 加速搜索的算法使用Open表、Closed表,A算法伪代码,初始化open表、closed表为空，定义s为初始状态结点。计算f(s) := g(s) + h(s)。将s加入到open表中。如果open表为空，则搜索失败退出，否则从open表中取出第一个结点n，将n插入到closed表中如果n是目标结点，搜索成功，返回问题的解应用每一个可用的算子Opi ，扩展n生成子结点 mi，计算g(mi)=g(n)+ C(n, mi); f=g(mi)+h(mi);如果mi已经存在于open表中或者在close
3、d表中，且先前计算的g(mi)小于等于当前的g(mi)，那么goto 6。否则从open表或closed表中取出与mi相同的子结点mi令mi ：= mi ，将mi的父指针指向n将结点mi插入到open表，然后将open表按f值排序。goto 3,A算法数据结构,结点n需要以下属性：用于识别相同结点的标志IDg, f, h指向父结点的指针open表用优先级队列实现，并提供以下操作add_sort (open, n)get_first (open, n)search( open, n)remove(open,n)closed表的操作add (closed, n)search( open, n)re
4、move(closed,n),A算法搜索过程,演示,A搜索过程示意图,广度优先,A搜索,最优搜索算法A*算法,A*算法流程与A算法完全一样启发式函数A算法对h(n)没有任何要求A*算法要求 对每一个节点，h(n) h*(n)。例如h(n)=0解的效果A算法不保证找到最优解A*算法保证找到最优解,A*算法的可采纳性,可采纳性对任意的图，当存在初始状态s到目标节点g的路径的时候，如果搜索算法总是在s到g的最佳路径上停止搜索，则称该算法是可采纳的。A*算法是可采纳的A*算法能找到最优解吗？在什么情况下能找到最优解？,A*算法的可采纳性,稳定条件图中的每个结点的后继结点是有限的。图中的弧的代价都大于某
5、个正数 。对图中的所有结点n， h(n) h*(n) 。也就是说h (n)决不会超过实际值h* (n)定理1：如果图和h(n)具有上述稳定条件，而且从开始结点n0到目标结点有一条有限代价的路径，那么A*算法保证终止于到达目标的一条最小代价路径。,A*算法的可采纳性,引理1： 在A*终止前的每一步，总有一个结点n* ，它在Open表中，并具有一下特性： n*在到达目标的一条最优路径上A*已经发现了到达n*的一条最优路径 f (n* ) f* (n*),最优路径：n0 , n1 , ,n* , np , ,G,引理一证明（1）,数学归纳法当m=1时，也就在是算法的第一步：仅有初始结点n0被放入Op
6、en表中。令n*= n0, 因为是n0起点，所以n0必然在从n0到目标的一条最优路径上,而且g (n0)=0 ， g *(n0)=0 。故结论(1)(2)在m1时成立因为f (n*)=f(n0)=h(n0) h*(n0)=f*(n0) =f*(n*)所以结论（3）也成立,引理一证明（2）,假设当算法在第m步时，引理1成立，那么在Open表中存在某个结点n*，满足下列条件n*在到达目标的一条最优路径上A*已经发现了到达n*的一条最优路径f(n* ) f*(n*)于是，当算法处在第m+1步时，有两种情况： n*没有被扩展：这种情况下， n*没有任何变化。所以引理1成立。n*被扩展：,最优路径：n0
7、 , n1 , ,n* , np , ,G,第m+1步，n*没有被扩展，结点x被扩展,最优路径：n0 , n1 , ,n* , np , ,G,第m+1步 结点n*被扩展,引理一证明（3）,n*被扩展：它的所有后继结点都被放入Open表中。由于n*处在从n0到目标的一条最优路径上，所以它的后继结点中，至少有一个结点np在最优路径上。所以引理1的结论1成立。A*找到了从n0到np的一条最优路径。（反证法）如果存在一条到达np更好的路径，那么它也是到达目标的更好路径，这与n*处在最优路径上矛盾。所以引理1的结论2成立。,引理一证明（4）,引理1的结论3的证明由结论2可知： g(n*)=g*(n*)
8、因为 g (np) = g (n*)+cost(n*, np) g*(np) = g*(n*)+cost(n*, np)所以 g(np)=g*(np)f (np)= g(np) +h(np)= g* (np)+h (np)又因为h(np) h* (np)所以 f (np) g* (np)+h* (np)= f* (np) f (np) f* (np) = f* (n0) 引理1在算法的第m+1步也成立。根据数学归纳法，引理1成立,回顾,引理1： 在A*终止前的每一步，总有一个结点n* ，它在Open表中，并具有一下特性： n*在到达目标的一条最优路径上A*已经发现了到达n*的一条最优路径 f
9、(n* ) f* (n*)定理1：如果图和h(n)具有上述稳定条件，而且从开始结点n0到目标结点有一条有限代价的路径，那么A*算法保证终止于到达目标的一条最小代价路径。,定理一的证明（1）,A*算法必定终止（反证法）：若不会终止，那么A*会不断扩展Open表中的结点。由于每个结点的后继结点有限，所以最终会扩展到比任何深度约束更深的结点。每个边的代价都大于,于是，Open表中的所有结点的g (n)值都将超过f*(n0) ，也就是说，所有结点的f(n)都将超过f*(n0) 。这于引理1的结论3矛盾，故A*算法必定会终止,定理一的证明（2）,A*终止于一条最优路径上（反证法）：A*只能终止于第3步或
10、第5步。终止于第3步的情况只能出现在不包含任何结点的有限图中。这与已知条件“从开始结点n0到目标结点有一条有限代价的路径”矛盾。所以不可能出现这种情况。 A*必然终止于目标结点。A*终止于目标节点ng上。假如A*找到的解不是最优解，那么有 f (ng)f* (n0) 。由引理可知，在扩展到ng时，必然有一个n*在open表中，且在最优路径上，f (n*)f* (n0)。 f (ng)f* (n0) f (n*) 这与算法A*总是选择f 值小的先扩展矛盾。于是， A*终止于一条最优路径上。,A*算法的灵通性,如果A*算法的两个版本A2和A1，其差别在于，对所有的非目标结点有：h1 h2，那么A2
11、比A1更灵通定理二 如果A2比A1更灵通，那么对任意一个图，如果存在从n 0到目标结点的一条路径，在搜索终止时，被A2扩展过的结点也被A1扩展过。,最灵通的算法是hh*相同代价搜索h0爬山法 f=hA算法f=g+h广度优先搜索与相同代价搜索都是可采纳的,演示,A*算法的单调条件,单调条件（一致性条件）如果nj是ni的后继，那么h(ni) - h(nj) c (ni, nj)定理三 如果h满足单调条件，那么当A*扩展到结点n时，它已经找到了到达结点n的一条最优路径A*不需要重定向指针，对图的搜索等同于对树的搜索,单调条件演示,A*算法的改进,缺陷：有可能反复扩展同一个节点改进：设计满足单调条件的
12、启发式函数修改算法过程,如何设计可采纳的启发式函数?,根据问题特征设计h，例如八数码问题h1位置不一致的棋子数目h1 (n)=1+1+0+1+1+0+0+0=4h2所有棋子到其目标位置的距离和h2 (n)=1+2+0+1+1+0+0+0=5,目标,结点n,如何设计可采纳的启发式函数?,组合启发式函数：如果已有h1, h2 , hm等可采纳启发式函数，那么： h = max(h1, h2 , hm)从经验中学习：已知某些特征x1与x2和h有关，但不知道具体的关系，那么可以定义h=c1x1 +c2x2 通过学习调整c1与c2。ABSOLVER程序能自动生成启发式。魔方的第一个有用的启发式就是它找到的模式数据库,h(n)对搜索效率的影响,二维地图上的路径规划h1=0h2取欧氏距离h3取城市距离h4取10倍的欧氏距离h5取20倍的欧氏距离h1h2 h3 h4 h5,演示,A*算法的应用,智力游戏路径规划定理证明行动规划,其它搜索算法,h(n)=0，相同代价搜索（uniform-cost）g(n)=0，最佳优先搜索（best-first）h(n)h*(n)双向搜索迭代加深的A*（IDA*）第一个广泛应用的最优启发式算法存储受限的最优启发式算法RBFS、MA*、SMA*,作业,Page 55， 二选一（1.2 ，1.3）,
