人工智能-第五章 搜索策略.pdf

《人工智能-第五章 搜索策略.pdf》由会员分享，可在线阅读，更多相关《人工智能-第五章 搜索策略.pdf（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第五章搜索策略搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关 系到智能系统的性能与运行效率，因而尼尔逊把它列为人工智能研究中的四个 核心问题之一。5.1 基本概念1.什么是搜索 人工智能所要解决的大部分问题是结构不良或非结构化的问题，对这样的问题一般不存在成熟的求解算法可供利用，而只能是利用已有的知识一步步摸索着前进。在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决。如：在正向推理中，1 对已知的初始事实，需要在知识库中寻找可使用的知识，这就 存在按何种线路进行寻找的问题。另外，可能存在多条线路都可实现对问题的求

2、解，这就又出现 按哪一条线路进行求解以获得较高的运行效率的问题。像这样根据问题的实际情况不断寻找可利用的知识，从而 构造一条代价较少的推理路线，使问题得到圆满解决的过程 称为搜索。搜索分为盲目搜索和启发式搜索。盲目搜索按预定的控制策略进行搜索，在搜索过程中获得的中间信 息不用来改进控制策略。这种搜索具有盲目性，效率不高,不便于复杂问题的求解。启发式搜索在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并 找到最优解。5.2求解问题的表示方法用搜索策略求解问题，首先要解决的问题也是：用什么样的形式把问题表示出来.一般来说，有两种方法：状态空间表示法；与/

3、或树表示法；1.状态空间表示法I 状态空间表示法是用来表示问题及其搜索过程的一种方法，它是人工智能中最 基本的形式化方法。状态空间表示法是用“状态”和“算符”来表示问题的一种方法。其中，I“状态”用以描述问题求解过程中不同时刻的状况；“算符”表示对状态的操作，算符的每一次使用就使问题由一种状态变换 为另-种状态；.解当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题 的一个解。I.状态状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序 组合表不：Q=（q，q2,）当给每一个分量以确定的值时，就得到了一个具体的状态。II.算符引起状态中某些分量发生变化，从而使问题由一

4、个状态变为另一个状态的操 作称为算符。在产生式系统中，每一条产生式规则就是一个算符。in.状态空间由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般 用一个四元组表示：（S,O,So,G）其中，S是问题的所有初始状态构成的集合；。是算符的集合；So是包含问题 的初始状态；G是目标状态的集合。状态空间的图示形式称为状态空间图。其中，节点表示状态；有向边（弧）表示 算符。4.1.2状态空间法2.状态空间问题求解状态空间法求解问题的基本过程：首先为问题选择适当的“状态”及“操作”的形式化 描述方法；然后从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为

5、止；此时，由初始状态到目标状态所使用的算符序列就是 该问题的一个解。例1:钱币翻转问题，如图所示。设有三个钱币，起初是状态为(反正反)，允许每次翻转一个钱币(只反一个，也必反一个)，连反三次，问是否可达到目标状态？(正正正)或(反反反)？设用Sk=(Si，S2，S3)表示问题的状态，=。表示钱币正面，S=1表示钱币反面。则钱币可能出现的状态有八种：So=(O,O,O)9 S1=(O,O,1),S2=(0,l,0)9 s3=(o,i9i)S4=(l,0,0)9 S5=(l,09l),S6=(l,l,o)9 s7=(l,l,l)s=s5目标状态集合：G=S09 S7算符：_把si翻-面；f2-把2

6、翻一面；fa-把S3翻一*面；上述问题的状态空间“四元组”为：(S,后2,3,S5,仁0g7)相应的状态空间图：SiS2从图中看出：从S5不可能经三次翻转到达So，从S5可经三次翻转到达S7,且有七种操作方式。S5-S-S5-S7S5一s7 S3 一S7S5f-S6-S7S5S4 f-S7G 跖 f2)任2,，3)任3,G，f 3)S5-S f-S7一 s7 s5 s7S5-S4 f f(G,G,h)(f 2?，2)任3,f3,f 2)3 状态空间的例子(1/11)例41二阶梵塔问题。设有三根钢针，它们的编号分别是 1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个 金片，A比B小，A位

7、于B的上面。要求把这两个金片全部移 到另一根钢针上，而且规定每次只能移动一个金片，任何时 刻都不能使大的位于小的上面。解：设用3卜=岔如,3)表示问题的状态，其中，Sa表示金 片A所在的钢针号，S-表示金片B所在的钢针号。全部可能 的问题状态共有以下9种：So=(l,1)SKI,2)S2=(l,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)3.状态空间的例子(2/11)问题的初始状态集合为5=5。目标状态集合为6=伪力S8初始状态So和目标状态S4、S8如图所示 II Ibf尸1 2 3 1 2 3 1 2 3s0=（i,1）s4=（29

8、2）s8=（3,3）二阶梵塔问题的初始状态和目标状态472r3.状态空间的例子(3/11)I操作分别用A(i,j)和B(i,j)表示I A(i,j)表示把金片A从第i号钢针移到j号钢针上；B(i,j)表示把金片B从第i号钢针一到第j号钢针上。共有12种 操作，它们分别是：A(l,2)A(l,3)A(2,1)A(2,3)A(3,1)A(3,2)B(l,2)B(l,3)B(2,1)B(2,3)B(3,1)B(3,2)根据上述9种可能的状态和12种操作，可构成二阶梵塔问题的 状态空间图，如下图所示。二阶梵塔的状态空间图从初始节点(1,1)到目标节点(2,2)及(3,3)的任何一条路径都是问题的一 个

9、解。其中，最短的路径长度是3,它由3个操作组成。例如，从(1,1)开始,通过使用操作A(1,3)、B(1,2)及A(3,2),可到达(3,3)。3 状态空间的例子(5/11)例4.2修道士(Missio na ries)和野人(Ca nniba问题倘称 MC 问题)。(N=2,3)设在河的一岸有2个野人、2个修道士和一条船，修道士想用 这条船把所有的人运到河对岸，但受以下条件的约束：一是修道士和野人都会划船，但每次船上至多可载两个人；二是在河的任一岸，如果野人数目超过修道士数，修道士会 被野人吃掉。如果野人会服从任何一次过河安排，请规划一个确保修道士 和野人都能过河，且没有修道士被野人吃掉的安

10、全过河计划。3 状态空间的例子(6/11)解：首先选取描述问题状态的方法。在这个问题中，需要 考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在 右岸。从而可用一个三元组来表示状态S=(m,c,b)其中，m表示左岸的修道士人数，c表示左岸的野人数，b表示 左岸的船数。右岸的状态可由下式确定：右岸修道士数nf=2m右岸野人数c，=2c右岸船数 bf=l-b在这种表示方式下，m和c都可取0、1、2中之一，b可取0和 1中之一。因此，共有3义3义2=18种状态。这18种状态并非全有意义，除去不合法状态和修道士被野人吃 掉的状态，有意义的状态只有10种：S=(2,2,1)S4=(0,2,0)S8=

11、(l,1,1)有了这些状态,*=(2,1,0)S2=(l,1,0)S3=(2,0,0)S5=(2,191)S6=(0,1,0)S7=(0,2,1)s9=(0,0,0)还需要考虑可进行的操作。操作是指用船把修道士或野人从河的左岸运到右岸，或从河的 右岸运到左岸。每个操作都应当满足如下条件：一是船至少有一个人（m或c）操作，离开岸边的m和c的减少数 目应该等于到达岸边的m和c的增加数目；二是每次操作船上人数不得超过2个；三是操作应保证不产生非法状态。因此，操作应由条件部分和动作部分：条件：只有当其条件具备时才能使用动作：刻划了应用此操作所产生的结果。操作的表示：用符号Pij表示从左岸到右岸的运人操

12、作用符号Qu表示从右岸到左岸的操作其中：i表示船上的修道士人数j表示船上的野人数操作集本问题有10种操作可供选择：F=P（）1，P10,Pu，P02,P2O，Qo i，Qio,Qu，Q02,Q20下面以P01和Q01为例来说明这些操作的条件和动作。I操作符号条件 动作P01 b=l,m=0或39 cl b=0,c=c-lQ01 b=03m=0或3,c(1,2,2),(1,2,2)=(3,2,2),(3,2,2)n(3,2,l),(3,2,l)n(3,3,l),(3,3,l)n(3,3,3)它指出 了移动金片的次序。5.3状态空间搜索策略1.概述(1)搜索过程中要用到的两个数据结构OPEN 表:

13、用于存放刚生成的节点。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。CLOSED 表:用于存放将要扩展或者已扩展的节点，所谓对节点进行“扩展”是指：用合适的算符对该节点进行操作,(2)状态空间法搜索策略 广度优先搜索 深度优先搜索 有界深度优先搜索 代价树的广度优先搜索 代价树的深度优先搜索(以上属于盲目搜索策略)局部择优搜索 全局择优搜索(以上搜索属于启发式搜索)OPEN 表1状态节点父节点rzqzntzzdCLOSED 表编号状态节点父节点(d)（1）基本思想从初始节点开始，按照某种生成规则（算符）逐步生成下一 级各子节点，顺序（先生成的子节点优先检查，优先扩展）地检 查是否出

14、现目标节点，在该级全部节点中沿广度进行“横向”扫 描，即：沿“广度”遍历所有节点，故称“广度优先搜索法”。（2）广度优先搜索法搜索过程I.把初始节点S。放人OPEN表，若S。为目标节点，则得到问题的退出；II.如果OPEN表为空,则问题无解，退出；III.把OPEN表的第一个节点（记为节点n）取出放入CLOSED表；W.考察节点n,若节点n不可扩展，则转第H步；V.扩展节点n,将其子节点放入OPEN表的尾部，并为每一个子 节点都配置指向父节点的指针；VI.如果n的任一个后继节点是目标节点，则找到问题的解，成 功退出，否则转向第H步。例：重排九宫问题。在3X3的方格棋盘上放置分别标有数字1,2,

15、3,4,5,6,7,8的八张牌，初始状态为SO,目标状态为S,如下图所示。可使用的算符有：空格左移，空格上移，空格右移，空格下移即，它们只允许把位于空格左，上，右，下边的牌移入空格。要求寻找从初始状态到目标状态的路径。应用广度优先搜索，可得到如图所示的搜索树。由图可以看出，解的路径是：Sof3-8 16 26(Sg)小结：缺点：广度优先搜索的盲目性较大，当目标节点距离初始节点较远时将会产生许 多无用节点，搜索效率低，这是它的缺点。优点：只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的 解，这是它的优点。3,深度优先搜索基本思想从初始节点So开始，按生成规则生成下一级各子节点，若

16、目标节点未出现，则按“最晚生成的子节点优先扩展”的原则，生成再下一级的子节点，如此下去,沿着最晚生成的子节点分支，逐级向“纵向”深入发展，故称为“深度优先搜索 法”。(2)深度优先搜索法搜索过程I该过程与广度优先搜索的唯一区别是：广度优先搜索是将节点n的子节点放入到OPEN表的尾部，而深度优先搜索是 把节点n的子节点放入到OPEN表的首部。仅此一点不同，就使得搜索的路线完全不一样。4CLOSED 表OPEN 表状态节点父节点8676543210Sg（8）编号状态节点父节点122y二 034y二 246,45例：对上节所示的重排九宫问题进行深度优先按索，可得如下图所示的搜索树。这只是搜索树的一部

17、分，尚未到达目标节点，仍可继续往下搜索。小结：在深度优先搜索中，搜索一旦进 入某个分支，就将沿着该分支一 直向下搜索。如果目标节点恰好 在此分支上，则可较快地得到解。但是，如果目标节点不在此分支 上，而该分支又是一个无穷分支,则就不可能得到解。所以深度优 先搜索是不完备的，即使问题有 解，它也不一定能求得解。另外，用深度优先搜索求得的 解，不一定是路径最短的解，其 道理是显然的。4.有界深度优先搜索(1)基本思想I 为了解决深度优先搜索不完备的问题，避免搜索过程陷入无穷分支的死循环,对深度优先搜索引入搜索深度的界限(设为dm),当搜索深度达到了深度界限,而尚未出现目标节点时，就换一个分支进行搜

18、索。(2)有界深度优先搜索的搜索过程例：设深度界度dm=4,用有界深度优先搜索方法求解重排九官问题。搜索树如图所示。解的路径是：20-25-26-28(Sg)2 8 3So 1 47 6 52 31 8 476 53 48653 45 8 6一2 173 4 58163 4 8652 178693 4 58 674 63 54 64538 628 3 145 7 634 5 867 2 1132 8 143 76 5W15XX142341 828 62 81 6 37 5428 3I 675 4345 8 7261345867213568 42 173 5 6847 218 3 54 6217

19、8352 4 61 74 53 862 174853 6 2173 4 52 8 6JI3 4 52 6187(3)有界深度优先搜索法的改进 上述方法存在两个问题：深度界限的选择很重要I 亳若太小，则达不到解的深度，得不到解；若太大，则搜索时将产生许多无用的子节 点，既浪费了计算机的存储空间与时间，又降低了搜索效率。由于解的路径长度事先难以预料，所以要恰当地给出亳的值是比较困难的。即使能求出解，它也不一定是最优解。解决方法：I.亳随搜索深度不断加大先任意给定一个较小的数作为心，然后进行上述的有界深度优先搜索，当搜索达到了 指定的深度界限dm仍未发现目标节点，并且CLOSED表中仍有待扩展节点时

20、.就将这些节点 送回OPEN表，同时增大深度界限亳，继续向下搜索。如此不断地增大亳，只要问题有解，就一定可以找到它。II,增加一个R表此时找到的解不一定是最优解。为找到最优解，可增设一个表(R),每找到一个目标节 点Sg后，就把它放入到R的前面，并令dm等于该目标节点所对应的路径长度，然后继续搜索。由于后求得的解的路径长度不会超过先求得的解的路径长度，所以最后求得的解一定是最 优解。求最优解的有界深度优 先搜索过程如图所示。其中Sg是目标节点.Sg*是距离S。最近的 目标节点。5.代价树的广度优先搜索(1)基本思想代价：从一个节点，经过一条支路，转移到另一个节点，所需支付的代价(时间、费用等)

21、。代价树：边上标有代价的树称为代价树。在代价树中，若用g(x)表示从初始节点S。到节点X的代价，用c(x X2)表示 从父节点X1到子节点X2的代价，则有：g(x2)=g(x+cCxp x2)代价树广度优先搜索的基本思想是：每次从OPEN表中选择节点往CLOSED表传送时，总是选择其代价为最小的节|点。也就是说，OPEN表中的节点在任一时刻都是按其代价从小至大排序的，|代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处 于什么位置。L J(2)代价树的广度优先搜索过程例：右图是五城市间的交通路线图，A城市是出发地,E城市是目的地，两城市间的交通费用（代价）如 图中数字所示。求从

22、A到E的最小费用交通路线。先将交通图转换为代价树，转换的方法是：从起始节点A开始，把与它直接相邻的节点作为它的子节点。对其它节点也做相同 的处理。若一个节点已作为某节点的直系先辈节点时，就不能再作为这个节点的子节点。例如，与节点C相邻的节点有A与D,但因A已作为C的父节点在代价树中出现了,所以它不能再作为c的子节点。图中的节点除起始节点A外，其它节点都可能要在 代价树中出现多次，为区分它的多次出现，分别用 下标L 2,标出，其实它们都是因中的同一节点。例如E,E2,E3,E4都是图中的节点E。第一步扩展A,得第1级子节点 G(3),Bi(4),第二步扩展Ci第三步扩展B按G，Bi排序,得第2级

23、子节点5,1按/I排序,得第2级子节点D2(8),G代价最小，优先扩展Bi代价最小，优先扩展%(9)按D,D2,Ei排序，Di代价最小，优先扩展第四步扩展Di得第3级子节点E2(8),B2(9)HH E2即为目标节点对此代价树进行代价树的广度优先搜索，可得到最优解为：AfGfDi f Ez 代价为8。由此可知从A城市到E城市舶最小费用路线为：AfCfD f E6.代价树的深度优先搜索(1)基本思想在代价树的广度优先搜索中，每次都是从OPEN表的全体节点中选择一个代价最 小的节点送入CLOSED表进行考察；代价树的深度优先搜索是从刚扩展出的子节点中选一个代价最小的节点送入CLOSED表进行考察。

24、例如上例：第一步扩展A,得第1级子节点C;(3),Bi(4),按G，Bl排序，G代价最小，优先扩展第二步扩展G得第2级子节点D1(5),按Di排序，I代价最小，优先扩展第三步扩展Di得第3级子节点E2(8),B2(9)E2即为目标节点由于代价树的深度优先搜索有可能进入无穷分支路径，因此它是不完备的。(2)代价树深度优先搜索的过程7.启发式搜索启发式搜索要用到问题自身的某些特性情息，以指导搜索朝着最有希望的方 向前进。由于这种搜索针对性较强，因而原则上只需要搜索问题的部分状态空 间，效率较高。启发性信息与估价函数启发信息在搜索过程中，关键的一步是如何确定下一个要考察的节点，确定的方法 不同就形成

25、了不同的搜索策略。如果在确定节点时能充分利用与问题求解有关的特性情息，估计出节点的重 要性，就能在搜索时选择重要性较高的节点，以利于求得最优解。像这样可用于指导搜索过程，且与具体问题求解有关的控制性信息称为启发性信息。估价函数用于估价节点重要性的函数称为估价函数。其一般形式为：f(x)=g(x)+h(x)其中：g(x)为从初始节点So到节点X已经实际付出的代价；h(x)是从节点x到目标节点Sg的最优路径的估计代价。h(x):称为启发函数，它体现了问题的启发性信息，其形式要根据问题的特性确定,例如：它可以是节点X到目标节点的距离，也可以是节点X处于最优路径上的概率等等。f(X):估价函数，它表示

26、从初始节点经过节点X到达目标节点的最优路径的代价估计值，它的作 用是估价OPEN表中各节点的重要程度，决定它们在OPEN表中的次序。g(x):指出了搜索的横向趋势，它有利于搜索的完备性，但影响搜索的效率。如果我们只关心到达目标节点的路径，并且希望有较高的搜索效率，则g(x)可 以忽略，但此时会影响搜索的完备件。因此，在确定f(x)时，要权衡各种利弊得失，使g(x)与h(x)各占适当的比重。例：设有如下结构的移动将牌游戏:其中：B代表黑色将牌；W代表白色将牌；E代表该位置为空。该游戏的玩法是:(1)当一个将脾移入相邻的空位置时，费用为一个单位。(2)一个将牌至多可跳过两个将牌进人空位置，其费用等

27、于跳过的将牌数加1。要求把所有的B都移至所有W的右边，请设计估价函数中的h(x)。根据要求可知，W左边的B越少越接近目标，因此可用W左边B的个数作为h(x),即：h(x)=3 x(每个W左边B个数的总和)I这里乘以系数3是为了扩大h(x)在f(x)中的比重。对于-B E B W W B Wh(x)=3 x(2+2+3)=21(2)局部择优搜索局部择优搜索是一种启发式搜索方法，是对深度优先搜索方法的一种改进。基本思想：当一个节点被扩展以后，按f(x)对每一个子节点计算估价值，并选择最小者 作为下一个要考察的节点，由于它每次都只是在子节点的范围内选择下一下要 考察的节点，范围比较狭窄，所以称为局部

28、择优搜索。搜索过程：I.把初始节点S。放入OPEN表，计算f(S0)；IL如果OPEN表为空，则问题无解，退出；III.把OPEN表的第一个节点(记为节点n)取出放入CLOSED表；W.考察节点n是否为目标节点。若是，则求得了问题的解，退出；V.若节点”不可扩展，则转第II步。VI.扩展节点n,用估价函数f(x)计算每个子节点的估价值，并按估价值从小 到大的顺序依次放到OPEN表的首部，为每个子节点配置指向父节点的指针。然后转第H步。深度优先搜索、代价树的深度优先搜索以及局部择优搜索比较 共同处：都是以子节点为考察对象，逐级向“纵向”深入发展；不同处：它们选择节点的标推不-样：深度优先搜索以子

29、节点的深度作为选择标准，后生成的子节点先被考察；代价树深度优先搜索以各子节点到父节点的代价作为选择标准，代价小者优先被选择;局部择优搜索以估价函数的值作为选择标准，哪一个子节点的f值最小就优先被选择。在局部择优搜索中，若令f(X)=g(x),则局部择优搜索就成为代价树的深度优先搜索；若令f(x)=d(x),这里d(x)表示节点X的深度，则局部择优搜索就成为深度优先 搜索。所以深度优先搜索和代价树的深度优先搜索可看作局部择优搜索的两个特例。(3)全局择优搜索基本思想局部择优搜索，只是从刚生成的子点节中选择一个节点进行考察，选择的范围比较狭窄;全局择优搜索，每次从OPEN表的全体节点中选择一个估价

30、值最小的节点进行考察。只此 一点与局部择优搜索不同。搜索过程:I.把初始节点So放入OPEN表，计算f(S0)；II.如果OPEN表为空,则问题无解，退出；III.把OPEN表的第一个节点(记为节点n)取出放入CLOSED表；IV.考察节点n是否为目标节点。若是，则求得了问题的解，退出；v.若节点”不可扩展，则转第n步。VI.扩展节点n,用估价函数f(x)计算每个子节点的估价值，为每个子节点配 置指向父节点的指针,把这些节点都送入OPEN表，然后对OPEN表中的全部 节点按估价值从小到大的排序，然后转第II步。广度优先搜索、代价树的广度优先搜索以及全局择优搜索比较若令f(x)=g(x),则全局

31、择优搜索就成为代价树的广度优先搜索；若令f(x)=d(x),这里d(x)表示节点X的深度，则全局择优搜索就成为广度优先搜索。所以广度优先搜索和代价树的广度优先搜索可看作全局择优搜索的两个特例。例：用全局择优搜索求解重排九宫问题。设估价函数为f(x)=d(x)+h(x)其中，d(x)表示节点x的深度，h(x)表示节点x的格局与目标节点格局不相同的牌数。g345 8 6217334586217为 解565 846 21753 45 816 2 756345816 27345816 27645 386 217345286173452867345286 174345 2 6 1878.状态空间的一般搜

32、索过程讲了前面的一些搜索策略后，我们总结一下搜索的一般过程。把初始节点S。放入OPEN表，并建立目前只包含So的图，记为G；(2)检查OPEDN表是否为空，若为空则问题无解，退出；(3)把OPEN表的第一个节点取出放入CLOSED表，并记该节点为节点n；(4)考察节点n是否为目标节点。若是，则求得了问题的解，退出；扩展节点m生成一组子节点。把其中不是节点n先辈的那些子节点记作集合M,并把 这些子节点作为节点n的子节点加入G中。(6)针对M中子节点的不同情况，分别进行如下处理：对于那些未曾在G中出现过的M成员设置一个指向父节点(即节点n)的指针，并把它们放入OPEN表；对于那些先前已在G中出现过

33、的M成员，确定是否需要修改它指向父节点的指针；对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节 点指向父节点的指针；(7)按某种搜索策略对OPEN表中的节点进行排序；(8)转第(2)步。在启发式搜索中，估价函数的定义是十分重要的，如定义不当，则上述搜索算法不一定 能找到问题的解，即使找到解，也不一定是最优的。为此，需要对估价函数进行某些限制。下面我们看A*算法。9.A*算法(i)a*算法如果使一般搜索过程满足如下限制，则它就成为A*算法:(1)把OPEN表中的节点按估价函数f(x)=g(x)+h(x)的值从小至大进行排序。(一般搜索过程的第步)(2)g(x)是对g*(x

34、)的估计,g(x)Oo(3)h(x)是h*(x)的下界，即对所有的x均有：h(x)g*(x)，h(x)的确定依赖于具体问题领域的启发性信息，其中h(x)h*(x)的限制是十分 重要的，它可保证A算法能找到最优解。(3)A*算法的特性 a*算法的可纳性对于可解状态空间图即(从初始节点到目标节点有路径存在)来说，如果一个搜索算法 能在有限步内终止，并且能找到最优解，则称该搜索算法是可纳的。A*算法是可纳的 a*算法的最优性A*算法的搜索效率在很大程度上取决于h(x),在满足h(x)W(h*(x)的前提下，h(x)的 值越大越好。h(x)的值越大，表明它携带的启发性信息越多，搜索时扩展的节点数越 少，搜索效率越高。A*算法的单调性限制