状态空间搜索.ppt

《状态空间搜索.ppt》由会员分享，可在线阅读，更多相关《状态空间搜索.ppt（181页珍藏版）》请在三一办公上搜索。

1、状态空间搜索,基于递归的搜索 递归 递归搜索模式驱动搜索产生式系统 定义与历史 产生式系统示例 产生式系统搜索的控制 产生式系统的优点,状态空间搜索策略 数据驱动和目标驱动的搜索状态空间可以从两个方向进行搜索：从实际问题的给定数据向目标搜索或者从目标到数据进行搜索。数据驱动搜索，也称为正向推理。搜索的过程是应用规则从给定的条件产生新的条件，再用规则从新的条件产生更多的新条件。这个过程持续到有一条满足目标要求的路径产生为止。,另一种求解方法是：先从欲想达到的目标开始，看哪些规则或合法移动能产生该目标以及应用这些规则产生目标时需要哪些条件。这些条件就成为我们要达到的新目标，即子目标。搜索就通过反向

2、的、连续的子目标不断地进行，一直到找到问题给定的条件为止。这样就找到了一条从数据到目标的移动或规则组成的链，尽管搜索方向和它正好相反。这种方法称为目标驱动的推理或反向推理。在实际的搜索系统中可能两种方法同时使用，即一方面从数据驱动向目标进行，可能搜索到某一个子目标；另一方面又从目标向数据方面进行搜索，刚好也搜索到该子目标，这时推理也结束，即假设的目标正确。,图搜索的实现,无论是目标还是数据驱动的搜索，其求解问题都是要在状态空间图中找到从初态到目标状态的路径。而路径上弧的序列就对应解题的先后步骤。若在选择解题路径时能给出绝对可靠的预言或绝对正确的机制，那就不需要搜索了，求解时会一次成功地穿过空间

3、到达目标，构造出一条求解路径来。但实际问题中没有绝对可靠的预言，求解时必须尝试多条路径直到找到目标为止。回溯是一种经常使用的技术。,图搜索的实现（续）,带回溯的搜索从初始状态出发，不停地寻找路径一直到它到达目标或“不可解端点”。若找到目标，就退出搜索，返回解题路径，若遇到不可解结点，就回溯到路径中最近的父结点上，查看是否有当前结点的兄弟结点未扩展，并沿这些分支继续搜索。算法在每个结点上的检查过程遵循下面的递归方式：,图搜索的实现（续）,若当前状态S未到达目标的要求，就对它的第一子状态Schild1递归调用回溯过程。如果在以Schild1为根的子图中没有找到目标，就对它的兄弟Schild2调用此

4、过程。此过程重复进行到某个结点的后裔是目标或者所有子结点都搜索完为止。,图搜索的实现（续）,算法就是以这种方式执行直到找到目标或遍历了状态空间为止。下图给出的是一个假设的状态空间的深度优先回溯搜索。1 A 2 B 8 C 10 DE 3 6 F 9 G H I J 4 5 7 一个假设状态空间的深度优先回溯搜索,图搜索的实现（续）,下面定义一个回溯搜索的算法：算法使用3张表保存状态空间中的结点。SL状态表列出了当前路径上的状态。如果找到了目标，SL就是解题路径上状态的有序集。NSL新状态表，包含了等待评估的结点，其后裔结点还未被扩展。DE不可解端点集,列出了找不到解题路径的状态。如果在搜索中再

5、遇到它们，就会检测到它们是DE中的成分而立即将其排除。为了在最普遍的情况下（是图而不是树）定义回溯算法，有必 要检测并删除多次出现的某些状态，以避免造成路径循环。检测可以通过对每一个新生成的状态判断它是否在上述3张表中来实现，如果它属于某一张表，就说明它已被搜索过不必再考虑。,图搜索的实现（续）,当前正在搜索的结点叫CS，即当前状态。CS总是等于最近加入SL中的状态，是当前正在探寻的解题路径的“前锋”。博弈中走步用的推理规则或者其他合适的问题求解操作都可应用于CS，得到一些新状态，即CS的子状态的有序集，重新视该集合中第一个状态为当前状态，其余的按次序放入NSL中，用于以后的搜索。新的CS加入

6、SL中，搜索就这样继续进行。若CS没有子状态，就要从SL，NSL中删除它，将其加入DE，然后回溯查找NSL中的下一个状态。,图搜索的实现（续）,Function backtrack(回溯算法）beginSL:=Start;NSL:=Start;DE:=;CS:=Start;/*初始化*/while NSL/*还有未检查的状态*/do begin if CS=目标（或符合目标的要求）then return(SL);/*成功，返回路径状态的表*/if CS没有子状态（不包括DE，SL和NSL中已有的状态）then begin while(SL非空）and(CS=SL中第一个元素),图搜索的实现（续

7、）,do begin 将CS加入DE；/*标明此状态不可解*/从SL中删除第一个元素；/*回溯*/从NSL中删去第一个元素；CS：=NSL中第一个元素；end;将CS加入SL；endelse begin将CS子状态（不包括DE、SL、NSL中有的）加入NSL；,图搜索的实现（续）,CS：=NSL中第一个元素；将CS加入SL；endend;return FAILend.假设状态空间的深度优先回溯搜索中的回溯轨迹如下：初值：SL=A；NSL=A；DE=；CS=A；,图搜索的实现（续）,重复 CS SL NSL DE0 A A A 1 B BA BCDA 2 E EBA EFBCDA 3 H HEB

8、A HIEFBCDA 4 I IEBA IEFBCDA H5 F FBA FBCDA EIH6 J JFBA JFBCDA EIH7 C CA CDA BFJEIH8 G GCA GCDA BFJEIH,1 A 2 B 8 C 10 D 3 E 6 F 9 G 4 H 5 I 7 J 一个假想的状态空间的深度优先回溯搜索,状态空间的一般搜索过程一个问题的状态空间是一个三元组，即S,F,G，其中S是问题所有可能的状态的集合，F是操作的集合，G是目标状态的集合一般，如果问题的状态空间不太大的话，可以用显式的方式画出其状态空间图，否则用隐式的方法画出其状态空间图对状态空间的搜索就是从图中某个初始状态

9、出发，寻求一条到达目标状态的路径,状态空间的一般搜索过程,对状态空间的搜索过程用到两张表：OPEN表和CLOSED表，它们的结构如下：Open 表状态节点父节点Closed表编号状态节点父节点,状态空间的一般搜索过程,其中open表存放刚生成的节点，对于不同的搜索策略，节点在open表中的排列顺序是不同的例如对宽度优先搜索是先生成的节点排在前面，而对深度优先搜索则是后生成的节点排在前面Closed表用于存放将要扩展或者已经扩展的节点搜索的一般过程如下：,状态空间的一般搜索过程,(1)把初始节点S0放进open表，并建立只包含S0的图，记为(2)检查open表是否为空，若为空则问题无解，退出(3

10、)把open表的第一个节点取出放入closed表，并记该节点为n.(4)考察节点n是否为目标节点，若是，则求得了问题的解，退出(5)扩展节点n，生成一组子节点把其中不是,状态空间的一般搜索过程,节点n的先辈的那些子节点记作集合，并把这些子节点作为节点n的子节点加入中(6)针对中子节点的不同情况，分别进行如下处理：)对那些未曾在中出现过的成员设置一个指向父节点（即节点n）的指针，并把它们放入open表)对于那些先前已在中出现的成员，确定是否需要修改它指向父节点的指针)对于那些先前已在中出现并且已经扩展,状态空间的一般搜索过程,了的成员，确定是否是需要修改其后继节点指向父节点的指针(7)按某种搜索

11、策略对open表中的节点进行排序(8)转第步说明：上面对状态空间的搜索过程具有通用性，后面讨论的各种搜索策略都可看作是它的一个特例各种搜索策略的主要区别仅在于open表中节点的排序准则不同例如在宽度优先搜索中是先生成的节点排在前，在深度优先搜索中是后生成的节点排在前等,状态空间的一般搜索过程,一个节点经一个算符操作后一般只生成一个子节点，但适用于一个节点的算符可能有多个，此时就会生成一组子节点在这些子节点中可能有些是当前扩展节点(即节点n)的父节点，祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点余下的子节点记作集合，并加入图中一个新生成的节点，它可能是第一次被生成的节点，也可能是先

12、前已作为其它节点的后继节点被生成过，当前又作为另一个节点的后继节,状态空间的一般搜索过程,点被再次生成此时，它应该作为哪一个节点的后继呢？一般由原始节点到该节点上所付出的代价来决定，哪条路径付出的代价小，相应的节点就作为它的父节点,深度和广度优先搜索,深度优先搜索、广度优先搜索、有界深度优先搜索及最好优先搜索都与backtrack方法类似，所不同的是，它们实现了另外一些搜索策略，为求解提供了更灵活的手段。广度优先搜索采取的是先横后纵的搜索策略，而深度优先搜索采取的是先纵后横的搜索策略。A B C D E F G H I J K L M N O P Q R S T U 用于深度和广度优先搜索的例

13、图,深度和广度优先搜索,例如在上面的深度和广度优先搜索图中，深度优先搜索的顺序是：A，B，E，K，S，L，T，F，M，C，G，N，H，O，P，U，I，Q，J，R而在广度优先搜索中结点的顺序是：A，B，C，D，E，F，G，H，I，J，K，L，M，N，O，P，Q，R，S，T，U算法中设有两个表：OPEN表和CLOSED表。OPEN表中放的是未扩展的结点，CLOSED表中放的是已扩展的结点。,深度和广度优先搜索,可以看出这里的open表与回溯算法中的NSL相似，而closed表则是回溯算法中SL和DE的合并.当对解的先验信息有所了解时（比如知道解可能落在最右分枝或最左分枝上时）深度优先搜索的速度还是

14、很快的，如果弄错了方向可能会使搜索落入陷阱中，补救的措施是采用定界的方法有界深度优先搜索。其思想是定一个界d，这个界d可以是深度，也可以是一个代价。以上几种搜索方法都是盲目搜索的典型代表。,宽度优先搜索,宽度优先搜索的过程如下：、把初始节点放入open表、如果open表为空，则问题无解，退出、把open表的第一个节点(记为n)取出放入closed表、考察节点n是否为目标节点，若是则求得了问题的解，退出。、若节点n不可扩展，则转第步、扩展节点n将其子节点放入open表的尾部,宽度优先搜索,并为每一个子节点配置指向父节点指针，然后转其图示如p265的图所示例：重排九宫问题在一个的方格棋盘上放置分别

15、标有数字1,2,3,4,5,6,7,8的张牌，初始状态为S0目标状态为Sg即：S0为：Sg 为：,宽度优先搜索,可使用的算符有，空格左移，右移，上移，下移宽度优先搜索的图示如p267页的图,深度优先搜索,深度优先搜索的过程如下：、把初始节点放入open表、如果open表为空，则问题无解，退出、把open表的第一个节点(记为n)取出放入closed表、考察节点n是否为目标节点，若是则求得了问题的解，退出。、若节点n不可扩展，则转第步、扩展节点n将其子节点放入open表的首部,深度优先搜索,深度优先搜索和宽度优先搜索的区别仅在于：宽度优先搜索是把节点n的子节点放入到open表的尾部，而深度优先搜索

16、则是将节点n的子节点放入open表的首部深度优先搜索重排九宫的例子见p268页的图,有界深度优先搜索,为了解决深度优先搜索不完备的问题，避免搜索过程陷入无穷分支的死循环，提出了有界深度优先搜索方法其过程如下：、把初始节点放入open表，置S0深度d(S0)=0、如果open表为空，则问题无解，退出、把open表的第一个节点(记为n)取出放入closed表,有界深度优先搜索,、考察节点n是否为目标节点，若是则求得了问题的解，退出。、若节点n的深度d(n)=dm则转、若节点n不可扩展，转、扩展节点n将其子节点放入open表的首部，并为其配置指向父节点的指针，转如果问题有解，且其路径长度 dm，则上

17、述搜索过程一定能求得解，若解的路径长度 dm则上述搜索过程就得不到解即界的选择很重要的不是越大就越好,有界深度优先搜索,有界深度优先搜索的例子见p269的图,代价树的宽度优先搜索,在上面的搜索中都没有考虑代价的问题，即假设各边上的代价是相同的，如果不是这样，边上是附有不同的数字的即代价（这样的树称为代价树）在代价树中如果用g(x)表示从初始节点S0到节点x的代价，用c(x1,x2)表示从父节点x1到子节点x2的代价，则有：g(x2)=g(x1)+c(x1,x2)代价宽度优先搜索的基本思想就是每次从open表中选择节点往closed表传送时总是选择代价最小的节点也就是说open表中的节点在任一时

18、刻都是按代价从小到大排序的,代价树的宽度优先搜索,其搜索过程如下：、把初始节点放入open表，置S0的代价g(S0)=0、如果open表为空，则问题无解，退出、把open表的第一个节点(记为n)取出放入closed表、考察节点n是否为目标节点，若是则求得了问题的解，退出。5、若节点n不可扩展，转,代价树的宽度优先搜索,6、扩展节点n将其子节点放入open表中，并为其配置指向父节点的指针，计算各子节点的代价，并按代价对open表中的全部节点按从小到大的顺序排序，转搜索过程见p270页的图书上例.7给出了求城市间交通图，现要求从城市到城市的最小费用交通路线求解该问题时首先要把图转换成代价树,代价树

19、的宽度优先搜索,A 4 B 4 4 C 2 D 5 3 E 交通图,代价树的宽度优先搜索,转化成代价树A 3 4 C1 B1 2 4 5 D1 D2 E1 3 4 2 3 E2 B2 C2 E3 5 E4 交通图的代价树,代价树的宽度优先搜索,从起始节点开始，把与它直接相邻的节点作为它的子节点，若一个节点已经作为某个节点的直系先辈，则不能再作为该节点的子节点为了区别一个节点可能在代价树中的多次出现，用下标1,2,标出例如，E1,E2等都是图中的节点广度优先搜索的结果是：AC D E代价树的深度优先搜索类似宽度优先搜索，只是把代价当作深度限制搜索的过程,对与/或图的搜索,对与/或图的搜索与一般图

20、的回溯相比，要求保留更多的记录。对属于或结点的后裔结点的检查与回溯算法中一样；一旦找到一条从初始状态沿或结点通向目标的路径，问题就解决了，除非这条路径被证明是失败的，算法就要回溯，探索另一分支。但检查与结点时，要证明父结点为真，必须证明它所有的子结点为真。如果在代价树中计算与结点的代价时，有两种计算方法：和代价法，最大代价法。具体使用见下图例。,对与/或图的搜索（续）,和代价法：取与结点逐子结点的代价之和作为该与结点的代价。最大代价法：取逐子结点中代价最大的作为该与结点的代价。S,a1,b1,解树A,解树B,a2,a3,a4,a5,a6,b2,t,t,t,b3,b4,b5,5,6,2,4,4,

21、3,4,4,2,4,5,7,3,t,与/或树的搜索（续）,上图中原始问题S可以分解成解树A或解树B，即只要解决其中一个原始问题S即可解。哪一个花费的代价更少，当然就是我们希望的那个分支。1、按和代价计算的结果：A树为25；B树为232、按最大代价法计算结果：A树为：14；B树为18所以规定好计算方法取代价花费小的即可。,启发式优先搜索,前面我们介绍的搜索均是盲目搜索的情形，即在寻求下一步应扩展结点时，对解的先验信息一点都不知道。启发（heuristic)式优先搜索就是从状态空间中选择最有希望到达问题解的路径。它在选择待扩展结点时利用启发式函数f(x)对OPEN表中的结点进行计算并排序,然后再进

22、行扩展的原则。而不同问题的启发式函数也不同，启发式函数是影响搜索效率的一个关键。启发式函数：f(x)=g(x)+h(x)其中g(x)是从初始结点到结点x已经付出的代价，h(x)是从结点x到目标结点将要付出代价的估计值。一般影响f(x)的主要因素是h(x)。,启发式优先搜索 算法,速度比较快的一种搜索是局部择优（也称瞎子爬山（hill climbing)法）搜索.它的特点也是其缺点，是省略了一个OPEN表，速度提高了，但由于它没有保留所走过的信息，所以它不能修正错误的路径，可能导致它陷入无穷尽地搜索中。瞎子爬山法在单峰单值的情况，搜索速度较快，可能找到一个最佳解；但在多峰多值的情况下只能找到较好

23、解但不是最好解。,人工智能中Samuel的跳棋程序最早应用的就是该方法。跳棋程序中根据几个不同启发值的总合来估算棋局的状态。,启发式优先搜索算法,最好优先搜索法（有序搜索法）在最好优先搜索法中也利用两张表OPEN表和CLOSED表来记录已生成而未扩展的结点和已扩展的结点。算法中有一步是根据启发函数，按结点距离目标结点的长度大小重排OPEN表中结点的顺序。扩展时（或循环时）只考虑OPEN表中状态最好的结点，这就是最好优先搜索法。它既不是广度优先中的先进先出，也不是深度中的后进先出而是一个按启发函数计算的大小为序的一个表，有时称为“优先队”。最好优先搜索的算法描述如下：,最好优先搜索法（续）,启动

24、,把S0放入OPEN表计算f(x),OPEN=NIL,取OPEN表最前面的结点N放入CLOSED表并冠以顺序编号n,N=Sg?,N可扩展？,失败,是,否,成功,是,扩展N并用f(x)估计每个子结点Ni及配上指向N的返回指针，将Ni并入OPEN表，利用f(x)对OPEN表重新排序（小的在前）,是,否,否,启发式函数的实现,前面我们介绍过启发式优先搜索的关键是启发式函数的制定上，不同的问题有不同的启发式函数。下面介绍的是处理重排九宫问题时制定启发式函数的原则。2 8 3 1 6 4 5 6 0 7 5 2 8 3 1 2 31 4 3 4 0 8 4 7 6 5 7 6 52 8 31 6 4 5

25、 6 07 5,位置不符将牌,距离总和,二倍将牌逆转数,目标,启发式函数的实现,2 1 3 1 2 38 4 8 47 5 6 7 6 5,目标,九宫问题的目标状态及有两个逆转位置的状态1和2，5和6,下面给出重排九宫问题的两个启发式函数：f1(x)=p(x)+w(x)其中p(x)是x结点和目标结点相比将牌不相符的数目，w(x)是结点x和目标结点相比每个将牌的距离之和。,启发式函数的实现,f2(x)=p(x)+3s(x)其中p(x)是x结点和目标结点相比每个将牌“离家”的最短距离之和；s(x)是这样计算的：每个将牌和目标相比，若该将牌的后继和目标中该将牌的后继不同，则该将牌得2分，相同则该将牌

26、得0分，中间位置有将牌得1分，没将牌得0分。显然f2(x)的启发强度要比f1(x)大。对于给定的格局和目标请大家按两种启发式函数给出搜索的状态空间图。2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5,初始状态,目标状态,博弈树的启发式搜索策略,下棋、打牌、战争等竞争性智能活动称为博弈。其中最简单的一种称为二人零和非偶然性全信息博弈。所谓二人零和、全信息非偶然性搏弈是指：（1）对垒的双方A、B轮流采取行动，博弈的结果只有三种情况：A胜，B败；B胜A败；和局。（2）对垒的双方都了解当前的格局和过去的历史。（3）任何一方在采取行动之前，都要根据当前的实际情况进行得失分析，选取对自己最为

27、有利而对对方最不利的对策，不存在碰运气的偶然因素。,博弈树的启发式搜索策略,在博弈过程中，任何一方都希望自己获得胜利。因此，在A方有多个行动方案可供选择时，他总是选对自己有利而对B方不利的方案，站在A方的立场看问题，供A方选择的方案之间是一种或的关系，因为主动权操在A方的手里，他或者选择这个方案或这者选择另一个方案。但是，若B方也有可供选择的若干方案，则对A方来说这些方案之间是与的关系，因为这时主动权操在B手里，这些可供选择的方案中任何一个都可能被B选中，A方必须考虑到对自己最不利的情况发生。站在任何一方的立场上画出来的博弈树都是一棵与或结点交替产生的与/或树称为博弈树。,博弈树的启发式搜索策

28、略,博弈树的特点如下：（1）博弈的初始格局是初始结点。（2）在博弈树中“或”结点和“与”结点是逐层交替出现的。自己一方扩展的结点之间是或关系，对方扩展结点之间是与关系。双方轮流扩展结点。（3）所有使自己获胜的终局都是本原问题，相应的结点是可解结点；所有使对方获胜的终局都是不可解结点。,博弈树的启发式搜索策略,极大极小分析法：在二人博弈问题中，为了从众多可供选择的方案中选出一个对自己有利的行动方案就需要对当前情况及将要发生的情况进行分析，从中选出最优者。最常用的方法是极大极小分析法。其基本思想是：（1）设博弈的一方是A，另一方是B。极大极小分析就是为其中的一方（例如A方）寻找最优行动方案的方法。

29、（2）为了找到当前的最优行动方案，需要对各个方案可能产生的后果进行比较。具体地说就是，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。,博弈树的启发式搜索策略,（3）计算得分，需要根据问题的特性信息定义一个估计函数，用来估算当前博弈树端结点的得分。此时估算出来的得分称为静态估值。（4）当端结点的估值计算出来后，再推算父结点的得分。推算的方法是对“或”结点，选其子结点中最大的得分作为父结点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”结点，选其子结点中一个最小的得分作为父结点的得分，这是立足于最坏的情况。这样计算出来的父结点的得分称为倒退估值。（5）

30、如果一个行动方案能获得较大的倒退估值，则它是当前最好的方案。,博弈树的启发式搜索策略,在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会产生十分庞大的博弈树，例如，西洋跳棋完整的博弈树约有1040 个结点。试图用完整的博弈树来进行极大极小分析是很困难的。可行的办法是生成一定深度的博弈树，然后进行极大极小化分析找出当前最好的行动方案。如此进行下去，直到找到胜败的结果为止。每次生成博弈树的深度，根据实际情况而定。下面是一个比较简单的二人零和全信息非偶然性博弈的例子。,博弈树的启发式搜索策略例：一字棋游戏，在一个3*3的方格棋盘中，由A、B两人对弈，轮到谁走棋谁就往空格上放上自己的一只棋子，

31、谁先使自己的棋子构成三子一线，谁就取得了胜利。设A的棋子用a表示，B的棋子用b表示，假设每次仅扩展两层。估计函数定义如下：设棋局为P，估计函数为e(P)(1)若P是A必胜的棋局，则e(P)=+（2）若P是B必胜的棋局，则e(P)=-（3）若P是胜负未定的棋局，则e(P)=e(+P)-e(-P)其中，e(+P)表示棋局P上有可能使a成为三子一线的数目。e(-P)表示棋局P上有可能使b成为三子一线的数目。,博弈树的启发式搜索策略例如对于右面的棋局：b e(P)=6-4=2 a 假定具有对称性的两个棋局算作一个棋局，还假定A先走棋我们站在A的立场上。下图给出了A的第一招走棋生成的博弈树。图中结点旁的

32、数字分别表示相应结点的静态估值或倒推值。从图中可以看出对于A来说最好的一着棋是S3，因为S3比S2和S1有较大的倒推值。在A走S3这一着棋后，B的最优选择是S4，因为这一着棋的静态估值较小，对A不利。不管B选择S4或S5，A都要运用极大极小化分析法产生深度为2的博弈树，以决定下一步应该如何走棋，其过程与上面类似。,一字棋,博弈树的启发式搜索,a,S0,S1,S2,S3,a,a,a,b,a,b,a,b,a,b,a,b,1,0,1,0,-1,-1,-2,1,b,a,-1,b,a,0,a,b,a,b,-1,0,a b,-2,b,a,1,S4,b,a,2,S5,最佳走步,一字棋的极大极小搜索,博弈树的

33、启发式搜索,从上面的讨论当中可以看出上面例子中定义的启发式函数考虑的因素太少了，实际上只给出了路的概念（即整行、整列、整对角线），并且没有对一条路上已有几个棋子站位的情况加以区分，仅仅考虑自己站位的情况。下面定义的一个启发式函数就比较精确。为此，引入以下概念：0阶路：一条路上没有任何棋子站位。0阶路即可属于A方也可属于B方，对得分没有影响，在估值时不予考虑。1阶路：如果一条路上仅有A方（或B方）的一个棋子站位，则称是留给A方（或B方）的一阶路。2阶路：如果一条路上仅有A方（或B方）的两个棋子站位，则称是留给A方（或B方）的二阶路。,博弈树的启发式搜索,一个比较好的启发函数h2(n)定义如下：如

34、果n是非终局结点，则A方的静态估值函数是：h2(n)=(A方的一阶路数-B方的一阶路数）+4（A方的二阶路数 B方的二阶路数）+a其中+2 若方出子占了方的阶路 a=-2若方出子占了方的阶路 0 其它,博弈树的启发式搜索例如对下面的格局按h2(n)计算静态估值函数：h2(A)=2 1+4(1-0)+0=5 h2(B)=2 2+4(0-0)+(-2)=-2,b,a,a,A格局,b,a,a,b,B格局,博弈树的启发式搜索请按A方的观点用h2(n)为静态估值函数，给出深度为4的极大极小分析过程。,b,a,a,b,专家系统,专家系统是人工智能应用领域中最活跃的一个分支,自1968年费根鲍姆等人研制成功

35、第一个专家系统DENDRAL以来,应用于医疗诊断、图象处理、石油化工、地质勘探、金融决策、实时监控、分子遗传工程、教学、军事等不同领域中的专家系统就象雨后春笋般涌现出来。成功的专家系统不仅取得了极大的社会效益和经济效益，同时也促进了人工智能基本理论和基本技术的研究和发展。,专家系统,本章将对专家系统的有关概念及建造技术进行讨论，并给出相应的实例。,专家系统（续）,什麽是专家系统？关于专家系统到现在尚没有一个严格的定义，但专家们共识：一个专家系统是一个智能程序系统，它里面应具有大量相关领域专家的知识，它能应用人工智能技术模拟领域专家求解问题的思维过程进行推理，解决相关领域内的困难问题，并且达到甚

36、至超过领域专家的水平。,专家系统（续）,专家系统的分类：按照专家系统求解问题的性质，可以把它分为下列几种类型。1.解释专家系统（expert system for interpretation）解释专家系统的任务是通过对已知信息和数据的分析与解释，确定它们的涵义。解释专家系统具有下列的特点：（1）系统处理的数据量很大，而且往往是不准确的、有错误的、或不完全的。,专家系统（续）,（2）系统能够从不完全的信息中得出解释，并能对数据作出某些假设。（3）系统的推理过程可能很复杂并且很长，因此要求系统具有对自身的推理过程作出解释的能力。作为解释专家系统的例子有语音理解、图象分析、系统监视、化学结构分析和

37、信号解释等。,专家系统（续）,2.预测专家系统（expert system for prediction）预测专家系统的任务是通过对过去和现在已知状况的分析，推断未来可能发生的情况。一个预测专家系统具有下列特点：（1）系统处理的数据随时间变化，而且可能是不准确和不完全的。（2）系统需要有随时间变化的动态模型，能够从不完全和不准确的信息中得出预报，并达到快速响应的要求。预测专家系统的例子有气象预报、军事预测、人口预测、交通预测、经济预测和谷产量预测等。,专家系统（续）,3.诊断专家系统（expert system for diagnosis）诊断专家系统的任务是根据观察到的情况（数据）来推断出某

38、个对象机能失常（即故障）的原因。诊断专家系统具有下列特点：（1）能够了解被诊断对象或客体各组成部分的特性以及它们之间的关系。（2）能够区分一种现象及其所掩盖的另一种现象。（3）能够向用户提出测量的数据，并从不确切信息中得出尽可能正确的诊断。诊断专家系统的例子很多，如医疗诊断，电子机械和软件故障诊断以及材料失效诊断等。用于抗生素治疗的MYCIN、肝功能检验的PUFF、青光眼治疗的CASNET都是国内外颇有名气的实例。,专家系统（续）,4.设计专家系统（expert system for planning）设计专家系统的任务是根据设计要求，求出满足设计问题约束目标的目标配置。一个设计专家系统具有如

39、下的特点：（1）善于从多方面的约束中得到符合要求的设计结果。（2）系统需要检索较大的可能解空间。（3）善于分析各种子问题，并处理好子问题间的相互作用。（4）能够实验性地构造出可能设计，并易对所得设计方案进行修改。（5）能够使用已被证明是正确的设计来解释当前的（新的）设计。,专家系统（续）,设计专家系统涉及电路（如数字电路和集成电路）设计、土木建筑工程设计、计算机结构设计、机械产品设计和生产工艺设计等。5.规划专家系统（expert system for planning）规划专家系统的任务在于寻找出某个能够达到给定目标的动作序列或步骤。规划专家系统的特点如下：（1）所要规划的目标是动态的或静态

40、的，因而需要对未来动作做出预测。（2）所涉及的问题可能很复杂，要求系统能抓住重点，处理好各子目标间的关系和不确定的数据信息，并通过实验性动作得出可行规划。,专家系统（续）,规划专家系统可用于机器人规划、交通运输调度、工程项目论证、通信与军事指挥以及农作物施肥方案规划等。比较典型的规划专家系统的例子有3界3号军事指挥调度系统、REPOS机器人规划专家系统、汽车和火车运行调度专家系统以及小麦和水稻施肥专家系统等。,专家系统（续）,6.监视专家系统（expert system for monitoring）监视专家系统的任务在于对系统、对象或过程的行为进行不断观察，并把观察到的行为与其应当具有的行为

41、进行比较，以发现异常情况，发出警报。监视专家系统具有以下特点：（1）系统具有快速反应能力，在造成事故之前及时发出警报。（2）系统发出的警要有很高的准确性。在需要发警报时发警报在不需要发警报时不得轻易发警报（假警报）（3）系统能随时间和条件的变化而动态地处理其输入信息。监视专家系统可用于核电站的安全监视、防空监视与报警、国家财政的监控、传染病疫情监视及农作物病虫害监视与报警等。,黏虫测报专家系统是监视专家系统的一个实例。7.控制专家系统（expert system for control）控制专家系统的任务是自适应地管理一个受控对象或客体的全面行为，使之满足预期要求。控制专家系统的特点是：能够解

42、释当前的情况，预测未来可能发生的情况，诊断可能发生的问题及其原因，不断修正计划，并控制计划的执行。也就是说，控制专家系统具有解释、预测、诊断、规划和执行等多种功能。空中交通管制、商业管理、自主机器人控制、作战管理、生产过程控制和生产质量控制等都是控制专家系统潜在的应用方面。例如，已经对海、陆、空自主车、生产线调度和产品质量控制等课题进行控制专家系统的研究。,专家系统（续）,专家系统（续）,8.调试专家系统（expert sysytem for debugging）调试专家系统的任务是对失灵的对象给出处理的意见和方法。调试专家系统的特点是同时具有规划、设计、预报和诊断等专家系统的功能。,专家系统

43、（续）,9.教学专家系统（expert system for instruction）教学专家系统的任务是根据学生的特点、弱点和基础知识，以最适当的教案和教学方法对学生进行教学和辅导。教学专家系统的特点是：（1）同时具有调试和诊断功能。（2）具有良好的人机界面。已经开发和应用的教学专家系统有美国麻省理工学院MACSYMA符号积分与定理证明系统，我国一些大学开发的计算机科学相关课程和物理智能计算机辅助教学系统以及聋哑人语言训练专家系统等。,专家系统（续）,10.修理专家系统（expert system for repair）修理专家系统的任务是对发生故障的对象（系统或设备）进行处理，使其恢复正常

44、工作。修理专家系统具有诊断、调试、计划和执行等功能。,专家系统（续）,专家系统的一般特点上面我们已经介绍了各类专家系统的特点，专家系统还有一些共性的特点。1.具有专家水平的专门知识由于专家系统是模拟人类专家解决问题和处理问题方式的智能程序系统，所以它必须具有专家级的知识，能够象专家那样工作。,专家系统（续）,一般来说，专家系统中的知识可分为三个层次，即数据级、知识库级和控制级。数据级知识是指具体问题所提供的初始事实以及问题求解过程中所产生的中间结论、最终结论等。例如，疾病诊断专家系统中患者的症状、化验结果以及由专家系统推出的病因、治疗方案等，这一类知识一般存放在数据库中。知识库级知识是指专家的

45、知识，例如医学常识、书本上的知识和医生诊治疾病的经验等。这一类知识是构成专家系统的基础，一个系统性能的高低取决于这种知识的质量和数量。控制级知识是如何运用前两种知识的知识，如搜索策略就属于这一种。由于控制级知识是用于控制系统的运行过程及推理的，因而其性能的优劣直接关系到系统的智能程度。,专家系统（续）,任何一个专家系统都是面向一个具体领域的，求解的问题仅仅限于一个较窄的范围，因此，专家系统的知识都具有专门性，它可能很精，但只限于所面向的领域，针对性较强。也正因为如此，专家系统能够抓住领域内问题的共性与本质，使系统有较高的可信性与效率。,专家系统（续）,2.能进行有效的推理专家系统的根本任务是求

46、解领域内的现实问题。问题的求解过程是一个思维过程。这要求专家系统必须具有相应的推理机构，能根据用户提供的已知事实，通过运用掌握的知识，进行有效的推理，以实现对问题的求解。由于不同专家系统所面向的领域有所不同，要求解的问题也有很大差别，所以，不同专家系统的推理机制也不尽相同。有的要求进行精确推理，有的要求进行不精确推理、不完全推理以及试探性推理等，需要根据问题领域的特点分别进行设计，以确保问题求解的有效性。,专家系统（续）,3.具有获取知识的能力专家系统的基础是知识。为了得到知识就必须有获取知识的能力。然而令人遗憾的是目前专家系统在这方面的能力还比较弱。当前应用较多的是建立知识编辑器，知识工程师

47、或领域专家通过知识编辑器把领域知识传授给专家系统，以便建立起知识库。,专家系统（续）,4.具有灵活性在大多数专家系统中，其体系结构都采用了知识库与推理机分离的构造原则，彼此既有联系又相互独立。这样做的好处是，既可在系统运行时能根据具体问题的不同要求分别选取合适的知识构成不同的求解序列，实现对问题的求解，又能在一方进行修改时不致影响到另外一方。特别是对于知识库，随着系统的不断完善，可能要经常对它进行增、删、改操作，由于它与推理机分离，这就不会因知识库的变化而要求修改推理机的程序。,专家系统（续）,另外，由于知识库与推理机分离，就有可能使一个技术上成熟的专家系统变为一个专家系统工具，这只要抽去知识

48、库中的知识，就可使它变为一个专家系统外壳。当要建立另外一个其功能与之类似的专家系统时，只要把相应的知识装入到该外壳的知识库中即可，这样将大大节省开发的时间。事实上，所谓专家系统开发工具就是这样得来的。例如，由专家系统MYCIN得到的构造工具EMYCIN，由PROSPECTOR得到的专家系统外壳KAS等。,专家系统（续）,5.具有透明性所谓一个计算机程序系统的透明性是指，系统自身及其行为能被用户所理解。专家系统具有较好的透明性，这是因为它具有解释功能。人们在应用专家系统求解问题时，不仅需要得到正确的答案，而且还希望知道得出该答案的依据，也就是希望系统说明为什麽是这样？是怎麽得出来的等。为此，专家

49、系统都设置了解释机构，用于向用户解释它的行为动机及得出某些推理答案的过程。解释系统的设置不仅增加了用户对系统的可信度和系统的透明度，而且能帮助系统设计者和领域专家方便地找出系统隐含的错误，便于对系统的维护。,专家系统（续）,6.具有交互性专家系统一般都是交互式系统。一方面它需要与领域专家或知识工程师进行对话以获取知识，另一方面它需要与用户对话以索取求解问题时所需要的已知事实以及回答用户的询问。专家系统的这一特征为用户提供了方便，亦是它得以广泛应用的原因之一。,专家系统（续）,7.具有实用性专家系统是根据领域问题的实际需求开发的，这一特点就决定了它具有坚实的应用背景。另外，专家系统拥有大量高质量

50、的专家知识，可使问题求解达到较高的水平，再加上它所具有的透明性、交互性等特征，就使得它容易被人们接受和应用。事实证明，专家系统已经被用于多种领域中，取得了巨大的经济效益和社会效益。,专家系统（续）,8.具有一定的复杂性及难度专家系统拥有知识，并能运用知识进行推理，以模拟人类求解问题的思维过程。但是，人类的知识是丰富多彩的，人们的思维方式也是多种多样的，因此要真正实现对人类思维的模拟还是一件十分困难的工作，有赖于其它多种学科的共同发展。从这个意义上说，专家系统的发展也必然促进其它学科的发展。专家系统是一个智能程序系统，它和一般的程序系统有什麽区别呢？,专家系统（续）,（1）常规的计算机程序是对数