人工智能课件42

4.2状态空间的盲目搜索五.代价树搜索在前面讨论的各种搜索策略中，实际上都作了一种假设，认为状态空间中各边的代价都相同，且都为一个单位量。从而，可用路径的长度来代替路径的代价。但是，对许多实际问题，这种假设是不现实的，它们的状态空间中的各个边的代价不可能完全相同。例如，城市交通问题，各城市之间的距离是不同的。为此，我们需要在搜索树中给每条边都标上其代价。这种边上标有代价的树称为代价树。

在代价树中，可以用g（n）表示从初始节点S0到节点n的代价，用c（n1，n2）表示从父节点n1到其子节点n2的代价。这样，对节点n2的代价有

g（n2）=g（n1）＋c（n1，n2）

在代价树中，最小代价的路径和最短路径（即路径长度最短）是有可能不同的。最短路径不一定是最小代价路径；最小代价路径不一定是最短路径。代价树搜索的目的是为了找到最佳解，即找到一条代价最小的解路径。

前面所讨论的广度优先搜索策略和深度优先搜索策略都可应用到代价树的搜索上来，因此，代价树搜索也可分为代价树的广度优先搜索和代价树的深度优先搜索。14.2状态空间的盲目搜索五.代价树搜索在前面讨论4.2状态空间的盲目搜索五.代价树搜索1．代价树的广度优先搜索

代价树的广度优先搜索也称为分枝界限法。它每次从Open表中选择节点或往Closed表中存放节点时，总是选择代价最小的节点。也就是说，Open表中的节点总是按照其代价从小到大排列的，代价小的节点排在前面，代价大的节点排在后面，与节点在树中的位置无关。

24.2状态空间的盲目搜索五.代价树搜索1．代价树的广度4.2状态空间的盲目搜索五.代价树搜索

1．代价树的广度优先搜索

代价树的广度优先搜索算法如下：

（1）把初始节点S0放人Open表中，置S0的代价g(S0)=0；

（2）如果Open表为空，则问题无解，失败退出；

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

（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；

（5）若节点n不可扩展，则转第（2）步；

（6）扩展节点n，生成其子节点ni,（其中i=1,2,3,……），将这些子节点放入Open表中，并为每一个子节点设置指向父节点的指针；按如下公式g（ni）=g(n)＋c(n，ni)（i=1，2，…）计算Open表中的各子节点的代价，并根据各节点的代价对Open表中的全部节点按照从小到大顺序重新进行排序；然后转第（2）步。

代价树的广度优先搜索策略是完备的。如果问题有解，上述算法一定能够找到它，并且找到的一定是最优解。34.2状态空间的盲目搜索五.代价树搜索1．代价树的广度

例：城市交通问题。设有5个城市，它们之间的交通线路如左下图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从A市出发到E市，费用最小的交通路线。

解：左图是一个网络图，它不能直接用于搜索算法，需要先将其转换为代价树。转换后的代价树如右图所示。

城市交通图城市交通图的代价树ACDEB323445AC1B1D1E2B2E4D2E1C2E33445322345814119

1．代价树的广度优先搜索4例：城市交通问题。设有5个城市，它们之间的交通线路如左把一个网络图转换为代价树的方法是：

从起始节点A开始，把与它直接连接的节点作为其子节点。对其他节点也作同样处理。但当一个节点已作为某个节点的直系先辈节点时，就不能再作为这个节点的子节点。例如，上页左图中与节点B直接相邻的节点有节点A、D、E，但由于A已作为B的父节点在代价树中出现过了，因此A不能再作为B的子节点。此外，图中的节点除初始节点A外，其他节点都可能在代价树中出现多次，为区别它们的多次出现，分别用下标1，2，…标出，但实际上是同一个节点。

对上页右图所示的代价树，按广度优先搜索可得到最优解

A→C1→D1→E2

其代价为8。可见，从A市到E市的最小费用路线为

A→C→D→E

1．代价树的广度优先搜索4.2状态空间的盲目搜索五.代价树搜索5把一个网络图转换为代价树的方法是：

从起始节点A开始

代价树的深度优先搜索和代价树的广度优先搜索的区别在于每次选择最小代价节点的范围不同。广度优先搜索每次都是从Open表的全体节点中选择一个代价最小的节点，而深度优先搜索则是从刚扩展的子节点中选择一个代价最小的节点。

2．代价树的深度优先搜索4.2状态空间的盲目搜索五.代价树搜索6代价树的深度优先搜索和代价树的广度优先搜索的区别在于代价树的深度优先搜索算法如下：

（1）把初始节点S0放入Open表中，置S0的代价g（S0）=0；

（2）如果Open表为空，则问题无解，失败退出；

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

（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；

（5）若节点n不可扩展，则转第（2）步；

（6）扩展节点n，生成其子节点ni(i=1，2，…），将这些子节点按代价由小到大放入Open表的首部，并为每一个子节点设置指向父节点的指针。然后转第（2）步。

对上面的城市交通问题，用代价树的深度优先搜索找到的路径为

A→C1→D1→E2

和广度优先搜索相比，找到的路径是相同的。这只是一种巧合。一般来说，它找到的解不一定是最优解，即代价树的深度优先搜索策略是不完备的，当搜索进入无穷分支时，算法将找不到解。

2．代价树的深度优先搜索7代价树的深度优先搜索算法如下：

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

启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息又是通过估价函数作用到搜索过程中的。因此，在讨论启发式搜索方法之前需要先给出启发性信息与估价函数的概念。

1．启发性信息4.3状态空间的启发式搜索一.启发性信息和估价函数

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

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

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

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

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

2．估价函数4.3状态空间的启发式搜索一.启发性信息和估价函数用来估计节点重要性的函数称为估价函数。估价函数f（n）被定义为从初始节点S0出发，经过节点n约束到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式为

估价函数f（n）=g（n）＋h（n）

其中，g（n）是从初始节点S0到节点n的实际代价；h（n）是从节点n到目标节点Sg的最优路径的估计代价。对g（n）的值，可以按指向父节点的指针，从节点n反向跟踪到初始节点S0,得到一条从初始节点S0到节点n的最小代价路径，然后把这条路径上所有有向边的代价相加，就得到g（n）的值。对h（n）的值，则需要根据问题自身的特性来确定，它体现的是问题自身的启发性信息，因此也称h（n）为启发函数。102．估价函数4.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

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

28314765S011例：八数码难题。设问题的初始状态S0和目标状态Sg如前4.3状态空间的启发式搜索二.A算法

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

对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。124.3状态空间的启发式搜索二.A算法在图搜索算法4.3状态空间的启发式搜索二.A算法在全局择优搜索中，每当需要扩展节点时，总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：

（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表中；

（7）根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；

（8）转第（2）步。

1．全局择优搜索134.3状态空间的启发式搜索二.A算法在全局择优搜4.3状态空间的启发式搜索二.A算法由于上述算法的第（7）步要对Open表中的全部节点按其估价函数值从小到大重新进行排序，这样在算法第（3）步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。

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

1．全局择优搜索144.3状态空间的启发式搜索二.A算法由于上述算法

1．全局择优搜索二.A算法3.3状态空间的启发式搜索例：八数码难题。设问题的初始状态S0和目标状态Sg如前所述，估价函数与上例相同。请用全局择优搜索解决该问题。

解：这个问题的全局择优搜索树如图。在图中，每个节点旁边的数字是该节点的估价函数值。例如，对节点S2，其估价函数值的计算为

f（S2）=d（S2）＋W（S2）=1＋3=4

从该图还可以看出，该问题的解为

S0→S2→S7→S9→Sg八数码难题的全局择优搜索树283

4765S0283

14765238476528347652836475

8321476528371465

23847652384765

S94123847651238476512378465S55S66

S86

S74Sg

S104S116S14S24

S35S45151．全局择优搜索二.A算法3.3状态空间的启发式搜索例4.3状态空间的启发式搜索二.A算法在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：（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．局部择优搜索164.3状态空间的启发式搜索二.A算法在局部择优搜4.3状态空间的启发式搜索二.A算法

由于这一算法的第（6）步仅是把刚生成的子节点按其估价函数值从小到大放入Open表的首都，这样在算法第（3）步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。对这一算法进一步分析也可以发现：如果取估价函数f（n）=g（n），则它将退化为代价树的深度优先搜索；如果取估价函数f（n）=d（n），则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。

2．局部择优搜索174.3状态空间的启发式搜索二.A算法由于这一算法4.3状态空间的启发式搜索三.A*算法上一节讨论的启发式搜索算法，都没有对估价函数f(n)作任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的解，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制。A*算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。184.3状态空间的启发式搜索三.A*算法上一节讨论的4.3状态空间的启发式搜索三.A*算法假设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*算法。194.3状态空间的启发式搜索三.A*算法假设f*(有了A*算法的概念，下面就来讨论A*算法的有关特性。

1．A*算法的可纳性

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

2.A*算法的最优性

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

4.3状态空间的启发式搜索三.A*算法20有了A*算法的概念，下面就来讨论A*算法的有关特性。

1．AA*算法应用举例

例：八数码难题。问题的初始状态和目标状态和前例相同。要求用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*算法的限制条件。其搜索过程所得到的搜索树如下页图所示。在该图中，节点旁边虽然没有标出P（n）的值p，但却标出了估价函数f（n）的f值。对解路径，还给出了各个节点的g*（n）和h*（n）的g*值和h*值。从这些值还可以看出，最佳路径上的节点都有f*=g*+h*=4。

4.3状态空间的启发式搜索三.A*算法21A*算法应用举例

例：八数码难题。问题的初始状态和目标状28314765h*=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*=3,f=51

2384765g*=3h*=1,f=4h*=0,f=4h*=2,f=6八数码难题h（n）=P（n）的搜索树22283h*=4,f=4S02328328A*算法应用举例

例：传教士和野人问题。请用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值。4.3状态空间的启发式搜索三.A*算法23A*算法应用举例

例：传教士和野人问题。请用A*算法解决该(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)24(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=4.2状态空间的盲目搜索五.代价树搜索在前面讨论的各种搜索策略中，实际上都作了一种假设，认为状态空间中各边的代价都相同，且都为一个单位量。从而，可用路径的长度来代替路径的代价。但是，对许多实际问题，这种假设是不现实的，它们的状态空间中的各个边的代价不可能完全相同。例如，城市交通问题，各城市之间的距离是不同的。为此，我们需要在搜索树中给每条边都标上其代价。这种边上标有代价的树称为代价树。

在代价树中，可以用g（n）表示从初始节点S0到节点n的代价，用c（n1，n2）表示从父节点n1到其子节点n2的代价。这样，对节点n2的代价有

g（n2）=g（n1）＋c（n1，n2）

在代价树中，最小代价的路径和最短路径（即路径长度最短）是有可能不同的。最短路径不一定是最小代价路径；最小代价路径不一定是最短路径。代价树搜索的目的是为了找到最佳解，即找到一条代价最小的解路径。

前面所讨论的广度优先搜索策略和深度优先搜索策略都可应用到代价树的搜索上来，因此，代价树搜索也可分为代价树的广度优先搜索和代价树的深度优先搜索。254.2状态空间的盲目搜索五.代价树搜索在前面讨论4.2状态空间的盲目搜索五.代价树搜索1．代价树的广度优先搜索

代价树的广度优先搜索也称为分枝界限法。它每次从Open表中选择节点或往Closed表中存放节点时，总是选择代价最小的节点。也就是说，Open表中的节点总是按照其代价从小到大排列的，代价小的节点排在前面，代价大的节点排在后面，与节点在树中的位置无关。

264.2状态空间的盲目搜索五.代价树搜索1．代价树的广度4.2状态空间的盲目搜索五.代价树搜索

1．代价树的广度优先搜索

代价树的广度优先搜索算法如下：

（1）把初始节点S0放人Open表中，置S0的代价g(S0)=0；

（2）如果Open表为空，则问题无解，失败退出；

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

（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；

（5）若节点n不可扩展，则转第（2）步；

（6）扩展节点n，生成其子节点ni,（其中i=1,2,3,……），将这些子节点放入Open表中，并为每一个子节点设置指向父节点的指针；按如下公式g（ni）=g(n)＋c(n，ni)（i=1，2，…）计算Open表中的各子节点的代价，并根据各节点的代价对Open表中的全部节点按照从小到大顺序重新进行排序；然后转第（2）步。

代价树的广度优先搜索策略是完备的。如果问题有解，上述算法一定能够找到它，并且找到的一定是最优解。274.2状态空间的盲目搜索五.代价树搜索1．代价树的广度

例：城市交通问题。设有5个城市，它们之间的交通线路如左下图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从A市出发到E市，费用最小的交通路线。

解：左图是一个网络图，它不能直接用于搜索算法，需要先将其转换为代价树。转换后的代价树如右图所示。

城市交通图城市交通图的代价树ACDEB323445AC1B1D1E2B2E4D2E1C2E33445322345814119

1．代价树的广度优先搜索28例：城市交通问题。设有5个城市，它们之间的交通线路如左把一个网络图转换为代价树的方法是：

从起始节点A开始，把与它直接连接的节点作为其子节点。对其他节点也作同样处理。但当一个节点已作为某个节点的直系先辈节点时，就不能再作为这个节点的子节点。例如，上页左图中与节点B直接相邻的节点有节点A、D、E，但由于A已作为B的父节点在代价树中出现过了，因此A不能再作为B的子节点。此外，图中的节点除初始节点A外，其他节点都可能在代价树中出现多次，为区别它们的多次出现，分别用下标1，2，…标出，但实际上是同一个节点。

对上页右图所示的代价树，按广度优先搜索可得到最优解

A→C1→D1→E2

其代价为8。可见，从A市到E市的最小费用路线为

A→C→D→E

1．代价树的广度优先搜索4.2状态空间的盲目搜索五.代价树搜索29把一个网络图转换为代价树的方法是：

从起始节点A开始

代价树的深度优先搜索和代价树的广度优先搜索的区别在于每次选择最小代价节点的范围不同。广度优先搜索每次都是从Open表的全体节点中选择一个代价最小的节点，而深度优先搜索则是从刚扩展的子节点中选择一个代价最小的节点。

2．代价树的深度优先搜索4.2状态空间的盲目搜索五.代价树搜索30代价树的深度优先搜索和代价树的广度优先搜索的区别在于代价树的深度优先搜索算法如下：

（1）把初始节点S0放入Open表中，置S0的代价g（S0）=0；

（2）如果Open表为空，则问题无解，失败退出；

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

（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；

（5）若节点n不可扩展，则转第（2）步；

（6）扩展节点n，生成其子节点ni(i=1，2，…），将这些子节点按代价由小到大放入Open表的首部，并为每一个子节点设置指向父节点的指针。然后转第（2）步。

对上面的城市交通问题，用代价树的深度优先搜索找到的路径为

A→C1→D1→E2

和广度优先搜索相比，找到的路径是相同的。这只是一种巧合。一般来说，它找到的解不一定是最优解，即代价树的深度优先搜索策略是不完备的，当搜索进入无穷分支时，算法将找不到解。

2．代价树的深度优先搜索31代价树的深度优先搜索算法如下：

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

启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息又是通过估价函数作用到搜索过程中的。因此，在讨论启发式搜索方法之前需要先给出启发性信息与估价函数的概念。

1．启发性信息4.3状态空间的启发式搜索一.启发性信息和估价函数

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

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

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

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

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

2．估价函数4.3状态空间的启发式搜索一.启发性信息和估价函数用来估计节点重要性的函数称为估价函数。估价函数f（n）被定义为从初始节点S0出发，经过节点n约束到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式为

估价函数f（n）=g（n）＋h（n）

其中，g（n）是从初始节点S0到节点n的实际代价；h（n）是从节点n到目标节点Sg的最优路径的估计代价。对g（n）的值，可以按指向父节点的指针，从节点n反向跟踪到初始节点S0,得到一条从初始节点S0到节点n的最小代价路径，然后把这条路径上所有有向边的代价相加，就得到g（n）的值。对h（n）的值，则需要根据问题自身的特性来确定，它体现的是问题自身的启发性信息，因此也称h（n）为启发函数。342．估价函数4.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

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

28314765S035例：八数码难题。设问题的初始状态S0和目标状态Sg如前4.3状态空间的启发式搜索二.A算法

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

对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。364.3状态空间的启发式搜索二.A算法在图搜索算法4.3状态空间的启发式搜索二.A算法在全局择优搜索中，每当需要扩展节点时，总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：

（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表中；

（7）根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；

（8）转第（2）步。

1．全局择优搜索374.3状态空间的启发式搜索二.A算法在全局择优搜4.3状态空间的启发式搜索二.A算法由于上述算法的第（7）步要对Open表中的全部节点按其估价函数值从小到大重新进行排序，这样在算法第（3）步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。

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

1．全局择优搜索384.3状态空间的启发式搜索二.A算法由于上述算法

1．全局择优搜索二.A算法3.3状态空间的启发式搜索例：八数码难题。设问题的初始状态S0和目标状态Sg如前所述，估价函数与上例相同。请用全局择优搜索解决该问题。

解：这个问题的全局择优搜索树如图。在图中，每个节点旁边的数字是该节点的估价函数值。例如，对节点S2，其估价函数值的计算为

f（S2）=d（S2）＋W（S2）=1＋3=4

从该图还可以看出，该问题的解为

S0→S2→S7→S9→Sg八数码难题的全局择优搜索树283

4765S0283

14765238476528347652836475

8321476528371465

23847652384765

S94123847651238476512378465S55S66

S86

S74Sg

S104S116S14S24

S35S45391．全局择优搜索二.A算法3.3状态空间的启发式搜索例4.3状态空间的启发式搜索二.A算法在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：（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．局部择优搜索404.3状态空间的启发式搜索二.A算法在局部择优搜4.3状态空间的启发式搜索二.A算法

由于这一算法的第（6）步仅是把刚生成的子节点按其估价函数值从小到大放入Open表的首都，这样在算法第（3）步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。对这一算法进一步分析也可以发现：如果取估价函数f（n）=g（n），则它将退化为代价树的深度优先搜索；如果取估价函数f（n）=d（n），则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。

2．局部择优搜索414.3状态空间的启发式搜索二.A算法由于这一算法4.3状态空间的启发式搜索三.A*算法上一节讨论的启发式搜索算法，都没有对估价函数f(n)作任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的解，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制。A*算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。424.3状态空间的启发式搜索三.A*算法上一节讨论的4.3状态空间的启发式搜索三.A*算法假设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*算法。434.3状态空间的启发式搜索三.A*算法假设f*(有了A*算法的概念，下面就来讨论A*算法的有关特性。

1