搜索与求解-人工智能导论课件.ppt

《搜索与求解-人工智能导论课件.ppt》由会员分享，可在线阅读，更多相关《搜索与求解-人工智能导论课件.ppt（150页珍藏版）》请在三一办公上搜索。

1、1,第 2 章 搜 索,2,本章知识结构,3,本章学习要点,理解搜索及回溯的概念，掌握启发式搜索和盲目搜索的概念；掌握宽度优先搜索算法和深度优先搜索算法，并了解二者的区别；了解A*算法。,4,主 要 内 容,2.1 搜索概述2.2 状态空间搜索2.3 状态空间盲目搜索2.4 状态空间启发式搜索2.5 代价树的搜索2.6 与/或树搜索2.7 博弈树的启发式搜索,5,2.1 搜索的概述,现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法，而只能利用已有知识一步一步摸索前进。根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过

2、程，就称为搜索。,6,搜索的含义：,搜索包含两层含义：（1）要找到从初始事实到问题最终答案的一条推理路线；（2）找到的这条路线是时间和空间复杂程度最小的求解路线。,7,搜索的基本技术：,搜索是人工智能技术中进行问题求解的基本技术，也是人工智能中的一个核心技术，是推理不可分隔的一部分，它直接关系到智能系统的性能和运行效率。人工智能进行问题求解的两种基本技术：图搜索 搜索算法,8,（1）图搜索,运用领域知识，以符号推演的方式，顺序地在问题空间进行搜索。其中的问题空间表示为某种状态图（空间）或与或图的形式。该方法模拟人脑分析问题。,9,（2）搜索算法,以计算的方法，随机地在问题的解空间中进行搜索。该

3、方法是借鉴或模拟自然现象或生命现象。,10,搜索的类型：,根据搜索过程中是否使用启发式信息，可以把搜索的类型分为两种：盲目搜索（无信息搜索）启发式搜索（有信息搜索）,11,（1）盲目搜索,指在搜索过程中，按照原来规定的搜索策略进行搜索，而没有加入任何中间信息来改变这些控制策略。搜索带有盲目性、效率低。该方法通常只用于解决比较简单的问题。,12,（2）启发式搜索,指在搜索过程中，根据问题本身的特性或一些在搜索过程中产生的信息来不断修改或调整搜索的方向，是搜索向着最有利的方向前进，加快问题求解的速度，并找到最优解。该方法是更易于求解复杂的问题。,13,主 要 内 容,2.1 搜索概述2.2 状态空

4、间搜索2.3 状态空间盲目搜索2.4 状态空间启发式搜索2.5 代价树的搜索2.6 与/或树搜索2.7 博弈树的启发式搜索,14,Sg,内容：状态空间的搜索问题 搜索策略：盲目搜索启发式搜索关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。,S0,2.2 状态空间搜索,15,讨论的问题：如何用状态空间法表示问题和问题的求解过程？使用状态空间法求解问题的具体过程如何？,16,【准备知识1：状态空间定义】（参见教材62页）,状态：描述问题求解过程中不同时刻状况的数据结构。一般用一组变量的有序集合表示：Q=(q0,q1,q2,qn)算符（操作）：引起状态中某些分量发生变化，从而使问题由一个

5、状态变为另一个状态的操作。,17,状态空间,由表示一个问题的全部状态及一切可用算符构成的集合称为该问题的状态空间。状态空间可以用空间三元组(S,F,G)表示：S-问题初始状态的集合F-操作或算符的集合G-目标状态的集合 状态空间的图示形式称为状态空间图。其中的节点表示状态，有向边（弧）表示算符。,18,【状态空间的例子1迷宫问题】,以例3.1中的迷宫为例。我们以每个格子作为一个状态,并用其标识符作为其表示。那么,两个标识符组成的序对就是一个状态转换规则。于是,该迷宫的状态空间表示为,S：SoF：(So,S4),(S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S

6、2,S3),(S3,S2),(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S6),(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)G：Sg,19,迷宫问题的空间状态图为：,20,问题求解,从问题的初始状态集Qs出发，经过一系列的算符运算，到达目标状态Qg。该过程中所用算符的序列f构成问题的一个解。QsS,QgG,算子序列f：f=f1,f2,fn 使得 Qg=fn(f2(f1(Qs),21,【问题求解的例子-八数码难题】,在3*3的方格棋盘上，分别放置了标有数字1、2、3、4、5、6、7、8的八张牌，初始状态So,目标状态为

7、Sg。操作规则是：与空格相邻的数码可通过左移、上移、下移、右移来移入空格。,初始状态So,目标状态Sg,22,状态转移-规则,数码上移,23,路径-状态序列搜索-寻找从初始状态到目标状态的路径;,24,状态空间,25,难点,可用操作冲突如何消解？,如何搜索到最优解？,26,【状态空间及问题求解的例子梵塔问题】(P64),设有三根宝石杆,在1号杆上穿有A、B两个金盘,A小于B,A位于B的上面。要求把这两个金盘全部移到另一根杆上,而且规定每次只能移动一个盘子,任何时刻都不能使B位于A的上面。,27,设用二元组(SA,SB)表示问题的状态,SA表示金盘A所在的杆号,SB表示金盘B所在的杆号,这样,全

8、部可能的状态有9种,可表示如下：(1,1),(1,2),(1,3)(2,1),(2,2),(2,3)(3,1),(3,2),(3,3),28,二阶梵塔的全部状态,29,这里的状态转换规则就是金盘的搬动规则，分别用A(i,j)及B(i,j)表示：A(i,j)表示把A盘从第i号杆移到第j号杆上;B(i,j)表示把B盘从第i号杆移到第j号杆上。经分析，共有12个操作，它们分别是：,A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2),30,由这9种可能的状态和12种操作,二阶梵塔问题的状态

9、空间图如图所示：,31,小 结,使用状态空间表示法表示问题时：首先定义状态的描述形式，并使用这种描述形式把问题的状态全部表示出来；其次定义一组操作，通过使用这些操作把问题从一种状态变为另一种状态。问题的求解过程实际是一个不断操作作用于状态的过程。如果使用某种操作得到的新状态就是目标状态，就得到了问题的一个解。这个解是从问题初始状态到目标状态的操作序列。,32,课 堂 练 习 题,设有三只琴键开关一字排开,初始状态为“关、开、关”,问连按三次后是否会出现“开、开、开”或“关、关、关”的状态？要求每次必须按下一个开关,而且只能按一个开关。请画出状态空间图。【注：琴键开关有这样的特点,若第一次按下时

10、它为“开”,则第二次按下时它就变成了“关”。】,33,【准备知识2：状态图搜索方式】（参见教材50页）,树式搜索 在搜索过程中记录所经过的所有节点和边，记录轨迹为一棵“树”。线式搜索 在搜索过程中只记录那些当前认为处在所找路径上的节点和边，记录轨迹是一条“线”（折线）。,34,【准备知识3：状态图搜索策略】（参见教材51页）,盲目搜索策略 就是无“向导”的搜索。启发式搜索策略 就是有“向导”的搜索。,35,【准备知识4：状态图搜索基本概念】,节点深度：根节点深度=0；其它节点深度=父节点深度+1。,0,2,36,路径 设一节点序列为(n0,n1,nk)，对于 i=1,k，若节点ni-1具有一个

11、后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。,37,扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。,38,2.2.1 状态空间搜索的一般过程,状态空间搜索实际上就是对有向图的搜索。先把问题的初始状态当作当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了该问题的解；若没有出现，则按照某种搜索策略从已生成的子节点中选择一个作为当前扩展节点。重复上述过程，直到目标状

12、态出现在子节点中或没有可供扩展的节点为止。,39,2.2.2 状态空间图搜索的一般算法（参见教材P51）,Open表用于存放还没有扩展的节点，因此，Open表称为未扩展的节点表。Closed表用于存放已经扩展或将要扩展的节点，因此，Closed称为已扩展的节点表。用S0表示问题的初始状态，G表示搜索过程所得到的搜索图，M表示当前扩展节点新生成的且不为自己先辈的子节点集。,40,1.G=G0(G0=s0),OPEN:=(s0);%建立一个只有起始节点S0组成的图G,把S0放到OPEN表中；2.CLOSED:=();%建立一个CLOSED表，置为空；3.LOOP:IF OPEN=()THEN EX

13、IT(FAIL);%判断OPEN表是否为空,若为空,则问题无解,退出;4.n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);%从OPEN表中取出第一个节点n放入CLOSED表。5.IF GOAL(n)THEN EXIT(SUCCESS);%如果n是目标节点，成功结束；6.EXPAND(n)mi,G:=ADD(mi,G);%扩展节点n,后继节点记为M=mi，把M加入G中；,41,7.标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8.对OPEN中的节点按某种原则重新排序

14、；9.GO LOOP；,42,状态空间一般搜索流程图,43,修改返回指针,原有返回指针：DCBS0修改后返回指针：DAS0,44,修改指针举例,指针返回路径：423BAS0,B,A,45,原有指针返回路径：423BAS0修改后指针返回路径：46DCS0,46,原有指针返回路径：46DCS0修改后指针返回路径：421S0,47,搜索图,在搜索过程中，生成一个图G，它是问题状态空间图的一部分。,48,搜索树：,由搜索图G中所有节点及指向父节点的反向指针所构成的集合。,49,主 要 内 容,2.1 搜索概述2.2 状态空间搜索2.3 状态空间盲目搜索2.4 状态空间启发式搜索2.5 代价树的搜索2.

15、6 与/或树搜索2.7 博弈树的启发式搜索,50,2.3 状态空间盲目搜索(参见教材53页),在搜索过程中，只按预定的搜索控制策略进行搜索，没有任何中间信息来改变搜索控制策略。由于问题本身的特性对搜索控制策略没有任何影响，使得这样的搜索带有盲目性，效率不高。只适用于解决比较简单的问题。,51,盲目搜索的方法：,主要的盲目搜索方法有：宽度(广度)优先搜索 深度优先搜索 有界深度优先搜索,52,2.3.1 宽度优先搜索(Breadth-first Search),又称为广度优先搜索，是一种盲目搜索策略。宽度优先搜索的基本思想是：从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n

16、层的节点没有全部扩展并考察之前，不对第n1层的节点进行扩展。OPEN表中的节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。,53,1.G:=G0(G0=s),OPEN:=(s),CLOSED:=();2.LOOP:IF OPEN=()THEN EXIT(FAIL);3.n:=FIRST(OPEN);4.IF GOAL(n)THEN EXIT(SUCCESS);5.REMOVE(n,OPEN),ADD(n,CLOSED);6.EXPAND(n)mi,G:=ADD(mi,G);7.IF 目标在mi中 THEN EXIT(SUCCESS);8.ADD(OPEN,mj),并标记

17、mj 到 n 的指针;9.GO LOOP;,宽度优先搜索算法,54,宽度优先搜索算法流程图,节点n可扩展吗？,回溯求解路径,N,Y,55,2 31 8 47 6 5,1,2,5,6,7,3,目标点,8,4,9,【例】宽度优先求解八数码问题,10,11,12,13,14,15,16,17,解路径：S03817,起始点,56,宽度优先搜索的性质,当问题有解时，一定能找到解搜索效率较低方法与问题无关，具有通用性搜索得到的解是搜索树中路径最短的解（最优解）属于完备搜索策略,57,2.3.2 深度优先搜索(Depth-first Search),在深度优先搜索中，首先扩展最新产生的(即最深的)节点。深度

18、相等的节点可以任意排列。,58,深度优先搜索的基本思想,从初始节点S0开始扩展，若没有得到目标节点，则选择最后产生的子节点进行扩展，若还是不能到达目标节点，则再对刚才最后产生的子节点进行扩展，一直如此向下搜索。当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行考察。,59,深度优先搜索算法：,1.G:=G0(G0=s),OPEN:=(s),CLOSED:=();2.LOOP:IF OPEN=()THEN EXIT(FAIL);3.n:=FIRST(OPEN);4.IF GOAL(n)THEN EXIT(SUCCESS);5.REMOVE(n,OPEN),ADD(n

19、,CLOSED);6.EXPAND(n)mi,G:=ADD(mi,G);7.ADD(mj,OPEN),并标记mj到n的指针;8.GO LOOP;,60,深度优先搜索算法流程图,节点n可扩展吗？,回溯求解路径,N,Y,61,2 31 8 47 6 5,1,2,3,4,目标,例深度优先求解八数码问题,解路径：S0234,62,深度优先搜索的性质,一般不能保证找到最优解最坏情况时，搜索空间等同于穷举是一个通用的与问题无关的方法,63,深度优先搜索不完备问题,为了解决深度优先搜索不完备问题，避免搜索过程陷入无穷分支的死循环，提出了有界深度优先搜索方法。,64,2.3.3 有界深度优先搜索,有界深度优先

20、搜索的基本思想是：对深度优先搜索方法引入搜索深度的界限（设dm），当搜索深度达到了深度界线，而尚未出现目标节点时，就换一个分支进行搜索。,65,有界深度优先搜索算法：,1.G:=G0(G0=s),OPEN:=(s),CLOSED:=();2.LOOP:IF OPEN=()THEN EXIT(FAIL);3.n:=FIRST(OPEN);4.IF GOAL(n)THEN EXIT(SUCCESS);5.REMOVE(n,OPEN),ADD(n,CLOSED);6.IF DEPTH(n)Dm GO LOOP;(有界深度限制）7.EXPAND(n)mi,G:=ADD(mi,G);8.IF 目标在mi

21、中 THEN EXIT(SUCCESS);9.ADD(mj,OPEN),并标记mj到n的指针;10.GO LOOP;,66,有界深度优先搜索算法流程图,节点n可扩展吗？,N,Y,节点n的深度=dm?,Y,N,67,有界深度优先搜索的性质,不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制是不完备搜索,深度界限dm的选择很重要！,68,小 结,深度优先搜索与宽度优先搜索的区别,69,70,课 堂 练 习 题,对于如图所示的状态空间图，请给出宽度优先搜索和深度优先搜索的OPEN表和CLOSED表的变化情况。（假设N为目标状态）,H,71,主 要 内 容,2.1 搜索概述

22、2.2 状态空间搜索2.3 状态空间盲目搜索2.4 状态空间启发式搜索2.5 代价树的搜索2.6 与/或树搜索2.7 博弈树的启发式搜索,72,2.4 状态空间启发式搜索(参见教材56页),2.4.1 概述,定义：利用问题自身特性信息来提高搜索效率的搜索策略，称为启发式搜索或有信息搜索。可用于指导搜索过程且与具体问题求解有关的控制信息称为启发信息。,73,启发信息的分类：,按其用途划分,启发性信息可分为以下三类：(1)用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展。(2)用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。(3)用于删除节点的选择,即用

23、于决定应删除哪些无用节点,以免造成进一步的时空浪费。,74,引入启发信息的目的：,引入启发信息，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。启发信息的强度强：降低搜索工作量，但可能导致找不到最优解。弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。,75,估价函数（教材P60）,我们将要介绍的启发式搜索算法中，采用的启发式信息属于第一种，即决定哪个节点是下一步要扩展的节点。通常构造一个函数来表示节点要扩展的“希望”程度，称这种函数为估价函数。估价函数的任务就是估计待搜索节点的重要程度，给它们排定次序。,76,估价函数的一般形式：f(x)=g(x)+h(x),

24、已经付出的代价,将要付出的代价,启发函数！,估价函数是针对具体问题构造的，与问题特性密切相关。在构造估价函数时，启发函数h(x)的构造尤为重要。,代价函数！,77,2.4.2 启发式搜索策略,最佳优先搜索又称为有序搜索或择优搜索，它总是选择最有希望的节点作为下一个要扩展的节点，而这种最有希望的节点是按估价函数f(x)的值来挑选的。一般估价函数值越小，它的希望程度越大。最佳优先搜索分为两种：局部择优搜索 全局择优搜索,78,（1）局部择优搜索,当对某以节点扩展之后，对其每一个后继节点计算估价函数f(x)的值，并在这些后继节点的范围内，选择一个f(x)最小的节点作为下一个要考察的节点。它每次只在后

25、继节点的范围内选择下一个要考察的节点，范围比较小，所以称为局部择优搜索。,79,局部择优搜索算法流程图,节点n可扩展吗？,N,Y,为每个后继节点设置指向节点n的指针,80,（2）全局择优搜索,在确定下一个扩展节点时，在OPEN表中全部节点中选择一个估价函数f(x)值最小的节点作为下一个要考察的节点。它每次选择的范围是OPEN表中的全部节点，所以称为全局择优搜索。,81,全局择优搜索算法流程图,节点n可扩展吗？,N,Y,把后继节点送入OPEN表,对其中的所有节点按估价函数值从小到大排序,82,例 全局最佳优先求解八数码问题（教材P57）,解路径：S0S1S2S3Sg,83,2.4.3 A算法,一

26、种基于估价函数f(x)的加权状态图启发式搜索算法。,84,A算法流程图,节点n可扩展吗？,N,Y,把后继节点送入OPEN表,对其中的所有节点按估价函数值从小到大排序,85,A算法（加权状态图启发式搜索算法）,1.OPEN:=(s),f(s):=g(s)+h(s);2.LOOP:IF OPEN=()THEN EXIT(FAIL);3.n:=FIRST(OPEN);4.IF GOAL(n)THEN EXIT(SUCCESS);5.REMOVE(n,OPEN),ADD(n,CLOSED);6.EXPAND(n)mi,计算f(n,mi):=g(n,mi)+h(mi);,86,ADD(mj,OPEN),

27、标记mj到n的指针；IF f(n,mk)f(mk)THEN f(mk):=f(n,mk),标记mk到n的指针；IF f(n,ml)f(ml,)THEN f(ml):=f(n,ml),标记ml到n的指针;ADD(ml,OPEN);7.OPEN中的节点按f值从小到大排序；8.GO LOOP；,87,A算法的例子,定义估价函数：f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的耗散值（节点深度）h(n)为当前节点“不在位”的将牌数,2 8 31 6 47 5,1 2 38 47 6 5,88,“不在位”的将牌数h(n)=4,2 8 31 6 47 5,1 2 3,45,7 6,8,h(n)

28、的计算举例,89,G(3+3),90,2.4.4 A*算法,A*算法也是一种启发式搜索方法，对A算法中的扩展节点的选择方法做了一些限制，选用了一个比较特殊的估价函数。这时的估价函数f(x)=g(x)+h(x)是对下列函数 f*(x)=g*(x)+h*(x)的一种估计或近似。即：f(x)是对f*(x)的一种估计；g(x)是对g*(x)的估计；h(x)是对h*(x)的估计。,91,在A算法中，如果要求启发函数h(x)是h*(x)的下界，即对任意节点x均满足条件：h(x)h*(x)则A算法称为A*算法。,保证A*算法找到最优解！,92,1.可采纳性：若存在从初始节点s0到目标节点g有路径存在，则A*

29、算法必能在有限步内找到最佳解结束。2.单调性：如果对A*算法中的h(x)加以适当的单调性限制条件，就可以使它对所扩展的一系列节点的估价函数值单调递增（或非递减），从而减少对OPEN表或CLOSED表的检查和调整，提高搜索效率。,A*算法的性质,93,3.信息性：A*算法的搜索效率主要取决于启发函数h(x)，h(x)的值越小，表明它携带的与求解问题相关的启发信息越多，搜索效率就越高。,94,状态图搜索策略小结,重点掌握哦！,95,主 要 内 容,2.1 搜索概述2.2 状态空间搜索2.3 状态空间盲目搜索2.4 状态空间启发式搜索2.5 代价树的搜索2.6 与/或树搜索2.7 博弈树的启发式搜索

30、,96,2.5.1 代价树概念（参见教材58页）,前面讨论的各种搜索策略，都是假设状态空间中各边的代价都相同，且都为一个单位量。但在实际问题中，这种假设是不现实的。例如城市交通问题，各城市间的距离是不同的。在搜索树中给每条边都标上其代价，这种标有代价的树称为代价树。,97,旅行交通加权状态图,旅行交通代价树,98,显然,加权状态图的搜索与权值有关,并且要用权值来导航。具体来讲,加权状态图的搜索算法,要在一般状态图搜索算法基础上再增加权值的计算与传播过程,并且要由权值来确定节点的扩展顺序。,99,所谓代价,可以是两点之间的距离、交通费用或所需时间等等。通常用：g(x)-表示从初始节点So到节点x

31、的代价；c(xi,xj)-表示父节点xi到子节点xj的代价,即边(xi,xj)的代价。从而有：,g(xj)g(xi)c(xi,xj),而g(S0)0,100,在代价树中，最小代价路径和最短路径是有可能不同的。代价树搜索的目标是找到一条代价最小的解路径。,101,其基本思想是：每次从OPEN表中选出g(x)值最小的节点,移入CLOSED表。因此，每当对一节点扩展之后，就要计算其所有后继节点的代价，并将它们与OPEN表中已有的待扩展的节点按代价的大小从小到大依次排序，选择排在最前面的节点（代价最小）进行扩展。,2.5.2 分支界限法(最小代价优先法),102,【代价树的搜索例子-城市交通问题】,最

32、优路径：ACDE最优路径的代价为：3+2+3=8,103,与代价树的分支界限法搜索的区别在于，每次选择最小代价节点的方法不同。最近择优搜索是从刚扩展的子节点中选择一个代价最小的节点。,2.5.3 最近择优法(瞎子爬山法),104,【代价树的搜索例子-城市交通问题】,最优路径：ACDE最优路径的代价为：3+2+3=8,105,课 堂 练 习 题,如图所示5个城市之间的交通路线图，A城市为出发地，E城市目的地，两个城市之间的交通费用如图中的数字，求从A到E的最小费用交通路线。,106,主 要 内 容,2.1 搜索概述2.2 状态空间搜索2.3 状态空间盲目搜索2.4 状态空间启发式搜索2.5 代价

33、树的搜索2.6 与/或树搜索2.7 博弈树的启发式搜索,107,与或树是不同于状态空间法的另外一种用于表示问题及其求解过程的形式化方法，通常用于表示比较复杂的问题求解。在求解比较复杂问题的时候，人们通常会将复杂问题分解或转化为一系列本原问题，然后通过对本原问题的求解来实现对原问题的求解。这种把一个复杂问题分解或变换为一组本原问题的过程称为归约。,108,2.6.1 与或树概念（参见教材73页）,本原问题：指那种不能（或不需要）再进行分解或变换，且可以直接解答的子问题。问题的分解和“与树”：把一个复杂问题分解为若干个子问题时，可以用一个“与树”来表示这种分解。3.问题的变换和“或树”：把一个复杂

34、的问题变换为若干个与之等价的新问题时，可用一个“或树”来表示这种变换。,109,4.与/或树：如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，则其求解过程可用一个“与/或树”表示。,110,5.可解节点与不可解节点：在与/或树中，满足以下条件之一的节点称为“可解节点”：该节点是一个终止节点；该节点是一个“或”节点，且其子节点中至少有一个为可解节点；该节点是一个“与”节点，且其子节点中全部为可解节点。,111,在与/或树中，满足以下条件之一的节点称为“不可解节点”：该节点是一个端节点，但却不是终止节点；该节点是一个“或”节点，但其子节点中没有一个是可解节点；该节点是一个“与”节点，

35、且其子节点中至少有一个为不可解节点。,112,6.解树：一个由可解节点构成，并且可由这些可解节点推出初始节点（对应原始问题）的子树。,113,2.6.2 与或树的树式搜索,与状态图的树式搜索类似。步骤如下：Setp1:把初始节点S0放入Open表中；Setp2:把Open表的第一个节点取出放入Closed表中，并记该节点为节点n；,114,Setp3:若节点n可扩展，则做下列工作：扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针；考察这些子节点是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点或先辈节点中可解节点进行标记。如初始节点S

36、0被标记为可解节点，得到解树，成功退出。如不能确定S0为可解节点，则从Open表中删除具有可解先辈的节点；转第2步,115,Step4:如果节点不可扩展，则做下列工作：标记节点n 为不可解节点；用不可解标记过程对节点n的先辈节点中不可解节点进行标记。如初始节点S0被标记为不可解节点，原问题无解而失败退出。如不能确定S0为不可解节点，则从Open表中删除具有不可解先辈的节点；转第2步,116,【例】与或树广度优先搜索,117,2.6.3 与或树的启发式搜索,解树的代价,最优解树是指代价最小的那棵解树。“终止节点”代价为0“或节点”代价取其子节点中的最小值“与节点”有和代价法与节点代价最大值法；“

37、不可解节点”代价“根节点”的代价为解树的代价,118,【解树的代价实例1】,如图所示一棵与/或树，已知节点S4、S5、S9、S12、S13是本原问题，边上的数字是操作的代价。试求：（1）按和代价法发求出最优解树；（2）按最大代价法求出最优解树。,119,和代价法计算解树代价：,左边解树：HL(S1)=10,右边解树：HR(S1)=8,120,最大代价法计算解树代价：,左边解树：HL(S1)=6,右边解树：HR(S1)=7,121,【解树的代价实例2】,g(n0)=C(n0,n1)+g(n1)=1+g(n1)=1+C(n1,n3)+g(n3)=1+1+g(n3)=1+1+2+g(n5)+g(n6

38、)=1+1+2+1+g(n6)+g(n6)=1+1+2+1+2+g(n7)+g(n8)+g(n6)=1+1+2+1+2+g(n6)=1+1+2+1+2+2+g(n7)+g(n8)=1+1+2+1+2+2=9,122,【课堂练习】求解树的代价,图（a）,已知n7、n8为本原节点。,123,图（b）,图（c）,已知n7、n8为本原节点。,124,希望树,为找到最佳解树，搜索过程的任何时刻都应该选择那些最有希望成为最佳解树一部分的节点进行扩展。由于这些节点及其父节点所构成的与/或树最有可能成为最佳解树的一部分，因此称之为希望树。希望树主要是针对“或节点”而言。希望树会随着搜索过程而不断变化。,125

39、,【希望树定义】初始节点S0在希望树T中；如果节点x在希望树T中，则一定有：（1）如果x是具有子节点y1,y2,yk的”或”节点，则具有minc(x,yi)+g(yi)(i=1,2,n)值的那个子节点yi也应在T中；（2）如果x是”与”节点，则x的全部子节点都在希望树T中。,126,与/或树的启发式搜索算法（AO*算法）,与/或树的启发式搜索算法也称为AO*算法。与/或树的启发式搜索需要不断地选择、修正希望树,127,AO*算法,利用h(x)探索求解。分为两个过程：,图生成过程，即扩展节点从最优的局部图中选择一个节点扩展计算耗散值的过程对当前的局部图重新计算代价值,128,【AO*算法举例】,

40、已知其中：h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0,129,黑色：g(n0)=(1+1)+(1+1)=4 蓝色：g(n0)=1+2=3,n0,n1(2),n4(1),n5(1),h(n1)=2,h(n2)=4,h(n3)=4,h(n4)=1,h(n5)=1,h(n6)=2,h(n7)=0,h(n8)=0,130,黑色：g(n0)=2+2=4蓝色：g(n0)=1+5=6,h(n1)=2,h(n2)=4,h(n3)=4,h(n4)=1,h(n5)=1,h(n6)=2,h(n7)=0,h(n8)=0,131,黑色：

41、g(n5)=min(3,2)=2g(n0)=1+g(n5)+1+g(n4)=5 蓝色：1+5=6,3,132,初始节点,n0,n4(1),n5(1),n1,n2(4),n3(4),5,2,1,3,绿色：g(n5)=min(3,2)=2g(n4)=0+1=1g(n0)=1+g(n5)+(1+g(n4)=5 蓝色：1+5=6,133,主 要 内 容,2.1 搜索概述2.2 状态空间搜索2.3 状态空间盲目搜索2.4 状态空间启发式搜索2.5 代价树的搜索2.6 与/或树搜索2.7 博弈树的启发式搜索,134,2.7 博弈树搜索（参见教材81页）,博弈问题 双人 一人一步 双方信息完备 零和,135

42、,2.7.1 博弈树的概念,（1）双人完备信息博弈原理双方都希望自己能够获胜，任何一方走步时，都选择自己最为有利而对方不利的行动方案。假设博弈双方分别为A、B，在A走步时，可供自己走的所有方案是“或”关系，而估计对方走步时，B的所有的可走方案之间是“与”关系，A必须防止那种对自己最为不利的情况发生。,136,（2）博弈树：若把双人完备信息博弈过程用图表示出来，就可得到一棵与/或树，这种与/或树被称为博弈树。（3）博弈树的特点：“与”、“或”节点逐层交替出现的整个博弈过程始终站在某一方的立场上,137,2.7.2 博弈树的启发式搜索,在二人博弈问题中,为了从众多可供选择的行动方案中选出一个对自己

43、最为有利的行动方案,就需要对当前的情况以及将要发生的情况进行分析,从中选出最优的走步。最常使用的分析方法是极小极大分析法。,138,MAX/MIN搜索算法的基本思想,(1)设博弈的双方中一方为A，另一方为B。然后为其中的一方(例如A)寻找一个最优行动方案。(2)为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较,具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。(3)为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。,139,(4)当端节点的估值计算出来后,再推算出父节点的得分,推算的

44、方法是：对“或”节点,选其子节点中一个最大的得分作为父节点的得分,这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点,选其子节点中一个最小的得分作为父节点的得分,这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。(5)如果一个行动方案能获得较大的倒推值,则它就是当前最好的行动方案。,140,【倒推值的计算实例】,“或节点”-取极大值“与节点”-取极小值,141,中国象棋,一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不可能穷举。试图利用完整的博弈树来进行极小极大分析是困难的。可行的办法是只生成一定深度的博弈树

45、,然后进行极小极大分析,找出当前最好的行动方案。,142,【一字棋的极大极小搜索】,143,极小极大过程,1,极大,极小,a,b,144,2.7.3 博弈树的-剪枝技术,上述的极小极大分析法,实际是先生成一棵博弈树,然后再计算其倒推值。这样做的缺点是效率较低。于是,人们又在极小极大分析法的基础上,提出了-剪枝技术。,145,-剪枝技术的基本思想,边生成博弈树边计算评估各节点的倒推值,并且根据评估出的倒推值范围,及时停止扩展那些已无必要再扩展的子节点,即相当于剪去了博弈树上的一些分枝,从而节约了机器开销,提高了搜索效率。,146,(1)对于一个”与”节点MIN,若能估计出其倒推值的上确界,并且这

46、个值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界,即,则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为剪枝。(2)对于一个”或”节点MAX,若能估计出其倒推值的下确界,并且这个值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界,即,则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为剪枝。,-剪枝技术的具体方法：,147,【-剪枝例题】,148,-剪枝小结：,极大节点(或节点）的下界为。极小节点（与节点）的上界为。剪枝的条件：后辈节点的值祖先节点的值时，剪枝后辈节点的 值祖先节点的值时，剪枝,149,此节内容结束，谢 谢！,150,练 习 题,教材85页：习题三 第12、15题,