第一章 搜索问题1

启发式图搜索过程利用知识来引导搜索，到达减少搜索范围，降低问题复杂度的目的启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解希望引入启发知识，在保证找到最正确解的情况下，尽可能减少搜索范围，提高搜索效率编辑ppt启发能力的强弱比较不同搜索方法的效果可用启发能力的强弱来度量在大多数实际问题中，人们感兴趣的是使路径的耗散值和求得路径所需搜索的耗散值两者的某种组合最小更一般的情况是考虑搜索方法对求解所有可能遇见的问题，其平均的组合耗散值最小搜索空间〔代价〕小如果搜索方法1的平均组合耗散值比方法2的平均组合耗散值低，那么认为方法1比方法2有更强的启发能力编辑ppt根本思想优先扩展有希望的结点要对OPEN表进行排序这就需要有一种方法来计算待扩展结点有希望通向目标结点的不同程度一种最常用的方法是定义一个评价函数f〔Evaluationfunction〕对各个子结点进行计算，其目的就是用来估算出“有希望〞的结点来通常可以参考的原那么有：一个结点处在最正确路径上的概率求出任意一个结点与目标结点集之间的距离度量或差异度量根据格局〔博弈问题〕或状态的特点来打分编辑ppt启发式搜索算法A简称为A算法是一种典型的启发式搜索算法其根本思想是定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的结点来扩展评价函数的形式如下：f(n)＝g(n)＋h(n)n是被评价的结点编辑pptg*(n)表示从初始结点s到结点n的最短路径的耗散值h*(n)表示从结点n到目标结点g的最短路径的耗散值f*(n)=g*(n)+h*(n)表示从初始结点s经过结点n到目标结点g的最短路径的耗散值而f(n)、g(n)和h(n)那么分别表示是对f*(n)、g*(n)和h*(n)三个函数值的的估计值编辑ppt①OPEN:＝〔s〕，f〔s〕:＝g〔s〕+h〔s〕;②LOOP：IFOPEN＝〔〕THENEXIT〔FAIL〕；③n:＝FIRST〔OPEN〕；④IFGOAL〔n〕THENEXIT〔SUCCESS〕；⑤REMOVE〔n，OPEN〕，ADD〔n，CLOSED〕；

编辑ppt⑥EXPAND〔n〕→{mi}，计算f〔n，mi〕＝g〔n，mi〕+h〔mi〕；g〔n，mi〕是从s通过n到mi的耗散值，f〔n，mi〕是从s通过n、mi到目标结点耗散值的估计。·ADD〔mj，OPEN〕，标记mi到n的指针。·IFf〔n，mk〕<f〔mk〕THENf〔mk〕:＝f〔n，mk〕，标记mk到n的指针；比较f〔n，mk〕和f〔mk〕，f〔mk〕是扩展n之前计算的耗散值。·IFf〔n，m1〕<f〔m1〕THENf〔m1〕:＝f〔n，m1〕，标记m1到n的指针，ADD〔m1，OPEN〕；当f〔n，m1〕<f〔m1〕时，把m1重放回OPEN中，不必考虑修改到其子结点的指针。⑦OPEN中的结点按f值从小到大排序；⑧GOLOOP；编辑pptA算法说明由一般的图搜索算法改变而成在算法的第7步，按照f值从小到大对OPEN表中的结点进行排序，表达了A算法的含义计算f(n)、g(n)和h(n)g(n)根据已经搜索的结果，按照从初始结点s到结点n的路径，计算这条路径的耗散值就可以了h(n)与问题有关的，需要根据具体的问题来定义h(n)通常称为启发函数A算法的结束条件从OPEN中取出第一结点时，如果该结点是目标结点，那么算法成功结束只要目标结点一出现就立即结束编辑ppt扩展n后新生成的子结点m1〔∈{mj}〕、m2〔∈{mk}〕、m3〔∈{ml}〕f(m1)=g(m1)+h(m1)

f(n，m2)=g(n，m2)+h(m2)

f(n，m3)=g(n，m3)+h(m3)编辑pptA算法举例—八数码问题在3×3九宫格棋盘上，摆有8个将牌，分别刻有数字1-8，棋盘中留有一个空格，允许其周围的将牌向空格移动。给定一种初始布局和目标布局，找出一个合法的走步序列。编辑ppt八数码问题设评价函数f(n)形式如下：

f(n)=d(n)+W(n)

其中d(n)代表结点的深度，取g(n)=d(n)表示讨论单位耗散的情况；取h(n)=W(n)表示"不在位"的将牌个数作为启发函数的度量，这时f(n)可估计出通向目标结点的希望程度。比较上面两个图，发现1、2、6和8四个将牌不在目标状态的位置上，所以初始状态的"不在位的将牌数"就是4，也就是初始状态的h值。编辑ppt八数码问题括弧中的数字是该结点的评价函数值f。圆圈中的值，表示结点的扩展顺序。在出现相同的f值时，可以任意选择其中的一个结点首先扩展。编辑ppt八数码问题

搜索过程的OPEN表和CLOSED表编辑ppt爬山法过程Hill-climbing

①n:=s；s为初始结点

②LOOP：IFGOAL〔n〕THENEXIT(SUCCESS)；

③EXPAND〔n〕→{mi}，计算h(mi)，nextn:=m(minh(mi)的结点)；

④IFh(n)<h(nextn)THENEXIT(FAIL);

⑤n:=nextn；

⑥GOLOOP；编辑ppt爬山法〔续〕H(n)表示目标与当前结点之间的距离。或称为山顶与当前位置n之间的高度差。用不言退，总是登向山顶。问题：多峰山肩编辑ppt分支界限法分支界限法是优先扩展当前具有最小耗散值分支路径的端结点n，其评价函数为f(n)=g(n)。该算法的根本思想很简单，实际上是建立一个局部路径〔或分支〕的队列表，每次都选耗散值最小的那个分支上的端结点来扩展，直到生成出含有目标结点的路径为止。编辑ppt分支界限法过程Branch-Bound

①QUEUE:=(s-s)，g(s)=0;

②LOOP：IFQUEUE=()THENEXIT(FAIL);

③PATH:=FIRST(QUEUE)，n:=LAST(PATH);

④IFGOAL(n)THENEXIT(SUCCESS);

⑤EXPAND(n)→{mi}，计算g(mi)=g(n，mi)，REMOVE〔s-n，QUEUE〕，ADD(s-mi，QUEUE);

⑥QUEUE中局部路径g值最小者排在前面；

⑦GOLOOP；编辑ppt分支界限法〔最短路径问题〕八城市地图示意图分支界限搜索树g=7编辑ppt动态规划法在A算法中，当h(n)≡0时由于在A算法中，很多问题的启发函数h难于定义，因此动态规划算法是至今一直被经常使用的算法动态规划法实际上是对分支界限法的改进分支界限队列中有冗余求s→t的最正确路径时，对某一个中间结点I，只要考虑s到I中最小耗散值这一条局部路径就可以，其余s到I的路径是多余的，不必加以考虑编辑ppt动态规划法QUEUE:=(s-s),g(s)=0LOOP：IFQUEUE=()THENEXIT(FAIL)PATH:=FIRST(QUEUE)，n:=LAST(PATH)IFGOAL(n)THENEXIT(SUCCESS)EXPAND(n)→{mi},计算g(mi)=g(n,mi),REMOVE(s-n,QUEUE),ADD(s-mi,QUEUE);假设QUEUE中有多条到达某一公共结点的路径，那么只保存耗散值最小的那条路径，其余删去，并重新排序，g值最小者排在前面GOLOOP编辑ppt动态规划法编辑pptA*算法当在算法A的评价函数中，使用的启发函数h(n)是处在h﹡〔n〕的下界范围，即满足h(n)≤h*(n)时，称为算法A﹡。对任意一个图，当s到目标结点有一条路径存在时，如果搜索算法总是在找到一条从s到目标结点的最正确路径上结束，那么称该搜索算法是可采纳的。A﹡就具有可采纳性〔admissibility〕。编辑pptA*算法的性质A*算法的假设设ni、nj是任意两个结点，有：C(ni,nj)>ε，其中ε为大于0的常数几个等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始结点，t是目标结点，n是s到t的最正确路径上的结点编辑pptA*算法的性质〔续〕定理1.1： 对有限图，如果从初始结点s到目标结点t有路径存在，那么算法A一定成功结束。A*是A的特例对有限图，如果有解，A*一定能在找到到达目标的路径结束无限图呢？编辑pptA*算法的性质〔续〕引理1.1： 对无限图，假设有从初始结点s到目标结点t的路径，那么A*不能结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)>f*(s)。编辑pptA*算法的性质〔续〕引理1.2： A*结束前，OPEN表中必存在f(n)≤f*(s)。存在一个结点n，n在最正确路径上。f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)编辑pptA*算法的性质〔续〕定理1.2： 对无限图，假设从初始结点s到目标结点t有路径存在，那么A*一定成功结束。引理1.1：A*如果不结束，那么OPEN中所有的n有f(n)>f*(s)引理1.2：在A*结束前，必存在结点n，使得f(n)≤f*(s)所以，如果A*不结束，将导致矛盾。只说明能结束，未必最优编辑pptA*算法的性质〔续〕推论1.1： OPEN表上任一具有f(n)<f*(s)的结点n，最终都将被A*选作扩展的结点。由定理1.2，知A*一定结束由A*的结束条件，OPEN表中f(t)最小时才结束而f(t)≥

f*(t)＝f*(s)所以f(n)<f*(s)的n，均被扩展编辑pptA*算法的性质〔续〕定理1.3(可采纳性定理)： 假设存在从初始结点s到目标结点t有路径，那么A*必能找到最正确解结束。编辑pptA*可采纳性的证明由定理1.1、1.2知A*一定找到一条路径结束设找到的路径s→t不是最正确的〔t为目标〕那么： f(t)=g(t)>f*(s)由引理1.2知结束前OPEN中存在f(n)≤f*(s)的结点n，所以 f(n)≤f*(s)<f(t)因此A*应选择n扩展，而不是t。与假设A*选择t结束矛盾。得证。注意：A*的结束条件编辑pptA*算法的性质〔续〕推论1.2： A*选作扩展的任一结点n，有f(n)≤f*(s)由引理1.2知在A*结束前，OPEN中存在结点n’，f(n’)≤f*(s)设此时A*选择n扩展。如果n＝n’，那么f(n)≤f*(s)，得证。如果n≠n’，由于A*选择n扩展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得证。编辑ppt启发函数与A*算法的关系应用A*的过程中，如果选作扩展的结点n，其评价函数值f(n)=f*(n)，那么不会去扩展多余的结点就可找到解可以想象到f(n)越接近于f*(n)，扩展的结点数就会越少，即启发函数中，应用的启发信息〔问题知识〕愈多，扩展的结点数就越少编辑pptA*算法的性质〔续〕定理1.4：设对同一个问题定义了两个A*算法A1和A2，假设A2比A1有较多的启发信息，即对所有非目标结点有h2(n)>h1(n)，那么在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个结点，也必定由A1所扩展，即A1扩展的结点数至少和A2一样多。简写：如果h2(n)>h1(n)(目标结点除外)，那么A1扩展的结点集合包含A2扩展的结点集合编辑ppt定理1.4的证明使用数学归纳法，对结点的深度进行归纳〔1〕当d(n)＝0时，即只有一个结点，显然定理成立。〔2〕设d(n)≤k时定理成立。〔归纳假设〕〔3〕当d(n)=k+1时，用反证法。 设存在一个深度为k＋1的结点n，被A2扩展，但没有被A1扩展。而由假设，A1扩展了n的父结点，即n已经被生成了。因此当A1结束时，n将被保存在OPEN中。编辑ppt定理1.4的证明〔续〕 所以有：f1(n)≥f*(s) 即：g1(n)+h1(n)≥f*(s) 所以：h1(n)≥f*(s)-g1(n) 由于A2扩展了n，有f2(n)≤f*(s) 即：h2(n)≤f*(s)–g2(n) 由于d(n)=k时，A2扩展的结点A1一定扩展，有g1(n)≤g2(n)(因为A2的路A1均走到了) 所以： h1(n)≥f*(s)-g1(n)≥f*(s)–g2(n) 比较A、B两式，有h1(n)≥h2(n)，与定理条件矛盾。定理得证。编辑ppt定理1.4的说明针对同一个问题都是A*的h2(n)>h1(n)对任何非目标结点成立同一结点扩展屡次，只算一个该定理的意义在于，在使用A*算法求解问题时，定义的启发函数h，在满足A*的条件下，应尽可能地大一些，使其接近于h*，这样才能使得搜索的效率高编辑ppt使用h(n)缩小搜索空间的例子编辑pptA*算法的改进在A算法的第六步，对于ml类结点，存在重新放回到OPEN表的可能，因此一个结点有可能被反复扩展屡次。因此单纯用"扩展的结点数"并不能客观地来评判搜索算法的好坏。因为即便是扩展的结点数比较少，但如果很多结点被屡次重复扩展的话，搜索效率同样是很低的如果不使用启发函数，那么每个结点仅扩展一次，虽然扩展的结点数相同，但A*扩展的次数多。如果对启发函数施加一定的限制〔后面说的单调限制〕，那么当A*算法选某一个结点扩展时，就已经找到到该结点的最正确路径〔就不可能重复扩展了〕编辑ppth=14重复扩展的例子为什么会出现这种现象？编辑ppt单调性条件一个启发函数h，如果对所有结点ni和nj〔nj是ni的子结点〕，都有 h(ni)-h(nj)≤C(ni,nj) 【或h(ni)≤C(ni,nj)＋h(nj)】 且h(ti)＝0那么称该h函数满足单调限制条件其意义是从ni到目标结点，最正确路径耗散值估计h(ni)不大于nj到目标结点最正确路径耗散值估计h(nj)与ni到nj孤线耗散值两者之和h(ni)ninjh(nj)c(ni,nj)t编辑ppth单调的例子8数码问题：h为“不在位〞的将牌数1 h(ni)-h(nj)=0 (nj为ni的后继结点)-1 h(t)=0 c(ni,nj)=1满足单调的条件 编辑ppth单调时的A*定理1.5： 假设h(n)是单调的，那么A*扩展了结点n之后，就已经找到了到达结点n的最正确路径。 即：当A*选n扩展时，有g(n)=g*(n)。编辑ppt定理1.5的证明设n是A*扩展的任一结点。当n＝s时，定理显然成立。下面考察n≠s的情况。设P＝(n0=s,n1,n2,…,nk=n)是s到n的最正确路径P中一定有结点在CLOSED中，设P中最后一个出现在CLOSED中的结点为nj，那么nj+1在OPEN中。编辑ppt定理1.5的证明〔续〕由单调限制条件，对P中任意结点ni有： h(ni)≤C(ni,ni+1)+h(ni+1) g*(ni)+h(ni)≤g*(ni)+C(ni,ni+1)+h(ni+1)由于ni、ni+1在最正确路径上，所以：g*(ni+1)=g*(ni)+C(ni,ni+1)代入上式有：g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)从i=j到i=k-1应用上不等式，有：g*(nj+1)+h(nj+1)≤g*(nk)+h(nk)即：f(nj+1)≤g*(n)+h(n)注意：(nj在CLOSED中，nj+1在OPEN中)编辑ppt定理1.5的证明〔续〕重写上式：f(nj+1)≤g*(n)+h(n)另一方面，A*选n扩展，必有：f(n)=g(n)+h(n)≤f(nj+1)比较两式，有：g(n)≤g*(n)但g*(n)是最正确路径的耗散值，所以只有：g(n)=g*(n)。得证。编辑ppth单调时的A*〔续〕定理1.6： 假设h(n)是单调的，那么由A*所扩展的结点序列其f值是非递减的 即f(ni)≤f(nj)编辑ppt定理1.6的证明由单调限制条件，有：h(ni)–h(nj)≤C(ni,nj)=f(ni)-g(ni)=f(nj)-g(nj)f(ni)-g(ni)-f(nj)+g(nj)≤C(ni,nj)=g(ni)+C(ni,nj)f(ni)-g(ni)-f(nj)+g(ni)+C(ni,nj)≤C(ni,nj)

f(ni)-f(nj)

≤0，得证。编辑ppth单调的好处定理1.5和1.6的意义如果h满足单调限制条件，应用算法A*时，第6步可不必进行结点的指针修正工作，因而改善了A*的效率因h不满足单调限制条件，在扩展结点n时，有可能还没有找到到达n的最正确路径，因此该结点还会再次被放入OPEN中，从而造成了该结点被重复扩展编辑ppt对算法加以改进定义一个单调的h并不是一件很容易的事那么能否通过修改算法，来到达防止或者减少重复结点扩展的问题呢在改进A*算法的时候一是要保持A*算法的可采纳性二是不能增加过多的计算工作量由推论1.1我们知道，OPEN表上任一具有f(n)<f*(s)的结点n定会被扩展。由推论1.2我们知道，A*选作扩展的任一结点，定有f(n)≤f*(s)。这两个推论正是我们改进A*算法的理论根底编辑ppt改进算法的思路必须扩展的结点尽量不重复扩展OPEN=(…………)f*(s)f值小于f*(s)的结点f值大于等于f*(s)的结点fm：到目前为止已扩展结点的最大f值，用fm代替f*(s)编辑ppt修正的A*算法①OPEN:=(s),f(s)=g(s)+h(s),fm:=0;②LOOP:IFOPEN=()THENEXIT(FAIL);③ NEST:={ni|f(ni)<fm} IFNEST≠()THEN n:=NEST中g最小的结点 ELSE n:=FIRST(OPEN),fm:=f(n);④……⑧ 同过程A。编辑ppth=14修正的A*算法的例子OPENfmCLOSED初始化：(s(0+20))1(A(11+1)B(9+4)C(6+8)D(1+14))2(A(7+1)B(5+4)C(2+8))3(A(5+1)B(3+4))4(A(4+1))5(t(22+0))成功结束02020202020()(s(0+20))(s(0+20)D(1+14))(s(0+20)C(2+8)D(1+14))(s(0+20)B(3+4)C(2+8)D(1+14))(s(0+20)A(4+1)B(3+4)C(2+8)D(1+14))编辑pptA*算法应用举例8数码问题两个hW(n)P(n)编辑pptA*算法应用举例传教士和野人问题〔M-C问题〕编辑pptA*算法应用举例迷宫问题h可定义为两点间的Manhattan距离〔city-block距离〕h(n)=|XG–xn|+|YG–yn|编辑ppt评价函数的启发能力一般来说启发能力强，那么搜索效率较高。有时选用不是h*(n)下界范围的h(n)时，虽然会牺牲找到最正确解的性能，但可使启发能力得到改善，从而有利于求解一些较难的问题例子见教材P46