1、4.2 4.2 状态空间的盲目搜索状态空间的盲目搜索五五. . 代价树搜索代价树搜索 在前面讨论的各种搜索策略中，实际上都作了一种假设，认为状态空间在前面讨论的各种搜索策略中，实际上都作了一种假设，认为状态空间中中各边的代价都相同，且都为一个单位量各边的代价都相同，且都为一个单位量。从而，可用路径的长度来代替路。从而，可用路径的长度来代替路径的代价。但是，对许多实际问题，这种假设是不现实的，它们的状态空间径的代价。但是，对许多实际问题，这种假设是不现实的，它们的状态空间中的各个边的代价不可能完全相同。例如，城市交通问题，各城市之间的距中的各个边的代价不可能完全相同。例如，城市交通问题，各城市之
2、间的距离是不同的。为此，我们需要在搜索树中给每条边都标上其代价。离是不同的。为此，我们需要在搜索树中给每条边都标上其代价。这种边上这种边上标有代价的树称为标有代价的树称为代价树代价树。 在代价树中，可以用在代价树中，可以用g g（n n）表示从初始节点表示从初始节点S0S0到节点到节点n n的代价，用的代价，用c c（n1n1，n2n2）表示从父节点表示从父节点n1n1到其子节点到其子节点n2n2的代价。这样，对节点的代价。这样，对节点n2n2的代价有的代价有 g g（n2n2）=g=g（n1n1）c c（n1n1，n2n2） 在代价树中，在代价树中，最小代价的路径最小代价的路径和和最短路径最
3、短路径（即路径长度最短）是有可能（即路径长度最短）是有可能不同的。最短路径不一定是最小代价路径；最小代价路径不一定是最短路径。不同的。最短路径不一定是最小代价路径；最小代价路径不一定是最短路径。代价树搜索的目的是为了找到代价树搜索的目的是为了找到最佳解最佳解，即找到一条，即找到一条代价最小代价最小的解路径的解路径。 前面所讨论的广度优先搜索策略和深度优先搜索策略都可应用到代价树前面所讨论的广度优先搜索策略和深度优先搜索策略都可应用到代价树的搜索上来，因此，代价树搜索也可分为代价树的广度优先搜索和代价树的的搜索上来，因此，代价树搜索也可分为代价树的广度优先搜索和代价树的深度优先搜索。深度优先搜索
4、。24.2 4.2 状态空间的盲目搜索状态空间的盲目搜索五五. . 代价树搜索代价树搜索 1 1代价树的广度优先搜索代价树的广度优先搜索 代价树的广度优先搜索也称为代价树的广度优先搜索也称为分枝界限法分枝界限法。它每。它每次从次从OpenOpen表中选择节点或往表中选择节点或往ClosedClosed表中存放节点时，表中存放节点时，总是选择总是选择代价最小代价最小的节点。也就是说，的节点。也就是说，OpenOpen表中的节表中的节点总是按照其代价从小到大排列的点总是按照其代价从小到大排列的，代价小的节点排，代价小的节点排在前面，代价大的节点排在后面，在前面，代价大的节点排在后面，与节点在树中的
5、与节点在树中的位位置无关置无关。4.2 4.2 状态空间的盲目搜索状态空间的盲目搜索五五. . 代价树搜索代价树搜索 1 1代价树的广度优先搜索代价树的广度优先搜索 代价树的广度优先搜索算法如下：代价树的广度优先搜索算法如下： （1 1）把初始节点把初始节点 S0S0放人放人 OpenOpen表中，表中，置置S0S0的代价的代价 g(S0)=0g(S0)=0； （2 2）如果如果OpenOpen表为空，则问题无解，失败退出；表为空，则问题无解，失败退出； （3 3）把把 OpenOpen表的第一个节点取出放入表的第一个节点取出放入 ClosedClosed表，并记该节点为表，并记该节点为n n
6、； （4 4）考察节点考察节点n n是否为目标节点。若是，则找到了问题的解，成功退出；是否为目标节点。若是，则找到了问题的解，成功退出； （5 5）若节点若节点n n不可扩展，则转第（不可扩展，则转第（2 2）步；）步； （6 6）扩展节点扩展节点 n n，生成其子节点生成其子节点 nini, , （其中其中i=1,2,3,i=1,2,3,），），将这些子将这些子节点放入节点放入 OpenOpen表中，并为每一个子节点设置指向父节点的指针；按如下公式表中，并为每一个子节点设置指向父节点的指针；按如下公式 g g（nini）= =g(n)g(n)c(nc(n，ni)ni)（i i=1=1，2 2
7、，）计算计算OpenOpen表中的各子节点的表中的各子节点的代价代价，并，并根据各节点的代价根据各节点的代价对对OpenOpen表中的表中的全部全部节点节点按照按照从小到大从小到大顺序重新进行排序；然顺序重新进行排序；然后转第（后转第（2 2）步。）步。 代价树的广度优先搜索策略是代价树的广度优先搜索策略是完备的完备的。如果问题有解，上述算法一定能。如果问题有解，上述算法一定能够找到它，并且找到的一定是最优解。够找到它，并且找到的一定是最优解。4 例：例：城市交通问题。设有城市交通问题。设有5 5个城市，它们之间的交通线路如左下图个城市，它们之间的交通线路如左下图所示，图中的数字表示两个城市之
8、间的交通费用，即代价。用代价树的所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从广度优先搜索，求从A A市出发到市出发到E E市，费用最小的交通路线。市，费用最小的交通路线。 解解：左图是一个网络图，它不能直接用于搜索算法，需要先将其：左图是一个网络图，它不能直接用于搜索算法，需要先将其转换为代价树。转换后的代价树如右图所示。转换为代价树。转换后的代价树如右图所示。 城市交通图城市交通图 城市交通图的代价树城市交通图的代价树ACDEB323445AC1B1D1E2B2E4D2E1C2E33445322345814119 1代价树的广度优先搜索代价树的广度优先搜索
9、5把一个网络图转换为代价树的方法是：把一个网络图转换为代价树的方法是： 从起始节点从起始节点A A开始，把与它开始，把与它直接连接直接连接的节点作为其子节点。对其他节点也作的节点作为其子节点。对其他节点也作同样处理。但同样处理。但当一个节点已作为某个节点的直系先辈节点时，就不能再作为这个当一个节点已作为某个节点的直系先辈节点时，就不能再作为这个节点的子节点节点的子节点。例如，上页左图中与节点。例如，上页左图中与节点B B直接相邻的节点有节点直接相邻的节点有节点A A、D D、E E，但由但由于于A A已作为已作为B B的父节点在代价树中出现过了，因此的父节点在代价树中出现过了，因此A A不能再
10、作为不能再作为B B的子节点。此外，的子节点。此外，图中的节点除初始节点图中的节点除初始节点A A外，其他节点都可能在代价树中出现多次，为区别它们外，其他节点都可能在代价树中出现多次，为区别它们的多次出现，分别用下标的多次出现，分别用下标1 1，2 2，标出，但实际上是同一个节点。标出，但实际上是同一个节点。 对上页右图所示的代价树，按广度优先搜索可得到最优解对上页右图所示的代价树，按广度优先搜索可得到最优解 A C1D1E2A C1D1E2其代价为其代价为8 8。可见，从。可见，从A A市到市到E E市的最小费用路线为市的最小费用路线为 ACDEACDE 1代价树的广度优先搜索代价树的广度优
11、先搜索4.2 4.2 状态空间的盲目搜索状态空间的盲目搜索五五. . 代价树搜索代价树搜索6 代价树的深度优先搜索和代价树的广度优先搜索代价树的深度优先搜索和代价树的广度优先搜索的区别在于每次的区别在于每次选择最小代价节点的范围不同选择最小代价节点的范围不同。广度广度优先优先搜索每次都是从搜索每次都是从OpenOpen表的表的全体节点全体节点中选择中选择一个代一个代价最小的节点，而价最小的节点，而深度优先深度优先搜索则是搜索则是从从刚扩展刚扩展的子节的子节点中选择一个代价最小的节点点中选择一个代价最小的节点。 2代价树的深度优先搜索代价树的深度优先搜索4.2 4.2 状态空间的盲目搜索状态空间
12、的盲目搜索五五. . 代价树搜索代价树搜索代价树的深度优先搜索算法如下：代价树的深度优先搜索算法如下： （1 1）把初始节点把初始节点 S0S0放入放入 OpenOpen表中，置表中，置S0S0的代价的代价 g g（S0S0）=0=0； （2 2）如果如果 OpenOpen表为空，则问题无解，失败退出；表为空，则问题无解，失败退出； （3 3）把把OpenOpen表的第一个节点取出放入表的第一个节点取出放入ClosedClosed表，并记该节点为表，并记该节点为n n； （4 4）考察节点考察节点n n是否为目标节点。若是，则找到了问题的解，成功退出；是否为目标节点。若是，则找到了问题的解，成
13、功退出； （5 5）若节点若节点n n不可扩展，则转第（不可扩展，则转第（2 2）步；）步； （6 6）扩展节点扩展节点n n，生成其子节点生成其子节点nini (i=1 (i=1，2 2，），），将将这些子节点这些子节点按代价按代价由小到大放入由小到大放入OpenOpen表的表的首部首部，并为每一个子节点设置指向父节点的指针。然后，并为每一个子节点设置指向父节点的指针。然后转第（转第（2 2）步。）步。 对上面的城市交通问题，用代价树的深度优先搜索找到的路径为对上面的城市交通问题，用代价树的深度优先搜索找到的路径为 AC1D1E2AC1D1E2 和广度优先搜索相比，找到的路径是相同的。和广度
14、优先搜索相比，找到的路径是相同的。这只是一种巧合这只是一种巧合。一般。一般来说，它找到的解不一定是最优解，即代价树的深度优先搜索策略是来说，它找到的解不一定是最优解，即代价树的深度优先搜索策略是不完备不完备的，的，当搜索进入无穷分支时，算法将找不到解。当搜索进入无穷分支时，算法将找不到解。 2代价树的深度优先搜索代价树的深度优先搜索8 前面讨论的各种搜索方法都没有用到问题本身前面讨论的各种搜索方法都没有用到问题本身的特性信息，只是按照事先设定的线路进行搜索，的特性信息，只是按照事先设定的线路进行搜索，具有较大的盲目性。事实上，如果能够利用搜索过具有较大的盲目性。事实上，如果能够利用搜索过程所得
15、到的问题自身的一些特性信息来程所得到的问题自身的一些特性信息来指导指导搜索过搜索过程，则对搜索将是十分有益的。这种程，则对搜索将是十分有益的。这种利用问题自身利用问题自身的特性信息的特性信息来引导搜索过程的搜索方法称为来引导搜索过程的搜索方法称为启发式启发式搜索搜索。由于启发式搜索方法具有较强的针对性，因。由于启发式搜索方法具有较强的针对性，因此，可以缩小搜索范围，提高搜索效率。此，可以缩小搜索范围，提高搜索效率。4.3 4.3 状态空间的启发式搜索状态空间的启发式搜索9 启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息又是通
16、过又是通过估价函数估价函数作用到搜索过程中的。因此，在讨论启发式搜索方法作用到搜索过程中的。因此，在讨论启发式搜索方法之前需要先给出启发性信息与估价函数的概念。之前需要先给出启发性信息与估价函数的概念。 1启发性信息启发性信息4.3 4.3 状态空间的启发式搜索状态空间的启发式搜索一一. . 启发性信息和估价函数启发性信息和估价函数 启发性信息启发性信息是指那种是指那种与具体问题求解过程有关与具体问题求解过程有关的，并可指导搜索过的，并可指导搜索过程朝着最有希望方向前进的程朝着最有希望方向前进的控制信息控制信息。启发性信息一般有以下三种：。启发性信息一般有以下三种： 有效地帮助有效地帮助确定扩
17、展节点确定扩展节点的信息；的信息； 有效地帮助决定有效地帮助决定哪些后继节点应被生成哪些后继节点应被生成； 能决定在扩展一个节点时能决定在扩展一个节点时哪些节点应哪些节点应从搜索树上从搜索树上被删除被删除。 一般来说，搜索过程所使用的启发性信息的启发能力越强，扩一般来说，搜索过程所使用的启发性信息的启发能力越强，扩展的无用节点就越少。展的无用节点就越少。 2估价函数估价函数4.3 4.3 状态空间的启发式搜索状态空间的启发式搜索一一. . 启发性信息和估价函数启发性信息和估价函数 用来估计用来估计节点重要性节点重要性的函数称为的函数称为估价函数估价函数。估价函数。估价函数f f（n n）被定义
18、为从初被定义为从初始节点始节点S0S0出发，出发，经过节点经过节点n n约束约束到达目标节点到达目标节点SgSg的所有路径中最小路径代价的的所有路径中最小路径代价的估计值。它的一般形式为估计值。它的一般形式为 估价函数估价函数f f（n n）=g=g（n n）h h（n n）其中，其中，g g（n n）是从初始节点是从初始节点S0S0到节点到节点n n的的实际代价实际代价；h h（n n）是从节点是从节点n n到目标节到目标节点点SgSg的最优路径的的最优路径的估计代价估计代价。 对对g g（n n）的值，可以按指向父节点的指针，从节点的值，可以按指向父节点的指针，从节点n n反向跟踪到初始节
19、点反向跟踪到初始节点S0,S0,得到一条从初始节点得到一条从初始节点S0S0到节点到节点n n的最小代价路径，然后把这条路径上所有有的最小代价路径，然后把这条路径上所有有向边的代价相加，就得到向边的代价相加，就得到g g（n n）的值。的值。 对对h h（n n）的值，则需要根据问题自身的特性来确定，它的值，则需要根据问题自身的特性来确定，它体现的是问题自身体现的是问题自身的启发性信息，因此也称的启发性信息，因此也称h h（n n）为启发函数为启发函数。例例： 八数码难题。设问题的初始状态八数码难题。设问题的初始状态S0S0和目标状态和目标状态 SgSg 如前所述，且估如前所述，且估价函数为价
20、函数为: : f f（n n）=d=d（n n）W W（n n）其中，其中，d d（n n）表示节点表示节点 n n在搜索树中的深度；在搜索树中的深度； w w（n n）表示节点表示节点 n n中中“不不在位在位”的数码个数。请计算初始状态的数码个数。请计算初始状态S0S0的估价函数值的估价函数值f f（S0S0）。）。 解解：在本例的估价函数中，取：在本例的估价函数中，取g g（n n）=d=d（n n），），h h（n n）=W=W（n n）。）。它说它说明是用从明是用从S0S0到到n n的路径上的单位代价表示实际代价，用的路径上的单位代价表示实际代价，用n n中中“不在位不在位”的数的数
21、码个数作为启发信息。一般来说，某节点中的码个数作为启发信息。一般来说，某节点中的“不在位不在位”的数码个数越多，的数码个数越多，说明它离目标节点越远。说明它离目标节点越远。 对初始节点对初始节点 S0S0，由于由于 d d（S0S0）= 0= 0， W W（S0S0）= 3= 3，因此有因此有 f f（S0S0）=0=03=33=3 这个例子仅是为了说明估价函数的含义及估价函数值的计算。在这个例子仅是为了说明估价函数的含义及估价函数值的计算。在问题搜索过程中，除了需要计算初始节点的估价函数之外，更多的是要计问题搜索过程中，除了需要计算初始节点的估价函数之外，更多的是要计算新生成节点的估价函数值
22、。算新生成节点的估价函数值。 2 8 31 47 6 5S0124.3 4.3 状态空间的启发式搜索状态空间的启发式搜索二二. . A A算法算法 在图搜索算法中，如果能在搜索的每一步都在图搜索算法中，如果能在搜索的每一步都利用利用估价函数估价函数f f（n n）=g=g（n n）h h（n n）对对OpenOpen表中的节点表中的节点进行进行排序排序，则该搜索算法为，则该搜索算法为A A算法算法。由于估价函数中。由于估价函数中带有问题自身的启发性信息，因此，带有问题自身的启发性信息，因此，A A算法算法也被称为也被称为启发式搜索算法启发式搜索算法。 对启发式搜索算法，又可根据搜索过程中选择扩
23、对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为展节点的范围，将其分为全局择优搜索算法全局择优搜索算法和和局部择局部择优搜索算法优搜索算法。4.3 4.3 状态空间的启发式搜索状态空间的启发式搜索二二. . A A算法算法 在在全局择优全局择优搜索中，每当需要扩展节点时，总是从搜索中，每当需要扩展节点时，总是从OpenOpen表的表的所有节点所有节点中选中选择一个择一个估价函数值最小估价函数值最小的节点进行扩展。其搜索过程可描述如下：的节点进行扩展。其搜索过程可描述如下： （1 1）把初始节点把初始节点S0S0放入放入OpenOpen表中，表中，f(S0)=gf(S0)=g（S
24、0S0）h h（S0S0）；）； （2 2）如果如果OpenOpen表为空，则问题无解，失败退出；表为空，则问题无解，失败退出； （3 3）把把OpenOpen表的第一个节点取出放入表的第一个节点取出放入ClosedClosed表，并记该节点为表，并记该节点为n n； （4 4）考察节点考察节点n n是否为目标节点。若是，则找到了问题的解，成功退出；是否为目标节点。若是，则找到了问题的解，成功退出； （5 5）若节点若节点n n不可扩展，则转第（不可扩展，则转第（2 2）步；）步； （6 6）扩展节点扩展节点n n，生成其子节点生成其子节点nini（i i=1,2,=1,2,），），计算每一个
25、子节点的估计算每一个子节点的估价值价值f(nif(ni) ) （i=1,2,i=1,2,），），并为每一个子节点设置指向父节点的指针，然后并为每一个子节点设置指向父节点的指针，然后将这些子节点放入将这些子节点放入 OpenOpen表中；表中； （7 7）根据各节点的估价函数值根据各节点的估价函数值，对，对OpenOpen表中的表中的全部节点按从小到大全部节点按从小到大的顺序的顺序重新进行排序；重新进行排序； （8 8）转第（转第（2 2）步。）步。 1全局择优搜索全局择优搜索4.3 4.3 状态空间的启发式搜索状态空间的启发式搜索二二. . A A算法算法 由于上述算法的第（由于上述算法的第（
26、7 7）步要对）步要对OpenOpen表中的表中的全部节点全部节点按其估价函数值从小到大重新进行排序，这样在算法第按其估价函数值从小到大重新进行排序，这样在算法第（3 3）步取出的节点就一定是）步取出的节点就一定是OpenOpen表的所有节点中估价函表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索数值最小的一个节点。因此，它是一种全局择优的搜索方式。方式。 对上述算法进一步分析还可以发现：如果取估价函对上述算法进一步分析还可以发现：如果取估价函数数f(n)=gf(n)=g（n n），则它将则它将退化为代价树的广度优先搜索退化为代价树的广度优先搜索；如果取估价函数如果取估价函
27、数f(n)=df(n)=d（n n），则它将则它将退化为广度优先搜退化为广度优先搜索索。可见，。可见，广度优先搜索和代价树的广度优先搜索是全广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例局择优搜索的两个特例。 1全局择优搜索全局择优搜索15 1全局择优搜索全局择优搜索二二. . A A算法算法3.3 3.3 状态空间的启发式搜索状态空间的启发式搜索例：例： 八数码难题。设问题的初始状态八数码难题。设问题的初始状态S0S0和目标状态和目标状态SgSg如前所述，如前所述，估价函数与上例相同。请用全局择优搜索解决该问题。估价函数与上例相同。请用全局择优搜索解决该问题。解解：这个问题的全局
28、择优搜索树如图。在图中，每个节点旁边的数字这个问题的全局择优搜索树如图。在图中，每个节点旁边的数字是该节点的估价函数值。例如，对节点是该节点的估价函数值。例如，对节点S2S2，其估价函数值的计算为其估价函数值的计算为 f f（S2S2）=d=d（S2S2）W W（S2S2）=1=13=43=4 从该图还可以看出，该问题的解为从该图还可以看出，该问题的解为 S0S2 S7 S9 S0S2 S7 S9 SgSg八数码难题的全局择优搜索树八数码难题的全局择优搜索树2 8 31 47 6 5S02 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5
29、8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 5 S9 41 2 3 8 47 6 51 2 38 47 6 51 2 3 7 8 4 6 5S5 5S6 6 S8 6 S7 4Sg S10 4S11 6S1 4S2 4 S3 5S4 5164.3 4.3 状态空间的启发式搜索状态空间的启发式搜索二二. . A A算法算法 在局部择优搜索中，每当需要扩展节点时，总是从在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点刚生成的子节点中中选选择一个估价函数值最小择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：的节点进行扩
30、展。其搜索过程可描述如下：（1 1）把初始节点把初始节点S0S0放入放入 OpenOpen表中，表中，f(S0)=g(S0)+h(S0) ;f(S0)=g(S0)+h(S0) ;（2 2）如果如果OpenOpen表为空，则问题无解，失败退出；表为空，则问题无解，失败退出；（3 3）把把OpenOpen表的第一个节点取出放入表的第一个节点取出放入ClosedClosed表，并记该节点为表，并记该节点为n n；（4 4）考察节点考察节点n n是否为目标节点。若是，则找到了问题的解，成功退出；是否为目标节点。若是，则找到了问题的解，成功退出；（5 5）若节点若节点n n不可扩展，则转第（不可扩展，则
31、转第（2 2）步；）步；（6 6）扩展节点扩展节点n n，生成其子节点生成其子节点ni(ini(i=1=1，2 2，) )，计算每一个子节点的估计算每一个子节点的估价值价值f f（nini） （i=1i=1，2 2，），），并并按估价值从小到大按估价值从小到大的顺序依次放入的顺序依次放入OpenOpen表的表的首部，首部，并为每一个子节点设置指向父节点的指针，然后转第（并为每一个子节点设置指向父节点的指针，然后转第（2 2）步。）步。 2局部择优搜索局部择优搜索174.3 4.3 状态空间的启发式搜索状态空间的启发式搜索二二. . A A算法算法 由于这一算法的第（由于这一算法的第（6 6）步
32、仅是把刚生成的子节点按其估）步仅是把刚生成的子节点按其估价函数值从小到大放入价函数值从小到大放入 OpenOpen表的首都，这样在算法第（表的首都，这样在算法第（3 3）步取出的节点仅是步取出的节点仅是刚生成刚生成的子节点中的子节点中估价函数值最小估价函数值最小的一个的一个节点。因此，它是一种局部择优的搜索方式。节点。因此，它是一种局部择优的搜索方式。 对这一算法进一步分析也可以发现：如果取估价函数对这一算法进一步分析也可以发现：如果取估价函数f f（ n n）=g=g（n n），），则它将退化为代价树的深度优先搜索；如则它将退化为代价树的深度优先搜索；如果取估价函数果取估价函数f f（n n
33、）=d=d（n n），），则它将退化为深度优先搜索。则它将退化为深度优先搜索。可见，可见，深度优先搜索和代价树的深度优先搜索是局部择优搜深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例索的两个特例。 2局部择优搜索局部择优搜索184.3 4.3 状态空间的启发式搜索状态空间的启发式搜索三三. . A A* *算法算法 上一节讨论的启发式搜索算法，都没有对估价函数上一节讨论的启发式搜索算法，都没有对估价函数f(n)f(n)作任何限制。实际上，估价函数对搜索过程是十作任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的解分重要的，如果选择不当，则有可能找不
34、到问题的解，或者找到的不是问题的最优解。为此，需要对估价，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制。函数进行某些限制。A A* * 算法算法就是就是对估价函数加上一些对估价函数加上一些限制限制后得到的一种启发式搜索算法后得到的一种启发式搜索算法。4.3 4.3 状态空间的启发式搜索状态空间的启发式搜索三三. . A A* *算法算法 假设假设f f* *(n)(n)为从初始节点为从初始节点S0S0出发，出发，约束经过节点约束经过节点n n到达目标节点的最小代价值到达目标节点的最小代价值。估价函数。估价函数f(n)f(n)是是f f* *(n)(n)的估计值。显然，的估计值。
35、显然，f f* *（n n）应由以下两部分所组成：一部应由以下两部分所组成：一部分是从初始节点到节点分是从初始节点到节点n n的的最小最小代价，记为代价，记为g g* *（n n）；）；另一部分是从节点另一部分是从节点n n到目标到目标节点的节点的最小最小代价，记为代价，记为h h* *（n n），），当问题有多个目标节点时，应取其中代价最小当问题有多个目标节点时，应取其中代价最小的一个。因此有的一个。因此有 f f* *（n n）g g* *（n n）h h* *（n n） 把估价函数把估价函数f(n)f(n)与与f f* *(n)(n)相比，相比，g g（n n）是对是对g g* *（n
36、n）的一个估计，的一个估计，h h（n n）是对是对h h* *（n n）的一个估计。在这两个估计中，尽管的一个估计。在这两个估计中，尽管g g（n n）的值容易计算，但它不一定的值容易计算，但它不一定就是从初始节点就是从初始节点S0S0到节点到节点n n的真正最小代价，很有可能从初始节点的真正最小代价，很有可能从初始节点S0S0到节点到节点n n的真的真正最小代价还没有找到，故有正最小代价还没有找到，故有g g（n n）gg* *（n n）。 有了有了g g* *（n n）和和h h* *（n n）的定义，如果我们对的定义，如果我们对A A算法（全局择优的启发式搜索算法（全局择优的启发式搜索
37、算法）中的算法）中的g g（n n）和和h h（n n）分别提出如下限制：分别提出如下限制： 第一，第一，g g（n n）是对是对g g* *（n n）的估计，且的估计，且g g（n n）0 0； 第二，第二，h h（n n）是是h h* *（n n）的下界，即对任意节点的下界，即对任意节点n n均有均有h h（n n）hh* *（n n）。）。则称得到的算法为则称得到的算法为A A* * 算法。算法。20有了有了A A* *算法的概念，下面就来讨论算法的概念，下面就来讨论A A* *算法的有关特性。算法的有关特性。1 1A A* *算法的可纳性算法的可纳性 一般来说，对任意一个状态空间图，当
38、从初始节点到目标节点有一般来说，对任意一个状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的。节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的。A A* *算法是可采纳的。算法是可采纳的。 ( (证明略）。证明略）。2. 2. A A* *算法的最优性算法的最优性 A A* * 算法的搜索效率很大程度上取决于估价函数算法的搜索效率很大程度上取决于估价函数h h（n n）。）。一般来一般来说，在满足说，在满足h h（n n）
39、hh* *（n n）的前提下，的前提下，h h（n n）的值越大越好。的值越大越好。h h（n n）的值越大，说明它携带的启发性信息越多，的值越大，说明它携带的启发性信息越多，A A* * 算法搜索时扩展的算法搜索时扩展的节点就越少，搜索效率就越高。节点就越少，搜索效率就越高。A A* *算法的这一特性也称为信息性。算法的这一特性也称为信息性。( (证明略证明略) )4.3 4.3 状态空间的启发式搜索状态空间的启发式搜索三三. . A A* *算法算法A A* * 算法应用举例算法应用举例例：例： 八数码难题。问题的初始状态和目标状态和前例相同。要求用八数码难题。问题的初始状态和目标状态和前
40、例相同。要求用A A* * 算法算法解决该问题。解决该问题。解：解：在上例中，我们取在上例中，我们取h h（n n）=W=W（n n）。）。尽管我们对尽管我们对h h* *（n n）不能确切知道，不能确切知道，但当采用单位代价时，通过对但当采用单位代价时，通过对“不在位不在位”数码个数的估计，可以得出至少要数码个数的估计，可以得出至少要移动移动W W（n n）步才能到达目标，显然有步才能到达目标，显然有W W（n n）hh* *（n n）。）。因此，前例中所定因此，前例中所定义的义的h h（n n）满足满足A A* *算法的限制条件。算法的限制条件。 这里再取另外一种启发函数这里再取另外一种启
41、发函数h h（n n）=P=P（n n），），P P（n n）定义为定义为每一个数码每一个数码与其目标位置之间距离（不考虑夹在其间的数码）的总和与其目标位置之间距离（不考虑夹在其间的数码）的总和，同样可以断定至，同样可以断定至少要移动少要移动P P（n n）步才能到达目标，因此有步才能到达目标，因此有P P（n n）hh* *（n n），），即满足即满足A A* *算法算法的限制条件。其搜索过程所得到的搜索树如下页图所示。在该图中，节点旁的限制条件。其搜索过程所得到的搜索树如下页图所示。在该图中，节点旁边虽然没有标出边虽然没有标出P P（n n）的值的值p p，但却标出了估价函数但却标出了估价
42、函数f f（n n）的的f f值。对解路径，值。对解路径，还给出了各个节点的还给出了各个节点的g g* *（n n）和和h h* *（n n）的的g g* *值和值和h h* *值。从这些值还可以看值。从这些值还可以看出，最佳路径上的节点都有出，最佳路径上的节点都有f f* *=g=g* *+h+h* *=4=4。 4.3 4.3 状态空间的启发式搜索状态空间的启发式搜索三三. . A A* *算法算法222 8 31 47 6 5h*=4, f=4S02 31 8 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 47 6 5g*=1 2 31 8 47 6 5
43、2 31 8 47 6 5g*=21 2 38 47 6 51 2 37 8 4 6 5Sgg*=4h*=5, f=6h*=5, f=6h*=3, f=4h*=5, f=6h*=2, f=4h*=3, f=51 2 3 8 47 6 5g*=3h*=1, f=4h*=0, f=4h*=2, f=6 八数码难题八数码难题h（n）=P（n）的搜索树的搜索树23A A* * 算法应用举例算法应用举例例：例：传教士和野人问题。请用传教士和野人问题。请用A A* *算法解决该问题。算法解决该问题。解：解：用用m m表示左岸的传教士人数，表示左岸的传教士人数，c c表示左岸的野人数，表示左岸的野人数，b
44、b表示左岸的船数，表示左岸的船数，用三元组（用三元组（m m，c c，b b）表示问题的状态。表示问题的状态。 对对A A* *算法，首先需要确定估价函数。算法，首先需要确定估价函数。 设设 g g（n n）=d=d（n n），），h h（n n）=m=mc c2b2b， 则有则有 f f（n n）=g=g（n n）h h（n n）=d=d（n n）m mc c2b2b其中，其中，d d（n n）为节点的深度。通过分析可知为节点的深度。通过分析可知h h（n n）h h* *(n)(n)，满足满足A A* *算法的算法的限制条件。限制条件。 M-C M-C 问题的搜索过程如下页图所示。在该图中
45、，每个节点旁边还问题的搜索过程如下页图所示。在该图中，每个节点旁边还标出了该节点的标出了该节点的h h值和值和f f值。值。4.3 4.3 状态空间的启发式搜索状态空间的启发式搜索三三. . A A* *算法算法24(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)
