一人工智能蔡自兴

第一章搜索问题内容： 状态空间的搜索问题。搜索方式：盲目搜索启发式搜索关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）。1搜索问题（续1）S0Sg问题全状态空间搜索空间解路径2搜索问题（续2）讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。31.1回溯策略例：皇后问题4()5()Q((1,1))6()QQ((1,1))((1,1)(2,3))7()Q((1,1))((1,1)(2,3))8()QQ((1,1))((1,1)(2,3))((1,1)(2,4))9()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))10()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))11()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))12()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))13()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))14()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))15()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))16()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))17回溯策略属于盲目搜索的一种。回溯策略是这样一种策略：

首先将规则给出一个固定排序，在搜索时，对当前状态依次检查每条规则，在当前状态未使用过的规则中找到第一条可应用规则应用于当前状态，得到的新状态设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经用过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前的状态。重复以上搜索，直到找到问题的解。回溯策略18递归的思想回溯有多种实现方法,其中递归是一种最直接的实现方法.从前有座山……从前有座山……

从前有座山……19回溯搜索算法 递归过程：BACKTRACK（DATA）

DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。20回溯搜索算法递归过程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;//满足结束条件时返回2, IFDEADEND(DATA)RETURNFAIL;//不合法状态的回溯点3, RULES:=APPRULES(DATA);//可应用规则集4, LOOP:IFNULL(RULES)RETURNFAIL;//全部规则均失败的回溯点5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);//删去第一条规则，减少可应用规则表的长度7, RDATA:=GEN(R,DATA);//调用规则R作用于当前状态，生成新状态8, PATH:=BACKTRACK(RDATA);//对新状态递归调用9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);//返回解路径规则表21递归的思想（续）当前状态n目标状态tr1r2ri-1rim1m2mi-1mi22存在问题及解决办法解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态问题：深度问题死循环问题23一些深入问题在回溯策略中，也可以引入一些与问题有关的信息来加快搜索解的速度。 基本思想(以皇后问题为例)：

尽可能选取划去对角线上位置数最少的。QQQQ322324回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：从初始到当前的状态表（逆向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。25回溯搜索算法11,DATA:=FIRST(DATALIST)//设置DATA为当前状态2,IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL; //TAIL取尾操作，取DATALIST中除第一个以外的所有元素，如果DATA在TAIL(DATALIST）中存在，则说明有回路，返回FAIL，必须回溯.3,IFTERM(DATA)RETURNNIL;//找到目标，结束4,IFDEADEND(DATA)RETURNFAIL;//状态不合法，返回FAIL，必须回溯.5,IFLENGTH(DATALIST)>BOUND RETURNFAIL;//LENGTH计算DATALIST的长度，即搜索深度，当搜索深度大于BOUND值时，搜索失败，返回FAIL，必须回溯.6,RULES:=APPRULES(DATA);//APPRULES计算DATA的可应用规则集，依某种原则（任意排列或启发式排列）排列后附给RULES.7,LOOP:IFNULL(RULES)RETURNFAIL;//规则用完没找到目标，返回FAIL,必须回溯。26回溯搜索算法1（续）8, R:=FIRST(RULES);//取第一条规则9, RULES:=TAIL(RULES);//删去第一条规则，减少可应用规则表的长度10,RDATA:=GEN(R,DATA);//调用规则R作用于当前状态，生成新状态11,RDATALIST:=CONS(RDATA,DATALIST);//将新状态加入到表DATALIST中12,PATH:=BACKTRCK1(RDATALIST)//递归调用本过程13,IFPATH=FAILGOLOOP;//递归调用失败，转移调用另一规则进行测试14,RETURNCONS(R,PATH);//返回解路径规则表27分析这个算法与BACKRACK的差别是递归过程自变量是状态的链表。在过程BACKRACK1中，形参DATALIST是从初始状态到当前状态的逆序表，即初始状态排在表的最后，当前状态排在表的最前面。在第2、5步增设了两个回溯点以检验是否重新访问已出现过的状态和限定搜索深度范围。

281.2图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。

29一些基本概念节点深度： 根节点深度=0 其它节点深度=父节点深度+1012330一些基本概念（续1）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若任一节点ni-1都具有一个后继节点ni，则该节点序列称为从n0到nk的长度为k的一条路径。路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值.路径耗散值可按如下递推公式计算：

C(ni,t)=C(ni,nj)+C(nj,t)31一些基本概念（续1）扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。32一般的图搜索算法1,G=G0(G0=s),OPEN:=(s);//设置open表,最初只含有初始点s2,CLOSED:=();//设置closed表,初始为空表3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);//n为当前节点5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);

//子节点集{mi}中不包含n的父辈节点33一般的图搜索算法（续）7,标记和修改指针：

ADD(mj,OPEN),并标记mj到n的指针；//mj为open表和closed表中未出现过的子结点

计算是否要修改mk、ml到n的指针；

//mk为已出现在open表中的子结点，ml为已出现在closed表中的子结点，{mj}={mj}∪{mk}∪{ml}

计算是否要修改ml到其后继节点的指针；

8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；34说明这里给出的是一个图搜索的一般框架，不是一个具体的算法，关键是算法的第8步，按不同的原则对OPEN表进行排序，将得到不同的图搜索算法。

算法中有两个表：OPEN表和CLOSED表。其中OPEN表记录的是已经被生成出来，但还没有被扩展的节点；CLOSED表记录的是已经被扩展过的节点。

35几类节点的图例说明如上图所示，假设n是当前被扩展的节点。在n被扩展之前，节点mk和ml已经被生成出来了，其中mk还没有被扩展，他们在OPEN表中，而ml已经被扩展了，他们在CLOSED表中。当n被扩展时，它生成了节点mi，mi由mj、mk和ml三部分组成，其中mj是新出现的节点。36算法解释图搜索算法，简单地说就是，每次从OPEN表中取出第一个节点进行扩展，生成的新节点放到OPEN表中，然后按照某种原则对OPEN表进行排序。不同的排序原则构成了不同的图搜索算法。值得注意的是算法成功结束的判断方法，是当从OPEN表中取出一个节点后，再判断该节点是否是目标节点，而不是在扩展节点，生成新节点时判断。这一点一定要注意，在后面将可以看到，这是构成某些最优算法的关键所在。37算法解释这个过程是在第8步要对OPEN表上的节点进行排序，以便在第4步能选出一个“最好”的节点优先扩展。不同的排序方法便可构成形式多样的专门搜索算法，这在后面还要进一步讨论。如果选出待扩展的节点是目标节点，则算法在第5步成功结束，并可根据回溯到s的指针给出解路径。如果某个循环中，搜索树不再剩有待选的节点，即OPEN表变空时，则过程失败结束，问题找不到解。

38算法解释现在说明一下第7步中标记和修改指针的问题。如果要搜索的隐含图是一棵树，则可肯定第6步生成的后继节点不可能是以前生成过的，这时搜索图就是搜索树，不存在mk、ml这种类型的子节点，因此不必进行修改指针的操作。如果要搜索的隐含图不是一棵树，则有可能出现这样的子节点，就是说这时又发现了到达的新通路，这样就要比较不同路径的耗散值，把指针修改到具有较小耗散值的路径上。39例如，下图所示的两个搜索图中，实心圆点在CLOSED表中（已扩展过的节点），空心圆点则在OPEN表中（待扩展点）。先设下一步轮到要扩展节点6，并设生成的两个子节点，其中有一个4已在OPEN中，那么原先路径（s→3→2→4）耗散值为5（设每段路径均为单位耗散），新路径（s→6→4）的耗散值为4，所以4的指针应由指向2修正到指向6，如图2.5（a）所示。接着设下一循环要扩展节点1，若节点1只生成一个子节点2（它已在CLOSED上），显然这时节点2原先指向节点3的指针，要修改到指向节点1，由此又引起子节点3的指针又修改为指向2，如图2.5（b）所示。401.3无信息图搜索过程无信息图搜索属于盲目搜索，这里给两种常用的无信息图搜索方法：深度优先搜索宽度优先搜索41所谓深度优先搜索，就是在每次扩展一个节点时，选择到目前为止深度最深的节点优先扩展。第7步中的ADD（mj，OPEN）表示将被扩展节点n的所有新子节点mj加到OPEN表的前面。开始时，OPEN表中只有一个初始节点s，s被扩展，其子节点被放入OPEN表中。在算法的第3步，OPEN表的第一个元素(设为n)被取出扩展，这时节点n的深度在OPEN表中是最大的，OPEN表中的其他节点的深度都不会超过n的深度。n的子节点被放到OPEN表的最前面。由于子节点的深度要大于父节点的深度，实际上OPEN表是按照节点的深度进行排序的，深度深的节点被排在了前面，而深度浅的节点被放在了后面。这样当下一个循环再次取出OPEN表的第一个元素时，实际上选择的就是到目前为止深度最深的节点，从而实现了深度优先的搜索策略。42一般情况下，当问题有解时，深度优先搜索不但不能保证找到最优解，也不能保证一定能找到解。如果问题的状态空间是有限的，则可以保证找到解，当问题的状态空间是无限的时，则可能陷入"深渊"，而找不到解。为此，像回溯算法一样，可以加上对搜索的深度限制。其方法是在算法的第7步，当节点的深度达到限制深度时，则不将其子节点加入到OPEN表中，从而实现对搜索深度的限制。当然，这个深度限制应该设置的合适，深度过深影响搜索的效率，而深度过浅，则可能影响找到问题的解。

43回溯和深度优先的区别在有些书上所讲的深度优先实际上指的是我们这里所说的回溯策略，在本书中还是将二者区分开来。从形式上来说，二者确实很相似，所表现出来的都是每次选择深度最深的节点首先扩展。但二者还是有区别的，这里所说的深度优先属于图搜索策略，不足是占用较多的存储空间，好处是对于特殊的问题，可能会提高搜索的效率。44设某问题的状态空间如图所示。从图中可以看出该问题的特点：初始节点有若干个子节点，每个子节点都链接到三条很深的路径中，而目标假定在最右边的路径中。当采用回溯策略时，由于回溯策略只保留从初始节点到当前节点的一条路径，所以从第一个子节点（从左数）进入第一条路径搜索（从左遍数），回溯后，又进入第二条路径。由于没有找到解，又回溯到第二个子节点。从第二个子节点，同样要搜索第一条路径、第二条路径。第三个字节点、第四个子节点……也都同样。这样，第一和第二条路径将被多次搜索，影响了搜索的效率。而对于深度优先策略（单指这里所说的图搜索深度优先），由于保留了所有已经搜索过的路径，当通过第一个节点搜索了第一、第二条路径后，当通过第二个子节点搜索时，由于第一、第二条路径已经被搜索，并且被记录了，所以就不必重复搜索了，提高了搜索的效率。这一点在算法中是如何体现出来的呢？关键是算法的第7步，在n的子节点中，只将mj类节点加入到了OPEN表中，而对于mk类节点和ml类节点则不予考虑。

45深度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目标在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;46231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标47深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法48宽度优先搜索同深度优先算法一样，宽度优先算法也是从一般的图搜索算法变化而成。在深度优先搜索中，每次选择深度最深的节点首先扩展，而宽度优先搜索则正好相反，每次选择深度最浅的节点优先扩展。与深度优先算法不同的只是第7步，这里ADD（OPEN，mj）表示将mj类子节点放到OPEN表的后边，从而实现了对OPEN表中的元素按节点深度排序，只不过这次将深度浅的节点放在OPEN表的前面了，而深度深的节点被放在了OPEN表的后边。当问题有解时，宽度优先算法不但能一定找到解，而且在单位耗散的情况下，可以保证找到最优解。49宽度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,IF目标在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GOLOOP;5023184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标823418765451宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法521.4启发式图搜索利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解53希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。54基本思想启发式搜索过程中，要对OPEN表进行排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度，我们总是希望能找到最有希望通向目标节点的待扩展节点优先扩展。一种最常用的方法是定义一个评价函数f（Evaluationfunction）对各个子节点进行计算，其目的就是用来估算出“有希望”的节点来。定义一个评价函数可以参考的原则有：一个节点处在最佳路径上的概率；求出任意一个节点与目标节点集之间的距离度量或差异度量；根据格局（博弈问题）或状态的特点来打分。即根据问题的启发信息，从概率角度、差异角度或记分法给出计算评价函数的方法。551.启发式搜索算法A（A算法）启发式搜索算法A，一般简称为A算法，是一种典型的启发式搜索算法。其基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。评价函数的格式： f(n)=g(n)+h(n) f(n)：评价函数 h(n)：启发函数56符号的意义g*(n)：从s到n的最短路径的耗散值h*(n)：从n到g的最短路径的耗散值f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值,是一种预测。A算法就是利用这种预测，来达到有效搜索的目的的。它每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。57A算法利用评价函数f（n）＝g（n）＋h（n）来排列OPEN表节点顺序的图搜索算法称为A算法。58A算法过程

1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},//{mi}={mj}∪{mk}∪{ml}

①计算f(n,mi):=g(n,mi)+h(mi);

//g（n，mi）是从s通过n到mi的耗散值，f（n，mi）是从s通过n、mi到目标节点耗散值的估计。

59A算法（续）

②ADD(mj,OPEN),标记mj到n的指针；

③IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),标记mk到n的指针；

//比较f（n,mk）和f（mk），f（mk）是扩展n之前计算的耗散值。

④IFf(n,ml)<f(ml)THENf(ml):=f(n,ml), 标记ml到n的指针,ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序；8,GOLOOP；60A算法同样由一般的图搜索算法改变而成。在算法的第7步，按照f值从小到大对OPEN表中的节点进行排序，体现了A算法的含义。算法要计算f(n)、g(n)和h(n)的值，g(n)根据已经搜索的结果，按照从初始节点s到节点n的路径，计算这条路径的耗散值就可以了。而h(n)是与问题有关的，需要根据具体的问题来定义。有了g(n)和h(n)的值，将他们加起来就得到f(n)的值。注意A算法的结束条件：当从OPEN中取出第一节点时，如果该节点是目标节点，则算法成功结束。而不是在扩展一个节点时，只要目标节点一出现就立即结束。我们在后面将会看到，正是由于有了这样的结束判断条件，才使得A算法有很好的性质。61算法中f（n）规定为对从初始节点s出发，约束通过节点n到达目标点t，最小耗散值路径的耗散值f*(n)的估计值，通常取正值。f（n）由两个分量组成，其中g（n）是到目前为止，从s到n的一条最小耗散值路径的耗散值，是作为从s到n最小耗散值路径的耗散值g*(n)的估计值，h（n）是从n到目标节点t，最小耗散值路径的耗散值h*(n)的估计值。

62一个A算法的例子定义评价函数： f(n)=g(n)+h(n) g(n)为从初始节点到当前节点的耗散值 h(n)为当前节点“不在位”的将牌数

283164751238476563h计算举例 h(n)=42

831

64751234576

8642831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标12345665根据目标节点L返回到s的指针，可得解路径S(4)，B(4)，E(5)，I(5)，K(5)，L(5)662．爬山法爬山法（局部搜索算法）672．爬山法过程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；

显然如果将山顶作为目标，h(n)表示山顶与当前位置n之间高度之差，则该算法相当于总是登向山顶，在单峰的条件下，必能到达山峰。683．分支界限法分支界限法是优先扩展当前具有最小耗散值分支路径的端节点n，其评价函数为f(n)=g(n)。该算法的基本思想很简单，实际上是建立一个局部路径（或分支）的队列表，每次都选耗散值最小的那个分支上的端节点来扩展，直到生成出含有目标节点的路径为止。

69过程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；70应用分支界限法求下图的最短路径，求解过程中QUEUE的结果简记如下（D(4)代表耗散值为4的s-D分支，其余类推）：g=771初始（s(0)）

1.（A（3）D（4））

2.（D（4）B（7）D（8））

3.（E（6）B（7）D（8）A（9））

4.（B（7）D（8）A（9）F（10）B（11））

5.（D（8）A（9）F（10）B（11）C（11）E（12））

6.（A（9）E（10）F（10）B（11）C（11）E（12））

7.（E（10）F（10）B（11）C（11）E（12）B（13））

8.（F（10）B（11）C（11）E（12）B（13）F（14）B（15））

9.（B（11）C（11）E（12）t（13）B（13）F（14）B（15））

10.（C（11）E（12）t（13）B（13）F（14）A（15）B（15）C（15））

11.（E（12）t（13）B（13）F（14）A（15）B（15）C（15））

12.（t（13）B（13）F（14）D（14）A（15）B（15）C（15）F（16））

13.结束。724．动态规划法在A算法中，当h(n)≡0时，则A算法演变为动态规划算法。由于在A算法中，很多问题的启发函数h难于定义，因此动态规划算法是至今一直被经常使用的算法。734．动态规划法动态规划法实际上是对分支界限法的改进。从图2.9看出，第二循环扩展A（3）后生成的D（8）节点（D（4）已在QUEUE上）和第三循环扩展D（4）之后生成的A（9）节点（A（3）已以QUEUE上）都是多余的分支，因为由s－D到达目标的路径显然要比s－A－D到达目标的路径要好。因此删去类似于s－A－D或s－D－A这样一些多余的路径将会大大提高搜索效率。动态规划原理指出，求s→t的最佳路径时，对某一个中间节点I，只要考虑s到I中最小耗散值这一条局部路径就可以，其余s到I的路径是多余的，不必加以考虑。74动态规划st第一阶段第二阶段第三阶段第四阶段第五阶段754．动态规划法过程Dynamic-Programming

①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；

765.最佳图搜索算法A*（OptimalSearch）当在算法A的评价函数中，使用的启发函数h(n)是处在h﹡（n）的下界范围，即满足h(n)≤h*(n)时，则我们把这个算法称为算法A﹡。775.A*算法A﹡算法实际上是分支界限和动态规划原理及使用下界范围的h相结合的算法。当问题有解时，A﹡一定能找到一条到达目标节点的最佳路径。例如在极端情况下，若h(n)≡0（肯定满足下界范围条件），因而一定能找到最佳路径;若g≡d，则算法等同于宽度优先算法。前面已提到过，宽度优先算法能保证找到一条到达目标节点最小长度的路径，因而这个特例从直观上就验证了A﹡的一般结论。一般地说对任意一个图，当s到目标节点有一条路径存在时，如果搜索算法总是在找到一条从s到目标节点的最佳路径上结束，则称该搜索算法是可采纳的（Admissibility）。A﹡就具有可采纳性。78对于以下的定理、引理和推论，我们只要求掌握其结论和含义，不要求掌握其具体的证明过程。但是证明过程有助于你对算法的理解。以下定理的证明，正文部分是严格的，而解释部分，则不是严格的证明，只是从直观上，或者从思路上进行说明。在以下的定理证明过程中，要明确这样几个关系：

f*(s)=f*(t)=h*(s)，其中s是初始节点，t是目标节点（有时也用g表示）。当n是从初始节点到目标节点t的最优路径上的节点时，

f*(n)=f*(s)=f*(t)=h*(s)。5.A*算法79A*算法的性质（续1）定理1.1： 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。证明：设A搜索失败，则算法在第2步结束，OPEN表变空，而CLOSED表中的节点是在结束之前被扩展过的节点。由于图有解，令（n0=s，n1，n2，…，nk=t）表示某一解路径，我们从nk开始逆向逐个检查该序列的节点，找到出现在CLOSED表中的节点ni，即niCLOSED，ni+1CLOSED（ni一定能找到，因为n0CLOSED，nkCLOSED）。由于ni在CLOSES中，必定在第6步被扩展，且ni+1被加到OPEN中，因此在OPEN表空之前，ni+1已被处理过。若ni+1是目标节点，则搜索成功，否则它被加入到CLOSED中，这两种情况都与搜索失败的假设矛盾，因此对有限图不失败则成功。[证毕]

80A*算法的性质（续2）引理1.1：对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)>f*(s)。该引理的证明中，隐含了两个假设：（1）任何两个节点之间的耗散值都大于某个给定的大于零的常量；（2）h(n)对于任何n来说，都大于等于零。

由于当问题有解存在时，从初始节点到目标节点的路径的耗散值总是一个有限的常量。那么在该解路径上的任何一个节点n，由于f(n)=g(n)+h(n)，而g(n)是有限的，h(n)≤h*(n)也是有限的（因为h*(n)有限），所以f(n)也是有限的。而对于一个无限图来说，那些不在解路径上的无限路径，随着搜索的进行，其耗散值总会趋于无穷大，因此那些在解路径上的节点的f值总会变得最小，总会有机会被排在OPEN表的第一个位置，从而被A*扩展。而目标节点也是解路径上的一个节点，这样它同样会有机会被排在OPEN表的第一个位置，从而使得算法成功结束，找到问题的解路径。81A*算法的性质（续2）引理1.2：对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)>f*(s)。证明：设d﹡(n)是A﹡生成的搜索树中，从s到任一节点n最短路径长度的值（设每个弧的长度均为1），搜索图上每个弧的耗散值为C(ni，ni+1)（C取正）。令e=minC(ni，ni+1)，则g﹡(n)≥d﹡(n)e。而g(n)≥g﹡(n)≥d﹡(n)e，故有：

f(n)=g(n)+h(n)≥g(n)≥d﹡(n)e（设h(n)≥0）

若A﹡不结束，d﹡(n)趋向于∞，f值将增到任意大。

82A*算法的性质（续2）该引理可以这样来理解：如果问题从初始节点s到目标节点g的路径存在时，则一定有一个最短路径存在。在A*没有结束之前，OPEN表中的节点不会为空。由于总是从OPEN表中取出节点来扩展，所以最优路径肯定要通过OPEN表中的某个节点，设该节点为n。那么n有两个特点，一是n是从s到g的最优路径上的节点，二是到目前为止已经找到了从s到n的最优路径。第一点会比较容易接受，第二点是如何保证的呢？如果到目前为止找到的不是从s到n的最优路径，同样的理由，在OPEN表中一定有一个节点--假定为n'--在从s到n的最优路径上，当然他也一定在从s到g的最优路径上。用n'来代替n，重复下去，一直找到满足以上两个特点的n为止。当然，我们不一定明确的知道到底OPEN表中的哪个节点满足这样的特点，但从以上的叙述可以知道，这样的节点一定存在。

对于具有这样特点的n，由于以上所说的第一个特点有g(n)=g*(n)，所以有f(n)=g*(n)+h(n)，而由于算法是A*的，所以有h(n)≤h*(n)，所以f(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)。对于最后一个等式，是由于对于任何两个最优路径上的节点n1和n2，都有f*(n1)=f*(n2)，而n和s都是最优路径上的节点。引理1.2得证。

83A*算法的性质（续3）引理1.3： A*结束前，OPEN表中必存在f(n)≤f*(s)的节点（n是在最佳路径上的节点）

。证明：设从初始节点s到目标节点t的一条最佳路径序列为：

(n0=s，n1，…，nk=t)

算法初始化时，s在OPEN中，由于A﹡没有结束，在OPEN中存在最佳路径上的节点。设OPEN表中的某节点n是处在最佳路径序列中（至少有一个这样的节点，因s一开始是在OPEN上），显然n的先辈节点np已在CLOSED中，因此能找到s到np的最佳路径，而n也在最佳路径上，因而s到n的最佳路径也能找到，因此有

f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)

而最佳路径上任一节点均有f*（n）=f*(s)（f*(s)是最佳路径的耗散值），所以f(n)≤f*(s)。[证毕]84A*算法的性质（续3）定理1.2： 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。证明：假定A*不结束，由引理2.1有f(n)＞f*(s)，或OPEN表中最小的一个f值也变成无界，这与引理2.2的结论矛盾，所以A*只能成功结束。[证毕]85A*算法的性质（续4）推论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，均被扩展。得证。86A*算法的性质（续5）定理1.3(可采纳性定理)： 若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。87可采纳性的证明由定理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*的结束条件88A*算法的性质（续6）推论1.2： A*选作扩展的任一节点n，有f(n)≤f*(s)。由引理2.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)。得证。89A*算法的性质（续7）定理1.4：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n)>h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。简写：如果h2(n)>h1(n)(目标节点除外)，则A1扩展的节点数≥A2扩展的节点数90A*算法的性质（续7）注意：

在定理1.4中，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只计算一次。91定理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中。92定理1.4的证明（续1）所以有：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)(A)由于d(n)=k时，A2扩展的节点A1一定扩展，有g1(n)≤g2(n)(因为A2的路A1均走到了)所以：h1(n)≥f*(s)-g1(n)≥f*(s)–g2(n)(B)比较A、B两式，有h1(n)≥h2(n)，与定理条件矛盾。故定理得证。933，A*算法的改进问题的提出： 因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。94s(10)A(1)B(5)C(8)G目标631118一个例子：OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)B(8)s(10)A(5)B(8)s(10)C(9)A(5)s(10)B(7)C(9)s(10)A(4)B(7)C(9)s(10)95出现多次扩展节点的原因在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。s(10)A(1)B(5)C(8)G目标63111896解决的途径对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。97改进的条件可采纳性不变不多扩展节点不增加算法的复杂性98对h加以限制定义：一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足 h(ni)-h(nj)≤c(ni,nj) h(t)=0 或h(ni)≤c(ni,nj)+h(nj) h(t)=0则称h是单调的。h(ni)ninjh(nj)c(ni,nj)99h单调的性质定理1.5： 若h(