第03章搜索推理技术

1、 三、搜索推理技术三、搜索推理技术1. 1. 搜索的概念和种类搜索的概念和种类2. 2. 图搜索策略图搜索策略3. 3. 盲目搜索盲目搜索4. 4. 启发式搜索启发式搜索 概概 述述l搜索是人工智能的一个基本问题，是推理不可分割的一部分；l搜索是求解问题的一种方法；l为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来 3.1. 3.1. 搜索的概念和种类搜索的概念和种类 搜索 根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程。含义 从初始事实到问题答案的一条推理路线； 找到的这条路线是时间和空间复杂度最小的求解

2、路线。搜索的概念搜索的概念 盲目搜索（无信息搜索）：在搜索过程中，只按照预定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。 搜索带有盲目性，效率不高，如果遇到比较复杂的问题，其求解的效率可能就相当低。 用于解决比较简单的问题。搜索的种类搜索的种类 启发式搜索（有信息搜索）：在搜索求解过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。 虽然启发式搜索由于考虑到问题本身的特性并利用这些特性，从而使搜索求解的效率更高，更易于求解复杂的问题，然而并不是对所有的问题都能方便地抽取问题的有关特性和信

3、息，因此尽管启发式搜索好于盲目搜索，但盲目搜索也会在很多问题的求解中得到应用。搜索的种类搜索的种类 3.2. 3.2. 图搜索策略图搜索策略 什么是状态空间图？什么是状态空间图？ 使用图示的方式用状态空间图对一个使用图示的方式用状态空间图对一个问题进行描述的方法。问题进行描述的方法。 状态空间图是一个有向图。当把一个状态空间图是一个有向图。当把一个待求解的问题表示为状态空间以后，就可待求解的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的以通过对状态空间的搜索，实现对问题的求解。如果从状态空间的角度来看，则对求解。如果从状态空间的角度来看，则对问题的求解就相当于在有向图上寻找一

4、条问题的求解就相当于在有向图上寻找一条从某一节点（初始状态节点）到另一节点从某一节点（初始状态节点）到另一节点（目标节点）的路径。（目标节点）的路径。3.2. 3.2. 图搜索策略（图搜索策略（1 1） 若要把表示问题的整个状态空间都存若要把表示问题的整个状态空间都存入计算机，往往需要占据巨大的存储空间，入计算机，往往需要占据巨大的存储空间，尤其对比较复杂的问题，这几乎是不能实尤其对比较复杂的问题，这几乎是不能实现的。并且一般也无这种必要。因为对于现的。并且一般也无这种必要。因为对于一个具体的问题，其解往往只与状态空间一个具体的问题，其解往往只与状态空间的一部分相关，只要计算机生成并存储与的一

5、部分相关，只要计算机生成并存储与问题有关的解状态空间部分，即可将问题问题有关的解状态空间部分，即可将问题解决。解决。 如何来生成并存储与问题有关的部分如何来生成并存储与问题有关的部分状态空间？状态空间？ 3.2. 3.2. 图搜索策略（图搜索策略（2 2） 求解的基本思想求解的基本思想 （1 1）将问题的初始状态（状态空间图）将问题的初始状态（状态空间图中的初始节点）当作当前节点，选择一适中的初始节点）当作当前节点，选择一适当的算符作用于当前状态，生成一组后继当的算符作用于当前状态，生成一组后继状态（或后继节点）。状态（或后继节点）。 （2 2）检查这组后继状态中有没有目标）检查这组后继状态中

6、有没有目标状态，如果有，则说明搜索成功，从初始状态，如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的状态到目标状态的一系列算符即是问题的解。解。 （3 3）若没有，则按照某种控制策略从）若没有，则按照某种控制策略从已生成的状态中再选择一个状态作为当前已生成的状态中再选择一个状态作为当前状态。状态。 （4 4）重复上述过程，直到目标状态出）重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。现或不再有可供操作的状态及算符时为止。 3.2. 3.2. 图搜索策略（图搜索策略（3 3） 状态空间图是由节点节点和分支分支构成的集合。节点数目有限的状态空间图被称为有限节点

7、有限节点图图。一个分支连接两个节点，其中有方向的分支称为有向分支有向分支，没有方向的称为无向分无向分支支。当存在从节点N1到节点N2的路径时，节点N1被称为节点N2的父节点父节点；节点N2被称为节点N1的子节点子节点。如果从N1到N2的路径只有一条的时候，而且两端的节点相同，则这种路径称为闭路闭路。3.2. 3.2. 图搜索策略（图搜索策略（4 4） 3.2. 3.2. 图搜索策略（图搜索策略（5 5） 已扩展节点已扩展节点 用适合的算符对某个节点进行操作生用适合的算符对某个节点进行操作生成一组后继节点，扩展过程实际上就是求成一组后继节点，扩展过程实际上就是求后继节点的过程。所以，对状态空间图

8、的后继节点的过程。所以，对状态空间图的某个节点，如果求出了它的后继节点，则某个节点，如果求出了它的后继节点，则此节点为此节点为已扩展的节点已扩展的节点，而尚未求出它的，而尚未求出它的后继节点的节点称为后继节点的节点称为未扩展节点未扩展节点。 状态节点状态节点父节点父节点未扩展未扩展OPEN表表编号编号状态节点状态节点父节点父节点扩展扩展CLOSED表表 3.2. 3.2. 图搜索策略（图搜索策略（6 6） 状态空间的搜索算法如下：状态空间的搜索算法如下：（1）建立一个只含有初始节点）建立一个只含有初始节点S的搜索图的搜索图G,把把S放入放入OPEN表中。表中。（2）建立）建立CLOSED表，且

9、置为空表。表，且置为空表。（3）LOOP: 若若OPEN表是空表，则失败退出。表是空表，则失败退出。（4）选择）选择OPEN表上的第一个节点，把它从表上的第一个节点，把它从OPEN表移出并放进表移出并放进CLOSED表中，称此节点为节点表中，称此节点为节点n。（5）若）若n为一目标节点，则有解并成功退出，此解是追踪图为一目标节点，则有解并成功退出，此解是追踪图G中中沿着指针从沿着指针从n到到S这条路径而得到的。这条路径而得到的。（6）扩展节点）扩展节点n，同时生成不是，同时生成不是n的祖先的那些后继节点的集合的祖先的那些后继节点的集合M。把。把M的这些成员作为的这些成员作为n的后继节点添入图的

10、后继节点添入图G中。中。（7）对那些未曾在）对那些未曾在G中出现过的，中出现过的，M成员设置一个通向成员设置一个通向n的指针，的指针，把把M的这些成员加进的这些成员加进OPEN表。对已经在表。对已经在OPEN或或CLOSED表上表上的每一个的每一个M成员，确定是否需要更改通到成员，确定是否需要更改通到n的指针方向。对已在的指针方向。对已在CLOSED表上的每个表上的每个M成员，确定是否需要更改图成员，确定是否需要更改图G中通向它的中通向它的每个后裔节点的指针方向。每个后裔节点的指针方向。（8）按某一任意方式或按某个试探值，重排）按某一任意方式或按某个试探值，重排OPEN表。表。（9）GO LO

11、OP 3.2. 3.2. 图搜索策略（图搜索策略（7 7）开始开始节点节点n是否为是否为目标节点目标节点失败退出失败退出YN根据后入先出或先入先出的原则从根据后入先出或先入先出的原则从Open表中选择一个节点，并置为表中选择一个节点，并置为n将将n的子节点中未包含在的子节点中未包含在Closed表表中的节点加入中的节点加入Open表中表中Open表是否空表是否空成功退出成功退出YN将初始节点加入将初始节点加入Open表表Closed表置空表置空 3.2. 3.2. 图搜索策略（图搜索策略（8 8） 各种搜索策略的主要区别各种搜索策略的主要区别 第（第（8 8）步对）步对OPENOPEN表中的节

12、点排序的算表中的节点排序的算法不同。在（法不同。在（8 8）中对）中对OPENOPEN表中的节点排序表中的节点排序时，主要希望从未扩展的节点中选出一个时，主要希望从未扩展的节点中选出一个最有希望的节点作为第（最有希望的节点作为第（4 4）不扩展来用。）不扩展来用。若这时的排序是任意的或者盲目的，则搜若这时的排序是任意的或者盲目的，则搜索即为盲目搜索，按照某种启发信息或准索即为盲目搜索，按照某种启发信息或准则进行排序，则其就是启发式搜索。则进行排序，则其就是启发式搜索。 在搜索过程中，生成一个图在搜索过程中，生成一个图G G，它是问，它是问题状态空间图的一部分，称为题状态空间图的一部分，称为搜索

13、图搜索图。 3.3 3.3 盲目搜索盲目搜索 无信息搜索或盲目搜索 无需重新安排OPEN表的搜索。 （1）宽度优先搜索(breadth-first search)； （2）深度优先搜索(depth-first search) ； （3）等代价搜索(equal-cost search)。3.3 3.3 盲目搜索（盲目搜索（1 1） 宽度优先搜索如果搜索是以接近起始节点的程度来依次扩展节点。3.3 3.3 盲目搜索（盲目搜索（2 2）SOLMQRPV 搜索是逐层进行的，在对下一层的任意节点进行搜索之前，必须搜索完本层的所有节点。 3.3 3.3 宽度优先搜索（宽度优先搜索（3 3） 宽度优先搜索算

14、法如下：宽度优先搜索算法如下：（1）把初始节点放到）把初始节点放到OPEN表中（如果起始节点为一表中（如果起始节点为一目标节点，则求得一个解答）。目标节点，则求得一个解答）。（2）如果）如果OPEN是一个空表，则没有解，失败退出；是一个空表，则没有解，失败退出；否则继续。否则继续。（3）把第一个节点从）把第一个节点从OPEN表移出，并放进表移出，并放进CLOSED表表中，称此节点为节点中，称此节点为节点n。（4）扩展节点）扩展节点n。如果没有后继节点，则转向步骤。如果没有后继节点，则转向步骤(2)。（5）把）把n的所有后继节点放到的所有后继节点放到OPEN表的末端，并提供从表的末端，并提供从这

15、些后继节点回到这些后继节点回到n的指针。的指针。（6）如果）如果n的任意节点是个目标节点，则找到一个解答，的任意节点是个目标节点，则找到一个解答，成功退出；否则转向步骤成功退出；否则转向步骤(2)。 3.3 3.3 宽度优先搜索（宽度优先搜索（4 4）开始开始是否有任何后继是否有任何后继节点为目标节点节点为目标节点失败退出失败退出YN把第一个节点把第一个节点n从从OPEN表中移出，表中移出，并把它放入并把它放入CLOSED表中表中扩展扩展n，把它的后继节点放到，把它的后继节点放到OPEN表的表的末端，提供回到末端，提供回到n的指针的指针Open表是否空表是否空成功退出成功退出YN把把S放入放入

16、OPEN表表 例：八数码难题：设在八数码难题：设在3 3 3 3的一个方格模盘上，摆放的一个方格模盘上，摆放着着8 8个数码个数码1 1、2 2、3 3、4 4、5 5、6 6、7 7、8 8，有一个方格是空，有一个方格是空格，其初始状态和目标状态如图，要求对空格执行下格，其初始状态和目标状态如图，要求对空格执行下列的操作（或算符）：列的操作（或算符）： 空格左移，空格上移，空格右移，空格下移。空格左移，空格上移，空格右移，空格下移。要求寻找从初始状态到目标状态的路径。要求寻找从初始状态到目标状态的路径。3.3 3.3 宽度优先搜索（宽度优先搜索（5 5）2 8 31 47 6 5初始状态S0

17、1 2 38 47 6 5目标状态Sg2 8 3 1 4 07 6 552 8 31 47 6 51S02 8 31 6 47 0 542 8 30 1 47 6 522 0 31 8 47 6 532 8 37 1 40 6 570 8 32 1 47 6 562 3 01 8 47 6 590 2 31 8 47 6 582 8 31 6 47 5 0112 8 31 6 40 7 5102 8 01 4 37 6 5122 8 31 4 57 6 0132 8 37 1 46 0 5158 0 32 1 47 6 5142 3 41 8 07 6 5171 2 30 8 47 6 516

18、2 8 31 6 07 5 4192 8 30 6 41 7 5182 0 81 4 37 6 5202 8 31 4 57 0 6218 1 32 0 47 6 5238 3 02 1 47 6 5222 8 37 1 46 5 0252 8 37 0 46 1 5241 2 38 0 47 6 5271 2 37 8 40 6 526Sg 深度优先搜索3.3 3.3 盲目搜索（盲目搜索（7 7）SOLMNQPR 先扩展最新产生的节点，深度相等的节点可以任意排列。为了避免考虑太长的路径，往往给出一个节点扩展的最大深度深度界限。达到深度界限，认为没有后继节点。 4.3 4.3 盲目搜索（盲目搜

19、索（8 8） 深度有界的深度优先搜索算法如下：深度有界的深度优先搜索算法如下：（1）把初始节点放到）把初始节点放到OPEN表中（如果起始节点为一表中（如果起始节点为一目标节点，则求得一个解答）。目标节点，则求得一个解答）。（2）如果）如果OPEN是一个空表，则没有解，失败退出；是一个空表，则没有解，失败退出；否则继续。否则继续。（3）把第一个节点（节点）把第一个节点（节点n）从）从OPEN表移到表移到CLOSED表表中。中。（4）如果节点）如果节点n的深度等于最大深度，则转向步骤的深度等于最大深度，则转向步骤(2)。（5）扩展节点）扩展节点n，产生其全部后裔，并把它们放入到，产生其全部后裔，并

20、把它们放入到OPEN表的前头。如果没有后裔，则转向步骤表的前头。如果没有后裔，则转向步骤(2)。（6）如果）如果n的任意节点是个目标节点，则找到一个解答，的任意节点是个目标节点，则找到一个解答，成功退出；否则转向步骤成功退出；否则转向步骤(2)。 3.3 3.3 盲目搜索（盲目搜索（9 9） 代价树的宽度优先搜索代价树的宽度优先搜索 在实际问题中，从一个状态变换成另在实际问题中，从一个状态变换成另一个状态所付出的操作代价是不一样的。一个状态所付出的操作代价是不一样的。问题：采用何种搜索策略，以保证付出的问题：采用何种搜索策略，以保证付出的代价（或费用）是最小的。代价（或费用）是最小的。代价树：

21、有向边上标有代价的搜索树。代价树：有向边上标有代价的搜索树。 3.3 3.3 盲目搜索（盲目搜索（1010） 代价树的宽度优先搜索代价树的宽度优先搜索 记号：记号： (1) (1)起始节点记为起始节点记为S;S; (2) (2)从节点从节点i i到它的后继节点到它的后继节点j j的代价记的代价记为为c(i,j);c(i,j); (3) (3)从起始节点从起始节点S S到任一节点到任一节点i i的路径代的路径代价记为价记为g(i)g(i)。 3.3 3.3 盲目搜索（盲目搜索（1010）例例 推销员旅行问题推销员旅行问题 假设假设A A、B B、C C、D D、E E是五个城市，是五个城市，推销

22、员从城市推销员从城市A A出发，到达城市出发，到达城市E E，走，走怎样的路线费用最省？怎样的路线费用最省？ACBDE7657864.4 4.4 启发式搜索（启发式搜索（1 1）盲目搜索的特点：盲目搜索的特点： 搜索线路是事先决定好的，没有搜索线路是事先决定好的，没有利用被求解问题的任何信息。利用被求解问题的任何信息。 在决定要被扩展的节点时，没有在决定要被扩展的节点时，没有考虑节点是否可能出现在解的路径上。考虑节点是否可能出现在解的路径上。 没有考虑它是否有利于问题的求没有考虑它是否有利于问题的求解以及所求的解是否为最优解。解以及所求的解是否为最优解。3.4 3.4 启发式搜索（启发式搜索（

23、2 2）盲目搜索的缺点：盲目搜索的缺点： 搜索所需要扩展的节点数目很大。搜索所需要扩展的节点数目很大。 产生的无用节点很多，效率很低。产生的无用节点很多，效率很低。3.4 3.4 启发式搜索（启发式搜索（3 3）启发式搜索（有信息搜索）：启发式搜索（有信息搜索）： 找到一种方法用于排列待扩展节找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加点的顺序，即选择最有希望的节点加以扩展，搜索效率将会大大提高。以扩展，搜索效率将会大大提高。 heuristically searchheuristically search informed search informed search3.4.

24、1 3.4.1 启发信息与估价函数启发信息与估价函数搜索的关键搜索的关键 选择下一个要被考察的选择下一个要被考察的节点节点，不，不同的选择方法即是不同的同的选择方法即是不同的搜索策略搜索策略。启发信息启发信息 指导搜索过程且与具体问题求解指导搜索过程且与具体问题求解有关的有关的控制性信息控制性信息。3.4.1 3.4.1 启发信息与估价函数（启发信息与估价函数（2 2）启发信息的种类启发信息的种类1.1.用于决定要用于决定要扩展的下一个节点扩展的下一个节点，以免，以免在宽度优先或深度优先那样盲目扩展。在宽度优先或深度优先那样盲目扩展。2.2.在扩展节点的过程中，用于在扩展节点的过程中，用于决定

25、要生决定要生成哪一个或几个后继节点成哪一个或几个后继节点，以免盲目的，以免盲目的同时生成所有可能的节点。同时生成所有可能的节点。3.3.用于确定某些应该从搜索树中用于确定某些应该从搜索树中抛弃或抛弃或修剪修剪的节点。的节点。3.4.1 3.4.1 启发信息与估价函数（启发信息与估价函数（3 3）估价函数估价函数构造一个构造一个函数函数来表示节点的来表示节点的“希望希望”程程度。度。估价函数的任务估价函数的任务 估计待搜索节点的估计待搜索节点的重要程度重要程度，给它，给它们们排定次序排定次序。3.4.1 3.4.1 启发信息与估价函数（启发信息与估价函数（4 4）估价函数估价函数f(x)f(x)

26、1.1.可以是节点可以是节点x x处于最佳路径上的处于最佳路径上的概率概率。2.2.节点节点x x到目标节点之间的到目标节点之间的距离距离。估价节点应考虑的因素估价节点应考虑的因素 已经付出的代价已经付出的代价 将要付出的代价将要付出的代价3.4.1 3.4.1 启发信息与估价函数（启发信息与估价函数（5 5）估价函数估价函数f(x)f(x)定义为从初始节点经定义为从初始节点经过节点过节点x x到达目标节点的最小代价到达目标节点的最小代价路径的代价估算值。路径的代价估算值。一般形式一般形式 f(x)=g(x)+h(x)f(x)=g(x)+h(x)g(x)g(x)从初始节点从初始节点S S0 0

27、到节点到节点x x已实际付出的代价；已实际付出的代价；h(x)h(x)从节点从节点x x到目标节点到目标节点S Sg g的最优路径的估价代价。的最优路径的估价代价。3.4.1 3.4.1 启发信息与估价函数（启发信息与估价函数（6 6）启发函数启发函数h(x)h(x) 搜索的启发信息主要由搜索的启发信息主要由h(x)h(x)来体现，来体现，g(x)g(x)可以根据已生成的搜索树计算得出，而可以根据已生成的搜索树计算得出，而h(x)h(x)要依赖于某种经验估计。要依赖于某种经验估计。 在在f(x)f(x)中，中，g(x)g(x)的比重越大，搜索方向的比重越大，搜索方向倾向于广度优先搜索；倾向于广

28、度优先搜索； h(x)h(x)的比重越大，越倾向于深度优先搜的比重越大，越倾向于深度优先搜索。索。3.4.1 3.4.1 启发信息与估价函数（启发信息与估价函数（7 7） 搜索的启发信息主要由搜索的启发信息主要由h(x)h(x)来体现，来体现，g(x)g(x)可以根据已生成的搜索树计算得出，而可以根据已生成的搜索树计算得出，而h(x)h(x)要依赖于某种经验估计。要依赖于某种经验估计。 在在f(x)f(x)中，中，g(x)g(x)的比重越大，搜索方向的比重越大，搜索方向倾向于广度优先搜索；倾向于广度优先搜索；h(x)h(x)的比重越大，越的比重越大，越倾向于深度优先搜索。倾向于深度优先搜索。

29、g(x)h(x)g(x)h(x)时，可忽略时，可忽略g(x)g(x)。这时，。这时，f(x)=h(x)f(x)=h(x)，这会有利于搜索效率的提高，这会有利于搜索效率的提高，但影响搜索算法的完备性，即有可能找不到但影响搜索算法的完备性，即有可能找不到问题的解。问题的解。3.4.2 3.4.2 最佳优先搜索（最佳优先搜索（1 1） 最佳优先搜索（有序搜索、择优搜索）最佳优先搜索（有序搜索、择优搜索） 它总是选择最有希望的节点作为下一个它总是选择最有希望的节点作为下一个要扩展的节点，而这种最有希望的节点是按要扩展的节点，而这种最有希望的节点是按估价函数估价函数f(x)f(x)的值来挑选的，一般估价

30、函数的值来挑选的，一般估价函数的值越小，它的希望程度就越大。的值越小，它的希望程度就越大。分为两种分为两种q 局部优先搜索局部优先搜索q 全局优先搜索全局优先搜索3.4.2 3.4.2 最佳优先搜索（最佳优先搜索（2 2） 局部最佳优先搜索局部最佳优先搜索 类似于深度优先搜索法，但由于使用了类似于深度优先搜索法，但由于使用了与问题特性相关的估价函数确定下一个待扩与问题特性相关的估价函数确定下一个待扩展的节点，所以它是一种启发式搜索方法。展的节点，所以它是一种启发式搜索方法。基本思想基本思想 当对某个节点扩展之后，对它的每一个当对某个节点扩展之后，对它的每一个后继节点计算估价函数后继节点计算估价

31、函数f(x)f(x)的值。由于它每的值。由于它每次只是在后继节点范围内，选择一个次只是在后继节点范围内，选择一个f(x)f(x)的的值最小的节点，作为下一个要考察的节点，值最小的节点，作为下一个要考察的节点，范围较小。范围较小。3.4.2 3.4.2 最佳优先搜索（最佳优先搜索（3 3） 局部最佳优先搜索算法局部最佳优先搜索算法(1)(1)把初始节点把初始节点S0S0放入放入OPENOPEN表中，并计算估价函数表中，并计算估价函数f(S0). f(S0). (2)(2)如果如果OPENOPEN为空，则问题无解，退出；否则转为空，则问题无解，退出；否则转(3).(3).(3)(3)从从OPENO

32、PEN表中选取第一个节点（记为表中选取第一个节点（记为n,n,其估价函数最小）转其估价函数最小）转入入CLOSEDCLOSED表。表。(4)(4)考察节点考察节点n n是否目标节点，若是则求得问题的解，退出；是否目标节点，若是则求得问题的解，退出；否则转否则转(5)(5)。(5)(5)如果节点如果节点n n可扩展，转可扩展，转(6)(6)；否则转；否则转(2)(2)(6)(6)对节点对节点n n进行扩展，对它的所有后继节点计算估价函数进行扩展，对它的所有后继节点计算估价函数f(x)f(x)的值，并按估价函数的值，并按估价函数f(x)f(x)从小到大的顺序依次放入从小到大的顺序依次放入OPENO

33、PEN表表的前端。的前端。(7)(7)为每个后继节点设置指向为每个后继节点设置指向n n的指针。的指针。(8)(8)转转(2)(2)。3.4.2 3.4.2 最佳优先搜索（最佳优先搜索（4 4） 全局最佳优先搜索全局最佳优先搜索 类似于宽度优先搜索法，但由于使用了类似于宽度优先搜索法，但由于使用了与问题特性相关的估价函数确定下一个待扩与问题特性相关的估价函数确定下一个待扩展的节点，所以它是一种启发式搜索方法。展的节点，所以它是一种启发式搜索方法。基本思想基本思想 当对某个节点扩展之后，对它的每一个当对某个节点扩展之后，对它的每一个后继节点计算估价函数后继节点计算估价函数f(x)f(x)的值。由

34、于它每的值。由于它每次在次在OPENOPEN表的全部节点范围内，选择一个表的全部节点范围内，选择一个f(x)f(x)的值最小的节点，作为下一个要考察的节点，的值最小的节点，作为下一个要考察的节点，范围较小。范围较小。3.4.2 3.4.2 最佳优先搜索（最佳优先搜索（5 5） 全局最佳优先搜索算法全局最佳优先搜索算法(1)(1)把初始节点把初始节点S0S0放入放入OPENOPEN表中，并计算估价函数表中，并计算估价函数f(S0). f(S0). (2)(2)如果如果OPENOPEN为空，则问题无解，退出；否则转为空，则问题无解，退出；否则转(3).(3).(3)(3)从从OPENOPEN表中选

35、取第一个节点（记为表中选取第一个节点（记为n,n,其估价函数最小）转其估价函数最小）转入入CLOSEDCLOSED表。表。(4)(4)考察节点考察节点n n是否目标节点，若是则求得问题的解，退出；是否目标节点，若是则求得问题的解，退出；否则转否则转(5)(5)。(5)(5)如果节点如果节点n n可扩展，转可扩展，转(6)(6)；否则转；否则转(2)(2)(6)(6)对节点对节点n n进行扩展，对它的所有后继节点计算估价函数进行扩展，对它的所有后继节点计算估价函数f(x)f(x)的值，为每个后继节点设置指向的值，为每个后继节点设置指向n n的指针。的指针。 (7)(7)把这些节点都送入把这些节点

36、都送入OPENOPEN表，然后对表，然后对OPENOPEN表中的全部节点按表中的全部节点按照估价值从小到大顺序排序。照估价值从小到大顺序排序。(8)(8)转转(2)(2)。3.4.2 3.4.2 最佳优先搜索（最佳优先搜索（6 6） 例例: :用全局最佳优先搜索方法求解八数用全局最佳优先搜索方法求解八数码难题。码难题。2 0 31 8 4 7 6 5S01 2 38 0 4 7 6 5Sg3.4.3 A3.4.3 A* *算法（算法（1 1） A A* *算法的定义算法的定义 它选用了一个比较特殊的估价函数。这它选用了一个比较特殊的估价函数。这时的估价函数是下列估价函数时的估价函数是下列估价函

37、数 f f* *(x)=g(x)=g* *(x)+h(x)+h* *(x)(x)的一种估计或近似。的一种估计或近似。f(x)f(x)是对是对f f* *(x)(x)的一种估的一种估算；算； g(x)g(x)是对是对g g* *(x)(x)的一种估算；的一种估算； h(x)h(x)是对是对h h* *(x)(x)的一种估算的一种估算. .3.4.3 A3.4.3 A* *算法（算法（2 2） f f* *(x):(x):表示从节点表示从节点S0S0到节点到节点x x的一条最佳路径的一条最佳路径的实际代价加上从节点的实际代价加上从节点x x到目标节点的一条到目标节点的一条最佳路径的代价之和。最佳路

38、径的代价之和。 g g* *(x)(x)表示从节点表示从节点S0S0到节点到节点x x的一条最佳路径的一条最佳路径的实际代价。的实际代价。 h h* *(x)(x)表示从节点表示从节点x x到目标节点的一条最佳路到目标节点的一条最佳路径的代价。径的代价。3.4.3 A3.4.3 A* *算法（算法（3 3） A A* *算法定义算法定义 如果在一般状态空间图的搜索算法中的第如果在一般状态空间图的搜索算法中的第8 8步，依据估价函数步，依据估价函数 f(x)=g(x)+h(x)f(x)=g(x)+h(x)对对OPENOPEN表中的节点进行排序，并且要求启发函表中的节点进行排序，并且要求启发函数数

39、h(x)h(x)是是h h* *(x)(x)的一个下界，即的一个下界，即h(x)=hh(x)=h* *(x).(x).A A算法：没有限制。算法：没有限制。3.4.3 A3.4.3 A* *算法（算法（4 4） A A* *算法实例算法实例 假设某个人要从假设某个人要从A点到达点到达B点，而一堵墙点，而一堵墙把这两个点隔开了，如把这两个点隔开了，如下图所示，绿色部分代下图所示，绿色部分代表起点表起点A，红色部分代，红色部分代表终点表终点B，蓝色方块部，蓝色方块部分代表之间的墙。分代表之间的墙。3.4.3 A3.4.3 A* *算法（算法（5 5） A A* *算法实例算法实例 G从起点从起点A

40、沿着已生成的沿着已生成的路径到一个给路径到一个给定方格的移动定方格的移动开销。开销。 H从给定方从给定方格到目的方格格到目的方格的估计移动开的估计移动开销。销。3.4.3 A3.4.3 A* *算法（算法（6 6） A A* *算法实例算法实例 3.4.3 A3.4.3 A* *算法（算法（7 7） A A* *算法实例算法实例 3.4.3 A3.4.3 A* *算法（算法（8 8） A A* *算法实例算法实例 3.4.3 A3.4.3 A* *算法（算法（9 9） A A* *算法算法 1. 将开始节点放入将开始节点放入Open(开始节点的开始节点的F和和G值都视为值都视为0);Repeat 1.1 在在Open表中查找具有最小表中查找具有最