级人工智能原理-10-1853

1前面讨论的各种搜索方法都没有用到问题本身的特性信息，只是按照事先设定的线路进行搜索，具有较大的盲目性。事实上，如果能够利用搜索过程所得到的问题自身的一些特性信息来指导搜索过程，则对搜索将是十分有益的。这种利用问题自身的特性信息来引导搜索过程的搜索方法称为启发式搜索。由于启发式搜索方法具有较强的针对性，因此，可以缩小搜索范围，提高搜索效率。4.5状态空间的启发式搜索2启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息又是通过估价函数作用到搜索过程中的。1．启发性信息一.启发性信息和估价函数启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。启发性信息一般有以下三种：①有效地帮助确定扩展节点的信息；②有效地帮助决定哪些后继节点应被生成；③能决定在扩展一个节点时哪些节点应从搜索树上被删除。一般来说，搜索过程所使用的启发性信息的启发能力越强，扩展的无用节点就越少。32．估价函数用来估计节点重要性的函数称为估价函数。估价函数f（n）被定义为从初始节点S0出发，经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式为f（n）=g（n）＋h（n）其中，g（n）是从初始节点S0到节点n的实际代价；h（n）是从节点n到目标节点S0的最优路径的估计代价。对g（n）的值，可以按指向父节点的指针，从节点n反向跟踪到初始节点S0,得到一条从初始节点S0到节点n的最小代价路径，然后把这条路径上所有有向边的代价相加，就得到g（n）的值。对h（n）的值，则需要根据问题自身的特性来确定，它体现的是问题自身的启发性信息，因此也称h（n）为启发函数。ng(n)h(n)4例：八数码难题。设问题的初始状态S0和目标状态Sg如前所述，且估价函数为:f（n）=d（n）＋W（n）其中，d（n）表示节点n在搜索树中的深度；w（n）表示节点n中“不在位”的数码个数。请计算初始状态S0的估价函数值f（S0）。解：在本例的估价函数中，取g（n）=d（n），h（n）=W（n）。它说明是用从S0到n的路径上的单位代价表示实际代价，用n中“不在位”的数码个数作为启发信息。一般来说，某节点中的“不在位”的数码个数越多，说明它离目标节点越远。对初始节点S0，由于d（S0）=0，W（S0）=3，因此有f（S0）=0＋3=3这个例子仅是为了说明估价函数的含义及估价函数值的计算。在问题搜索过程中，除了需要计算初始节点的估价函数之外，更多的是要计算新生成节点的估价函数值。283147655二.A算法在图搜索算法中，如果能在搜索的每一步都利用估价函数f（n）=g（n）＋h（n）对Open表中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息，因此，A算法也被称为启发式搜索算法。对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。6每当需要扩展节点时，总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：（1）把S0放入Open表中，f(s0)=g（So）＋h（So）；（2）如果Open表为空，则问题无解，失败退出；（3）把Open表的第一个节点取出放入Closed表，记该节点为n；（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；（5）若节点n不可扩展，则转第（2）步；（6）扩展节点n，生成其子节点ni（i=1,2,……），计算每一个子节点的估价值f(ni)（i=1,2,……），并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中；（7）根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；（8）转第（2）步。1．全局择优搜索7由于上述算法的第（7）步要对Open表中的全部节点按其估价函数值从小到大重新进行排序，这样在算法第（3）步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。对上述算法进一步分析还可以发现：如果取估价函数f(n)=g（n），则它将退化为代价树的广度优先搜索；如果取估价函数f(n)=d（n），则它将退化为广度优先搜索。可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。8例：八数码难题。28314765S02831476523184765283147652831647583214765283714652318476523184765S94123847651238476512378465S55S66S86S74SgS104S116S14S24S35S459在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：（1）把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0);（2）如果Open表为空，则问题无解，失败退出；（3）把Open表的第一个节点取出放入Closed表，并记该节点为n；（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；（5）若节点n不可扩展，则转第（2）步；（6）扩展节点n，生成其子节点ni(i=1，2，…)，计算每一个子节点的估价值f（ni）（i=1，2，…），并按估价值从小到大的顺序依次放入Open表的首部，并为每一个子节点设置指向父节点的指针，然后转第（2）步。2．局部择优搜索(瞎子爬山法)10由于这一算法的第（6）步仅是把刚生成的子节点按其估价函数值从小到大放入Open表的首都，这样在算法第（3）步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。对这一算法进一步分析也可以发现：如果取估价函数f（n）=g（n），则它将退化为代价树的深度优先搜索；如果取估价函数f（n）=d（n），则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。11三.A*算法前面讨论的启发式搜索算法，都没有对估价函数f(n)作任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的解，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制。A*算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。12假设f*(n)为从初始节点S0出发，约束经过节点n到达目标节点的最小代价值。估价函数f(n)是f*(n)的估计值。显然，f*（n）应由以下两部分所组成：一部分是从初始节点到节点n的最小代价，记为g*（n）；另一部分是从节点n到目标节点的最小代价，记为h*（n），当问题有多个目标节点时，应取其中代价最小的一个。因此有f*（n）＝g*（n）＋h*（n）把估价函数f(n)与f*(n)相比，g（n）是对g*（n）的一个估计，h（n）是对h*（n）的一个估计。在这两个估计中，尽管g（n）的值容易计算，但它不一定就是从初始节点S0到节点n的真正最小代价，很有可能从初始节点S0到节点n的真正最小代价还没有找到，故有g（n）≥g*（n）。有了g*（n）和h*（n）的定义，如果对A算法（全局择优的启发式搜索算法）中的g（n）和h（n）分别提出如下限制：第一，g（n）是对g*（n）的估计，且g（n）＞0；第二，h（n）是h*（n）的下界，即对任意节点n均有h（n）≤h*（n）。则称得到的算法为A*算法。13A*算法的有关特性。1．A*算法的可纳性一般来说，对任意一个状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的。A*算法是可采纳的。(证明略）。2.A*算法的最优性A*算法的搜索效率很大程度上取决于估价函数h（n）。一般来说，在满足h（n）≤h*（n）的前提下，h（n）的值越大越好。h（n）的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。A*算法的这一特性也称为信息性。(证明略)14A*算法应用举例例：八数码难题。问题的初始状态和目标状态和前例相同。要求用A*算法解决该问题。解：在上例中，我们取h（n）=W（n）。尽管我们对h*（n）不能确切知道，但当采用单位代价时，通过对“不在位”数码个数的估计，可以得出至少要移动W（n）步才能到达目标，显然有W（n）≤h*（n）。因此，前例中所定义的h（n）满足A*算法的限制条件。这里再取另外一种启发函数h（n）=P（n），P（n）定义为每一个数码与其目标位置之间距离（不考虑夹在其间的数码）的总和，同样可以断定至少要移动P（n）步才能到达目标，因此有P（n）≤h*（n），即满足A*算法的限制条件。23184765523847611528314765h*=4,f=4S023184765283164752831476528314765g*=12318476523184765g*=21238476512378465Sgg*=4h*=5,f=6h*=5,f=6h*=3,f=4h*=5,f=6h*=2,f=4h*=4,f=612384765g*=3h*=1,f=4h*=0,f=4h*=1,f=6八数码难题h（n）=P（n）的搜索树16例：设有如下结构的移动将牌游戏B代表黑色牌，W代表白色牌；E代表该位置为空。玩法：当一个牌移入相邻的空位时，费用等于挑过的牌数加1。一个牌至多可跳过两个牌进入空位置，其费用等于跳过的牌数加1。要求把所有的B都移到所有的W的右边，设计h(x)。解：显然W左边的B越少越接近目标，因此可用W左边B的个数作为h(x)h(x)=3*(每个W左边B个数的总和）h(x)=3*(2+2+3)=21BBBWWWEBBBWWWE17例：传教士和野人问题。请用A*算法解决该问题。解：用m表示左岸的传道士人数，c表示左岸的野人数，b表示左岸的船数，用三元组（m，c，b）表示问题的状态。对A*算法，首先需要确定估价函数。设g（n）=d（n），h（n）=m＋c－2b，则有f（n）=g（n）＋h（n）=d（n）＋m＋c－2b其中，d（n）为节点的深度。通过分析可知h（n）＜h*(n)，满足A*算法的限制条件。M-C问题的搜索过程如下页图所示。在该图中，每个节点旁边还标出了该节点的h值和f值。18(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=4,f=4f(n)=d(n)+m+c-2bhh=5,f=6h=4,f=5h=4,f=5(3,2,1)h=3,f=5(2,1,0)(3,0,0)h=3,f=6h=3,f=6(2,2,1)(3,1,1)h=2,f=6h=2,f=6h=2,f=7h=2,f=7传教士和野人问题的搜索图(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0)(1,1,0)19204.4与/或树的盲目搜索Q11Q12Q13Q11Q12Q13Q1Q21Q22Q23Q2Q21Q22Q23′′′′′′Q21概念:直接可解的简单问题称为本原问题，本原问题对应的节点称为终止节点，在与或图（树）中无子节点的节点称为端节点，一个节点的子节点如果是“与”关系，则该节点便称为与节点，一个节点的子节点如果是“或”关系，则该节点便称为或节点。注意，终止节点一定是端节点，但端节点不一定是终止节点。可解性判别(1)一个节点是可解，则节点须满足下列条件之一:①终止节点是可解节点；②一个与节点可解，当且仅当其子节点全都可解；③一个或节点可解，只要其子节点至少有一个可解。(2)一个节点是不可解，则节点须满足下列条件之一:①非终止节点的端节点是不可解节点；②一个与节点不可解，只要其子节点至少有一个不可解；③一个或节点不可解，当且仅当其子节点全都不可解。22一.与/或树的一般搜索与/或树的搜索过程实际上是一个不断寻找解树的过程。其一般搜索过程如下：（1）把原始问题作为初始节点S0，并把它作为当前节点；（2）应用分解或等价变换操作对当前节点进行扩展；（3）为每个子节点设置指向父节点的