状态空间搜索策略课件(-).ppt

1、第第5章章 状态空间搜索策略状态空间搜索策略Searching5.1 搜索概述搜索概述l在解空间中寻找解的过程与在解空间中寻找解的过程与策略策略l搜索问题的产生搜索问题的产生 （1）结构不良或非结构化的问题，无解析解）结构不良或非结构化的问题，无解析解 （2）理论上可解的问题，计算复杂度可能太高）理论上可解的问题，计算复杂度可能太高l基本搜索方式基本搜索方式 （1）盲目搜索盲目搜索 按预定策略进行搜索，不考虑问题本身的特性按预定策略进行搜索，不考虑问题本身的特性 （2）启发式启发式(Heuristic)搜索搜索 利用与问题有关的启发式信息，加快搜索过程利用与问题有关的启发式信息，加快搜索过程启

2、发式搜索启发式搜索l启发式信息启发式信息与与评价函数评价函数 反映问题特性，可用于确定搜索方向的信息反映问题特性，可用于确定搜索方向的信息 评价函数的作用是根据启发式信息，计算对应于评价函数的作用是根据启发式信息，计算对应于特定搜索方向的评价值，作为选择搜索方向的依特定搜索方向的评价值，作为选择搜索方向的依据。据。l局部局部(local)搜索搜索 vs.全局全局(global)搜索搜索 确定搜索方向时考虑局部信息还是全局信息？确定搜索方向时考虑局部信息还是全局信息？l任一解任一解 vs.最优解最优解搜索方法搜索方法l图搜索方法图搜索方法 宽度优先法宽度优先法(breadth-first)，深度

3、优先法，深度优先法(depth-first)，有界深度优先法，启发式最优图搜索法有界深度优先法，启发式最优图搜索法(A*，AO*).l博弈搜索方法博弈搜索方法 极小极大法极小极大法(MiniMax)，Alpha-Beta剪枝法剪枝法(pruning)l现代优化搜索方法现代优化搜索方法 爬山法爬山法(hill climbing)，模拟退火法，模拟退火法(simulated annealing)，遗传算法遗传算法(genetic algorithms).搜索策略的评价搜索策略的评价l完备性完备性 如果问题有解，能否保证找到？如果问题有解，能否保证找到？l最优性最优性(optimization)如果

4、问题存在不同的解，能否找到最优解？如果问题存在不同的解，能否找到最优解？l时间复杂性时间复杂性-找到一个解需要花费多少时间找到一个解需要花费多少时间l空间复杂性空间复杂性-在搜索过程中需要占用多少内存在搜索过程中需要占用多少内存时空复杂性的量度时空复杂性的量度l状态空间图的大小l分支因子 bl目标节点的深度 dl路径的最大长度 ml搜索深度限制 l5.2 问题及其搜索过程的表示问题及其搜索过程的表示l状态空间状态空间表示法表示法 通过通过“状态状态”表示问题，通过表示问题，通过“操作符操作符”求解问求解问题题 状态的改变状态的改变表示了问题求解过程表示了问题求解过程状态空间状态空间l以以“状态

5、状态”和和“操作符操作符”为基础为基础 状态状态：问题求解过程中任意时刻的状况问题求解过程中任意时刻的状况 操作符操作符：使问题从一个状态变为另一个状态的操作使问题从一个状态变为另一个状态的操作l问题的全部状态问题的全部状态(包含初始状态和目标状态包含初始状态和目标状态)及及一切可用操作符所构成的集合称为问题的状态一切可用操作符所构成的集合称为问题的状态空间。空间。,10kkkSSS GSFS,0初始初始状态状态中间中间状态状态1 1中间中间状态状态2 2目标目标状态状态状态空间例：状态空间例：二阶梵塔问题二阶梵塔问题l设有三根钢针，它们的编号分别是设有三根钢针，它们的编号分别是1 1号、号、

6、2 2号和号和3 3号。在初始情况下，号。在初始情况下，l l号钢针上穿有号钢针上穿有A A、B B两个两个金片，金片，A A比比B B小，小，A A位于位于B B的上面。要求把这两个的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于能移动一个金片，任何时刻都不能使大片位于小片的上面。小片的上面。l用用 Sk=Sk=Sk0Sk0，Sk1Sk1表示问题的表示问题的状态状态，其中，其中，Sk0Sk0表示金片表示金片A A所在的钢针号，所在的钢针号，Sk1Sk1表示金片表示金片B B所在的钢针号。全部可能的问题

7、状态共有以所在的钢针号。全部可能的问题状态共有以下下9 9种：种：SO=(1SO=(1，l)S1=l)S1=（1 1，2 2）S2=S2=（1 1，3 3）S3=(2S3=(2，1 1）S4=S4=（2 2，2 2）S5=S5=（2 2，3 3）S6=(3S6=(3，1 1）S7=S7=（3 3，2 2）S8=S8=（3 3，3 3）123BABABA123S0=(1,1)S4=(2,2)S8=(3,3)二阶梵塔问题的初始与目标状态二阶梵塔问题的初始与目标状态l操作符操作符：A(i,j)表示把金片表示把金片A从第从第i号钢针移到号钢针移到j号钢针号钢针上；上；B(i,j)表示把金片表示把金片B

8、从第从第i号钢针移到号钢针移到j号钢针上。号钢针上。共有共有12种操作，分别是：种操作，分别是：A(1，3)A(2，1)A(2，3)A(3，1)A(3，2)B(1，3)B(2，1)B(2，3)B(3，1)B(3，2)(1,1)(2,1)(2,3)(3,3)(1,3)(1,2)(2,2)(3,2)(3,1)A(1,3)B(1,2)A(3,2)l 根据状态和操作符，可构成根据状态和操作符，可构成二阶梵塔问题的状态图二阶梵塔问题的状态图最短路最短路径解径解l八数码游戏（八数码问题）描述为：在33组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其

9、周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。5.3 一般图搜索算法一般图搜索算法l无论是状态空间，还是与或图的问题表示，问无论是状态空间，还是与或图的问题表示，问题求解过程都可看作是在题求解过程都可看作是在“图图”中进行搜索。中进行搜索。l基本思想基本思想 不存储全部搜索图，而是逐步展开问题求解所需的不存储全部搜索图，而是逐步展开问题求解所需的搜索子图搜索子图l具体方法具体方法 从初始状态开始，不断扩展当前节点，即生成子从初始

10、状态开始，不断扩展当前节点，即生成子节点，直到目标状态出现在这些子节点中，或者没节点，直到目标状态出现在这些子节点中，或者没有可供扩展的节点为止。有可供扩展的节点为止。数据结构数据结构lOpen表（表（未扩展节点表未扩展节点表）存放未进行过扩展的节点存放未进行过扩展的节点lClosed表（表（已扩展节点表已扩展节点表）存放已经扩展过的节点存放已经扩展过的节点 节点 父节点 编号 节点 父节点Open表：表：Closed表：表：算法步骤算法步骤Step1 把初始节点把初始节点S0放入放入 Open表，建立仅包含表，建立仅包含S0的图的图 G；Step2 从从Open表中取出待扩展节点，放入表中取

11、出待扩展节点，放入Closed表表；（不同搜索策略的区别主要体现于此）（不同搜索策略的区别主要体现于此）Step3 对节点进行扩展，将扩展得到的、未在对节点进行扩展，将扩展得到的、未在G中出中出现过的子节点放入现过的子节点放入Open表；根据需要修改表；根据需要修改G中节中节点的指针；点的指针；Step4 重复重复Step2-3直到直到 状态空间状态空间：待扩展节点为目标节点或：待扩展节点为目标节点或Open表为空表为空盲目搜索策略盲目搜索策略l广度（宽度）优先搜索广度（宽度）优先搜索 先生成的节点先扩展先生成的节点先扩展l深度优先搜索深度优先搜索 后生成的节点先扩展后生成的节点先扩展l有界深

12、度优先搜索有界深度优先搜索 在深度优先策略中增加深度限制，在广度优先与在深度优先策略中增加深度限制，在广度优先与深度优先之间折衷深度优先之间折衷完备完备最小路径解最小路径解效率效率2 8 347 6 5S01 2 38 47 6 5Sg盲目搜索例（状态空间）盲目搜索例（状态空间）:八数码难题八数码难题在在 3*3 的方格棋盘上，分别放置了标有数字的方格棋盘上，分别放置了标有数字1、2、3、4、5、6、7、8的八张牌，初始状态的八张牌，初始状态S0和目标状态和目标状态Sg分别如图所示。可以使用的操作有：分别如图所示。可以使用的操作有：空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格

13、右移，空格下移寻找从初始状态到目标状态的解路径。寻找从初始状态到目标状态的解路径。广度优先搜索算法如下：(1)把初始结点放入Open表中；(2)如果Open表为空，则问题无解，失败退出；(3)把Open表的第一个结点取出，放入Closed表，并记该结点为n；(4)扩展节点n，如果没有后继节点，则转向第(2)步；(5)把n的所有后继结点放入Open表的末尾，并提供从这些后继结点回到父结点(编号值为n)的指针;(6)如果刚产生的这些后继结点中存在一个目标结点，则找到一个解。解可从目标结点开始直到初始结点的返回指针中得到，算法成功退出。否则转(2)继续。SLOMFPQNFFF起始结点起始把S0放入O

14、pen表Open表是否为空失败把第1个结点n，从Open表移出并把它放入Closed表中扩展n,把它的后继结点放入Open表的末端,提供回到n的指针是否有任何后继结点为目标结点？成功否是否是示意图示意图算法框图算法框图2 8 31 47 6 5S012 8 3 1 47 6 522 31 8 47 6 532 8 31 47 6 542 8 31 6 47 55 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 52 8 1 4 37 6 52 8 31 4 57 62 8 31 6 4 7 52 8 31 6 47 567 89 101

15、1 12138 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 41 87 6 52 8 1 4 37 6 52 8 31 4 57 62 8 3 6 41 7 52 8 31 67 5 41415218 32 1 47 6 58 1 32 47 6 522232 8 37 46 1 52 8 37 1 46 524251 2 38 47 6 51 2 3 7 8 4 6 52627Sg解的路径是：解的路径是：S S0 0 3 8 16 26(3 8 16 26(SgSg)八数码难题的广度优先搜索八数码难题的广度优先搜索广度优先搜索是一种完备策略，即只要问题

16、有广度优先搜索是一种完备策略，即只要问题有解解,它就一定可以找到解。并且广度优先搜索找它就一定可以找到解。并且广度优先搜索找到的解，还一定是路径最短的解。到的解，还一定是路径最短的解。深度优先搜索深度优先搜索深度优先搜索是一种后生成的结点先扩展的策后生成的结点先扩展的策略略。其搜索过程是：从初始结点S0开始，在其子结点中选择一个最新生成的结点进行考察，如果该子结点不是目标结点且可以扩展，则扩展该子结点，依此向下搜索，直到某个子结点既不是目标结点，又不能继续扩展时，才选择其兄弟结点进行考察。图示如下：S0123768459起始结点起始把S0放入Open表S0是否为目标结点是否Open为空表把Op

17、en表中的第一个结点n移入Closed表结点n的深度是否等于深度界限扩展结点n，把其后代放入Open表的前端是否有任何后继结点为目标结点成功失败成功是否是是是否否否示意图示意图算法框图算法框图深度优先搜索算法如下：(1)把初始结点S0放入Open表中；(2)如果Open表空，则问题无解，失败退出；(3)把Open表的第一个结点取出放入Close表，并记该结点为n;(4)考察结点n是否为目标结点，若是，则得到问题的解，成功退出；(5)若结点n不可扩展，则转(2)；(6)扩展结点n，将其子结点放入Open表的首部，并为每一个子结点设置指向父结点的指针，然后转(2)。2 8 31 47 6 5S01

18、2 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 522 8 31 6 4 7 52 8 31 6 47 532 8 31 67 5 442 81 6 37 5 42 8 31 67 5 452 81 6 37 5 46八数码难题的深度优先搜索八数码难题的深度优先搜索 从深度优先搜索的算法可以看出,搜索一旦进入某个分支，就将沿这个分支一直进行下去，如果目标恰好在这个分支上,则它可以很快找到解.但是,如果目标不在这个分支上，且分支是一个无穷分支，则搜索过程就不可能找到解。因此，深度优先搜索是一种不完备策略，即使问题有解，它也不一定能够找到解。

19、解路径为解路径为:So：l 11 12 13 14：SgSg 八数码难题的有界深度优先搜索八数码难题的有界深度优先搜索2 8 31 47 6 5S012 8 3 1 47 6 522 31 8 47 6 5112 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 52 8 1 4 37 6 52 8 31 4 57 62 8 31 6 4 7 52 8 31 6 47 537 138 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 41 87 6 52

20、8 1 4 37 6 52 8 31 4 57 62 8 3 6 41 7 52 8 31 67 5 4488 32 1 47 6 58 1 32 47 6 5562 8 37 46 1 52 8 37 1 46 59101 2 38 47 6 51 2 3 7 8 4 6 514 12深度限制为深度限制为4上面讨论的搜索方法都没有用到问题本身的特性信息，只是按事先设定的线路进行搜索，具有较大的盲目性。事实上，如果能利用搜索过程所得到的问题自身的一些特性信息来指导搜索过程，则对搜索将是非常有益的。这种利用问题自身的特性来引导搜索过程，提高搜索效提高搜索效率率的搜索策略称为启发式搜索启发式搜索或

21、有信息搜索有信息搜索。启发式搜索方法所依据的是问题自身的启发性信息启发性信息，而启发性信息又是通过估价函数估价函数而作用于搜索过程的。5.4启发式搜索启发式搜索l启发式算法启发式算法 利用问题的特殊性，选择待扩展的节点，以缩小利用问题的特殊性，选择待扩展的节点，以缩小搜索范围，提高搜索速度。搜索范围，提高搜索速度。l启发信息启发信息 可指导搜索过程，且与具体问题求解过程有关的可指导搜索过程，且与具体问题求解过程有关的控制性信息。一般有以下三种：控制性信息。一般有以下三种：帮助确定扩展节点的信息；帮助确定扩展节点的信息；帮助决定哪些后继节点应被生成的信息；帮助决定哪些后继节点应被生成的信息；在扩

22、展一个节点时决定哪些节点应被删除的信息在扩展一个节点时决定哪些节点应被删除的信息l估价函数估价函数f(n)：用于估计用于估计节点代价节点代价的函数的函数 定义定义为从初始节点为从初始节点S0出发，经过节点出发，经过节点n约束后，到达约束后，到达目标节点目标节点Sg的所有路径中最优路径的代价估计值。的所有路径中最优路径的代价估计值。一般形式一般形式为为 f(n)=g(n)h(n)g(n)是从初始节点是从初始节点S0到节点到节点n的实际代价。可以从节的实际代价。可以从节点点n反向跟踪到初始节点反向跟踪到初始节点S0,得到一条当前最小代价路得到一条当前最小代价路径，把这条路径上所有有向边的代价相加，

23、就得到径，把这条路径上所有有向边的代价相加，就得到g(n)的值。的值。；h(n)是从节点是从节点n到目标节点到目标节点S0的最优路径的估计代价。的最优路径的估计代价。需要根据问题自身的特性来确定，体现了问题自身的需要根据问题自身的特性来确定，体现了问题自身的启发性信息，因此也称为启发性信息，因此也称为启发函数启发函数。估价函数例：估价函数例：f(n)=d(n)+W(n)2 8 347 6 5S0节点节点n在搜索树中的深度在搜索树中的深度n中中“不在位不在位”的数码个数的数码个数f(S0)=?=0+3=31 2 38 47 6 5Sgl根据搜索过程中选择扩展节点的范围，分为全根据搜索过程中选择扩

24、展节点的范围，分为全局择优搜索和局部择优搜索。局择优搜索和局部择优搜索。1.全局择优全局择优 在在Open表的所有节点中选择一个估价函数值最小的节表的所有节点中选择一个估价函数值最小的节点进行扩展点进行扩展 2.局部择优局部择优 在刚生成的子节点中选择一个估价函数值最小的节点进在刚生成的子节点中选择一个估价函数值最小的节点进行扩展。行扩展。局部最佳优先搜索算法局部最佳优先搜索算法l对OPEN表中所有节点的f(n)进行比较，按从小到大的顺序重排OPEN表。l其算法效率类似于纵向搜索算法，但使用了与问题特性相关的估价函数来确定下一步待扩展的节点，因此是一种启发式搜索方法。开始开始把把S放入放入OP

25、EN表，表，计算估价函数计算估价函数 f(s)OPEN表为空表？表为空表？把把OPEN表中的第一个节点表中的第一个节点n放入放入CLOSED表表n为目标节点吗？为目标节点吗？扩展扩展n，计算所有子节点的估价函数值，计算所有子节点的估价函数值，并提供它们返回节点并提供它们返回节点n的指针。的指针。失败失败成功成功局部最佳优先搜索算法框图局部最佳优先搜索算法框图是是否否是是否否把子节点送入把子节点送入OPEN表，并对其中的所有表，并对其中的所有节点按估价函数值由小到大重排。节点按估价函数值由小到大重排。l 举例：八数码魔方（八数码魔方（8-puzzle problem）12384567（目标状态）

26、（目标状态）12384567（初始状态）（初始状态）57123845671238456712384567 (3)(5)(5)123845671238456712384567 (4)(3)(3)1238456712 384567 (2)(4)1238456712384567 (3)(4)12384567 (1)813245671 2384567 (0)(2)八数码魔方的局部八数码魔方的局部最佳优先搜索树最佳优先搜索树123846(4)75搜索得到的路径如黄线所示搜索得到的路径如黄线所示l本题采用了简单的估价函数 f(n)=W(n)其中：W(n)用来计算对应于节点n的数据库中错放的棋子个数。因此，

27、初始节点棋局的f(n)值等于4。12384567l第步有三种情况,我们选择其中f(n)最小的:l其它依次类推.最后用了7步得出了结果.123845671238456712384567 (3)(5)(5)l最佳优先算法有时无法得到最优解，因为它的估价函数f的选取时，忽略了从初始节点到目前节点的代价值。所以，可考虑对估价函数f(n)进行某些修改或限制。5.5 A*算法算法l对估价函数加上一些限制，以保证得到最优解对估价函数加上一些限制，以保证得到最优解的启发式搜索算法的启发式搜索算法l最优估价函数最优估价函数 f*(n)g*(n)h*(n)初始节点到节点初始节点到节点n的最小代价的最小代价节点节点

28、n到目标节点的最小代价到目标节点的最小代价l有关限制有关限制 1.g(n)是对是对g*(n)的估计，且的估计，且g(n)0；2.h(n)是是h*(n)的下界，即对任意节点的下界，即对任意节点n均有均有h(n)h*(n)A*算法例算法例1：八数码问题：八数码问题解解1：h(n)=W(n)。尽管不能确切知道。尽管不能确切知道h*(n)，但当采用单位代价时，通过对但当采用单位代价时，通过对“不在位不在位”数码数码个数的估计，可以得出至少要移动个数的估计，可以得出至少要移动W(n)步才能步才能到达目标，显然有到达目标，显然有W(n)h*(n)，满足，满足A*算法的算法的限制条件。限制条件。解解2：h(

29、n)=P(n)，P(n)定义为每一个数码与其定义为每一个数码与其目标位置之间距离（不考虑夹在其间的数码）目标位置之间距离（不考虑夹在其间的数码）的总和，同样可以断定至少要移动的总和，同样可以断定至少要移动P(n)步才能步才能到达目标，因此有到达目标，因此有P(n)h*(n)，即满足，即满足A*算法算法的限制条件。的限制条件。2 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 52 31 8 47 6 5g=21 2 38 47 6 51 2 37 8 4 6 5Sg

30、g=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八数码难题的的八数码难题的的A*搜索图搜索图（h(n)=P(n)）A*算法例算法例2：修道士和野人问题修道士和野人问题设在河的左岸有三个修道士、三个野人和一条设在河的左岸有三个修道士、三个野人和一条船，修道士想用这条船把所有的人运到河对岸，船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：但受以下条件的约束：1.修道士和野人都会划船，但每次船上至多修道士和野人都会划船，但每次船上至多可载两个人；可载两个人；2.河的任一

31、岸如果野人数目超过修道士数，河的任一岸如果野人数目超过修道士数，修道士就会被野人吃掉。修道士就会被野人吃掉。请给出一个确保修道士和野人都能过河，且没请给出一个确保修道士和野人都能过河，且没有修道士被野人吃掉的过河规划有修道士被野人吃掉的过河规划问题表示问题表示：需要考虑两岸的修道士人数和野人：需要考虑两岸的修道士人数和野人人数，船的位置。用三元式表示状态：人数，船的位置。用三元式表示状态：S=(m,c,b)其中，其中，m表示左岸修道士人数，表示左岸修道士人数，c表示左岸野表示左岸野人人数，人人数，b表示左岸船的数目。表示左岸船的数目。解解：确定估价函数。：确定估价函数。f(n)=g(n)h(n

32、)=d(n)m c 2b其中，其中，d(n)为节点深度。为节点深度。h(n)h*(n)，满足，满足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传教士和野人问题的传教士和野人问题的A*搜索图搜索图(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(

33、0,2,0)(1,1,0)关于关于A*算法的一些讨论算法的一些讨论lA*算法是到目前为止最快的一种计算最短路径的算法，但它是一种较优算法，即它一般只能找到较优解，而非最优解，但由于其高效性，使其在实时系统、人工智能等方面应用极其广泛。lA*算法结合了启发式方法（这种方法通过充分利用图给出的信息来动态地作出决定而使搜索次数大大降低）和形式化方法（这种方法不利用图给出的信息，而仅通过数学的形式分析，如Dijkstra算法）。它通过一个估价函数（Heuristic Function）f(h)来估计图中的当前点p到终点的距离(带权值)，并由此决定它的搜索方向，当这条路径失败时，它会尝试其它路径。l我们

34、可以发现，A*算法成功与否的关键在于估价函数的正确选择，从理论上说，一个完全正确的估价函数是可以非常迅速地得到问题的正确解答，但一般完全正确的估价函数是得不到的，因而A*算法不能保证它每次都得到正确解答。一个不理想的估价函数可能会使它工作得很慢，甚至会给出错误的解答。l为了提高解答的正确性，我们可以适当地降低估价函数的值，从而使之进行更多的搜索，但这是以降低它的速度为代价的，因而我们可以根据实际对解答的速度和正确性的要求而设计出不同的方案，使之更具弹性。A*算法的数据结构算法的数据结构l众所周知，对图的表示可以采用数组或链表，而且这些表示法也各有优缺点，数组可以方便地实现对其中某个元素的存取，

35、但插入和删除操作却很困难，而链表则利于插入和删除，但对某个特定元素的定位却需借助于搜索。而A*算法则需要快速插入和删除所求得的最优值以及可以对当前结点以下结点的操作，因而数组或链表都显得太通用了，用来实现A*算法会使速度有所降低。要实现这些，可以通过二分树、跳转表等数据结构来实现，实践中如采用简单而高效的带优先权的堆栈，经实验表明，一个1000个结点的图，插入而且移动一个排序的链表平均需500次比较和2次移动；未排序的链表平均需1000次比较和2次移动；而堆仅需10次比较和10次移动。需要指出的是，当结点数n大于10，000时，堆栈不再是正确的选择，但这足已满足我们一般的要求。估价函数（估价函

36、数（Heuristic Function）l估价函数的正确选取将直接关系到A*算法的成功与否，而函数的确定却与实际情形有着密切的关系。这里以网格地图的估价函数为例，其它情形需要作不同的分析，但至少估价函数应为连续函数。la.Manhattan Distance，这是一种标准的估价函数，h(A)=10*(abs(A.x-goal.x)+abs(A.y-goal.y)lb.Diagonal Distance，如果在地图上允许作斜线方向的运动，则Mahattan Distance修正为Diagonal Distance：h(A)=max(abs(A.x-goal.x),abs(A.y-goal.y)

37、估价函数的判优估价函数的判优l一般情形下，我们只需对估价函数的值进行比较而取其大者即可，但在几个结点的估价函数值相同的情形下，我们需要采取一定的策略来决定这几者谁更优，从而避免对多个点的搜索。从而如下代码可实现之：ldouble dx1=currentX-goalX;ldouble dy1=currentY-goalY;ldouble dx2=startX-goalX;ldouble dy2=startY-goalY;lcross=dx1*dy2-dx2*dy1;lif(cross0)cross=-cross;l.add cross*0.001 to the heuristic.l这段代码计算

38、始点、当前点和终点的矢量积，从而可以判断这三点是否共线（或近似共线），这样不同点间即使有微小的差别也会被放大，从而更利于判断。改进的改进的A*算法算法la.Beam Search。在A*算法中需要保留所有的结点，这将使得时间和空间的消耗都很大，而Beam Search方法对结点数作出限期，当结点数过多时，它会将一些不(大)可能为最优的点排除，从而降低时间和空间的要求，但需要说明的是，由于在排除结点后需对结点排序，当排序的工作量大于排除点后所节省的工作量，则该方法无意义。lb.Iterative deepening。这是一种在人工智能中常使用的方法，它首先产生一近似值，然后对它进行修正而逐步接近

39、最优解。这其实是一种博奕算法的变形。lc.Dynamic weighting。这种算法是基于这样的考虑，即在搜索初期以速度优先，在搜索后期以准确度优先(这可通过对搜索初、后期赋予不同的权值来实现)。即：f(p)=g(p)+w(p)*h(p)ld.Bidirectional search。这种算法从起点和终点同时应用A*算法，直到有结点相遇。其缺点在于复杂度太大，一般仅用于复杂的图形。le.Hierarchical A*。这种算法思想是将搜索过程化，对每个简单过程求解从而得全局较优解。正如当我们到另一城市时，可分解为从家里“搜索”一条路径至车站，再从车站“搜索”一条路径到另一城市，当我们从家里出

40、发时，需要考虑的是怎样尽快地到达车站，而不是怎样尽快地到另一城市。lf.Dynamic A*(D*)。这种算法主要用于人工智能和机器人技术。由于A*算法一开始要求获得全部信息，而这在实际中有时是不可能的，而D*算法就是在假定信息不完整的前提下应用A*算法，但它会随着得到信息的增多而不断改进结果，这就决定了它对空间的要求相当高，因为它需要保留以前的所有获得信息及运算情形。开放实验：不同搜索策略的算法实现与开放实验：不同搜索策略的算法实现与性能分析性能分析以以8数码问题求解为例数码问题求解为例l摘要l词汇表l第一章、8数码问题概述l第二章、x算法的一般描述l第三章、用x算法分析八数码问题l（第四章

41、、评价函数的启发能力）l第五章、x算法在y开发环境下的实现（不限编程语言）l （1.类（可参见附录）l 2.数据结构l 3.程序流程图与相关说明l第六章、性能比较与分析（如广度优先、深度优先）l第七章、进一步讨论（改进与研究）l附录l参考文献要求要求l编程语言环境不作要求（Matlab、C/C+、Java等均可）；l独立完成，至少包括一种非启发性、一种启发性算法；l提交最终报告与代码。1、先天下之忧而忧；后天下之乐而乐。范仲淹2、捐躯赴国难，视死忽如归。曹植3、近乡情更切，不敢问来人。宋之问4、气蒸云梦泽；波撼岳阳城。孟浩然5、中夜四五叹，常为大国忧。李白6、国耻未雪，何由成名？李白7、当须徇

42、忠义，身死报国恩。李希仲8、科学虽没有国界，但是学者却有他自己的国家。巴斯德9、虚荣的人注视着自己的名字，光荣的人注视着祖国的事业。马蒂10、爱国主义就是千百年来固定下来的对自己的祖国的一种最深厚的感情。列宁11、利于国者爱之，害于国者恶之。晏婴12、常思奋不顾身，而殉国家之急。司马迁13、爱国如饥渴。班固14、一身报国有万死，双鬓向人无再青。陆游15、死去原知万事空，但悲不见九州同。王师北定中原日，家祭无忘告乃翁。陆游16、人生自古谁无死，留取丹心照汗青。文天祥17、天下兴亡，匹夫有责。顾炎武18、南北驱驰报主情，江花边草笑平生。一年三百六十日，都是横戈马上行。戚继光19、瞒人之事弗为，害人

43、之心弗存，有益国家之事虽死弗避。吕坤20、各出所学，各尽所知，使国家富强不受外侮，足以自立于地球之上。詹天佑21、做人最大的事情是什么呢？就是要知道怎样爱国。孙中山22、我们爱我们的民族，这是我们自信心的泉源。周恩来23、为中华之崛起而读书。周恩来24、以身许国，何事不敢为？岳飞25、夜视太白收光芒，报国欲死无战场！陆游26、位卑不敢忘忧国。陆游27、寄意寒星荃不察，我以我血荐轩辕。鲁迅28、中国自古以来，就有埋头苦干的人，就有拼命硬干的人，就有为民请命的人，就有舍身求法的人。他们是中国的脊梁。鲁迅29、惟有民魂是值得宝贵的，惟有它发扬起来，中国人才有真进步。鲁迅30、我们中华民族有同自己的敌

44、人血战到底的气概，有在自力更生的基础上光复旧物的决心，有自立于世界民族之林的能力。毛泽东31、与其忍辱生，毋宁报国死。何香凝32、锦绣河山收拾好，万民尽作主人翁。朱德33、人民不仅有权爱国，而且爱国是个义务，是一种光荣。徐特立34、爱国的主要方法，就是要爱自己所从事的事业。谢觉哉35、中国是古老的民族，也是勇敢的民族。中华民族有两大优点：勇敢，勤劳。这样的民族多么可爱，我们爱我们民族（当然其他民族也有他们可爱之处，我们决不忽视这一点），这是我们自信心的泉源。周恩来36、真正的爱国者是爱人类的，爱国决不是排外。马铁丁37、爱国主义就是千百年来巩固起来的对自己的祖国的一种最深厚的感情。列宁38、必须经过祖国这一层楼，然后更上一层楼，达到人类的高度。罗曼罗兰39、黄金诚然是宝贵的，但是生气蓬勃的勇敢的爱国者却比黄金更为宝贵。林肯