《图搜索技术》PPT课件.ppt

《《图搜索技术》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图搜索技术》PPT课件.ppt（63页珍藏版）》请在三一办公上搜索。

1、1,第八章图搜索技术,李伟生信科大厦19楼Tel：62471342,2,第8章 图搜索技术,8.1 状态图搜索策略 8.2 启发式搜索 8.3 与或图搜索 8.4 博弈树搜索,3,迷宫问题：把迷宫每一个位置以及入口和出口都作为节点，把通道作为边，则迷宫可由一个有向图表示。走迷宫实际就是从该有向图的初始节点（入口）出发，寻找目标节点（出口）的问题，或者是寻找通向目标节点（出口）的路径的问题。8数码问题：在一个3*3的方格棋盘上放置着1，2，3，4，5，6，7，8八个数码，每个数码占一格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码才可以移入空格。问题：对于指定的初始棋局和

2、目标棋局，给出数码的移动序列。如果把一个棋局作为一个节点，相邻的节点就可以通过移动数码，一个一个地产生出来。这样，所有节点就可由它们相邻的关系连成一个有向图，图中的一条边就对应一次数码移动，反之，一次数码移动就对应着图中的一条边，边也就代表着一个移动规则或者移动规则的一次执行。该问题也就是要在该有向图中寻找目标节点，或找一条从初始节点到目标节点的路径问题。,例,4,上述两个问题虽然内容不同，但抽象地看，它们都是在某个有向图中寻找目标或路径的问题。我们把这种描述问题的有向图称为状态空间图，简称状态图。,例,5,8.1.1 图搜索策略的定义 8.1.2 图搜索算法中的几个重要名词术语 8.1.3

3、图搜索(GRAPH SEARCH)的一般过程 8.1.4 图搜索方法分析,8.1 状态图搜索策略,6,图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。研究图搜索的一般策略，能够给出图搜索过程的一般步骤。,8.1.1 图搜索策略的定义,7,（1）OPEN表与CLOSED表（2）搜索(状态)图与搜索树,登记当前待考查的节点,记录考查过的节点,OPEN,CLOSED,8.1.2 图搜索算法中的几个重要名词术语,8,(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫

4、做OPEN的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。,8.1.3 图搜索的一般过程,9,(7)对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把

5、M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GO LOOP。,图搜索的一般过程,10,图搜索的一般过程框图,11,图搜索过程的第8步（按某一方式重排OPEN表）对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节

6、点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点。1.宽度优先搜索2.深度优先搜索,8.1.4 图搜索方法分析,12,1)定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。(breadth-first search)2)特点这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。,1.宽度优先搜索,

7、13,3)宽度优先搜索算法,(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。,宽度优先搜索,14,(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个

8、空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。,宽度优先搜索,15,4)宽度优先搜索方法分析：,宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短

9、途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止)。,宽度优先搜索,16,5)例：八数码难题,把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：,2 8 31 47 6 5,1 2 38 47 6 5,宽度优先搜索,17,八数码难题宽度优先搜索树,18,1)定义在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。2)特点首先，扩展最深的节点的结果使得搜索沿着状态空间某条

10、单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。,2.深度优先搜索,19,3)深度界限为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度棗深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。4)含有深度界限的深度优先搜索算法请课后自学。,深度优先搜索,20,1.为什么需要启发式搜索 盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。2.定义 进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。,8

11、.2 启发式搜索,21,3.启发式搜索策略有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function)。,启发式搜索,22,4.估价函数为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)表示节点n的估价函数值建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概

12、率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。,启发式搜索,23,1、定义用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点。应用某个算法选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索(ordered search)或最佳优先搜索(best-first search)，而其算法就叫做有序搜索算法或最佳优先算法。尼尔逊(Nilsson)曾提出一个有序搜索的基本算法。估价函数f是这样确定的：一个节点的希望程序越大，其f值就越小。被

13、选为扩展的节点，是估价函数最小的节点。,8.2.1 有序搜索,24,2、实质,选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。,有序搜索,25,3、有序状态空间搜索算法,(1)把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。(2)如果OPEN是个空表，则失败退出，无解。(3)从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i.(4)把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。(5)如果i是个目标节点，则成功退

14、出，求得一个解。(6)扩展节点i，生成其全部后继节点。对于i的每一个后继节点j：,有序搜索,26,(6)扩展节点i，生成其全部后继节点。对于i的每一个后继节点j：(a)计算f(j)。(b)如果j既不在OPEN表中，又不在CLOSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。(c)如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小，则(i)以此新值取代旧值。(ii)从j指向i，而不是指向它的父辈节点。(iii)如果节点j在CLOSED表中，则把它移回OPEN表

15、(7)转向(2)，即GO TO(2)。,有序搜索,27,4、有序搜索方法分析,宽度优先搜索和深度优先搜索统统是有序搜索技术的特例。有序搜索的有效性直接取决于f的选择，如果选择的f不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么f的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。,有序搜索,28,5、例：八数码难题,采用了简单的估价函数 f(n)=d(n)+W(n)其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。因此，起始节点棋局2 8 31 6 47 5的f值

16、等于0+4=4。,1 2 38 47 6 5,有序搜索,29,八数码难题的有序搜索树,有序搜索,30,A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。,8.2.2 A*算法,31,1、几个记号,令k(ni，nj)表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点，函数k没有定义)。于是，从节点n到某个具体的目标节点ti，某一条最小代价路径的代价可由k(n,ti)给出。令h*(n)表示整个目标节点集合ti上所有k(n,ti)中最小的一个，因此，h*(n)就是从n到目标节点最小代价路径的代价，而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目

17、标节点的最佳路径(对于任何不能到达目标节点的节点n，函数h*没有定义)。,A*算法,32,2、估价函数的定义,定义g*为 g*(n)=k(S,n)定义函数f*，使得在任一节点n上其函数值f*(n)就是从节点S到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和，即f*(n)=g*(n)+h*(n),A*算法,33,希望估价函数f是f*的一个估计，此估计可由下式给出：f(n)=g(n)+h(n)其中：g是g*的估计；h是h*的估计。对于g(n)来说，一个明显的选择就是搜索树中从S到n这段路径的代价，这一代价可以由从n到S寻找指针时，把所遇到的各段弧线的代价加起来给出(

18、这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。这个定义包含了g(n)g*(n)。h*(n)的估计h(n)依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数W(n)所用的那种信息相似。把h叫做启发函数。,A*算法,34,3、A*算法定义,定义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*

19、算法就变为有序搜索算法。,A*算法,35,状态图搜索策略小结,36,例 Hanoi塔 状态图,为了便于分析，我们仅考虑二阶梵塔(即只有两个金盘)问题。设有三根宝石杆，在1号杆上穿有A、B两个金盘，A小于B，A位于B的上面.要求把这两个金盘全部移到另一根杆上，而且规定每次只能移动一个盘子，任何时刻都不能使B位于A的上面。,37,设用二元组(SA，SB)表示问题的状态，SA表示金盘A所在的杆号，SB表示金盘B所在的杆号。这样，全部可能的状态有9种，可表示如下：,这里的状态转换规则就是金盘的搬动规则，分别用A(i，J)及B(i，J)表示：A(i，J)表示把A从第i号杆移到第J号杆上；,共有l 2个操

20、作，它们分别是:A(1，2)，A(1，3)，A(2，1)，A(2，3)，A(3，1)，4(3，2)，B(1，2)，B(1，3)，B(2，1)，B(2，3)，B(3，1)，B3，2),38,二阶梵塔状态空间图,39,在现实世界中，经常会遇到这样的问题：一个问题可以有几种求解方法，只要其中一种方法可以求解问题，则该问题被求解。也就是说，对求解该问题来说，方法之间是“或”的关系。但在用每一种方法求解时，又可能需要求解几个子问题，这些子问题必须全部求解，才可能用该方法求解原始问题。也就是说，这些子问题之间是“与”的关系。此类问题可以用与或图来表示。,8.3 与或图搜索,40,它表示，如果要求解n0，可

21、以求解n1，或者求解n4、n5，也就是说，对于n0来说，n4和n5是与的关系，而n1和n4、n5的与之间是或的关系。其他节点之间也具有类似的关系。一个节点与它的k个与子节点间用下图的形式连接，称为k连接符。,与或图搜索一个与或图的示例,41,从图可以看出，节点n0有两个连接符：1-连接符指向节点n1；2-连接符指向节点集n4，n5。该2-连接符还用一小段圆弧括起来（对k1的k-连接符都应有小圆弧标记），以表示子节点间与的关系。可以看出这种标记法在节点间具有明确的关系。显然若用原先的术语，则对父节点n0来说，n4、n5是两个与节点，而n1可称为或节点；而n8既是n5的一个与节点，又是n4的一个或

22、节点，混淆难于避免。另外也把图中没有任何父节点的节点叫根节点，没有任何后继节点的节点叫端节点或叶节点。,与或图搜索一个与或图的示例,42,在普通图中，目标用一个节点表达，而在与或图中，目标则表现为一个节点的集合，该集合中由一些子目标节点组成。值得指出的是，解图不一定要求到达目标集中的每一个子目标节点，而只要求解图的端节点是目标集中的节点即可。也就是说，解图中的端节点是目标集的子集即可。,与或图搜索解图,43,与或图中某一个节点n到节点集N的一个解图类似于普通图中的一条解路径。解图的求法是：从节点n开始，正确选择一个外向连接符，再从该连接符所指的每一个后继节点出发，继续选一个外向连接符，如此进行

23、下去直到由此产生的每一个后继节点成为集合N中的一个元素为止。,与或图搜索解图的求法,44,在与或图是无环（即不存在这样的节点-其后继节后同时又是它的祖先）的假定下，解图可递归定义如下：定义：一个与或图G中，从节点n到节点集N的解图记为G，G是G的子图。若n是N的一个元素，则G由单一节点组成；若n有一个指向节点n1，nk的外向连接符K，使得从每一个ni到N有一个解图（i=1，k），则G由节点n，连接符K，及n1，nk中的每一个节点到N的解图所组成；否则n到N不存在解图。,与或图搜索解图的递归定义,45,递归定义局部图：定义：单一节点是一个局部图；对于一个局部图的任意叶节点n，选择一个n的外向连接

24、符K，则该局部图、外向连接符K，以及K所连接的n的后继节点一起组成的图，仍然组成一个局部图。,与或图搜索递归定义局部图,46,与或图一般表示问题的变换过程（而不是状态变换）。具体讲，它是从原问题出发，通过运用某些规则不断进行问题分解（得到与分支）和变换（得到或分支），而得到一个与或图。换句话说，与或图的节点一般代表问题。那么，整个图就表示问题空间。与或图中的父节点与其子节点服从逻辑上的与、或运算关系。所以，与或图表示的问题是否有解，要进行逻辑判断，与或图的搜索也受逻辑的制约。,与或图搜索问题的与或图表示,47,与或图也是一个三元组(Q0,F,Qn)Q0,表示初始问题，F表示问题变换规则集，Qn

25、表示本原问题集。,例如：积分公式，就是一些典型的问题分解和变换问题。所以，一般求不定积分就可用与或图来描述。,与或图搜索问题的与或图表示,48,例 三阶 Hanoi塔,1,2,3,三阶 Hanoi塔可分解为下面三个子问题：1）把A、B盘从1号杆移到2号杆。2）把C盘从1号杆移到3号杆。3）把A、B盘从2号杆移到3号杆。其中，子问题1）、3）又可分解为三个子问题。,49,三阶 Hanoi塔的与或图表示,(i,j,k)i:C盘所在杆号，j:B盘所在杆号，k:A盘所在杆号。,(1,1,1)(3,3,3),(1,1,1)(1,2,2),(1,2,2)(3,2,2),(3,2,2)(3,3,3),(1,

26、1,1)(1,1,3),(1,1,3)(1,2,3),(1,2,3)(1,2,2),(3,2,2)(3,2,1),(3,2,1)(3,3,1),(3,3,1)(3,3,3),7个本原问题，将他们的解按从左至右的顺序排列，就得到原始问题的解。,50,这里所讲的博弈，指的是类似于象棋这样的游戏问题。这类问题有以下一些特点：（1）双人对弈，对垒的双方轮流走步。（2）信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。（3）零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。,8.4 博弈树搜索,51

27、,博弈问题为什么可以用与或图表示呢？可以这样来看待这个问题：当轮到我方走棋时，只需从若干个可以走的棋中，选择一个棋走就可以了。从这个意义上说，若干个可以走的棋是“或”的关系。而对于轮到对方走棋时，对于我方来说，必须能够应付对手的每一种走棋。这就相当于这些棋是“与”的关系。因此，博弈问题可以看成是一个与或图，但是与一般的与或图并不一样，是一种特殊的与或图。,博弈树搜索,52,1概述,博弈一向被认为是富有智能行为的游戏，因而很早就受到人工智能界的重视，早在60年代就已经出现若干博弈程序，并达到一定水平。博弈问题的研究还不断提出一些新的研究课题，从而也推动了人工智能研究的发展。对于单人博弈的一些问题

28、，可用一般的搜索技术进行求解，本节着重讨论双人完备信息这一类博弈问题的搜索策略。由于双人博弈可用与或树（或图）来描述，因而搜索就是寻找最佳解树（图）的问题。,博弈树搜索,53,所谓双人完备信息，就是两位选手对垒，轮流走步，这时每一方不仅都知道对方过去已经走过的棋步，而且还能估计出对方未来可能的走步。对弈的结果是一方赢（另一方则输），或者双方和局。这类博弈的实例有：一字棋、余一棋、西洋跳棋、国际象棋、中国象棋、围棋等。对于带机遇性的任何博弈，因不具有完备信息，不属这里讨论范围，但有些论述可推广到某些机遇博弈中应用。,博弈树搜索,54,博弈问题可以用产生式系统的形式来描述，例如中国象棋，综合数据库

29、可规定为棋盘上棋子各种位置布局的一种描述，产生式规则是各类棋子合法走步的描述，目标则可规定为将（帅）被吃掉，规则作用于数据库的结果便生成出博弈图或博弈树。,博弈树搜索,55,2极小极大分析方法,极小极大搜索方法是博弈树搜索的基本方法，现在博弈树搜索中最常用的-剪枝搜索方法，就是从这一方法发展而来的。首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对我方不利，对对方有利。而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示

30、对方必胜。假设双方都是对弈高手，在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。会下棋的都知道，在只看一步的情况下最好的棋，从全局来说不一定就好，还可能很不好。因此为了走出好棋，必须多看几步，从多种可能状态中选择一步好棋。,博弈树搜索,56,想一想人是如何下棋的呢？人实际上采用的是一种试探性的方法。首先假定走了一步棋，看对方会有那些应法，然后再根据对方的每一种应法，看我方是否有好的回应.这一过程一直进行下去，直到若干步以后，找到了一个满意的走法为止。初学者可能只能看一、两个轮次，而高手则可以看几个，甚至十几个轮次。极小极大搜索方法，模拟的就是人的这样

31、一种思维过程。当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。然后从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。,博弈树搜索,57,在博弈问题中，每一个棋局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树。据统计，西洋跳棋完整的博弈树约有1040个节点。试

32、图利用完整的博弈树来进行极小极大分析是困难的。可行的办法是只生成一定深度的博弈树，然后进行极小极大分析，找出当前最好的行动方案。在此之后，再在已选定的分支上扩展一定深度，再选最好的行动方案。如此进行下去，直到取得胜败的结果为止。至于每次生成博弈树的深度，当然是越大越好，但由于受到存储空间的限制，只好根据实际情况而定。,博弈树搜索,58,例 一字棋,在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果就取胜。设A的棋子用（a）表示，对手B的棋子用（b）表示，A先走。静态估计函数f（p）规定如下:(p为棋局）若p对任何一方来说都不是获胜的格局，则f（p）（所有空格都

33、放上A的棋子之后，A的三子成线（行、列、对角）的总数（所有空格都放上B的棋子之后，B的三子成线（行、列、对角）的总数若p是A获胜的格局，则f（p）；若p是B获胜的格局，则f（p）。例如，当p的格局如下时，则可得f（p）642；,b,a,59,另外，我们假定具有对称性的两个棋局算作一个棋局。还假定A先走棋，我们站在A的立场上。,在A走S3这一着棋后，B的最优选择是S4，因为这一着棋的静态估值较小，对A不利。不管B选择S4或S5，A都要再次运用极小极大分析法产生深度为2的博奕树,以决定下一步应该如何走棋，其过程与上面类似，不再重复。,A的第一着走棋生成的博弈树,图中节点旁的数字分别表示相应节点的静

34、态估值或倒推值。由图可以看出，对于4来说最好的一着棋是S3：，因为S3比S1和S2有较大的倒推值。,博弈树搜索,60,思考题1,基于谓词逻辑的机器推理1.猴子香蕉问题已知一串香蕉挂在天花板上，猴子直接去拿是够不到的，但猴子可以走动且可以搬着梯子走动，也可以爬上梯子来达到吃香蕉的目的。用谓词逻辑描述该问题，并求得该问题的目标状态（猴子吃到香蕉列）。2.设已知：(1)能阅读者是识字的；(2)海豚不识字；(3)有些海豚是很聪明的。求证：有些聪明者并不能阅读。考虑：设已知：(1)凡是清洁的东西就有人喜欢；(2)人们都不喜欢苍蝇；用归结原理证明：苍蝇是不清洁的。,61,思考题2,知识表示方法1.用语义网

35、络表示下述命题：(1)树和草都是植物。(2)树和草都是有根、有叶的。(3)水草是草，且长在水中。(4)果树是树，且会结果。(5)苹果树是果树中的一种，它结苹果。2.用谓词公式表示下列规则性知识：(1)所有整数要么是偶数要么就是奇数。(2)自然数都是大于零的整数。,62,思考题3,1.设样本空间=a,b,c,d，M1,M2为定义在上的概率分配函数。已知：M1b,c,d=0.7,M1a,b,c,d=0.3 M2a,b=0.6,M2a,b,c,d=0.4求它们的正交和M1M2.2.设U=1,2,3,4,5，定义模糊子集 A=“小”=1/1+0.5/2+0/3+0/4+0/5 A=“比较小”=1/1+1/2+0.5/3+0.2/4+0/5 B=“大”=0/1+0/2+0.4/3+0.6/4+1/5已知(1)如果x小，那么y大；(2)x比较小问：y怎么样？（使用Zadeh的CRI法）,63,谢谢收看！,再 见,