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