《《人工智能原理》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《人工智能原理》PPT课件.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能原理第三章搜索推理技术1从问题表示到问题的解决，有一个求解的从问题表示到问题的解决，有一个求解的过程。接下来要研究的是实现求解的过程，过程。接下来要研究的是实现求解的过程，采用的基本方法包括采用的基本方法包括搜索搜索和和推理推理。本章先介绍本章先介绍搜索技术搜索技术，将要讨论问题求解，将要讨论问题求解的搜索原理，包括一些早期的搜索技术或的搜索原理，包括一些早期的搜索技术或用于解决比较简单问题的搜索原理和一些用于解决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原比较新的能够求解比较复杂问题的搜索原理，包括理，包括A*算法。算法。23.1 3.1 图搜索策略图搜索策略可把
2、图搜索策略看成一种在图中寻找路径可把图搜索策略看成一种在图中寻找路径的方法的方法图中的节点对应于状态，而连线对应于操图中的节点对应于状态，而连线对应于操作符。这些节点和连线作符。这些节点和连线(即状态与操作符即状态与操作符)又分别由产生式系统的数据库和规则来标又分别由产生式系统的数据库和规则来标记记初始节点和目标节点之间的路径。即求得初始节点和目标节点之间的路径。即求得把一个数据库变换为另一数据库的规则序把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题列问题就等价于求得图中的一条路径问题3例子：从某王姓家族的四代中找王例子：从某王姓家族的四代中找王A的后代且其的后代且其
3、寿命为寿命为X的人。的人。王王A：寿命：寿命47，有儿子王，有儿子王B1、王、王B3、王、王B2王王B1：寿命：寿命77，有儿子王，有儿子王C1、王、王C2王王B3：寿命：寿命52，有儿子王，有儿子王D1王王B2：寿命：寿命65，有儿子王，有儿子王E1、王、王E2王王F1：寿命：寿命32 王王G1：寿命：寿命96王王C2：寿命：寿命87，有儿子王，有儿子王F1王王D1：寿命：寿命77，没有儿子，没有儿子王王E1：寿命：寿命57，有儿子王，有儿子王G14 王王E2：寿命：寿命92，有儿子王，有儿子王H1 王王C1：寿命：寿命27，没有儿子，没有儿子王王H1：寿命：寿命51若若X=57，下面讨论一
4、种可通用的图搜索策略求解，下面讨论一种可通用的图搜索策略求解此问题。此问题。如果是一个如果是一个N代的家族表中找其寿命为代的家族表中找其寿命为X的人，的人，我们最可能用的我们最可能用的手工方法手工方法是从家族表的开始往下，是从家族表的开始往下，例中还要求所找的人是某人的后代，就比较复杂例中还要求所找的人是某人的后代，就比较复杂了。如果用了。如果用图图来表示，就很容易了。图中把姓氏来表示，就很容易了。图中把姓氏省去，每个成员的后代按例子中给出名字的先后省去，每个成员的后代按例子中给出名字的先后顺序。图示为：顺序。图示为：56图搜索图搜索(GRAPHSEARCH)(GRAPHSEARCH)的一般过
5、程如下：的一般过程如下：(1)建立一个只含有建立一个只含有起始节点起始节点S的搜索图的搜索图G，把，把S放到一个叫做放到一个叫做OPEN的的未未扩展扩展节点表中（简称节点表中（简称OPEN表）。表）。(2)建立一个叫做建立一个叫做CLOSED的的已扩展已扩展节点表（简称节点表（简称CLOSED表），其初表），其初始为空表。始为空表。(3)LOOP：若：若OPEN表是空表，则失败退出。表是空表，则失败退出。(4)选择选择OPEN表上的第一个节点，把它从表上的第一个节点，把它从OPEN表移出并放进表移出并放进CLOSED表中。称此节点为节点表中。称此节点为节点n，它是，它是CLOSED表中节点的编
6、号。表中节点的编号。(5)若若n为一目标节点，则有解并成功为一目标节点，则有解并成功退出退出，此解是追踪图，此解是追踪图G中沿着指针中沿着指针从从n到到S这条路径而得到的这条路径而得到的(指针将在第指针将在第7步中设置步中设置)。(6)扩展节点扩展节点n，同时生成不是，同时生成不是n的祖先的那些后继节点的集合的祖先的那些后继节点的集合M。把。把M的的这些成员作为这些成员作为n的后继节点添入图的后继节点添入图G中。中。(7)对那些未曾在对那些未曾在G中出现过的中出现过的(既未曾在既未曾在OPEN表上或表上或CLOSED表上出表上出现过的现过的)M成员成员设置设置一个通向一个通向n的指针。把的指针
7、。把M的这些成员加进的这些成员加进OPEN表。表。对已经在对已经在OPEN或或CLOSED表上的每一个表上的每一个M成员，确定是否需要成员，确定是否需要更改更改通通到到n的指针方向。对已在的指针方向。对已在CLOSED表上的每个表上的每个M成员，确定是否需成员，确定是否需要更改图要更改图G中通向它的每个中通向它的每个后裔后裔节点的指针方向。节点的指针方向。(8)按某一任意方式或按某个探试值，按某一任意方式或按某个探试值，重排重排OPEN表。表。(9)GO LOOP。7图搜索算法中的几个重要名词图搜索算法中的几个重要名词 1 1OPENOPEN表表 2 2CLOSEDCLOSED表表 节点节点父
8、节点父节点编号编号节点节点父节点父节点83 3搜索图与搜索树搜索图与搜索树此过程生成一个明确的图此过程生成一个明确的图G(称为搜索图称为搜索图)和和一个一个G的子集的子集T(称为搜索树称为搜索树)，树，树T上的每个节点上的每个节点也在图也在图G中。搜索树是由第中。搜索树是由第7步中设置的指针来确步中设置的指针来确定的。定的。G中的每个节点中的每个节点(除除S外外)都有一个只指向都有一个只指向G中一个父辈节点的指针，该父辈节点就定为树中中一个父辈节点的指针，该父辈节点就定为树中那个节点的唯一父辈节点。那个节点的唯一父辈节点。910图搜索方法的几点分析：图搜索方法的几点分析：图搜索过程的第图搜索过
9、程的第8步对步对OPEN表上的节点进行表上的节点进行排序排序，以便，以便能够从中选出一个能够从中选出一个“最好最好”的节点作为第的节点作为第4步扩展用。这步扩展用。这种排序可以是种排序可以是任意任意的即盲目的的即盲目的(属于盲目搜索属于盲目搜索)，也可以用，也可以用以后要讨论的各种以后要讨论的各种启发启发思想或其它准则为依据思想或其它准则为依据(属于启发属于启发式搜索式搜索)。每当被选作扩展的节点为目标节点时，这一过。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按
10、指针向点的这条成功路径，其办法是从目标节点按指针向S返回返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终失败告终(某些节点最终可能没有后继节点，所以某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表表可能最后变成空表)。在失败终止的情况下，从起始节。在失败终止的情况下，从起始节点出发，一定达不到目标节点。点出发，一定达不到目标节点。113.2 3.2 盲目搜索盲目搜索盲目搜索：无需重新安排盲目搜索：无需重新安排OPEN表的搜索表的搜索盲目搜索又叫做无信息搜索，一般只适用盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的
11、问题。于求解比较简单的问题。宽度优先搜索宽度优先搜索深度优先搜索深度优先搜索等代价搜索等代价搜索123.2.1 3.2.1 宽度优先搜索宽度优先搜索 回顾上一节的寻找寿命为回顾上一节的寻找寿命为X的人的例子，如果搜的人的例子，如果搜索时，从节点索时，从节点A开始，对他的三个儿子按从左至开始，对他的三个儿子按从左至右搜索，然后对他的所有孙子按从左至右搜索，右搜索，然后对他的所有孙子按从左至右搜索，依此下去。这种搜索方式就是宽度优先搜索。依此下去。这种搜索方式就是宽度优先搜索。宽度优先搜索宽度优先搜索(breadth-first search)的定义：的定义：如果搜索是以如果搜索是以接近接近起始节
12、点的程度依次扩展节点起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索的，那么这种搜索就叫做宽度优先搜索(breadth-first search)，如图，如图3.3所示。所示。13从图可见，这从图可见，这种搜索是种搜索是逐层逐层进行的；在对进行的；在对下一层的任一下一层的任一节点进行搜索节点进行搜索之前，必须搜之前，必须搜索完本层的所索完本层的所有节点。有节点。1415宽度优先搜索算法如下：宽度优先搜索算法如下：(1)把起始节点放到把起始节点放到OPEN表中表中(如果该起始节点为一如果该起始节点为一目标节点，则求得一个解答目标节点，则求得一个解答)。(2)如果如果OPEN是个空表，
13、则没有解，失败退出；否是个空表，则没有解，失败退出；否则继续。则继续。(3)把第一个节点把第一个节点(节点节点n)从从OPEN表移出，并把它放表移出，并把它放入入CLOSED扩展节点表中。扩展节点表中。(4)扩展节点扩展节点n。如果没有后继节点，则转向上述第。如果没有后继节点，则转向上述第(2)步。步。(5)把把n的所有后继节点放到的所有后继节点放到OPEN表的表的末端末端，并提，并提供从这些后继节点回到供从这些后继节点回到n的指针。（队列模式）的指针。（队列模式）(6)如果如果n的任一个后继节点是个目标节点，则找到一的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第个解答，成
14、功退出；否则转向第(2)步。步。1617宽度优先搜索方法分析：宽度优先搜索方法分析：宽度优先搜索是图搜索一般过程的宽度优先搜索是图搜索一般过程的特殊特殊情况，将图搜情况，将图搜索一般过程中的第索一般过程中的第8步具体化为本算法中的第步具体化为本算法中的第6步，这步，这实际是将实际是将OPEN表作为表作为“先进先出先进先出”的队列进行操作。的队列进行操作。宽度优先搜索方法能够保证在搜索树中找到一条通向宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的目标节点的最短途径最短途径；这棵搜索树提供了所有存在的；这棵搜索树提供了所有存在的路径路径(如果没有路径存在，那么对有限图来说，我们就如果没有
15、路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止说该法失败退出；对于无限图来说，则永远不会终止)。18例：把宽度优先搜索应用于八数码难题时所生成例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：目标棋局的问题：搜索树上的所有节点都标记它们所对应的状态描搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序述，每个节点旁边的数字表示节点扩展的顺序(按顺时针方向移动空格按顺时针方向移动空格)。图中最后一个节点是。图中最后一个节点是目标节点。目标节点
16、。19图图 3.5 3.5 八数码难题的宽度优先搜索树八数码难题的宽度优先搜索树 203.2.2 3.2.2 深度优先搜索深度优先搜索另一种盲目另一种盲目(无信息无信息)搜索叫做深度优先搜索搜索叫做深度优先搜索(depth-first search)。首先扩展最新产生的节点。如下图首先扩展最新产生的节点。如下图21图图 3.6 3.6 深度优先搜索示意图深度优先搜索示意图 图3.6深度优先搜索示意图22分析深度优先搜索示意图可看出，在深度优先搜分析深度优先搜索示意图可看出，在深度优先搜索中，我们首先扩展最新产生的索中，我们首先扩展最新产生的(即最深的即最深的)节点。节点。深度相等的节点可以深度
17、相等的节点可以任意任意排列。排列。23我们定义节点的深度如下：我们定义节点的深度如下：(1)起始节点起始节点(即根节点即根节点)的深度为的深度为0。(2)任何其它节点的深度等于其父辈节点深任何其它节点的深度等于其父辈节点深度加上度加上1。首先，扩展最深的节点的结果使得搜索沿着首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个去；只有当搜索到达一个没有后裔没有后裔的状态时，它的状态时，它才考虑另一条替代的路径。替代路径与前面已经才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后
18、试过的路径不同之处仅仅在于改变最后n步，而步，而且保持且保持n尽可能小。尽可能小。24对于许多问题，其状态空间搜索树的深度可能为对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的列的已知深度上限还要深。为了避免考虑太长的路径路径(防止搜索过程沿着无益的路径扩展下去防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度往往给出一个节点扩展的最大深度深度界限深度界限。任何节点如果达到了深度界限，那么都将把它们任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处
19、理。值得说明的是，即使应作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一用了深度界限的规定，所求得的解答路径并不一定就是最短的路径。定就是最短的路径。25含有深度界限的深度优先搜索算法如下：含有深度界限的深度优先搜索算法如下：(1)把起始节点把起始节点S放到未扩展节点放到未扩展节点OPEN表中。表中。如果此节点为一目标节点，则得到一个解。如果此节点为一目标节点，则得到一个解。(2)如果如果OPEN为一空表，则失败退出。为一空表，则失败退出。(3)把第一个节点把第一个节点(节点节点n)从从OPEN表移到表移到CLOSED表。表。(4)如果节点如果节点n的深度等
20、于最大深度，则转向的深度等于最大深度，则转向(2)。(5)扩展节点扩展节点n，产生其全部后裔，并把它们，产生其全部后裔，并把它们放入放入OPEN表的表的前头前头。如果没有后裔，则转向。如果没有后裔，则转向(2)。(6)如果后继节点中有任一个为目标节点，如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向则求得一个解，成功退出；否则，转向(2)。26算法演示图算法演示图 27例：按深度优先搜索生成的八数码难题搜索树，例：按深度优先搜索生成的八数码难题搜索树，我们设置深度界限为我们设置深度界限为5 5。图图3.83.8绘出了搜索树，粗线条的路径表明含绘出了搜索树，粗线条的路径表明含
21、有有5 5条应用规则的一个解。从图可见，深度优先条应用规则的一个解。从图可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界搜索过程是沿着一条路径进行下去，直到深度界限为止，然后再考虑只有最后一步有差别的相同限为止，然后再考虑只有最后一步有差别的相同深度或较浅深度可供选择的路径，接着再考虑最深度或较浅深度可供选择的路径，接着再考虑最后两步有差别的那些路径，等等。后两步有差别的那些路径，等等。28图图 3.8 3.8 八数码难题的深度优先搜索树八数码难题的深度优先搜索树 293.2.3 3.2.3 等代价搜索等代价搜索有些问题并不要求有应用算符序列为最少的解，有些问题并不要求有应用算符序列为
22、最少的解，而是要求具有某些特性的解。搜索树中每条连接而是要求具有某些特性的解。搜索树中每条连接弧线上的有关代价以及随之而求得的具有最小代弧线上的有关代价以及随之而求得的具有最小代价的解答路径，与许多这样的广义准则相符合。价的解答路径，与许多这样的广义准则相符合。宽度优先搜索可被推广用来解决这种寻找从起始宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做种推广了的宽度优先搜索算法叫做等代价搜索算等代价搜索算法。法。30有如下一些记号：有如下一些记号：起始节点记为起始节点记为S；从节点从节点i
23、到它的后继节点到它的后继节点j的连接弧线代价记的连接弧线代价记为为c(i,j)；从起始节点从起始节点S到任一节点到任一节点i的路径代价记为的路径代价记为g(i)。在搜索树上，我们假设在搜索树上，我们假设g(i)也是从起始节点也是从起始节点S到节到节点点i的的最少代价最少代价路径上的代价，因为它是唯一的路路径上的代价，因为它是唯一的路径；径；31等代价搜索算法等代价搜索算法等代价搜索方法以等代价搜索方法以g(i)的递增顺序扩展其节点，其算法：的递增顺序扩展其节点，其算法：(1)把起始节点把起始节点S放到未扩展节点表放到未扩展节点表OPEN中。如果此中。如果此起始节点为一目标节点，则求得一个解起始
24、节点为一目标节点，则求得一个解;否则令否则令g(S)=0。(2)如果如果OPEN是个空表，则没有解而失败退出。是个空表，则没有解而失败退出。(3)从从OPEN表中选择一个节点表中选择一个节点i，使其，使其g(i)为最小。为最小。如果有几个节点都合格，那么就要选择一个目标节点作为如果有几个节点都合格，那么就要选择一个目标节点作为节点节点i(要是有目标节点的话要是有目标节点的话)；否则，就从中选一个作为节；否则，就从中选一个作为节点点i。把节点。把节点i从从OPEN表移至扩展节点表表移至扩展节点表CLOSED中。中。(4)如果节点如果节点i为目标节点，则求得一个解。为目标节点，则求得一个解。(5)
25、扩展节点扩展节点i。如果没有后继节点，则转向第。如果没有后继节点，则转向第(2)步。步。(6)对于节点对于节点i的每个后继节点的每个后继节点j，计算，计算g(j)=g(i)+c(i,j)，并把所有后继节点，并把所有后继节点j放进放进OPEN表。提供回到节点表。提供回到节点i的指的指针。针。(7)转向第转向第(2)步。步。32图图 3.9 3.9 等代价搜索算法框图等代价搜索算法框图 333.3 3.3 启发式搜索启发式搜索 盲目搜索的不足：效率低，耗费过多的计算空间盲目搜索的不足：效率低，耗费过多的计算空间与时间与时间 分析前面介绍的宽度优先、深度优先搜索，分析前面介绍的宽度优先、深度优先搜索
26、，或等代价搜索算法或等代价搜索算法,其主要的差别是其主要的差别是OPEN表中待表中待扩展节点的顺序问题。人们就试图找到一种方法扩展节点的顺序问题。人们就试图找到一种方法用于排列待扩展节点的顺序，即选择用于排列待扩展节点的顺序，即选择最有希望最有希望的的节点加以扩展，那么，搜索效率将会大为提高。节点加以扩展，那么，搜索效率将会大为提高。启发信息启发信息：进行搜索技术一般需要某些有关：进行搜索技术一般需要某些有关具体问题领域具体问题领域的特性的，与具体问题求解过程有的特性的，与具体问题求解过程有关的，并可关的，并可指导指导搜索过程朝着最有希望方向前进搜索过程朝着最有希望方向前进的控制信息，把此种信
27、息叫做的控制信息，把此种信息叫做启发信息启发信息。把利用启发信息的搜索方法叫做把利用启发信息的搜索方法叫做启发性搜索方法启发性搜索方法343.3.1 3.3.1 启发式搜索策略启发式搜索策略启发信息按其用途可分为下列启发信息按其用途可分为下列3种：种：(1)用于决定用于决定要扩展要扩展的下一个节点，以免像在宽度优的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。先或深度优先搜索中那样盲目地扩展。(2)在扩展一个节点的过程中，用于决定要在扩展一个节点的过程中，用于决定要生成生成哪一哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节个或哪几个后继节点，以免盲目地同时生成所有可能的节
28、点。点。(3)用于决定某些应该从搜索树中用于决定某些应该从搜索树中抛弃抛弃或修剪的节点。或修剪的节点。在本节中，只讨论利用上述第一种启发信息的状态空在本节中，只讨论利用上述第一种启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。这种搜间搜索算法，即决定哪个是下一步要扩展的节点。这种搜索总是选择索总是选择“最有希望最有希望”的节点作为下一个被扩展的节点。的节点作为下一个被扩展的节点。这种搜索叫做这种搜索叫做有序搜索有序搜索(ordered search)。353.3.2 3.3.2 估价函数估价函数用来估算节点希望程度的量度，叫做用来估算节点希望程度的量度，叫做估价函数估价函数(eva
29、luation function)。估价函数的任务就是估计估价函数的任务就是估计OPEN表中各节点的重要程度。表中各节点的重要程度。一个节点的一个节点的“希望希望”(promise)有几种不同的定义方法。有几种不同的定义方法。在状态空间问题中，在状态空间问题中，一种方法一种方法是估算目标节点到此节点的是估算目标节点到此节点的距离；距离；另一种方法另一种方法认为，解答路径包括被估价过的节点，认为，解答路径包括被估价过的节点，并计算全条路径的长度或难度。每个不同的衡量标准只能并计算全条路径的长度或难度。每个不同的衡量标准只能考虑该问题中这个节点的某些决定性特性，或者对给定节考虑该问题中这个节点的某
30、些决定性特性，或者对给定节点与目标节点进行比较，以决定相关特性。点与目标节点进行比较，以决定相关特性。我们用符号我们用符号f来标记估价函数，用来标记估价函数，用f(n)表示节点表示节点n的估的估价函数值。暂时令价函数值。暂时令f为任意函数，为任意函数，以后我们将会提出以后我们将会提出f是从是从起始节点约束地通过节点起始节点约束地通过节点n而到达目标节点的最小代价路而到达目标节点的最小代价路径上的一个估算代价。径上的一个估算代价。一般形式：一般形式：f(n)=g(n)+h(n)，g(n)是从是从s0到到n的实际代价，的实际代价，h(n)是从节点是从节点n到目标节点到目标节点sg的估计代价。的估计
31、代价。363.3.3 3.3.3 有序搜索有序搜索 我们用估价函数我们用估价函数f来排列来排列GRAPHSEARCH第第8步中步中OPEN表上的节点。根据习惯，表上的节点。根据习惯，OPEN表上的节点按照它们表上的节点按照它们f函数函数值的递增顺序排列。根据推测，某个具有低的估价值的节值的递增顺序排列。根据推测，某个具有低的估价值的节点较有可能处在最佳路径上。应用某个算法点较有可能处在最佳路径上。应用某个算法(例如等代价例如等代价算法算法)选择选择OPEN表上具有最小表上具有最小f值的节点作为下一个要扩值的节点作为下一个要扩展的节点。这种搜索方法叫做展的节点。这种搜索方法叫做有序搜索有序搜索或
32、或最佳优先搜索最佳优先搜索，而其算法就叫做而其算法就叫做有序搜索算法有序搜索算法或或最佳优先算法最佳优先算法。可见它总。可见它总是选择最有希望的节点作为下一个要扩展的节点。是选择最有希望的节点作为下一个要扩展的节点。有序搜索有序搜索(ordered search)又称为又称为最好优先搜索最好优先搜索(best-first search)。尼尔逊（尼尔逊（Nilsson）曾提出一个有序搜索的基本算法。估价）曾提出一个有序搜索的基本算法。估价函数函数f是这样确定的：一个节点希望程度越大，其是这样确定的：一个节点希望程度越大，其f值就越值就越小。被选为扩展的节点，是估价函数最小的节点。小。被选为扩展
33、的节点，是估价函数最小的节点。37有序状态空间搜索算法如下：有序状态空间搜索算法如下：(1)把起始节点把起始节点S放到放到OPEN表中，计算表中，计算f(S)并把其值与节点并把其值与节点S联系起来。联系起来。(2)如果如果OPEN是个空表，则失败退出，无解。是个空表，则失败退出，无解。(3)从从OPEN表中选择一个表中选择一个f值最小的节点值最小的节点i。结果有几个节点。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点否则就选择其中任一个节点作为节点i。(4)把节点把节点i从从OPEN表中移出，并
34、把它放入表中移出，并把它放入CLOSED的扩展的扩展节点表中。节点表中。(5)如果如果i是个目标节点，则成功退出，求得一个解。是个目标节点，则成功退出，求得一个解。38(6)扩展节点扩展节点i，生成其全部后继节点。对于，生成其全部后继节点。对于i的每一个后继的每一个后继节点节点j：(a)计算计算f(j)。(b)如果如果j既不在既不在OPEN表中，又不在表中，又不在CLOSED表中，则用估价函表中，则用估价函数数f把它添入把它添入OPEN表。从表。从j加一指向其父辈节点加一指向其父辈节点i的指针，以便一的指针，以便一旦找到目标节点时记住一个解答路径。旦找到目标节点时记住一个解答路径。(c)如果如
35、果j已在已在OPEN表上或表上或CLOSED表上，则比较刚刚对表上，则比较刚刚对j计算计算过的过的f值和前面计算过的该节点在表中的值和前面计算过的该节点在表中的f值。如果值。如果新的新的f值较小值较小，则则(i)以此新值取代旧值。以此新值取代旧值。(ii)从从j指向指向i，而不是指向它的父辈节点。，而不是指向它的父辈节点。(iii)如果节点如果节点j在在CLOSED表中，则把它移回表中，则把它移回OPEN表表(7)转向转向(2)，即，即GO TO(2)。39注：注：步骤（步骤（6.c）是一般搜索图所需要的，该图中可能有一）是一般搜索图所需要的，该图中可能有一个以上的父辈节点。具有最小估价函数个
36、以上的父辈节点。具有最小估价函数f（j）的节点被）的节点被选作父辈节点。但是，由于搜索树，它最多只有一个选作父辈节点。但是，由于搜索树，它最多只有一个父辈节点，所以步骤（父辈节点，所以步骤（6.c）可以略去。值得提出的是，）可以略去。值得提出的是，即使搜索空间是一般的搜索图，其显示子搜索图总是即使搜索空间是一般的搜索图，其显示子搜索图总是一棵树，因为节点一棵树，因为节点j从来没有同时记录过一个以上的父从来没有同时记录过一个以上的父辈节点。辈节点。40图图3 310 10 有序搜索算法框图有序搜索算法框图 41宽度优先搜索、深度优先搜索和等代价搜索统统宽度优先搜索、深度优先搜索和等代价搜索统统是
37、有序搜索技术的特例。对于宽度优先搜索，我是有序搜索技术的特例。对于宽度优先搜索，我们选择们选择f(i)作为节点作为节点i的深度。对于等代价搜索，的深度。对于等代价搜索，f(i)是从起始节点至节点是从起始节点至节点i这段路径的代价。这段路径的代价。有序搜索的有效性直接有序搜索的有效性直接取决于取决于f的选择的选择，如果，如果选择的选择的f不合适，有序搜索就可能失去一个最好的不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量解甚至全部的解。如果没有适用的准确的希望量度，那么度，那么f的选择将涉及两个方面的内容：一方面的选择将涉及两个方面的内容：一方面是一个时间和空间之间
38、的折衷方案；另一方面是是一个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。保证有一个最优的解或任意解。42根据解答类型选择估价函数根据解答类型选择估价函数1.解空间中存在几个不同代价的解题路径解空间中存在几个不同代价的解题路径2.虽然存在几条路径，但是搜索的代价超过虽然存在几条路径，但是搜索的代价超过时空限制，为此要找最佳（和最优差异程时空限制，为此要找最佳（和最优差异程度比较小）度比较小）3.不考虑解答的最优化，或许仅仅存在一个不考虑解答的最优化，或许仅仅存在一个答案，或所有解等价答案，或所有解等价43有序搜索例子有序搜索例子下面让我们再次用八数码难题的例子来说明过程下面让
39、我们再次用八数码难题的例子来说明过程GRAPHSEARCH是如何应用估价函数排列节点是如何应用估价函数排列节点的。举例说明如下：的。举例说明如下：我们采用了简单的估价函数我们采用了简单的估价函数 f(n)=d(n)+W(n)其中：其中：d(n)是搜索树中节点是搜索树中节点n的深度；的深度；W(n)用用来计算对应于节点来计算对应于节点n的数据库中错放的棋子个数。的数据库中错放的棋子个数。44因此，起始节点棋局因此，起始节点棋局2 8 31 6 47 5的的f值等于值等于0+4=4。45八数码难题的有序搜索树八数码难题的有序搜索树图中表示出利用这个估价图中表示出利用这个估价函数把函数把GRAPHS
40、EARCH应用于八数码难题的结果。应用于八数码难题的结果。图中圆圈内的数字表示该图中圆圈内的数字表示该节点的节点的f值。值。46从图可见，这里所求得的解答路径和用其它搜索从图可见，这里所求得的解答路径和用其它搜索方法找到的解答路径相同。不过，估价函数的应方法找到的解答路径相同。不过，估价函数的应用用显著地减少显著地减少了被扩展的节点数了被扩展的节点数(如果我们只用如果我们只用估价函数估价函数f(n)=d(n)，那么我们就得到宽度优先搜，那么我们就得到宽度优先搜索过程索过程)。正确地选择估价函数对确定搜索结果具有决定性正确地选择估价函数对确定搜索结果具有决定性的作用。使用不能识别某些节点真实希望
41、的估价的作用。使用不能识别某些节点真实希望的估价函数会形成函数会形成非非最小代价路径；而使用一个过多地最小代价路径；而使用一个过多地估计了全部节点希望的估价函数估计了全部节点希望的估价函数(就像宽度优先就像宽度优先搜索方法得到的估价函数一样搜索方法得到的估价函数一样)又会扩展又会扩展过多过多的的节点节点473.3.4 A3.3.4 A*算法算法A*算法的估价函数：算法的估价函数：让我们描述一个特别的估价函数，这个估价函让我们描述一个特别的估价函数，这个估价函数数f使得在使得在任意节点任意节点上其函数值上其函数值f(n)能能估算估算出从节出从节点点S到节点到节点n的最小代价路径的代价与从节点的最
42、小代价路径的代价与从节点n到到某一目标节点的最小代价路径的代价之总和，也某一目标节点的最小代价路径的代价之总和，也就是说就是说f(n)是约束是约束通过节点通过节点n的一条的一条最小代价最小代价路径路径的代价的一个估计。因此，的代价的一个估计。因此，OPEN表上具有最小表上具有最小f值的那个节点就是所估计的加有最少严格约束条值的那个节点就是所估计的加有最少严格约束条件的节点，而且下一步要扩展这个节点是合适的。件的节点，而且下一步要扩展这个节点是合适的。48在正式讨论在正式讨论A*算法之前，先介绍几个记号。令算法之前，先介绍几个记号。令k(ni，nj)表示任意两个节点表示任意两个节点ni和和nj之
43、间最小代价路之间最小代价路径的径的实际代价实际代价(对于两节点间没有通路的节点，对于两节点间没有通路的节点，函数函数k没有定义没有定义)。于是，从节点。于是，从节点n到某个具体的到某个具体的目标节点目标节点ti，某一条最小代价路径的代价可由，某一条最小代价路径的代价可由k(n,ti)给出。给出。令令h*(n)表示整个目标节点表示整个目标节点集合集合ti上所有上所有k(n,ti)中最小的一个，因此，中最小的一个，因此，h*(n)就是从就是从n到目到目标节点最小代价路径的代价，而且从标节点最小代价路径的代价，而且从n到目标节到目标节点能够获得点能够获得h*(n)的任一路径就是一条从的任一路径就是一
44、条从n到某个到某个目标节点的最佳路径目标节点的最佳路径(对于任何不能到达目标节对于任何不能到达目标节点的节点点的节点n，函数，函数h*没有定义没有定义)。49通常我们感兴趣的是想知道从已知起始节点通常我们感兴趣的是想知道从已知起始节点S到到任意节点任意节点n的一条最佳路径的代价的一条最佳路径的代价k(S,n)。为此，。为此，引进一个新函数引进一个新函数g*，这将使我们的记号得到某些，这将使我们的记号得到某些简化简化。对所有从。对所有从S开始可达到开始可达到n的路径来说，函数的路径来说，函数g*定义为定义为g*(n)=k(S,n)其次，我们定义函数其次，我们定义函数f*，使得在任一节点，使得在任
45、一节点n上其函上其函数值数值f*(n)就是从节点就是从节点S到节点到节点n的一条最佳路径的的一条最佳路径的实际代价实际代价加上从节点加上从节点n到某目标节点的一条到某目标节点的一条最佳最佳路径的代价之和，即路径的代价之和，即 f*(n)=g*(n)+h*(n)50因而因而f*(n)值就是从值就是从S开始约束通过节点开始约束通过节点n的一条最佳路径的一条最佳路径的代价，而的代价，而f*(S)=h*(S)是一条从是一条从S到某个目标节点中间无到某个目标节点中间无约束的一条最佳路径的代价。约束的一条最佳路径的代价。我们希望估价函数我们希望估价函数f是是f*的一个估计，此估计可由下式给的一个估计，此估
46、计可由下式给出：出：f(n)=g(n)+h(n)其中：其中：g是是g*的估计；的估计；h是是h*的估计。的估计。对于对于g(n)来说，一个明显的选择就是搜索树中从来说，一个明显的选择就是搜索树中从S到到n这段路这段路径的代价，这一代价可以由从径的代价，这一代价可以由从n到到S寻找指针时，把所遇寻找指针时，把所遇到的各段弧线的代价加起来给出到的各段弧线的代价加起来给出(这条路径就是到目前为这条路径就是到目前为止用搜索算法找到的从止用搜索算法找到的从S到到n的最小代价路径的最小代价路径)。这个定义。这个定义包含了包含了g(n)g*(n)。对于对于h*(n)的估计的估计h(n)，它依赖于有关问题的领
47、域的启发信息。，它依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数这种信息可能与八数码难题中的函数W(n)所用的那种信所用的那种信息相似。我们把息相似。我们把h叫做叫做启发函数启发函数。51A A算法和算法和A*A*算法的定义算法的定义 定义定义1 在在GRAPHSEARCH过程中，如果第过程中，如果第8步的步的重排重排OPEN表是依据表是依据f(x)=g(x)+h(x)进行的，则称该过程为进行的，则称该过程为A算法算法定义定义2 在在A算法中，如果对所有的算法中，如果对所有的x，h(x)h*(x)成立成立,则称则称h(x)为为h*(x)的下界，它表示某种偏于保守的估计。的下界
48、，它表示某种偏于保守的估计。定义定义3 采用采用h*(x)的下界的下界h(x)为启发函数的为启发函数的A算法，称为算法，称为A*算算法。当法。当h=0时，时，A*算法就变为有序搜索算法。算法就变为有序搜索算法。A*算法是一种有序搜索算法，其特点在于对估价函数的算法是一种有序搜索算法，其特点在于对估价函数的定义定义上。对于一般的有序搜索，总是选择上。对于一般的有序搜索，总是选择f值最小的节点作值最小的节点作为扩展节点。因此，为扩展节点。因此，f是根据需要找到一条最小代价路径的是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点观点来估算节点的，所以，可考虑每个节点n的估价函数值
49、的估价函数值为两个分量：从起始节点到节点为两个分量：从起始节点到节点n的代价以及从节点的代价以及从节点n到达到达目标节点的代价。目标节点的代价。52A*算法算法(1)把把S放入放入OPEN表，记表，记f=h，令，令CLOSED为空表。为空表。(2)重复下列过程，直至找到目标节点止。若重复下列过程，直至找到目标节点止。若OPEN为为空表，则宣告失败。空表，则宣告失败。(3)选取选取OPEN表中未设置过的具有最小表中未设置过的具有最小f值的节点为最值的节点为最佳节点佳节点BESTNODE，并把它放入，并把它放入CLOSED表。表。(4)若若BESTNODE为一目标节点，则成功求得一解。为一目标节点
50、，则成功求得一解。(5)若若BESTNODE不是目标节点，则扩展之，产生后不是目标节点，则扩展之，产生后继节点继节点SUCCSSOR。53(6)对每个对每个SUCCSSOR进行下列过程：进行下列过程：(a)建立从建立从SUCCSSOR返回返回BESTNODE的指针。的指针。(b)计算计算g(SUC)=g(BES)+g(BES,SUC)。(c)如果如果SUCCSSOROPEN，则称此节点为，则称此节点为OLD，并把它添至，并把它添至BESTNODE的后继节点表中。的后继节点表中。(d)比较新旧路径代价。如果比较新旧路径代价。如果g(SUC)g(OLD),则则重新确定重新确定OLD的父辈节点为的父