级人工智能原理课件

前面讨论的各种搜索方法都没有用到问题本身的特性信息，只是按照事先设定的线路进行搜索，具有较大的盲目性。事实上，如果能够利用搜索过程所得到的问题自身的一些特性信息来指导搜索过程，则对搜索将是十分有益的。这种利用问题自身的特性信息来引导搜索过程的搜索方法称为启发式搜索。由于启发式搜索方法具有较强的针对性，因此，可以缩小搜索范围，提高搜索效率。4.5状态空间的启发式搜索1前面讨论的各种搜索方法都没有用到问题本身的特1

启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息又是通过估价函数作用到搜索过程中的。

1．启发性信息一.启发性信息和估价函数

启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。启发性信息一般有以下三种：

①有效地帮助确定扩展节点的信息；

②有效地帮助决定哪些后继节点应被生成；

③能决定在扩展一个节点时哪些节点应从搜索树上被删除。

一般来说，搜索过程所使用的启发性信息的启发能力越强，扩展的无用节点就越少。2启发式搜索方法所依据的是问题自身的启发性信息2

2．估价函数用来估计节点重要性的函数称为估价函数。估价函数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)32．估价函数用来估计节点重要性的函数称为估3例：八数码难题。设问题的初始状态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

这个例子仅是为了说明估价函数的含义及估价函数值的计算。在问题搜索过程中，除了需要计算初始节点的估价函数之外，更多的是要计算新生成节点的估价函数值。

283147654例：八数码难题。设问题的初始状态S0和目标状态Sg如前4二.A算法

在图搜索算法中，如果能在搜索的每一步都利用估价函数f（n）=g（n）＋h（n）对Open表中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息，因此，A算法也被称为启发式搜索算法。

对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。5二.A算法在图搜索算法中，如果能在搜索的5每当需要扩展节点时，总是从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．全局择优搜索6每当需要扩展节点时，总是从Open表的所有节点中选择6由于上述算法的第（7）步要对Open表中的全部节点按其估价函数值从小到大重新进行排序，这样在算法第（3）步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。

对上述算法进一步分析还可以发现：如果取估价函数f(n)=g（n），则它将退化为代价树的广度优先搜索；如果取估价函数f(n)=d（n），则它将退化为广度优先搜索。可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。7由于上述算法的第（7）步要对Open表中的全7例：八数码难题。2834765S028314765238476528347652836475

8321476528371465

23847652384765

S9

4123847651238476512378465S5

5S66

S8

6

S7

4SgS10

4S11

6S1

4S2

4

S3

5S4

58例：八数码难题。283S028328在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：（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．局部择优搜索(瞎子爬山法)9在局部择优搜索中，每当需要扩展节点时，总是从9

由于这一算法的第（6）步仅是把刚生成的子节点按其估价函数值从小到大放入Open表的首都，这样在算法第（3）步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。对这一算法进一步分析也可以发现：如果取估价函数f（n）=g（n），则它将退化为代价树的深度优先搜索；如果取估价函数f（n）=d（n），则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。10由于这一算法的第（6）步仅是把刚生成的子节点10三.A*算法前面讨论的启发式搜索算法，都没有对估价函数f(n)作任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的解，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制。A*算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。11三.A*算法前面讨论的启发式搜索算法，都没11假设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*算法。12假设f*(n)为从初始节点S0出发，约束经过12A*算法的有关特性。

1．A*算法的可纳性

一般来说，对任意一个状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的。A*算法是可采纳的。(证明略）。

2.A*算法的最优性

A*算法的搜索效率很大程度上取决于估价函数h（n）。一般来说，在满足h（n）≤h*（n）的前提下，h（n）的值越大越好。h（n）的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。A*算法的这一特性也称为信息性。(证明略)13A*算法的有关特性。

1313A*算法应用举例

例：八数码难题。问题的初始状态和目标状态和前例相同。要求用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*算法的限制条件。

23847655238476114A*算法应用举例

例：八数码难题。问题的初始状态和目标状1428314765h*=4,f=4S0231

8476528316475283

1476528314765g*=1

2318476523184765g*=21

23847651

2378465Sgg*=4h*=5,f=6h*=5,f=6h*=3,f=4h*=5,f=6h*=2,f=4h*=4,f=61

2384765g*=3h*=1,f=4h*=0,f=4h*=1,f=6八数码难题h（n）=P（n）的搜索树15283h*=4,f=4S0232832815例：设有如下结构的移动将牌游戏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)=21BBBWWWEBBBWWWE16例：设有如下结构的移动将牌游戏BBBWWWEBBBWWWE116例：传教士和野人问题。请用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值。17例：传教士和野人问题。请用A*算法解决该问题。

解：用m表示17(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)18(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=181919194.4与/或树的盲目搜索204.4与/或树的盲目搜索2020概念:直接可解的简单问题称为本原问题，本原问题对应的节点称为终止节点，在与或图（树）中无子节点的节点称为端节点，一个节点的子节点如果是“与”关系，则该节点便称为与节点，一个节点的子节点如果是“或”关系，则该节点便称为或节点。注意，终止节点一定是端节点，但端节点不一定是终止节点。可解性判别(1)一个节点是可解，则节点须满足下列条件之一:①终止节点是可解节点；②一个与节点可解，当且仅当其子节点全都可解；③一个或节点可解，只要其子节点至少有一个可解。(2)一个节点是不可解，则节点须满足下列条件之一:①非终止节点的端节点是不可解节点；②一个与节点不可解，只要其子节点至少有一个不可解；③一个或节点不可解，当且仅当其子节点全都不可解。21概念:2121一.与/或树的一般搜索与/或树的搜索过程实际上是一个不断寻找解树的过程。其一般搜索过程如下：

（1）把原始问题作为初始节点S0，并把它作为当前节点；

（2）应用分解或等价变换操作对当前节点进行扩展；

（3）为每个子节点设置指向父节点的指针；

（4）选择合适的子节点作为当前节点，反复执行第（2）步和第（3）步，在此期间需要多次调用可解标记过程或不可解标记过程，直到初始节点被标记为可解节点或不可解节点为止。

上述搜索过程将形成一棵与/或树，这种由搜索过程形成的与/或树称为搜索树。当搜索成功时，经可解标记过程标识的由初始节点及其下属的可解节点构成的子树称为解树。用与/或树法表示的问题求解过程与状态空间法类似，也是通过搜索来实现对问题求解的。与/或树的搜索策略也分为盲目搜索和启发式搜索两大类。22一.与/或树的一般搜索与/或树的搜索过程实22搜索过程中的可解标记过程与不可解标记过程都是自下而上进行的，即由子节点的可解性确定父节点、祖父节点的可解性；由子节点的不可解性确定父节点、祖父节点的不可解性。在与/或树中，除端节点和终止节点外，一个节点的可解性完全是由其子节点来决定的。对与节点，只有其所有子节点都为可解时它才为可解，只要有一个子节点不可解它就是不可解的；对或节点，只要有一个子节点可解它就是可解的，仅当所有子节点都是不可解时它才为不可解。这种由可解子节点来确定其父节点、祖父节点为可解节点的过程称为可解标记过程；由不可解子节点来确定其父节点、祖父节点为不可解节点的过程称为不可解标记过程。

由于与/或树搜索的目标是寻找解树，因此，如果搜索过程确定某个节点为可解节点，则其不可解的后裔节点就可从搜索树中删去；同样，如果搜索过程能确定某个节点为不可解节点，则其后裔节点也可从搜索树中删去。23搜索过程中的可解标记过程与不可解标记过程都是自下而上进行的，23与状态空间的广度优先搜索类似，只是在搜索过程中需要多次调用可解标记过程或不可解标记过程，其搜索算法如下：

（1）把初始节点S0放人Open表中；

（2）把Open表的第一个节点取出放入Closed表，并记该节点为n；

（3）如果节点n可扩展，则做下列工作：

①扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针；

②考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解节点进行标记。如果初始解节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点；

③

转第（2）步。二.与/或树的广度优先搜索24与状态空间的广度优先搜索类似，只是在搜索过程24（4）如果节点n不可扩展，则做下列工作：

①

标记节点n为不可解节点；

②

应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始解节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从Open表中删去具有不可解先辈的节点；

③转第（2）步。25（4）如果节点n不可扩展，则做下列工作：

25例：设有如下图所示的与/或树，节点按图中所标注的顺序号进行扩展，其中标有t1、t2、t3的节点是终止节点，A、B、C为不可解的端节点。

与/或树的广度优先搜索123A4t1t3CBt25搜索过程为：

（1）先扩展1号节点，生成2号节点和3号节点，由于这两个子节点都不是终止节点，因此接着扩展2号节点。（2）扩展2号节点，生成A节点和4号节点。由于这两个子节点均不是终止节点，因此接着扩展3号节点。（3）扩展3号节点，生成t1节点和5号节点。由于t1为终止节点，则标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于t1的父节点是一个与节点，因此不能确定3号节点是否可解。（4）扩展节点A，由于A是端节点，调用不可解标记过程，由于2号节点是或节点，因此不能确定2号节点是不可解节点。（5）扩展4号节点，生成t2节点和B节点。由于t2为终止节点，则标记它为可解节点，并应用可解标记过程，标记4号节点为可解节点，标记2号节点为可解节点，但不能标记1号节点为可解节点。（6）扩展5号节点，生成t3节点和C节点。由于t3为终止节点，标记它为可解节点，并应用可解标记过程，标记5号节点为可解节点，标记3号节点为可解节点。标记1号节点为可解节点。（7）搜索成功，得到由1、2、3、4、5号节点及t1、t2、t3节点构成的解树。该解树如上图中的粗线所示。26例：设有如下图所示的与/或树，节点按图中所标注的顺序号26可以带有深度限制dm，其搜索算法如下：

（1）把初始节点S0放入Open表中；

（2）把Open表的第一个节点取出放入Closed表，并记该节点为n；

（3）如果节点n的深度等于dm，则转第（5）步的第①点；

（4）如果节点n可扩展，则做下列工作：

①

扩展节点n，将其子节点放入Open表的首部，并为每一个子节点设置指向父节点的指针；

②

考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解节点进行标记。如果初始节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点；

③

转第（2）步。三.与/或树的深度优先搜索27可以带有深度限制dm，其搜索算法如下：

（1）把初始27（5）如果节点n不可扩展，则做下列工作：

①

标记节点n为不可解节点；

②应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定为不可解节点，则从Open表中删去具有不可解先辈的节点；

③

转第（2）步。

与/或树的深度优先搜索123A4t1t3CBt25例如，对上例所给出的与／或树，若按有界深度优先搜索，且给定dm=4，则其扩展节点的顺序为：

1，3，5，2，4

其解树与上例相同。28（5）如果节点n不可扩展，则做下列工作：

28与/或树的盲目搜索是按确定路线进行的，当要选择一个节点进行扩展时，只是根据节点在与/或树中所处的位置，而没有考虑要付出的代价，因而求得的解树不一定是代价最小的解树，即不一定是最优解树。因此，需要考虑与/或树的启发式搜索。在讨论与／或树的启发式搜索过程之前，需要先讨论几个有关的概念。

一.解树的代价与希望树

与／或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。对搜索的每一步，算法都试图找到一个最有希望成为最优解树的子树。最优解树是指代价最小的那棵解树。4.5与/或树的启发式搜索29与/或树的盲目搜索是按确定路线进行的，当要291．解树的代价

在与/或树的启发式搜索过程中，解树的代价可按如下规则计算：

（1）若n为终止节点，则其代价h（n）=0。

（2）若n为或节点，且子节点为n1，n2，…，nk，则n的代价为h（n）=min{c（n，ni）＋h（ni）}(1≤i≤k)其中，c（n，ni）是节点n到其子节点ni的边代价。

（3）若n为与节点，且子节点为n1，n2，…，nk，则n的代价可用和代价法或最大代价法。

若用和代价法，则其计算公式为：h（n）=Σ((c(n，ni)＋h(ni))i=1,2,……,k

若用最大代价法，则其计算公式为：

h（n）=max｛c（n，ni）＋h（ni）｝(1≤i≤k)

（4）若n是端节点，但又不是终止节点，则n不可扩展，其代价定义为h（n）=∞

（5）根节点的代价即为解树的代价。301．解树的代价

在与/或树的启发式搜索过程中30例：设右图是一棵与/或树，其中包括两棵解树，左边的解树由S0、A、t1、C及t3组成；右边的解树由S0、B、t2、D及t4组成。在此与/或树中，t1、t2、t3、t4为终止节点；E、F是端节点；边上的数字是该边的代价。请计算解树的代价。S0ABt1Ct3Et2Dt4F与／或树的代价22463521解：先计算左边的解树

按和代价：h（S0）=2＋4＋6＋2=14

按最大代价：h（S0）=8＋2=10

再计算右边的解树

按和代价：h（S0）=1＋5＋3＋2=11

按最大代价：h（S0）=6＋2=8

在本例中，无论按和代价还是最大代价，右边的解树都是最优解树。但在有些情况下，当采用的代价法不同时，找到的最优解树有可能不同。31例：设右图是一棵与/或树，其中包括两棵解树，左边的解树由S312．希望树

为了找到最优解树，搜索过程的任何时刻都应该选择那些最有希望成为最优解树一部分的节点进行扩展。由于这些节点及其父节点所构成的与/或树最有可能成为最优解树的一部分，因此称它为希望解树，也简称为希望树。需要注意，希望解树是会随搜索过程而不断变化的。定义：希望解树T

（1）初始节点S0在希望树T中；

（2）如果n是具有子节点n1，n2，…，nk的或节点，则n的某个子节点ni在希望树T中的充分必要条件是

h（n）=min{c（n，ni）＋h（ni）}1≤i≤k

（3）如果n是与节点，则n的全部子节点都在希望树T中。322．希望树

为了找到最优解树，搜索过程的任何时刻都应32

与／或树的启发式搜索需要不断地选择、修正希望树，其搜索过程如下：

（1）把初始节点S0放入Open表中，计算h（S0）；

（2）计算希望树T；

（3）依次在Open表中取出T的端节点放入Closed表，记节点为n；

（4）如果节点n为终止节点，则做下列工作：

①标记节点n为可解节点；

②在T上应用可解标记过程，对n的先辈节点中的所有可解节点进行标记；

③如果初始节点S0能够被标记为可解节点，则T就是最优解树，成功退出；

④

否则，从Open表中删去具有可解先辈的所有节点；

⑤转第（2）步。二.与/或树的启发式搜索过程33与／或树的启发式搜索需要不断地选择、修正希望树，其搜33（5）如果节点n不是终止节点，但可扩展，则做下列工作：

①扩展节点n，生成n的所有子节点；

②把这些子节点都放入Open表中，并为每一个子节点设置指向父节点n的指针；

③计算这些子节点及其先辈节点的h值；

④

转第（2）步。

（6）如果节点n不是终止节点，且不可扩展，则做下列工作：

①

标记节点n为不可解节点；

②

在T上应用不可解标记过程，对n的先辈节点中的所有不可解节点进行标记；

③

如果初始节点S0能够被标记为不可解节点，则问题无解，失败退出；

④否则，从Open表中删去具有不可解先辈的所有节点；

⑤转第（2）步。34（5）如果节点n不是终止节点，但可扩展，则做下列工作：

34例，搜索过程每次扩展节点时都同时扩展两层，且按一层或节点、一层与节点的间隔方式进行扩展。设初始节点为S0，对S0扩展后得到的与/或树如下图所示。其中，端节点B、C、E、F下面的数字是用启发函数估算出的h值，节点A、D旁边的数字是按和代价法计算出来的节点代价。此时，S0的右子树是当前的希望树，下面对其端节点进行扩展。S0ADBCEF873332扩展S0后的与／或树835例，搜索过程每次扩展节点时都同时扩展两层，且35扩展节点E，由右子树求出的h（S0）=12，而由左子树求出的h（S0）=9。故当前的希望树应改为左子树。对B扩展两层。由于H和I是可解节点，调用可解标记过程，得节点G、B也为可解节点，但不能标记S0为可解节点，须继续扩展。当前的希望树仍然是左子树。对C扩展。扩展两层后得到的与／或树如图3所示。S0ADBCEF8332

3222776119图1扩展E后的与／或树S0ADBCEF8332

3222776119GKHILJ002226图2扩展B后的与／或树S0DEFABC8332

3222776119IGKHLJ002226MNP005229图3扩展C后的与／或树9由于N和P是可解节点，调用可解标记过程，得节点M、C、A也为可解节点，进而S0为可解节点。求出了代价最小的解树，即最优解树，如图中粗线所示。按和代价法，该最优解树的代价为9。36扩展节点E，由右子树求出的h（S0）=1236

博弈是一类富有智能行为的竞争活动，如下棋、打牌、战争等。博弈可分为双人完备信息博弈和机遇性博弈。所谓双人完备信息博弈，就是两位选手对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。对弈的结果是一方赢，另一方输；或者双方和局。所谓机遇性博弈，是指存在不可预测性的博弈，例如掷币等。对机遇性博弈，由于不具备完备信息，因此不作讨论。假设博弈的一方为MAX，另一方为MIN。在博弈过程的每一步，可供MAX和MIN选择的行动方案都可能有多种。从MAX方的观点看，可供自己选择的那些行动方案之间是“或”的关系，选择哪个方案完全是由自己决定的；而对那些可供MIN选择的行动方案之间则是“与”的关系，主动权掌握在MIN的手里，任何一个方案都有可能被MIN选中，MAX必须防止那种对自己最为不利的情况的发生。4.6博弈树的启发式搜索一.概述37博弈是一类富有智能行为的竞争活动，如下棋、打37若把双人完备信息博弈过程用图表示出来，就可得到一棵与/或树，这种与/或树被称为博弈树。在博弈树中，那些下一步该MAX走步的节点称为MAX节点，而下一步该MIN走步的节点称为MIN节点。博弈树具有如下特点：（l）博弈的初始状态是初始节点；（2）博弈树中的“或”节点和“与”节点是逐层交替出现的；（3）整个博弈过程始终站在某一方的立场上，所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。例如，站在MAX方，所有能使MAX方获胜的节点都是可解节点，所有能使MIN方获胜的节点都是不可解节点。38若把双人完备信息博弈过程用图表示出来，就可得38对简单的博弈问题，可以生成整个博弈树，找到必胜的策略。但对于复杂的博弈，如国际象棋，大约有10120个节点，要生成整个搜索树是不可能的。一种可行的方法是用当前正在考察的节点生成一棵部分博弈树，由于该博弈树的叶节点一般不是哪一方的获胜节点，因此，需利用估价函数f(n)对叶节点进行静态评估，对MAX有利的节点其估价函数取正值；那些对MIN有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于0的值。二.极大极小过程为了计算非叶节点的值，必须从叶节点向上倒推。对于MAX节点，由于MAX方总是选择估值最大的走步，因此，MAX节点的倒推值应该取其后继节点估值的最大值。对于MIN节点，由于MIN方总是选择使估值最小的走步，因此MIN节点的倒推值应取其后继节点估值的最小值。这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。这一过程称为极大极小过程。39对简单的博弈问题，可以生成整个博弈树，找到必39例：一字棋游戏。设有一个三行三列的棋盘，如下图所示，两个棋手轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。设MAX方的棋子用×标记，MIN方的棋子用

○标记，并规定MAX方先走步。

解：为了对叶节点进行静态估值，规定估价函数e（P）如下：

若P是MAX的必胜局，则e（P）=+∞；

若P是MIN的必胜局，则e（P）=-∞；一字棋棋盘若P对MAX、MIN都是胜负未定局，则e（P）=e（+P）－e（-P）

其中，e（+P）表示棋局P上有可能使×成三子一线的数目；e（-P）表示棋局P上有可能使○成三子一线的数目。40例：一字棋游戏。设有一个三行三列的棋盘，如下图所示，两个棋40例如，对图1所示的棋局有估价函数值e（P）＝6-4＝2图1棋局1在搜索过程中，具有对称性的棋局认为是同一棋局。例如，图2所示的棋局可以认为是同一个棋局，这样可以大大减少搜索空间。图3给出了第一着走棋以后生成的博弈树。图中叶节点下面的数字是该节点的静态估值，非叶节点旁边的数字是计算出的倒推值。从图中可以看出，对MAX来说S2是一着最好的走棋，它具有较大的倒推值。图2对称棋局的例子41例如，对图1所示的棋局有估价函数值e（P）＝6-4＝2图41

图3一子棋的极大极小搜索S0S1S2S3S4S5-11-26-5=15-5=06-5=15-5=04-5=-15-6=-15-5=06-6=05-6=-14-6=-25-4=16-4=242

图3一子棋的极大极小搜42极大极小值算法FunctionMAX-MIN-DECISION(state)returnsanaction inputs:state(currentstateingame) v←MAX-VALUE(state) returntheactioninSUCCESSORS(state)withvaluevFunctionMAX-VALUE(state)returnsautilityvalue ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←-∞ fora,sinSUCCESSORS(state)dov←MAX(v,MIN-VALUE(s)) returnv (a=action招数)FunctionMIN-VALUE(state)returnsautilityvalue ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←+∞ fora,sinSUCCESSORS(state)dov←MIN(v,MAX-VALUE(s)) returnv43极大极小值算法FunctionMAX-MIN-DECISI43上述极大极小过程是先生成与/或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率较低。如果能边生成节点边对节点估值，从而可以剪去一些没用的分枝，这种技术称为α-β剪枝过程。三.α-β剪枝<=23S0DEFABC5332对于一个与节点来说，它取当前子节点中的最小倒推值作为它倒推值的上界，称该值为β值。对于一个或节点来说，它取当前子节点中的最大倒推值作为它倒推值的下界，称该值为α

值。44上述极大极小过程是先生成与/或树，然后再计算44α-β剪枝的方法如下：

（1）MAX节点的α值为当前子节点的最大倒推值；

（2）

MIN节点的β值为当前子节点的最小倒推值；

（3）

α-β剪枝的规则如下：

①

任何MAX节点n的α值大于或等于它先辈节点的β值，则n以下的分枝可停止搜索，并令节点n的倒推值为α。这种剪枝称为β剪枝。

②

任何MIN节点n的β值小于或等于它先辈节点的α值，则n以下的分枝可停止搜索，并令节点n的倒推值为β。这种剪枝称为α剪枝。

三.α-β剪枝≥αmin≤βmax≥α45α-β剪枝的方法如下：

（1）MAX节点的α值45S0ABCDFGHEIJKLMNPQRS4861580-64≥4≤1≤4＝45≥5＝4≥4≥0＝0≤-6＝0≤0＝4＊＊＊＊＊α-β剪枝的例子T446S0ABCDFGHEIJKLMNPQRS4861580-6446S00-330031653-322-3-254-3089-347S00-330031653-322-3-254-3089-347S00-330031653-322-3-254-3089-3＊＊＊＊＊＊跳棋程序的学习策略48S00-330031653-322-3-254-3089-348-剪枝算法在极大极小值算法基础上增加了剪枝功能，即在返回值基础上增加了判断FunctionALPHA-BETA-SEARCH(state)returnsanaction inputs:state(currentstateingame) v←MAX-VALUE(state,-∞,+∞) returntheactioninSUCCESSORS(state)withvaluev49-剪枝算法在极大极小值算法基础上增加了剪枝功能，即在返回49-剪枝算法FunctionMAX-VALUE(state,,)returnsautilityvalue inputs:state ,thevalueofthebestalternativeforMAXalongthepathtostate ,thevalueofthebestalternativeforMINalongthepathtostate ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←-∞ fora,sinSUCCESSORS(state)do v←MAX(v,MIN-VALUE(s,,)) ifv≥thenreturnv

←MAX(,v) returnv50-剪枝算法FunctionMAX-VALUE(stat50-剪枝算法FunctionMIN-VALUE(state,,)returnsautilityvalue inputs:state ,thevalueofthebestalternativeforMAXalongthepathtostate thevalueofthebestalternativeforMINalongthepathtostate ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←+∞ fora,sinSUCCESSORS(state)do v←MIN(v,MAX-VALUE(s,

,)) ifv≤thenreturnv

←MIN(,v) returnv51-剪枝算法FunctionMIN-VALUE(stat51产生式系统与图搜索分析产生式正向推理算法，可以看出，它们只能用于解决逻辑推理性问题。若要求解规划性问题则还需要：(1)记录动态数据库状态变化的历史，这就需要增设一个CLOSED表。(2)若要回溯，则还需保存与每个动态数据库状态对应的可用规则集。因为动态数据库状态与可用规则集实际是一一对应的。(3)要进行树式搜索，还需设置一个OPEN表，以进行新生动态数据库的状态保存和当前动态数据库状态的切换。(4)还要考虑一条规则是否只允许执行一次。若是，则要对已执行了的规则进行标记。成功退出失败退出把初始数据放入综合数据库综合数据库中有解吗？形成可用知识集可用知识集空？按照冲突消解策略从该知识集中选出一条知识进行推理推出的是新事实？将该新事实加入到综合数据库中把用户补充的新事实加入到综合数据库中用户可以补充新事实吗？知识库中有可用知识吗？YYYYYNNNNN52产生式系统与图搜索分析产生式正向推理算法，52可以看出，二者实际是一回事。图搜索技术描述了问题求解的方法，产生式系统则给出了实施这种方法的一种计算机程序系统的结构模式。这样，问题求解、图搜索和产生式系统三者的关系是：问题求解是目的，图搜索是方法，产生式系统是形式。53可以看出，二者实际是一回事。图搜索技术描述了问题求解53前面讨论的各种搜索方法都没有用到问题本身的特性信息，只是按照事先设定的线路进行搜索，具有较大的盲目性。事实上，如果能够利用搜索过程所得到的问题自身的一些特性信息来指导搜索过程，则对搜索将是十分有益的。这种利用问题自身的特性信息来引导搜索过程的搜索方法称为启发式搜索。由于启发式搜索方法具有较强的针对性，因此，可以缩小搜索范围，提高搜索效率。4.5状态空间的启发式搜索54前面讨论的各种搜索方法都没有用到问题本身的特54

启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息又是通过估价函数作用到搜索过程中的。

1．启发性信息一.启发性信息和估价函数

启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。启发性信息一般有以下三种：

①有效地帮助确定扩展节点的信息；

②有效地帮助决定哪些后继节点应被生成；

③能决定在扩展一个节点时哪些节点应从搜索树上被删除。

一般来说，搜索过程所使用的启发性信息的启发能力越强，扩展的无用节点就越少。55启发式搜索方法所依据的是问题自身的启发性信息55

2．估价函数用来估计节点重要性的函数称为估价函数。估价函数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)562．估价函数用来估计节点重要性的函数称为估56例：八数码难题。设问题的初始状态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

这个例子仅是为了说明估价函数的含义及估价函数值的计算。在问题搜索过程中，除了需要计算初始节点的估价函数之外，更多的是要计算新生成节点的估价函数值。

2831476557例：八数码难题。设问题的初始状态S0和目标状态Sg如前57二.A算法

在图搜索算法中，如果能在搜索的每一步都利用估价函数f（n）=g（n）＋h（n）对Open表中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息，因此，A算法也被称为启发式搜索算法。

对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。58二.A算法在图搜索算法中，如果能在搜索的58每当需要扩展节点时，总是从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．全局择优搜索59每当需要扩展节点时，总是从Open表的所有节点中选择59由于上述算法的第（7）步要对Open表中的全部节点按其估价函数值从小到大重新进行排序，这样在算法第（3）步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。

对上述算法进一步分析还可以发现：如果取估价函数f(n)=g（n），则它将退化为代价树的广度优先搜索；如果取估价函数f(n)=d（n），则它将退化为广度优先搜索。可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。60由于上述算法的第（7）步要对Open表中的全60例：八数码难题。2834765S028314765238476528347652836475

8321476528371465

23847652384765

S9

4123847651238476512378465S5

5S66

S8

6

S7

4SgS10

4S11

6S1

4S2

4

S3

5S4

561例：八数码难题。283S0283261在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：（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．局部择优搜索(瞎子爬山法)62在局部择优搜索中，每当需要扩展节点时，总是从62

由于这一算法的第（6）步仅是把刚生成的子节点按其估价函数值从小到大放入Open表的首都，这样在算法第（3）步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。对这一算法进一步分析也可以发现：如果取估价函数f（n）=g（n），则它将退化为代价树的深度优先搜索；如果取估价函数f（n）=d（n），则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。63由于这一算法的第（6）步仅是把刚生成的子节点63三.A*算法前面讨论的启发式搜索算法，都没有对估价函数f(n)作任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的解，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制。A*算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。64三.A*算法前面讨论的启发式搜索算法，都没64假设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*算法。65假设f*(n)为从初始节点S0出发，约束经过65A*算法的有关特性。

1．A*算法的可纳性

一般来说，对任意一个状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的。A*算法是可采纳的。(证明略）。

2.A*算法的最优性

A*算法的搜索效率很大程度上取决于估价函数h（n）。一般来说，在满足h（n）≤h*（n）的前提下，h（n）的值越大越好。h（n）的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。A*算法的这一特性也称为信息性。(证明略)66A*算法的有关特性。

1366A*算法应用举例

例：八数码难题。问题的初始状态和目标状态和前例相同。要求用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*算法的限制条件。

23847655238476167A*算法应用举例

例：八数码难题。问题的初始状态和目标状6728314765h*=4,f=4S0231

8476528316475283

1476528314765g*=1

2318476523184765g*=21

23847651

2378465Sgg*=4h*=5,f=6h*=5,f=6h*=3,f=4h*=5,f=6h*=2,f=4h*=4,f=61

2384765g*=3h*=1,f=4h*=0,f=4h*=1,f=6八数码难题h（n）=P（n）的搜索树68283h*=4,f=4S0232832868例：设有如下结构的移动将牌游戏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)=21BBBWWWEBBBWWWE69例：设有如下结构的移动将牌游戏BBBWWWEBBBWWWE169例：传教士和野人问题。请用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值。70例：传教士和野人问题。请用A*算法解决该问题。

解：用m表示70(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)71(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=717219724.4与/或树的盲目搜索734.4与/或树的盲目搜索2073概念:直接可解的简单问题称为本原问题，本原问题对应的节点称为终止节点，在与或图（树）中无子节点的节点称为端节点，一个节点的子节点如果是“与”关系，则该节点便称为与节点，一个节点的子节点如果是“或”关系，则该节点便称为或节点。注意，终止节点一定是端节点，但端节点不一定是终止节点。可解性判别(1)一个节点是可解，则节点须满足下列条件之一:①终止节点是可解节点；②一个与节点可解，当且仅当其子节点全都可解；③一个或节点可解，只要其子节点至少有一个可解。(2)一个节点是不可解，则节点须满足下列条件之一:①非终止节点的端节点是不可解节点；②一个与节点不可解，只要其子节点至少有一个不可解；③一个或节点不可解，当且仅当其子节点全都不可解。74概念:2174一.与/或树的一般搜索与/或树的搜索过程实际上是一个不断寻找解树的过程。其一般搜索过程如下：

（1）把原始问题作为初始节点S0，并把它作为当前节点；

（2）应用分解或等价变换操作对当前节点进行扩展；

（3）为每个子节点设置指向父节点的指针；

（4）选择合适的子节点作为当前节点，反复执行第（2）步和第（3）步，在此期间需要多次调用可解标记过程或不可解标记过程，直到初始节点被标记为可解节点或不可解节点为止。

上述搜索过程将形成一棵与/或树，这种由搜索过程形成的与/或树称为搜索树。当搜索成功时，经可解标记过程标识的由初始节点及其下属的可解节点构成的子树称为解树。用与/或树法表示的问题求解过程与状态空间法类似，也是通过搜索来实现对问题求解的。与/或树的搜索策略也分为盲目搜索和启发式搜索两大类。75一.与/或树的一般搜索与/或树的搜索过程实75搜索过程中的可解标记过程与不可解标记过程都是自下而上进行的，即由子节点的可解性确定父节点、祖父节点的可解性；由子节点的不可解性确定父节点、祖父节点的不可解性。在与/或树中，除端节点和终止节点外，一个节点的可解性完全是由其子节点来决定的。对与节点，只有其所有子节点都为可解时它才为可解，只要有一个子节点不可解它就是不可解的；对或节点，只要有一个子节点可解它就是可解的，仅当所有子节点都是不可解时它才为不可解。这种由可解子节点来确定其父节点、祖父节点为可解节点的过程称为可解标记过程；由不可解子节点来确定其父节点、祖父节点为不可解节点的过程称为不可解标记过程。

由于与/或树搜索的目标是寻找解树，因此，如果搜索过程确定某个节点为可解节点，则其不可解的后裔节点就可从搜索树中删去；同样，如果搜索过程能确定某个节点为不可解节点，则其后裔节点也可从搜索树中删去。76搜索过程中的可解标记过程与不可解标记过程都是自下而上进行的，76与状态空间的广度优先搜索类似，只是在搜索过程中需要多次调用可解标记过程或不可解标记过程，其搜索算法如下：

（1）把初始节点S0放人Open表中；

（2）把Open表的第一个节点取出放入Closed表，并记该节点为n；

（3）如果节点n可扩展，则做下列工作：

①扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针；

②考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解节点进行标记。如果初始解节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点；

③

转第（2）步。二.与/或树的广度优先搜索77与状态空间的广度优先搜索类似，只是在搜索过程77（4）如果节点n不可扩展，则做下列工作：

①

标记节点n为不可解节点；

②

应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始解节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从Open表中删去具有不可解先辈的节点；

③转第（2）步。78（4）如果节点n不可扩展，则做下列工作：

78例：设有如下图所示的与/或树，节点按图中所标注的顺序号进行扩展，其中标有t1、t2、t3的节点是终止节点，A、B、C为不可解的端节点。

与/或树的广度优先搜索123A4t1t3CBt25搜索过程为：

（1）先扩展1号节点，生成2号节点和3号节点，由于这两个子节点都不是终止节点，因此接着扩展2号节点。（2）扩展2号节点，生成A节点和4号节点。由于这两个子节点均不是终止节点，因此接着扩展3号节点。（3）扩展3