启发式搜索ppt课件.ppt

《启发式搜索ppt课件.ppt》由会员分享，可在线阅读，更多相关《启发式搜索ppt课件.ppt（37页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、启发式搜索 启发式信息加速搜索 盲目搜索的缺陷根据与问题相关的知识问题，引入启发式信息。从初始结点S出发，选择离目标最近离目标最近的子节点扩展。经过结点n的且从起点到目标的最短路径长度的估计函数。 f(n)的值越小，表示路径越短引入的搜索过程f(n)=g + g表示起始结点到n的最短路径长度的估计表示n到目标结点的最短路径长度的估计)(ng)(nh引入的搜索过程)()()(nhngnf)(* ng)(* nh)(*)( )(*)(*)(* )(*)(*)(*nfnfnhngnfnnfnnhnng的最短路径的代价是经过结点到目标最短路径的代价是结点的最短路径的代价是初始结点到结点八数码问题数为位

2、置不正确的数字个令的深度为初始结点到结点令)()(nhnng1)(nh启发式搜索算法A算法 定义g(n)为已发现已发现的初始结点到结点n所有路径中的最短路径的代价。 定义h(n)为结点n到目标结点的最短路径长度的估计，也称启发式函数。 f(n) =g(n)+ h(n) 利用f 加速搜索的算法 使用Open表、Closed表A算法伪代码1.初始化open表、closed表为空，定义s为初始状态结点。2.计算f(s) := g(s) + h(s)。将s加入到open表中。3.如果open表为空，则搜索失败退出，4.否则从open表中取出第一个结点n，将n插入到closed表中5.如果n是目标结点，

3、搜索成功，返回问题的解6.应用每一个可用的算子Opi ，扩展n生成子结点 mi，a)计算g(mi)=g(n)+ C(n, mi); f=g(mi)+h(mi);b)如果mi已经存在于open表中或者在closed表中，且先前计算的g(mi)小于等于当前的g(mi)，那么goto 6。否则从open表或closed表中取出与mi相同的子结点mic)令mi ：= mi ，将mi的父指针指向nd)将结点mi插入到open表，然后将open表按f值排序。7.goto 3A算法数据结构 结点n需要以下属性： 用于识别相同结点的标志ID g, f, h 指向父结点的指针 open表用优先级队列实现，并提供

4、以下操作 add_sort (open, n) get_first (open, n) search( open, n) remove(open,n) closed表的操作 add (closed, n) search( open, n) remove(closed,n)A算法搜索过程openclosed1S=02A=4,B=8S3C=5,D=7,B=8S,A4D=7,B=8S,A,C5G=8,B=8S,A,C,D演示A搜索过程示意图广度优先A搜索最优搜索算法A*算法 A*算法流程与A算法完全一样 启发式函数 A算法对h(n)没有任何要求 A*算法要求 对每一个节点，h(n) h*(n)。例如

5、h(n)=0 解的效果 A算法不保证找到最优解 A*算法保证找到最优解A*算法的可采纳性 可采纳性 对任意的图，当存在初始状态s到目标节点g的路径的时候，如果搜索算法总是在s到g的最佳路径上停止搜索，则称该算法是可采纳的。 A*算法是可采纳的 A*算法 能找到最优解吗？ 在什么情况下能找到最优解？A*算法的可采纳性 稳定条件 图中的每个结点的后继结点是有限的。 图中的弧的代价都大于某个正数 。 对图中的所有结点n， h(n) h*(n) 。也就是说h (n)决不会超过实际值h* (n) 定理1：如果图和h(n)具有上述稳定条件稳定条件，而且从开始结点n0到目标结点有一条有限代价的路径有一条有限

6、代价的路径，那么A*算法保证终止于到达目标的一条最小代最小代价路径价路径。A*算法的可采纳性引理1： 在A*终止前的每一步，总有一个结点n* ，它在Open表中，并具有一下特性： n*在到达目标的一条最优路径上 A*已经发现了到达n*的一条最优路径 f (n* ) f* (n*)最优路径：n0 , n1 , ,n* , np , ,G引理一证明（1） 数学归纳法 当m=1时，也就在是算法的第一步：仅有初始结点n0被放入Open表中。令n*= n0, 因为是n0起点，所以n0必然在从n0到目标的一条最优路径上,而且g (n0)=0 ， g *(n0)=0 。 故结论(1)(2)在m1时成立 因为

7、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 , n1 , ,n* , np , ,G第m+1步，n*没有被扩展，结点x被扩展最优路径：n0 , n1 , ,n* , np , ,G第m+1步 结点n*被扩展引理一证明

8、（3） n*被扩展：它的所有后继结点都被放入Open表中。 由于n*处在从n0到目标的一条最优路径上，所以它的后继结点中，至少有一个结点np在最优路径上。所以引理1的结论1成立。 A*找到了从n0到np的一条最优路径。（反证法）如果存在一条到达np更好的路径，那么它也是到达目标的更好路径，这与n*处在最优路径上矛盾。所以引理1的结论2成立。引理一证明（4） 引理1的结论3的证明由结论2可知： g(n*)=g*(n*)因为 g (np) = g (n*)+cost(n*, np) g*(np) = g*(n*)+cost(n*, np)所以 g(np)=g*(np)f (np)= g(np) +

9、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 (n* ) f* (n*) 定理1：如果图和h(n)具有上述稳定条件稳定条件，而且从开始结点n0到目标结点有一条有限代价的路径有一条有限代价的路径，那么A*算法保证终止于到达

10、目标的一条最小代价最小代价路径路径。定理一的证明（1） A*算法必定终止（反证法）： 若不会终止，那么A*会不断扩展Open表中的结点。 由于每个结点的后继结点有限，所以最终会扩展到比任何深度约束更深的结点。 每个边的代价都大于,于是，Open表中的所有结点的g (n)值都将超过f*(n0) ，也就是说，所有结点的f(n)都将超过f*(n0) 。 这于引理1的结论3矛盾， 故A*算法必定会终止定理一的证明（2） A*终止于一条最优路径上（反证法）： A*只能终止于第3步或第5步。终止于第3步的情况只能出现在不包含任何结点的有限图中。这与已知条件“从开始结点n0到目标结点有一条有限代价的路径”矛

11、盾。所以不可能出现这种情况。 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 h*(n) 双向搜索 迭代加深的A*（IDA*） 第一个广泛应用的最优启发式算法 存储受限的最优启发式算法 RBFS、MA*、SMA*作业 Page 55， 二选一（1.2 ，1.3）