启发式搜索

启发式搜索[e-mail]启发式信息加速搜索•盲目搜索的缺陷•改进：根据与问题相关的知识问题，引入启发式信息。•策略：从初始结点S出发，选择离目标最近的子节点扩展。•定义：f(n)为经过结点n的且从起点到目标的最短路径长度的估计函数。f(n)的值越小，表示路径越短BSFEGCDGH……引入f(n)的搜索过程SG434344444SGnn0n1nk………f(n)f(n)＝？•f(n)=g(n)+h(n)–g(n)表示起始结点到n的最短路径长度的估计–h(n)表示n到目标结点的最短路径长度的估计•g=?h=?SGn)(ng)(nh引入g(n)、h(n)的搜索过程SGng(n)h(x)SG1,41,31,42,12,22,23,13,14,10,33,0)()()(nhngnff(n)≈f*(n)SGn)(*ng)(*nh)(*)()(*)(*)(*)(*)(*)(*nfnfnhngnfnnfnnhnng的最短路径的代价是经过结点到目标最短路径的代价是结点的最短路径的代价是初始结点到结点八数码问题28316475数为位置不正确的数字个令的深度为初始结点到结点令)()(nhnng28316475283164751)(nh28316475283164752831647528316475rightupleftrightupleft28316475283164752831647528316475283164752831647528316475updownrightleft283164752831647528316475rightdowndown0+41+51+31+52+32+32+43+33+43+43+24+15+05+1启发式搜索算法——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是目标结点，搜索成功，返回问题的解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)，那么goto6。否则从open表或closed表中取出与mi相同的子结点mi’c)令mi：=mi’，将mi的父指针指向nd)将结点mi插入到open表，然后将open表按f值排序。7.goto3A算法——数据结构•结点n需要以下属性：–用于识别相同结点的标志ID–g,f,h–指向父结点的指针•open表用优先级队列实现，并提供以下操作–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演示SGABCD21252245331010A搜索过程示意图广度优先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*算法的可采纳性•稳定条件–图中的每个结点的后继结点是有限的。–图中的弧的代价都大于某个正数ε。–对图中的所有结点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*)n1n0npn*G最优路径：n0,n1,…,n*,np,…,G引理一证明（1）•数学归纳法•当m=1时，也就在是算法的第一步：仅有初始结点n0被放入Open表中。令n*=n0,因为是n0起点，所以n0必然在从n0到目标的一条最优路径上,而且g(n0)=0，g*(n0)=0。–故结论(1)(2)在m＝1时成立–因为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被扩展nin0npn*Gxxn1n0npn*G最优路径：n0,n1,…,n*,np,…,G第m+1步结点n*被扩展引理一证明（3）•n*被扩展：它的所有后继结点都被放入Open表中。–由于n*处在从n0到目标的一条最优路径上，所以它的后继结点中，至少有一个结点np在最优路径上。所以引理1的结论1成立。–A*找到了从n0到np的一条最优路径。（反证法）如果存在一条到达np更好的路径，那么它也是到达目标的更好路径，这与n*处在最优路径上矛盾。所以引理1的结论2成立。nknpn0n*引理一证明（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)+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成立n*npGn0f*(np)=f*(n*)=f*(n0)=f*(G)cost(n*,np)g*(np)=g*(n*)+cost(n*,np)回顾•引理1：在A*终止前的每一步，总有一个结点n*，它在Open表中，并具有一下特性：①n*在到达目标的一条最优路径上②A*已经发现了到达n*的一条最优路径③f(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步或第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，其差别在于，对所有的非目标结点有：h1h2，那么A2比A1更灵通•定理二如果A2比A1更灵通，那么对任意一个图，如果存在从n0到目标结点的一条路径，在搜索终止时，被A2扩展过的结点也被A1扩展过。•最灵通的算法是h≡h*•相同代价搜索h≡0•爬山法f=h•A算法f=g+h•广度优先搜索与相同代价搜索都是可采纳的深度优先广度优先h≡0h≤h*f=g+hf=h一般的图搜索算法演示A*算法的单调条件•单调条件（一致性条件）如果nj是ni的后继，那么h(ni)-h(nj)≤c(ni,nj)•定理三如果h满足单调条件，那么当A*扩展到结点n时，它已经找到了到达结点n的一条最优路径•A*不需要重定向指针，对图的搜索等同于对树的搜索njniGc(ni,nj)h(nj)h(ni)单调条件演示A*算法的改进•缺陷：–有可能反复扩展同一个节点•改进：–设计满足单调条件的启发式函数–修改算法过程如何设计可采纳的启发式函数?•根据问题特征设计h，例如八数码问题–h1位置不一致的棋子数目–h1(n)=1+1+0+1+1+0+0+0=4–h2所有棋子到其目标位置的距离和–h2(n)=1+2+0+1+1+0+0+0=52831647528316475目标结点n如何设计可采纳的启发式函数?•组合启发式函数：如果已有h1,h2,······,hm等可采纳启发式函数，那么：h=max(h1,h2,······,hm)•从经验中学习：已知某些特征x1与x2和h有关，但不知道具体的关系，那么可以定义h=c1x1+c2x2通过学习调整c1与c2。•ABSOLVER程序能自动生成启发式。魔方的第一个有用的启发式就是它找到的•模式数据库h(n)对搜索效率的影响•二维地图上的路径规划–h1=0–h2取欧氏距离–h3取城市距离–h4取10倍的欧氏距离–h5取20倍的欧氏距离–h1≤h2≤h3≤h4≤h5代价结点h1136.112002h2136.12045h3138.0672h4304.0147h5468.5131演示h1h2h3h4h5解的代价结点数目A*算法的应用•智力游戏•路径规划•定理证明•行动规划其它搜索算法•h(n)=0，相同代价搜索（uniform-cost）•g(n)=0，最佳优先搜索（best-first）•h(n)h*(n)•双向搜索•迭代加深的A*（IDA*）–第一个广泛应用的最优启发式算法–存储受限的最优启发式算法•RBFS、MA*、SMA*作业•Page55，二选一（1.2，1.3）