第四章一般搜索原理优秀PPT.ppt

《第四章一般搜索原理优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第四章一般搜索原理优秀PPT.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章一般搜索原理第一页，本课件共有51页一般搜索原理一般搜索原理 n前面研究的知识表示方法是问题求解所必需的。前面研究的知识表示方法是问题求解所必需的。表示问题是为了进一步解决问题。从问题表示到表示问题是为了进一步解决问题。从问题表示到问题的解决，有个求解的过程。也就是搜索过程。问题的解决，有个求解的过程。也就是搜索过程。在这一过程中，采用适当的搜索技术，包括各种在这一过程中，采用适当的搜索技术，包括各种规则、过程和算法等推理技术，力求找到问题的规则、过程和算法等推理技术，力求找到问题的解答。本章讨论一些早期的搜索技术或用于解决解答。本章讨论一些早期的搜索技术或用于解决比较简单问题的搜索原理

2、。比较简单问题的搜索原理。第二页，本课件共有51页n 从本节起，我们将要研究如何通过网络寻找路径，进而求解问题。我们还将学习宽度优先搜索和深度优先搜索，它们均属于盲目搜索方法。盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。n1.一般搜索过程n 对于一个具体问题，如如何生成它所需要的部分状态空间从而实现对问题的求解呢？在人工智能中是通过运用搜索技术来解决这一问题的。n 其基本思想是：首先把问题的初始状态（即初始节点）作为当前状态，选择适用的算符对其进行操作，生成一组子状态（或称为后继状态，后继节点，子节点），然后检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若不出现

3、，则按某种搜索策略从已生成的状态中再选出一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。盲目搜索盲目搜索第三页，本课件共有51页解；若不出现，则按某种搜索策略从已生成的状态中再选出一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。下面列出状态空间的一般搜索过程。搜索过程中要用到两个数据结构(OPEN表与CLOSED表)。OPEN表用于存放刚生成的节点。CLOSED表用于存放将要扩展或者已扩展的节点。(所谓对一个节点进行“扩展”是指：用合适的算符对该节点进行操作，生成一组子节点。)第五页，本课件共有51页第六页，本

4、课件共有51页搜索的一般过程如下：(1)把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G。(2)检查OPEN表是否为空，若为空则问题无解，退出。(3)把OPEN表的第一个节点取出放入CLOSED表，并记该节点为节点n。(4)考察节点n是否为目标节点。若是，则求得了问题的解，退出。(5)扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中。(6)针对M中子节点的不同情况，分别进行如下处理：对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表。对于那些先前已在G中出现过的M成员，确定是

5、否需要修改它指向父节点的指针。第七页，本课件共有51页 对于那些先前已在G中出现并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。(7)按某种搜索策略对OPEN表中的节点进行排序 (8)转第(2)步。说明:(1)上述过程是状态空间的一般搜索过程，具有通用性，在此之后讨论的各种搜索策略都可以看作它的一个特例。各种搜索策略的主要区别是对OPEN表中节点排序的准则不同。例如：宽度优先搜索则把后生成的子节点排在前面。(2)一个节点经一个算符操作后一般只生成一个子节点，但适用于一个节点的算符可能有多个，此时就会生成一组子节点。在这些子节点中可能有些是当前扩展节点(即节点n)的父节点，祖父

6、节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。余下的子节点记为集合M，并加入圈G中。这就是第(5)步要说明的意思。第八页，本课件共有51页 (3)一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为被生成，当前又作为另一个节点的后继节点被再次生成。此时，它究竟应作为哪个节点的后继节点呢？一般由原始节点到该节点路径上所付出的代价来决定，哪条路径付出的代价最下，相应当节点就作为它的父节点。这就是搜索过程第(6)步所阐述的内容。由于盲目搜索仅适用于其状态空间是树状结构的问题，因此对盲目搜索而言，不会出现一般搜索过程第(6)步中两点的问题，每个节点经扩展后生成的子节点都是第一次出

7、现的节点，不必检查并修改指针方向。(4)通过搜索所得到的图称为搜索图，由搜索图中的所有节点及反向指针(在第(6)步形成的指向父节点的指针)所构成的集合是一颗树，称为搜索树。第九页，本课件共有51页 (5)在搜索过程中，一旦某个被考虑的节点是目标节点(第(4)步)就得到一个解。该解是由从初始节点到该目标节点上的算符构成的，而路径由第(6)步形成的反向指针指定。(6)如果在搜索中一直找不到目标节点，而且OPEN表中不再有可供扩展的节点，则搜索失败，在第(2)步退出。上述搜索过程可以看出，问题的求解过程实际上就是搜索过程，问题求解状态空间图是通过搜索逐步形成的，边搜索边形成，而且搜索每前进一步，就要

8、检查一下是否到达了目标状态，这样就可能尽量少生成与问题求解无关的状态，既节省了存储空间，又提高了求解效率。第十页，本课件共有51页2.2.宽度优先搜索宽度优先搜索 如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索 (breadth-first search)。基本思想：从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。OPEN表中的节点总是按进入的先后顺序排序列，先进入的节点排在前面，后进入的排在后面。其搜索过程如下：(1)把起始节点S0放到OPEN表中。(2)如果OPEN是个空表，则

9、问题没有解，退出，否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED表。第十一页，本课件共有51页(4)扩展节点n是否为目标节点。若是，则求得了问题的解退出。(5)若节点n不可扩展，则转第(2)步。(6)扩展节点n，将其子节点放入OPEN表的尾部，并为每个子节点都配置指向父节点的指针，然后转第(2)。第十二页，本课件共有51页宽度优先搜索流程第十三页，本课件共有51页 这一算法假定起始节点本身不是目标节点。要检验起始节点是目标节点的可能性，只要在第(1)步的未了，加上一句“如果起始节点为一目标节点，则求得一个解答”即可做到，正如第(1)步括号内所写的。这个过程产生的

10、节点和指针构成一棵隐式定义的状态空间树的子树我们称它为搜索树。显而易见宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止)。图3.4绘出把宽度优先搜索应用于八数码难题时所生成的搜索树。这个问题就是要把初始棋局变为如下目标棋局的问题：第十五页，本课件共有51页1 2 38 47 6 5 搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序(按顺时针方向移动空格)。图3.4中的第27个节点是目标节点。第十六页，本课件共有51页第十七页

11、，本课件共有51页例：设有三个大小不等的圆盘A,B,C套在一根轴上，每个圆盘上都有数字1,2,3,4,并且每个圆盘都可独立地绕轴做逆时针转动，每次转动90度，其初始状态S0和目标状态S9如图所示，用广度优先所所思求出从S0到S9的路径。第十八页，本课件共有51页3.深度优先搜索 基本思想：从初始节点S0开始选择一个节点进行考察，若不是目标节点，则再在该节点的子节点选择一个节点进行考察，一直如此向下搜索。当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其它节点进行考察。深度优先搜索与宽度优先搜索唯一区别：宽度优先搜索是将节点n的子节点放入OPEN表的尾部，而深度优先搜索是把节点

12、n的子节点放入OPEN表的首部。仅次一点不同，就使得搜索的路径完全不一样。在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。第十九页，本课件共有51页第二十页，本课件共有51页n在深度优先搜索中，在深度优先搜索中，n我们首先扩展最新产生的我们首先扩展最新产生的(即最深的即最深的)节点，节点，深度相等的节点可以任意排列。深度相等的节点可以任意排列。n我们定义节点的深度如下；我们定义节点的深度如下；n

13、(1)起始节点起始节点(即根节点即根节点)的深度为的深度为0。n (2)任何其它节点的深度等于其父辈节点任何其它节点的深度等于其父辈节点n深度加上深度加上1。第二十一页，本课件共有51页为了解决深度优先搜索不完备的问题，避免搜索过程陷入无穷分支的死循环，提出了有界深度优先搜索方法。有界深度优先搜索的基本思想：对深度优先搜索引入搜索深度的界限(设为dm)，当搜索深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行搜索。如果问题有解，且其路径长度dm，则上述搜索过程一定能求得解。但是，若解的路径长度dm，则搜索过程就得不到解。这说明在有界深度优先搜索中，深度界限的选择是很重要的。但这并不是说

14、深度界限越大越好，因为当dm太大时，搜索时将会产生许多无用的子节点，既浪费计算机的存储空间与时间，又降低了搜索效率。第二十二页，本课件共有51页n含有深度界限的深度优先搜索算法如下：含有深度界限的深度优先搜索算法如下：n (1)把起始节点把起始节点S放到末扩展节点放到末扩展节点OPEN表中。如果此节表中。如果此节点为一个目标节点，则得到一个解。点为一个目标节点，则得到一个解。n (2)如果如果OPEN为一空表，则失败退出。为一空表，则失败退出。n (3)把第一个节点把第一个节点(节点节点n)从从OPEN表移到表移到CLOSED表。表。n (4)如果节点如果节点n的深度等于最大深度，则转向的深度

15、等于最大深度，则转向(2)。n (5)扩展节点扩展节点n，产生其全部后裔，并把它们故入，产生其全部后裔，并把它们故入OPEN表的前头。如果没有后裔，表的前头。如果没有后裔，Rn转向转向(2)。n(6)如果后继节点中有任一个为目标节点则求得一个解，成如果后继节点中有任一个为目标节点则求得一个解，成功退出；否则，转向功退出；否则，转向(2)。n有界深度优先搜索算法的程序框图见图有界深度优先搜索算法的程序框图见图 第二十三页，本课件共有51页第二十四页，本课件共有51页 由于解的路径长度事先难预测，所以要恰当地给出dm的值是比较困难的。另外，即使能求出解，它也一定是最优解。为此，可采用下述方法进行改

16、进：先任意给定一个较小的数作为dm，然后进行上述的有界深度优先搜索，当搜索达到了指定的深度界限dm仍未发现目标节点，并且CLOSED表中仍有待扩展节点时，就将这些节点送回OPEN表，同时增大深度界限dm，继续向下搜索。如此不断增大dm，只要问题有解，就一定可以找到它。但是此时找到的解不一定是最优解。为找到最优解，可增设一个表(R)，每找到一个目标节点后，就把它放入到R的前面，并令dm等于该目标节点所对应的路径长度，然后继续搜索。由于后求得的解的路径长度不会超过先求得的解的路径长度，所以最后求得的解一定是最优解。第二十五页，本课件共有51页第二十六页，本课件共有51页下面绘出按深度优先搜索生成的

17、八数码难题搜索树，下面绘出按深度优先搜索生成的八数码难题搜索树，其中，我们设置深度界限为其中，我们设置深度界限为5。粗线条的路径表明含有。粗线条的路径表明含有5条应用规则的一个解。从图可见，深度优先搜索过程条应用规则的一个解。从图可见，深度优先搜索过程是沿着一条路径进行下去，宜到深度界限为止，然后是沿着一条路径进行下去，宜到深度界限为止，然后再考虑只有最后一步有差别的相同深度或较浅深度可再考虑只有最后一步有差别的相同深度或较浅深度可供选择的路径，接着再考虑最后两步有差别的那些路供选择的路径，接着再考虑最后两步有差别的那些路径，等等。径，等等。第二十七页，本课件共有51页第二十八页，本课件共有5

18、1页4.等代价搜索(推广的宽度优先搜索)有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解。搜索树中每条连接弧线上的有关代价以及随之而求得的具有员小代价的解答路径，与许多这样的广义准则相符合。宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法；如果所有的连接弧线具有相等的代价，那么等代价算法就简化为宽度优先搜索算法。在等代价搜索算法中，不是描述沿着等长度路径断层进行的扩展，而是描述沿着等代价路径断层进行的扩展。在等代价搜索算法中，我们把从节点i到它的后继节点j的连接弧线代价记为c(i,j)，把从起始节

19、点S到任一节点i的路径代价记为g(i)。在搜索树上，我们假设g(t)也是从起始节点S到节点i的最少代价路径上的代价，因为它是唯一的路径*等代价搜索方法以g(i)的递增顺序扩展其 第二十九页，本课件共有51页其节点，其节点，其算法如下；其算法如下；(1)把把起起始始节节点点S放放到到末末扩扩展展节节点点表表OPEN中中。如如果果此此起起始节点为一目标节点则求得一个解。否则令始节点为一目标节点则求得一个解。否则令g(S)0。(2)如果如果OPEN是个空表，则没有解而失败退出。是个空表，则没有解而失败退出。(3)从从OPEN表表中中选选择择一一个个节节点点i，使使其其g(i)为为最最小小。如如果果有

20、有几几个个节节点点都都合合格格，那那么么就就要要选选择择一一个个目目标标节节点点作作为为节节点点i(要要是是有有目目标标节节点点的的话话)6否否则则就就从从中中选选一一个个作作为为节节点点。把把节点节点i从从OPEN表表移至扩展节点表移至扩展节点表CLOSED中。中。(4)如果节点如果节点i为目标节点，则求得一个解。为目标节点，则求得一个解。(5)扩展节点扩展节点i。如果没有后继节点，则转向第。如果没有后继节点，则转向第(2)步。步。(6)对对于于节节点点i的的每每个个后后继继节节点点j，计计算算g(5)g(i)十十c(i，j)，并把所有后继节点并把所有后继节点j放进放进OPEN表表。提供回到

21、节点。提供回到节点i的指针。的指针。(7)转向第转向第(2)步。步。等代价搜索算法框图如图等代价搜索算法框图如图3.8所示。所示。第三十页，本课件共有51页第三十一页，本课件共有51页例：五城市间的交通路线如图所示，例：五城市间的交通路线如图所示，A A城市是出发地，城市是出发地，E E城城市是目的地，两城市间的交通费用（代价）如图所示。求从市是目的地，两城市间的交通费用（代价）如图所示。求从A A到到E E的最小费用交通路线。的最小费用交通路线。第三十二页，本课件共有51页最优解AC1D1E2 代价为8路线：ACDE 第三十三页，本课件共有51页3.2 启发式搜索启发式搜索1.启发式搜索策略

22、 深度和宽度优先搜索法都是属于盲目搜索法，各子节点在OPEN中的次序是由搜索方法本身所确定的，没有利用各子节点状态信息或问题有关信息作引导，因而是盲目的，产生的无用节点较多，搜索空间较大，效率不高。对于复杂的问题求解系统，不仅显示出搜索效率降低，而且“组合爆炸”问题突出。例如一棵树，每个子节点有35个后继节点，共有100层，则总计有35100个节点，若计算每个节点用1毫秒，则需要10138年。因而在问题求解中引入与问题求解有关的启发式信息，对搜索效率和求解质量都是极为必要和有益的，为此，利用启发式信息引导搜索路径的方法称为启发式搜索法。可有三种基本启发式信息搜索策略来：第三十四页，本课件共有5

23、1页(1)节点选择：根据启发式信息决定要扩展的下一个节点（最有希望的节点）(2)操作选择：控制下层子节点产生，以避免盲目地同时生成所有可能的节点。(3)剪枝技术：在图搜索中对某些节点从图中剪去。在本节中，我们只讨论利用上述第一种启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。这种搜索叫做有序搜索(ordered search)。一个节点的“希望”(promise)有几种不同的定义方法。在状态空间问题中，一种方法是估算目标节点到此节点的距离；另一种方法认为，解答路径包括被估价过的节点，并计算全条路径的长度或难度。每个不同的衡量

24、标准只能考虑该问题中这个节点的某些决定性特性，或者对给定节点与目标节点进行比较，以决定相关特性。在所有这些情况下，用来估算节点希望程度的量度叫做估价函数。第三十五页，本课件共有51页2.估价函数 用来估算节点希望程度的量度，叫做估价函数。用符号f表示，用f(n)表示节点你的估价函数值。3.有序搜索(最好优先搜索)选择最有希望的节点作为下一个要扩展的节点。尼尔逊曾提出一个有序搜索的基本算法：估价函数f是这样确定的：一个节点的希望程度越大，其f值就越小。被选为扩展的节点是估价函数最小的节点。算法如下：(1)把起始节点S放到OPEN表中，计算f(s)，并把其值与节点S联系起来。(2)如果OPEN是个

25、空表，则失败退出。(3)从0PEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。第三十六页，本课件共有51页 (4)(4)把把节节点点i i从从OPENOPEN表表中中移移出出，井井把把它它放放入入CLOSEDCLOSED的的扩扩展展 节点表中。节点表中。(5)(5)如果如果6 6是个目标节点，则成功退出，求得一个解。是个目标节点，则成功退出，求得一个解。(6)(6)扩扩展展节节点点i i，生生成成其其全全部部后后继继节节点点。对对于于i i的的每每一一个个后后继继节点节点j j：(a)(a)计算计算f(j)f

26、(j)。(b)(b)如如果果j j既既不不在在0PEN0PEN表表中中，又又不不在在CLOSEDCLOSED表表中中，则则用用估估价价函函数数f f把把它它添添入入OPENOPEN表表。从从j j加加一一指指向向其其父父辈辈节节点点i i的的指指针针，以便一旦找到目标节点时记住一个解答路径。以便一旦找到目标节点时记住一个解答路径。(c)(c)如如果果j j已已在在OPENOPEN表表上上或或CLOSEDCLOSED表表上上则则比比较较刚刚刚刚对对j j计计算算过过的的f f值值和和前前面面计计算算过过的的该该节节点点在在表表中中的的f f值值。如如果果新新的的f f值较小，则值较小，则 (i)

27、(i)以此新值取代旧值。以此新值取代旧值。(ii)(ii)从从j j指向指向i i，而不是指向它后来的父辈节点。，而不是指向它后来的父辈节点。(iii)(iii)如果节点如果节点j j在在CLOSEDCLOSED表中，则把它移回表中，则把它移回OPENOPEN表表.第三十七页，本课件共有51页(7)转向(2)，即GoT0(2)。步骤(6c)是一般搜索图所需要的，该图中可能有一个以上的父辈节点，具有最小估价函数f(j)的节点被选作父辈节点。例：但是对于搜索树，每个节点最多只有一个父辈节点，所以对于搜索树步骤(6c)可以略去。第三十八页，本课件共有51页第三十九页，本课件共有51页 宽度优先搜索、

28、等代价搜索和深度优先搜索都是有序搜索技术的特例。对于宽度优先搜索，我们选择f(i)作为节点i的深度。对于等代价按索，f(i)是从起始节点至节点i这段路径的代价。有序搜索的有效性直接取决于f的选择，这将敏锐地辨别出有希望的节点和没有希望的节点。不过，如果这种辨别不准确，那么有序搜索就可能失去一个最好的解甚至全部的解第四十页，本课件共有51页例：八数码难题的有序搜索 取估价函数：f(x)=d(n)+w(n)操作符：f1：空格左移 f2：空格右移 f3：空格上移 f4：空格下移第四十一页，本课件共有51页第四十二页，本课件共有51页 正确地选择估价函数对确定搜索结果具有决定性的作用。使用不能识别某些

29、节点真实希望的估价函数会形成非最小代价路径；而使用一个过多地估计了全部节点希望的估价函数又会扩展过多的节点。第四十三页，本课件共有51页4.A*算法 让我们描述一个特别的估价函数，这个估价函数f使得在任意节点上其函数值f(n)能估算出从节点s到节点n的最小代价路径的代价与从节点n到某一目标节点的最小代价路径的代价之总和，也就是说f(a)是约束通过节点n的一条最小代价路径的代价的一个估计。因此，OPEN表上具有最小f值的那个节点就是所估计的加有最少严格约束条件的节点，而且下一步要扩展这个节点是合适的。在正式讨论A*算法之前，我们先介绍几个有用的记号。令k(ni,nj)表示任意两个节点ni和nj之

30、间最小代价路径的实际代价(对于两节点间没有通路的节点，函数k没有定义)。于是，从节点n到某个具体的目标节点ti，某一条最小代价路径的代价可由k(n，ti)给出。我们令h*(n)表示整个目标节点集合ti上所有k(n,ti)中最小的一个，因此，h*(n)就是从n到目标节点最小代价路径的代价，而且第四十四页，本课件共有51页从从n n到到目目标标节节点点能能够够获获得得h*(n)h*(n)的的任任一一路路径径就就是是一一条条从从n n到到某某个个目目标标节节点点的的最最佳佳路路径径(对对于于任任何何不不能能到到达达目目标标节节点点的的节节点点n n，函数函数h*h*没有定义没有定义)。通常我们感兴趣

31、的是想知道从已知起始节点通常我们感兴趣的是想知道从已知起始节点s s到任意节到任意节点点n n的一条最佳路径的代价的一条最佳路径的代价k(sk(s，n)n)。为此，引进一个新函数。为此，引进一个新函数g*g*，这将使我们的记号得到某些简化。对所有从，这将使我们的记号得到某些简化。对所有从s s开始可达开始可达到到n n的路径来说，函数的路径来说，函数g*g*定义为定义为 g*(n)=k(Sg*(n)=k(S，n)n)其其次次我我们们定定义义函函数数f*f*，使使得得在在任任一一节节点点n n上上其其函函数数值值fl(n)fl(n)就就是是从从节节点点s s到到节节点点n n的的一一条条最最佳佳

32、路路径径的的实实际际代代价价加加上上从从节节点点n n到某目标节点的一条最佳路径的代价之和，即到某目标节点的一条最佳路径的代价之和，即f*(n)=g*(n)+h*(n)f*(n)=g*(n)+h*(n)因因而而f*(n)f*(n)值值就就是是从从S S开开始始约约束束通通过过节节点点n n的的一一条条最最佳佳路路径径的的代代价价，而而f)(S)f)(S)h h从从s s到到某某个个目目标标节节点点中中间间无无约约束束的的一一条条最最佳路径的代价。佳路径的代价。第四十五页，本课件共有51页我们希望估价函数我们希望估价函数f是是f4的一个估计，可由下式给出：的一个估计，可由下式给出：f(n)g(n

33、)十十h(n)其中其中:g是是g*的估计的估计;h是是h*的估计。对于的估计。对于g(n)来说，一个明显的来说，一个明显的选择就是搜索树中从选择就是搜索树中从S到到n这段路径的代价，这一代价可以这段路径的代价，这一代价可以由从由从n到到S寻找指针时，把所遇到的各段弧线的代价加起来寻找指针时，把所遇到的各段弧线的代价加起来给出给出(这条路径就是到目前为止用搜索算法找到的从这条路径就是到目前为止用搜索算法找到的从S到到n的的最小代价路径最小代价路径)。这个定义包含了。这个定义包含了g(n)=g*(n)。对于。对于h*(n)的估的估计计h(n)它依赖于有关问题的领域的启发信息。这种信息可它依赖于有关

34、问题的领域的启发信息。这种信息可能与八数码难题中的函数能与八数码难题中的函数w(n)所用的那种信息相似。我们把所用的那种信息相似。我们把h叫做叫做启发函数启发函数。A*算法是一种算法是一种有序搜索算法有序搜索算法，其特点在于对估价函数的定，其特点在于对估价函数的定义上。对于一股的有序搜索，总是选择义上。对于一股的有序搜索，总是选择f值最小的节点作为扩值最小的节点作为扩展节点。因此，展节点。因此，f是根据需要找到一条最小代价路径的观点是根据需要找到一条最小代价路径的观点来信算节点的，所以，可考虑每个节点来信算节点的，所以，可考虑每个节点n的估价函数值为两个的估价函数值为两个分量：从起始节点到节点

35、分量：从起始节点到节点n的代价以及从节点的代价以及从节点n到达目标节点到达目标节点的代价。在讨论估价函数时说明过。的代价。在讨论估价函数时说明过。第四十六页，本课件共有51页第四十七页，本课件共有51页5.双向搜索 搜索过程的目的是发现一条通过问团空间从韧始状态到达目标状态的路径。这种搜索可以向两个方向进行：(1)从初始状态开始的正向搜索（数据驱动法）(2)从目标状态开始的逆向搜索（目标驱动法）双向搜索：同时从初始状态正向搜索及从目标状态逆向搜索，直到这两条路径在中途某处相交为止。第四十八页，本课件共有51页通用问题求解系统GPS 可实现双向推理。1957年，纽厄尔肖西蒙研究成功 两个基本原理

36、：中间结局分析 递归问题求解 中间结局分析是GPS程序的主要组成部分，它是一个按过程进行控制的求解方法，其中心在于发现现有目标(中间)和希望目标(结局)之间的差别，并加以分类。一旦这个差别被确定，就必然能够找到一个减少差别的操作符。可能这个操作符也不适用于现有目标，但是这样可以生成一个子问题，以使得到一个能够应用该操作符的目标。这个操作也可能还不能生成希望目标。于是，产生了第二个子问题从这个操作符所导致的状态得到目标状态的子问题。如果此操作符能够被正式确定，而且操作符能够有效地缩小这一差别，那么这两个子问题要比原始问题易于解决。第四十九页，本课件共有51页 中间结局分析技术对子问题(子目标)进

37、行递归分析。因此，从这一观点看，中间结局分析可以看成一种问题规约技术。GPS首先力图计算出S和G之间的差别，这个差别计算过程用一个函数来完成，而且对于不同的应用领域需要专门编写，差别通常用来选择有关的F规则，其方法是访问一下把F规则和差别联系起来的差别表。GPS过程如下：(1)until S与G匹配，do：；GPS的主循环为迭代方式(2)begin(3)dS和G间的一个差别 ；一个回溯点。(4)f与减少d有关的一条F规则 ；另一个回溯点(5)Pf的合适例的先决条件公式。(6)GPS（P）；解决子问题的一个递归调用(7)S对S应用f的合适例的结果(8)end 第五十页，本课件共有51页中间结局分析：找出差别并为减少差别选择F规则的过程。防止GPS进入错误路径须辨别：(1)每个目标应比父辈目标容易(2)新产生的目标不应比出现在最上面的目标大(3)一旦产生一个新目标，就不应当再产生相同的目标第五十一页，本课件共有51页