人工智能第7章搜索策略

第七章搜索策略

搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关系到智能系统的性能与运行效率，因而尼尔逊把它列入人工智能研究的四个核心问题之一。第一页，共一百五十二页。1第七章搜索策略

7.1基本概念

7.2状态空间的搜索技术7.3与/或图的搜索策略7.4博弈树搜索第二页，共一百五十二页。2第七章搜索策略7.1基本概念7.2状态空间的搜索技术7.3与/或图的搜索策略7.4博弈树搜索7.1.1什么是搜索7.1.2状态空间表示法

7.1.3与/或图表示法第三页，共一百五十二页。3第七章搜索策略根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，从而使问题圆满得到解决的过程称为搜索。

基本概念状态空间的搜索策略与/或图的搜索策略

7.1.1什么是搜索博弈树搜索第四页，共一百五十二页。4第七章搜索策略搜索分为盲目搜索和启发式搜索。

盲目搜索（或称非启发式搜索）是按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进搜索策略。

启发式搜索（或称非盲目搜索）是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并且找到最优解。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第五页，共一百五十二页。5第七章搜索策略1、什么是状态图例题7.1设有三个钱币，其初始状态为(反、正、反),欲得的目标状态为(正、正、正)或(反、反、反)。

7.1.2状态图表示法反正反反正正正反反初始状态目标状态基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索问题是允许每次只能且必须翻转一个钱币，连翻三次，问能否达到目标状态？第六页，共一百五十二页。6第七章搜索策略【解】要求解这个问题，可通过引入一个３维变量将问题表示出来。

设３维变量为：

Q=[q1,q2.q3]

其中：qi=0表示正，qi=1表示反（i=1,2,3）基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第七页，共一百五十二页。7第七章搜索策略共有八种组合：

Q0=(0,0,0)Q1=(0,0,1)Q2=(0,1,0)Q3=(0,1,1)Q4=(1,0,0)Q5=(1,0,1)

Q6=(1,1,0)Q7=(1,1,1)每个组合就视为一个节点。初始状态为Q5，目表状态为Q0和Q7

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第八页，共一百五十二页。8第七章搜索策略由图可得解有7个：

aab,aba,baa,bbb,bcc,cbc,ccb其中：a表示q1的变化，b表示q2的变化，c表示q3的变化。Q0(0,0,0)Q4(1,0,0)(1,1,0)Q6Q1(0,0,1)Q3(0,1,1)(0,1,0)Q2

Q7(1,1,1)Q5(1,0,1)cbaacbbacabc基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第九页，共一百五十二页。9第七章搜索策略把这种描述得到的有向图称为状态（空间）图。

其中的节点代表一种格局（或称为状态），而两节点之间的连线表示两节点之间的联系，它可视为某种操作、规则、变换等。在状态图中，从初始节点到目标节点的一条路径是一个解。

7.1.2状态图表示法基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第十页，共一百五十二页。10第七章搜索策略2、问题的状态空间表示法1)状态：描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：Sk=(Sk0，Sk1，

…),当给每一个分量以确定的值时，就得到了一个具体的状态。2)操作：亦称算符/算子/运算符。引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第十一页，共一百五十二页。11第七章搜索策略

3)状态空间：由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：

(S,F,G)其中S是问题的所有初始状态构成的集合；F是算符的集合；G是目标状态的集合。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第十二页，共一百五十二页。12第七章搜索策略例7.2

二阶梵塔问题。

设有3个钢针，在1号钢针上穿有A、B两个金片，A小于B，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一片，任何时刻都不能使B位于A的上面。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索123ＢＡ第十三页，共一百五十二页。13第七章搜索策略解：设用Sk=(Sk0,Sk1)表示问题的状态。其中Sk0表示金片A所在的钢针号，Sk1表示金片B所在的钢针号。

全部可能的状态有九种：

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第十四页，共一百五十二页。14第七章搜索策略

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索问题的初始状态集合为S={S0}，目标状态集合为G={S4，S8}。第十五页，共一百五十二页。15第七章搜索策略算符分别用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)

根据9种可能的状态和12种算符，可构成二阶梵塔问题的状态空间图。另：每个算符都含有“条件”和“动作”（如表7-1）。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第十六页，共一百五十二页。16第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索操作符条件操作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）sk0=1sk0=1sk0=2sk0=2sk0=3sk0=3sk0=3且sk1=1sk0=2且sk1=1sk0=3且sk1=2sk0=1且sk1=2sk0=2且sk1=3sk0=1且sk1=3sk0=2sk0=3sk0=1sk0=3sk0=1sk0=2sk1=2sk1=3sk1=1sk1=3sk1=1sk1=2表7-1二阶梵塔问题的12种操作

第十七页，共一百五十二页。17第七章搜索策略

7.1.2状态图表示法3,11,12,33,22,21,31,23,32,1基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索Ａ（２，１）Ａ（１，３）Ａ（３，２）Ｂ（１，２）B（3，１）Ａ（3，2）第十八页，共一百五十二页。18第七章搜索策略状态空间图中，从初始节点(1,1)到目标节点(2,2)及(3,3)的任何一条通路都是问题的一个解，其中最短的路径长度是3，它由3个算符组成，例如A(1,3)，B(1,2)，A(3,2)。

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第十九页，共一百五十二页。19第七章搜索策略由此例可以看出：1)用状态空间方法表示问题时，首先必须定义状态的描述形式，可把问题的一切状态都表示出来。

其次，还要定义一组算符，通过使用算符可把问题的一种状态转变为另一种状态。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第二十页，共一百五十二页。20第七章搜索策略2)问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用算符构成一个的序列。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第二十一页，共一百五十二页。21第七章搜索策略3)问题从初始状态到目标状态可能得到多个解，我们把使用算符最少的解称为最优解。评价解的优劣不仅要看使用算符的数量，还要看使用算符所付出的代价。4)对任何一个状态，可使用的算符可能不止一个，这样由一个状态所生成的后继状态就可能有多个。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第二十二页，共一百五十二页。22第七章搜索策略

当对这些后继状态使用算符生成更进一步的状态时，首先应对哪一个状态进行操作呢？这取决于搜索策略，不同搜索策略的操作顺序是不相同的，这正是本章要讨论的问题。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第二十三页，共一百五十二页。23第七章搜索策略与/或图示用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较复杂问题的求解。1、什么是与/或图例如要证明两个四角形相等，可先分别将其分成两个三角形，在证三角形相等的基础上再证四角形相等。2、对于一个复杂问题，直接求解往往比较困难。此时，可通过下面方法进行简化：

7.1.3与/或图表示法基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第二十四页，共一百五十二页。24第七章搜索策略1)分解把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解为若干更为简单的子问题，重复此过程，直到不需要再分解或者不能再分解为之。然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。例如：

P1

，P2

，P3

是问题P的三个子问题，只有当这三个子问题有解时，问题P才有解，称P1

，P2

，P3之间存在“与”关系；称节点P为“与”节点；基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第二十五页，共一百五十二页。25由P，P1

，P2

，P3所构成的图称为“与”树。在图中，为了标明某个节点是“与”节点，通常用一条弧把各条边连接起来。

7.1.3与/或图表示法PP2P3P1第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第二十六页，共一百五十二页。262）等价变换

对于一个复杂问题，除了可用“分解”方法进行分解外，还可利用同构或同态的等价变换，把它变换为若干个较容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。问题的等价变换过程，也可用一个图表示出来，称为“或”树。PP2P3P1第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第二十七页，共一百五十二页。273)“与/或”树：

上述两种方法也可结合起来使用，此时的图称为“与/或”树。其中既有“与”节点，又有“或”节点。注意：状态图是与/或图的特殊形式，即与/或图中既有与关系又有或关系，而状态图只有或关系。把一个问题经“分解”得到的子问题以及经“变换”得到的新问题统称为子问题；把“与”树及“或”树统称为“与/或”树；把子问题所对应的节点称为子节点。第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第二十八页，共一百五十二页。283、基本概念：1)根节点：无父节点的节点，为初始节点，对应初始问题下的描述；2)叶节点：无子节点的节点，亦称端节点；3)终止节点：有解的叶节点，对应本原问题。即终止节点一定是端节点，但端节点不一定是终止节点。第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第二十九页，共一百五十二页。294)可解节点：满足下列条件之一者：它是一个终止节点。它是一个“或”节点，且其子节点中至少有一个是可解节点。③它是一个“与”节点，且其子节点全部是可解节点。5)不可解节点：关于可解节点的三个条件全部不满足的节点。6)解树：由可解节点所构成，并且由这些可解节点可推出初始节点（它对于原始问题）为可解节点的子树称为解树。第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第三十页，共一百五十二页。30例7.3利用与/或图的方法二阶梵塔问题如下:根据例7.2的讨论，初始状态为:

P：({S0}，F，{S4，

S8})而P可等价变换为两个彼此独立的子问题：

P1：({S0}，F，{S4})P2：({S0}，F，{

S8})

任何一个子问题得解，P问题就有解，即：

P=P1

∨P2而P1

和P2又可进一步分解为若干个相关的子问题，第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第三十一页，共一百五十二页。31例如在P1问题中引入关键状态S7后，P1被分解为两个子问题的与：

P11：({S0}，F，{S7}) P12：({S7}，{A(3，2)}，{S4})

P12是本原问题，无须再分解；

P11中再引入关键状态S6后，又可以分解为两个子问题的与：

P111：({S0}，{A(1，3)}，{S6})本原问题 P112：({S6}，{B(1，2)}，{S7})本原问题第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第三十二页，共一百五十二页。32至此P1已得解：P1=P111∧P112∧P12类似P2可解得：P2=P211∧P212∧P22，其中：

P211：（{S0}，{A（1，2）}，{S3}）（本原问题） P212：（{S3}，{B（1，3）}，{S5}）（本原问题） P22：（{S5}，{A（2，3）}，{S8}）（本原问题）

这个转化过程可以用一个与/或图来表示。由于该与/或图的每一个叶节点都是一个合法操作可以实现的本原问题，故P问题有解，且有两个解。第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第三十三页，共一百五十二页。33与/或图的方法二阶梵塔问题：第七章搜索策略PP111P2P1P11P12P212P22P211P21P112第三十四页，共一百五十二页。34课堂练习以与/或图的方法表示例7-1的钱币翻转问题。第三十五页，共一百五十二页。35课堂练习参考答案

以与/或图的方法表示例7-1的钱币翻转问题。解:原始问题为： P: (Q5，F，{Q0，Q7})对P等价变换（即“或”）后为: P1: (Q5，F，Q0) P2: (Q5，F，Q7)因为，对P1无解，而P2有7个解，即aab，aba，baa，bbb，bcc，cbc，ccb.第三十六页，共一百五十二页。36对解1(aab)可得(分解,即“与”) P21: (Q5,F,Q5) P22: (Q5,b,Q7)而对P21又可分解（即“与”)得 P211: (Q5,a,Q1) P212: (Q1,a,Q5)同理对解2(aba)可得 P23: (Q5,F,Q3) P24: (Q3,a,Q7)而对P23又可分解（即“与”)得 P231: (Q5,a,Q1) P232: (Q1,b,Q3)第三十七页，共一百五十二页。37对解3(baa)可得 P25: (Q5,F,Q3) P26: (Q3,a,Q7)而对P25又可分解（即“与”)得 P251: (Q5,a,Q7) P252: (Q1,a,Q3)对解4(bbb)可得 P27: (Q5,F,Q5) P28: (Q5,b,Q7)而对P27又可分解（即“与”)得 P271: (Q5,b,Q7) P272: (Q7,b,Q5)第三十八页，共一百五十二页。38对解5(bcc)可得 P29: (Q5,F,Q6) P30: (Q6,c,Q7)而对P29又可分解（即“与”)得 P291: (Q5,b,Q7) P292: (Q7,c,Q6)对解6(cbc)可得 P31: (Q5,F,Q6) P32: (Q6,c,Q7)而对P31又可分解（即“与”)得 P311: (Q5,c,Q4) P312: (Q4,b,Q6)第三十九页，共一百五十二页。39对解7(ccb)可得 P33: (Q5,F,Q5) P34: (Q5,b,Q7)而对P33又可分解（即“与”)得 P331: (Q5,c,Q4) P332: (Q4,c,Q5)第四十页，共一百五十二页。40

PP2P1P26P21P24P22P25P23……P211P212P231P232……第四十一页，共一百五十二页。41第七章搜索策略7.1基本概念7.2状态空间的搜索技术7.3与/或图的搜索策略7.4博弈树搜索7.2.1图搜索的基本概念7.2.2宽度优先搜索7.2.3深度优先搜索7.2.4有限深度优先搜索7.2.5启发式搜索第四十二页，共一百五十二页。42第七章搜索策略1、显式图与隐式图为了求解问题，需要把有关的知识存储在计算机的知识库中，有以下两种存储方式。1)显式存储把与问题有关的全部状态空间图，即相应的全部有关知识（叙述性知识、过程性知识和控制性知识），都直接存入知识库，这种存储方式称为显式存储或显式图。

7.2.1图搜索的基本概念基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第四十三页，共一百五十二页。43第七章搜索策略2)隐式存储只存储与问题求解有关的部分知识(即部分状态空间)，这种存储方式称为隐式存储。在求解过程中，由初始状态出发，运用相应的知识，逐步生成所需的部分状态空间图，通过搜索推理，逐步转移到要求的目标状态，只需在知识库中存储局部状态空间图，这种图称为隐式图。

为了节约计算机的存储容量，提高搜索推理效率，通常采用隐式存储方式，进行隐式图搜索推理。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第四十四页，共一百五十二页。44第七章搜索策略2、图搜索的基本思想

图搜索就是一种在图中寻找路径的方法。这种寻找过程从图中的初始节点开始，至目标节点为止。其中，初始节点和目标节点分别代表产生式系统的初始数据库和满足终止条件的数据库。

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第四十五页，共一百五十二页。45第七章搜索策略

方法是先把问题的初始状态作为当前状态，选择适用的算符对其进行操作，生成一组子状态，检查目标状态是否在其中出现。

若出现，则搜索成功，找到了问题的解；

若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。

重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第四十六页，共一百五十二页。46第七章搜索策略3、图搜索的一般过程图搜索的一般搜索过程。它是由尼尔逊（N.J.Nilsson）提出的一个图搜索过程GRAPHSEARCH，它是表达能力很强的一个搜索策略框架。在此过程中要用到OPEN表和CLOSED表。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第四十七页，共一百五十二页。47第七章搜索策略

OPEN表用于存放刚生成的节点，这些节点将作为以后待考察的对象。OPEN表是一个“有进有出”的动态数据结构。

节点进入OPEN表的排列顺序，也是出表的顺序。而节点进入OPEN表的排列顺序是由搜索策略决定；基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第四十八页，共一百五十二页。48第七章搜索策略CLOSED表用于存放将要扩展或者已经扩展的节点，这些节点记录着求解中的信息。CLOSED表是一个“有进无出”的动态数据结构，当前节点进入CLOSED表的最后。

OPEN表和CLOSED表的结构如下所示。节点父节点编号节点父节点OPEN表CLOSED表基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第四十九页，共一百五十二页。49第七章搜索策略

宽度优先搜索(Breadth-FirstSearch)又称为广度优先搜索。1、宽度优先搜索的基本思想

宽度优先搜索是指从初始节点S0开始，向下逐层搜索。

在n层节点未搜索完之前，不进入n+1层搜索。

同层节点的搜索次序可以任意。

7.2.2宽度优先搜索基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第五十页，共一百五十二页。50第七章搜索策略具体就是：

先按生成规则生成第一层节点，在该层全部节点中沿宽（广）度进行横向扫描，检查目标节点Sg是否在这些子节点中。

若没有，则再将所有第一层节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含有Sg，如此依次按照先生成、先检查、先扩展的原则进行下去，直到发现Sg为止。所以宽度优先搜索是完备的。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第五十一页，共一百五十二页。51第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索广度优先搜索的示例第五十二页，共一百五十二页。52第七章搜索策略2、宽度优先搜索的流程⑴把初始节点S0放入OPEN表；⑵如果OPEN表为空，则问题无解，失败并退出。否则往下。⑶把OPEN表中的第一个节点取出放入CLOSED表中，并按顺序冠以编号n；⑷考察节点n是否为目标节点。若是，则求得了问题的解，成功并退出。否则往下。⑸若节点n不可扩展，则转第⑵步；⑹扩展节点n，将其子节点放到OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第⑵步。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第五十三页，共一百五十二页。53第七章搜索策略在宽度优先搜索下，如果问题有解，OPEN表中必然出现目标节点Sg，而且算法一定在⑷停止，这表示解已找到。从该目标节点Sg根据返回指针往回追溯，直到初始节点S0，所得到的一条路径就是问题的解。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第五十四页，共一百五十二页。54第七章搜索策略例7.4

重排九宫问题。在3×3的方格棋盘上,分别放置着标有数字1,2,3,4,5,6,7,8的八张纸牌,并留一个空格。要求是：只允许把空格上、下、左、右的纸牌移入空格，而空格移至该纸牌原有的位置。要求寻找从初始状态转移到目标状态的最短途径。如图(a)初始状态(b)目标状态283147652384765S0Sg基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第五十五页，共一百五十二页。55第七章搜索策略解：用宽度优先搜索法，生成规则为：纸牌移入空格的次序是由空格左边开始，顺时针方向移动，不允许斜方向移动，不允许返回。所生成的搜索树如P113例7.4图(图7-15)所示。由图可知，从初始状态S0转移到目标状态Sg的最短路径为：

S0→3→8→16→26（Sg）即为重排九宫问题的解。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第五十六页，共一百五十二页。56第七章搜索策略1、深度优先搜索的基本思想

深度优先搜索(Depth-FirstSearch)是一种一直向下的搜索策略。它是从初始节点S0开始,按生成规则生成下一级各子节点，检查是否出现目标节点Sg；

若未出现，则按“最晚生成的子节点优先扩展”的原则，再生成再下一级的子节点，再检查是否出现Sg；若仍未出现，则再沿着最晚生成的子节点分枝生成子节点，如此下去，即逐级“纵向”深入搜索。

7.2.3深度优先搜索基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第五十七页，共一百五十二页。57第七章搜索策略由于一个有解的问题常常含有无穷分枝，深度优先搜索过程如果误入无穷分枝，就不可能找到目标节点，所以它是不完备的。

与宽度优先搜索不同，深度优先搜索找到的解也不一定是最佳的。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第五十八页，共一百五十二页。58第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索深度优先搜索的示例第五十九页，共一百五十二页。59第七章搜索策略2、深度优先搜索的流程

深度优先搜索的搜索过程如下：⑴把初始节点S0放入OPEN表；⑵如果OPEN表为空，则问题无解，失败并退出。⑶把OPEN表中的第一个节点取出放入CLOSED表中，并按顺序冠以编号n；⑷考察节点n是否为目标节点。若是，则求得了问题的解，成功并退出。⑸若节点n不可扩展，则转第⑵步；⑹扩展节点n，将其子节点放到OPEN表的首部，并为其配置指向父节点的指针，然后转第⑵步。

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第六十页，共一百五十二页。60第七章搜索策略

如果问题有解，且问题树没有无穷分枝，则必在OPEN表中出现Sg，过程必将在⑷停止，搜索成功。所以深度优先搜索法仅对有限状态空间类问题来说具有算法性，但无可采纳性。一般说来它仅是一个过程，需要进一步改进。

例7.5：参见P115基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第六十一页，共一百五十二页。61第七章搜索策略1、有限深度优先搜索的基本思想在深度优先搜索法中，若目标节点Sg恰好处在最晚生成的子节点分枝树中，则可以较快地求得问题的解，效率比宽度优先搜索法高。但是，若误陷入无穷分枝，进入死循环，则搜索过程无法收敛，不能找到目标节点。

7.2.4有限深度优先搜索基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第六十二页，共一百五十二页。62第七章搜索策略

为了改进深度优先搜索法，以免搜索过程陷入无穷分枝的死循环，可以引入搜索深度界限（设为dm）。当沿“最晚”分枝纵向搜索，达到深度dm时，尚未出现目标节点Sg，则返回，对“次晚”分枝进行搜索，如此按有限深度(d≤dm)搜索下去，直到找到目标节点Sg为止。

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第六十三页，共一百五十二页。63第七章搜索策略因此，若问题有解（在问题树中存在目标节点Sg，且处在有限深度范围内），当所选取的搜索深度限制值（dm）大于或等于目标节点Sg所处实际深度时，则有界深度优先搜索法一定可以找到目标节点Sg，保证推理过程的收敛性，求得问题的解。

具有完备性基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第六十四页，共一百五十二页。64第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索有限深度优先搜索的示例第六十五页，共一百五十二页。65第七章搜索策略2、有限深度优先搜索的流程有限深度优先搜索的搜索过程如下所示：⑴把初始节点S0放入OPEN表中，置S0的深度d(S0)=0；⑵如果OPEN表为空，则问题无解，失败并退出。⑶把OPEN表中的第１个节点取出放入CLOSED表中，并按顺序冠以编号n；⑷考察节点n是否为目标节点。若是，则求得了问题的解，成功并退出。⑸如果节点n的深度d（n）=dm，则转第⑵步；⑹如果节点n不可扩展，则转第⑵步；⑺扩展节点n，将其子节点放入OPEN表的首部，并为其配置指向父节点的指针。然后转第⑵步。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第六十六页，共一百五十二页。66第七章搜索策略例7.6：设深度界限dm=4，用有界深度优先搜索方法求解图7-14所示（如下）的重排九宫问题。其搜索树如图7-19所示，解的路径是：

S0→20→25→26→28（Sg）。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索283147652384765(a)初始状态(b)目标状态第六十七页，共一百五十二页。67第七章搜索策略1、启发式信息前述的各种搜索方法都是非启发式搜索。其共同特点是都没有利用问题本身的特性信息，在决定要被扩展的节点时，都没有考虑该节点在解的路径上的可能性有多大，它是否有利于问题求解以及求出的解是否为最优解等。因此，这些搜索方法都具有较大的盲目性，产生的无用节点较多，搜索空间较大，效率不高。

7.2.5启发式搜索基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第六十八页，共一百五十二页。68第七章搜索策略利用与具体问题的解有关的控制性信息来确定下一个要考察的节点，这种控制性信息称之为启发式信息。

启发式搜索中要用到与问题本身的某些特性有关的启发性信息，以指导搜索朝着最有希望的方向前进。由于这种搜索针对性较强，因而原则上只需要搜索问题的部分状态空间，效率较高。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第六十九页，共一百五十二页。69第七章搜索策略2、估价函数在启发式搜索中，为了选定下一次要考察的节点，通过设计一个函数来控制搜索方向，这种函数称为估价函数。

估价函数能够提供一个评定候选扩展节点的方法以便确定哪个节点最有可能在通向目标的最佳路径上。

估价函数的任务就是估计OPEN表中各节点的重要程度，决定它们在OPEN表中的次序，使得搜索沿着那些被认为最有希望的区域扩展。

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第七十页，共一百五十二页。70第七章搜索策略

估价函数是用于估价节点重要性的实值函数。它定义为从初始节点经过x节点到达目标节点的最小代价路径的代价估计值。它综合考虑了两方面的因素：

已经付出的代价和将要付出的代价。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第七十一页，共一百五十二页。71第七章搜索策略

其一般形式为：

f（x）=g（x）+h（x）式中：f（x）表示从初始节点经过x节点到达目标节点的总代价,称为估价函数；g（x）表示从初始节点到达x节点已支付的实际代价；h（x）表示从x节点到达目标节点将支付的估计代价，称为启发函数。

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第七十二页，共一百五十二页。72第七章搜索策略

f(x)估价函数可以是任意一种函数。但是,正确地选择估价函数对确定搜索结果起着决定性的作用。

g(x)可以根据生成的搜索树实际计算出来。

启发信息主要体现在启发函数h(x)中，用于对将付出的代价进行估计，选择节点。其形式要根据问题的特性确定。它有赖于某种经验估计。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第七十三页，共一百五十二页。73第七章搜索策略3、关于估价函数f（x）的讨论在估价函数f（x）中，g（x）和h（x）各起着不同的角色。假如将估价函数写成如下的形式：

f（x）=v×g（x）+w×h（x）其中，v、w为权系数。v、w≥0。当w增加，v减小,即h（x）的比重增大,这时表示强调“启发信息”的作用和“纵向深入”的搜索。当w减小，v增加,即g（x）的比重增大,这时表示强调“历史信息”的作用和“横向扫描”的搜索。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第七十四页，共一百五十二页。74第七章搜索策略⑴在f（x）中，g（x）的权增大，搜索过程倾向于宽度优先搜索，有利于搜索过程的完备性，但抑制了纵向深度前进的速度，降低了搜索过程的启发性，不利于提高搜索效率。

例如，在宽度优先搜索法中：f（x）=g（x）=d（x）式中：d（x）：搜索深度。

没有利用启发信息，所以h（x）=0或w=0，效率较低。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第七十五页，共一百五十二页。75第七章搜索策略⑵在f(x)中，h(x)的权增大，搜索过程将倾向于深度优先搜索，强调“纵向深入”，沿最有希望的方向前进，利用启发性知识，提高搜索效率，压缩搜索空间，但却放弃了横向扫描，降低了搜索过程的完备性。

例如，在深度优先搜索法中：

f(x)=h(x)=n(x)式中：n(x)为节点x在该次生成时的次序。根据“最晚生成的优先扩展”的深度优先搜索规则，每次扩展时，将所生成的各子节点中最晚的，作为控制策略引入到评价函数f(x)中，假定最晚生成的节点的代价最小，是最有希望的搜索方向。而不论该节点处在哪一级，已经付出了多少代价，即不考虑g(x)的影响，相当于取v=0或g(x)=0。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第七十六页，共一百五十二页。76第七章搜索策略因此，单纯的“宽度优先”和“深度优先”搜索法是两种极端的情形。实际上，设计适用的、高效的估价函数，需要根据问题的有关知识及对解的特性的估计，既要考虑已付出的代价g(x)，也要考虑将要付出的代价h(x)，兼顾搜索过程的完备性与启发性，在“横向扫描”与“纵向深入”之间，在“宽度”搜索与“深度”搜索之间，进行权衡，适当协调配合，才能取得满意的效果，低代价、高效率、成功地搜索到最优解。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第七十七页，共一百五十二页。77第七章搜索策略例7.7利用估价函数方法求解图7-14所示的重排九宫问题。解：设估价函数为f（x）=d（x）+w（x）

其中：d（x）为搜索树中节点x的深度；

w（x）为在节点x时棋子错放的个数。这样，初始状态S0的估价函数值为：f（0）=0+3=3。图中圆圈内的数字表示该节点的估价值，不带圈的数字表示节点扩展的顺序。该问题解的路径是：（见图7-20所示）

S0→3→4→5→Sg。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第七十八页，共一百五十二页。78第七章搜索策略4、启发式搜索算法启发式搜索要用启发函数来控制搜索方向，其搜索算法就是在一般搜索算法的基础上再增加启发函数值的计算与传播过程，并且由启发函数来确定节点的扩展顺序。

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第七十九页，共一百五十二页。79第七章搜索策略⑴局部择优搜索局部择优搜索是一种启发式图搜索方法,是深度优先搜索的一种改进。它在控制策略中引入了启发性信息，如关于问题的解的特性、出现规律等，使搜索过程的估价函数f（x）反映启发信息，通过择优比较，选取最有希望逼近目标节点的方向，逐级沿纵向深度进行搜索，以便加快搜索过程，提高搜索效率。

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第八十页，共一百五十二页。80第七章搜索策略☆局部择优搜索的基本思想当一个节点被扩展后，按f（x）对每一个子节点计算估价值，并选择最小者作为下一个要考察的节点，由于在搜索过程中，只保留和扩展优选的节点，择优比较只是在被扩展的优选节点的所属子节点中进行，是小范围内的局部优选。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第八十一页，共一百五十二页。81第七章搜索策略☆局部择优搜索的算法①把初始节点S0放入OPEN表，计算f（S0）；②如果OPEN表为空，则问题无解，失败并退出。③把OPEN表中的第一个节点取出放入CLOSED表中，并按顺序冠以编号n；④考察节点n是否为目标节点。若是，则求得了问题的解，成功并退出。⑤若节点n不可扩展，则转第⑵步；⑥扩展节点n，用估价函数f（x）计算每一个子节点的估价值，并按估价值从小到大的顺序依次放入OPEN表的首部，为每个子节点配置指向父节点的指针。然后转第⑵步。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第八十二页，共一百五十二页。82第七章搜索策略☆局部择优搜索的特点

优点：方法简便、搜索过程快、占用计算机内存少（只需搜索部分状态空间，不需存储全部状态空间）。

缺点：只适用于单峰极值、单因素问题；对于多峰极值、多因素问题，可能搜索失败，找不到所求的目标节点。因此，局部择优法是不完备的推理。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第八十三页，共一百五十二页。83第七章搜索策略例7.8用局部择优搜索方法求解重排九宫问题。其中S0与Sg如下所示。

设估价函数为：f（x）=h（x）

（节点x的格局与目标格局不符合的牌数）其搜索树如图7-21所示。

在搜索过程中希望h（x）尽量小，目标状态h（Sg）=0。

该问题的解的路径为：

S0→S1→S2→S3→S4→S5→S6→S7→S8→Sg

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索2831647512384765S0Sg第八十四页，共一百五十二页。84第七章搜索策略⑵全局择优搜索是一种启发式图搜索方法，它弥补了局部择优搜索法的局限性。☆全局择优搜索的基本思想在OPEN表中保留所有已生成而未考察的节点,并用估价函数f(x)对它们全部进行估价,从中选出最优节点进行考察，而不管这个节点在搜索树的什么地方。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第八十五页，共一百五十二页。85第七章搜索策略

☆全局择优搜索的算法

①把初始节点S0放入OPEN表，计算f（S0）；②如果OPEN表为空，则搜索失败，失败并退出。③把OPEN表中的第1个节点从表中移出放入CLOSED表，并按顺序冠以编号n；④考察节点n是否为目标节点。若是，则求得了问题的解，成功并退出。⑤若节点n不可扩展，则转第⑵步；⑥扩展节点n，用估价函数f（x）计算每个子节点的估价值，并为每个子节点配置指向父节点的指针，把这些子节点都送入OPEN表中，然后对OPEN表中的全部节点按估价值从小到大的顺序进行排序。然后转第⑵步。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第八十六页，共一百五十二页。86

例7.9用全局优先搜索方法求解图7-14所示的重排九宫问题。设估价函数为:

f(x)=d(x)+h(x)式中:d(x)表示节点x的深度。h(x)表示节点x的格局与目标格局不符合的纸牌数。其搜索树如图7-22所示，图中节点旁的数字为该节点的估价值。只需四步就搜索成功。

该问题解的路径为：

S0→S1→S2→S3→Sg。

第八十七页，共一百五十二页。87第七章搜索策略课堂练习用全局择优搜索算法解例7.8.f（x）=d（x）+h（x）d（x）表示节点的深度；h（x）表示节点的格局与目标格局不符合的字牌数。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第八十八页，共一百五十二页。88第七章搜索策略

7.1基本概念7.2状态空间的搜索技术7.3与/或图的搜索策略7.4博弈树搜索

7.3.1与/或图搜索

7.3.2启发式与/或图搜索第八十九页，共一百五十二页。89第七章搜索策略与状态空间法类似，与/或图表示法也是通过搜索实现问题求解的。其搜索策略也分为非启发式搜索(盲目搜索)与启发式搜索两大类。本节首先介绍与/或图的非启发式搜索，然后再给出与/或图的启发式搜索。7.3与/或图的搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第九十页，共一百五十二页。90第七章搜索策略

当知识表达方式采用与/或图形式时，知识推理就要应用与/或图搜索法。

与/或图与状态图是两种结构不同的图。对状态图而言，在搜索过程中，一旦任何一级，任何一条分支树，出现目标节点，就意味着搜索成功。但对与/或图，由于“与”树的存在，只有当所有的“子节点”可解，“与”树的“父节点”才是可解的。

7.3.1与/或图搜索基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第九十一页，共一百五十二页。91第七章搜索策略1、与/或图的一般搜索过程1）基本概念对于一个问题，若用与/或图方法进行求解，原问题（对应于根节点）是否可解，将取决于它的子问题，这些子问题对应于子节点，这些子节点可以是等价变换后产生的或关系，也可以是分解后产生的与关系，由问题本身决定。

7.3.1与/或图搜索基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第九十二页，共一百五十二页。92第七章搜索策略

根据与/或图的特点，对于一个“与”节点，只有当其子节点全部为可解节点时，它才为可解节点，只要子节点中有一个为不可解节点，它就是不可解节点；对于一个“或”节点，只要子节点中有一个是可解节点，它就是可解节点，只有当全部子节点都是不可解节点时，它才是不可解节点。

7.3.1与/或图搜索基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第九十三页，共一百五十二页。93第七章搜索策略像这样由可解子节点来确定其父节点、祖父节点等为可解节点的过程称为可解标示过程；反之称为不可解标示过程。在与/或图的搜索过程中将反复使用这两个过程，直到初始节点（即原始问题）被标示为可解或不可解节点为止。

7.3.1与/或图搜索基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第九十四页，共一百五十二页。94第七章搜索策略2）与/或图的一般搜索过程

⑴把原始问题作为初始节点S0，并把它作为当前节点；⑵应用分解或等价变换算符对当前节点进行扩展；⑶为每个子节点设置指向父节点的指针；⑷选择合适的子节点作为当前节点，反复执行第⑵步和第⑶步，在此期间要多次调用可解标示过程和不可解标示过程，直到初始节点被标示为可解节点或不可解节点为止。7.3.1与/或图搜索基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第九十五页，共一百五十二页。95第七章搜索策略

由这个搜索过程所形成的节点和指针结构称为搜索树。

与/或图搜索的目标是寻找解树，从而求得原始问题的解。如果在搜索的某一时刻，通过可解标示过程可确定初始节点是可解的，则由此初始节点及其下属的可解节点就构成了解树。如果被选为扩展的节点不可扩展，并且它不是终止节点，则此节点就是不可解节点。此时可应用不可解标示过程确定初始节点是否为不可解节点，如果初始节点是不可解的，则搜索失败；否则继续扩展节点。7.3.1与/或图搜索基本概念状态空间的搜索策略与/或图的搜索策略第九十六页，共一百五十二页。96第七章搜索策略

可解和不可解标示过程都是自下而上进行的，即由子节点的可解性确定父节点的可解性。由于与/或图搜索的目标是寻找解树，因此，如果已确定某个节点为可解节点，则其不可解的后裔节点就不再有用，可从搜索树中删去；同样，如果确定某个节点是不可解节点，则其全部后裔节点都不再有用，可从搜索树中删去，但当前这个不可解节点还不能删去，因为在判断其先辈节点的可解性时还要用到它。这是与/或图搜索的两个特有的性质，可用来提高搜索效率。7.3.1与/或图搜索基本概念状态空间的搜索策略与/或图的搜索策略第九十七页，共一百五十二页。97第七章搜索策略2、与/或图的宽度优先搜索对于与/或图的搜索策略，在考虑到“与”节点及“与”树存在的情况下，也可以采用一般的树图搜索的方法。如宽度优先搜索法、深度优先搜索法、有限深度优先搜索法等。与/或图的宽度优先搜索与状态空间的宽度优先搜索类似，也是按照“先产生的节点先扩展”的原则进行搜索，只是在搜索过程中要多次调用可解标示过程和不可解标示过程。

7.3.1与/或图搜索基本概念状态空间的搜索策略与/或图的搜索策略第九十八页，共一百五十二页。98第七章搜索策略与/或图的宽度优先搜索过程：⑴把初始节点S0放入OPEN表；⑵把OPEN表中的第一个节点取出放入CLOSED表，并按顺序冠以编号n；⑶如果节点n可扩展，则做下列工作：①扩展节点n，将其子节点放入OPEN表的尾部，并为每个子节点配置指向父节点的指针，以备标示过程使用；②考察这些子节点中有否终止节点。若有，则标示这些终止节点为可解节点，并应用可解标示过程对其父节点、祖父节点等先辈节点中的可解节点进行标示。如果初始节点S0也被标示为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。转第⑵步；基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第九十九页，共一百五十二页。99第七章搜索策略⑷如果节点n不可扩展，则做下列工作：①标示节点n为不可解节点；②应用不可解标示过程对节点n的先辈节点中不可解的节点进行标示。如果初始节点S0也被标示为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从OPEN表中删去具有不可解先辈的节点；转第⑵步；基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第一百页，共一百五十二页。100第七章搜索策略例：设有如图7-23所示的与/或图，节点按图中所标注的顺序号进行扩展。其中1号节点为初始节点，标有t1，t2，t3，t4的节点均为终止节点，A和B为不可解的端节点。

图7-23与/或图的宽度优先搜索基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.1与/或图搜索第一百零一页，共一百五十二页。101第七章搜索策略搜索过程为：

⑴首先扩展1号节点，得到2号节点和3号节点，由于这两个子节点均不是终止节点，所以接着扩展2号节点。此时OPEN表中只剩下3号节点。⑵扩展2号节点后，得到4号节点和t1节点。此时OPEN表中的节点有：3号节点、4号节点和t1节点。由于t1是终止节点，则标示它为可解节点，并应用可解标示过程，对其先辈节点中的可解节点进行标示。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.1与/或图搜索第一百零二页，共一百五十二页。102第七章搜索策略例中，t1的父节点是一个“与”节点，因此仅由t1可解尚不能确定2号节点是否为可解节点。所以继续搜索，下一步扩展的是3号节点。⑶扩展3号节点得到5号节点与B节点，两者均不是终止节点，所以接着扩展4号节点。⑷扩展4号节点后得到节点A和t2。由于t2是终止节点，所以标示它为可解节点，并应用可解标示过程标示出4号节点、2号节点均为可解节点，但1号节点目前还不能确定它是否为可解节点。此时5号节点是OPEN表中的第一个待考察的节点，所以下一步扩展5号节点。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第一百零三页，共一百五十二页。103第七章搜索策略⑸扩展5号节点，得到t3和t4。由于t3和t4均为终止节点，所以被标示为可解节点，通过应用可解标示过程可得到5号、3号及1号节点均为可解节点。⑹搜索成功，得到了由1，2，3，4，5号节点及t1，t2，t3，t4节点构成的解树。如图7-23中粗线所示。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第一百零四页，共一百五十二页。104第七章搜索策略与/或图的宽度优先搜索等都是非启发式搜索，其共同点是：⑴搜索从初始节点开始，先自上而下地进行搜索，寻找终止节点及端节点，然后再自下而上地进行可解性标示，一旦初始节点被标示为可解节点或不可解节点，搜索就不再继续进行下去。⑵搜索都是按确定路线进行的，当要选择一个节点进行扩展时，只是根据节点在与/或图中所处的位置，而没有考虑要付出的代价，因而求得的解树不一定是代价最小的解树，即不一定是最优解树。7.3.2启发式与/或图搜索

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索第一百零五页，共一百五十二页。105第七章搜索策略

为了求得最优解树，就要在每次确定欲扩展的节点时，先往前多看几步，计算一下扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩展。像这样根据代价决定搜索路线的方法称为与/或图的有序搜索，它是一种重要的启发式搜索策略。下面讨论与/或图有序搜索的有关概念及其搜索过程。

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.2启发式与/或图搜索

第一百零六页，共一百五十二页。106第七章搜索策略1、解树的代价

解树的代价就是树根的代价。

树根的代价是从树叶开始自下而上逐层计算求得的。

解树的根对应的就是初始节点S0。这就是说，在与/或图的搜索过程中，代价的计算方向与搜索树的生长方向相反。这一点是与状态图不同的。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.2启发式与/或图搜索

第一百零七页，共一百五十二页。107第七章搜索策略具体来讲，有下面的计算方法：

设g（x）表示节点x的代价，c（x，y）表示节点x到其子节点y的代价（即边xy的代价），则⑴若x是“终止节点”，g（x）=0；⑵若x是“或”节点，其中y1，y2，…，yn是x的子节点；基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.2启发式与/或图搜索

第一百零八页，共一百五十二页。108第七章搜索策略⑶若x是“与”节点，则有两种计算公式：①称为和代价法；②称为最大代价法；其中y1，y2，…，yn是x的子节点。⑷对“非终止”的端节点x，g（x）=∞。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.2启发式与/或图搜索

第一百零九页，共一百五十二页。109第七章搜索策略例7．11如图7-24所示的与/或图，其中包括两棵解树，一棵解树由S0，A，t1和t2组成；另一棵解树由S0，B，D，G，t4和t5组成。在此与/或图中，t1，t2，t3，t4，t5为终止节点；E，F是端节点，其代价均为∞；边上的数字是该边的代价。图7-24含代价的与/或图基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.2启发式与/或图搜索

第一百一十页，共一百五十二页。110第七章搜索策略由右边的解树可得：按和代价：g（A）=11，g（S0）=13。按最大代价：g（A）=6，g（S0）=8。由左边的解树可得：按和代价：g（G）=3，g（D）=4，g（B）=6，g（S0）=8。按最大代价：g（G）=2，g（D）=3，g（B）=5，g（S0）=7。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.2启发式与/或图搜索

第一百一十一页，共一百五十二页。111第七章搜索策略显然，若按和代价计算，左边的解树是最优解树，其代价是8；若按最大代价计算，左边的解树仍然是最优解树，其代价是7。但有时用不同的计算代价方法得到的最优解树不相同。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.2启发式与/或图搜索

第一百一十二页，共一百五十二页。112第七章搜索策略2、希望树1）节点x的代价g（x）无论是用和代价法还是最大代价法，当要计算任意节点x的代价g（x）时，都要求已知其子节点yi的代价g（yi）。但是，搜索是自上而下进行的，即先有父节点，后有子节点，除非节点x的全部子节点都是不可扩展节点，否则子节点的代价是不知道的。

基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.2启发式与/或图搜索

第一百一十三页，共一百五十二页。113第七章搜索策略

节点x的代价g（x）的计算①根据问题本身提供的启发性信息定义一个启发函数，由启发函数估算出子节点yi的代价g（yi）。②再按和代价或最大代价计算出节点x的代价值g（x）。③节点x的父节点、祖父节点以及直到初始节点S0的各先辈节点的代价g都可自下而上地逐层推算出来。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.2启发式与/或图搜索

第一百一十四页，共一百五十二页。114第七章搜索策略

当节点yi被扩展后，也是先用启发函数估算出其子节点的代价，然后再算出g(yi)。此时算出的g(yi)可能与原先估算出的g(yi)不相同，这时应该用后算出的g(yi)取代原先估算出的g(yi)，并且按此g(yi)自下而上地重新计算各先辈节点的g值。当节点yi的子节点又被扩展时，上述过程又要重复进行一遍。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.2启发式与/或图搜索

第一百一十五页，共一百五十二页。115第七章搜索策略

总之，每当有新的一代节点生成时，都要自下而上地重新计算其先辈节点的代价g，这是一个自上而下地生成新节点，又自下而上地计算代价g的反复进行的过程。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索7.3.2启发式与/或图搜索

第一百一十六页，共一百五十二页。116第七章搜索策略2）希望树的定义有序搜索的目的是求出最优解树，即要求搜索过程中任意时刻求出的部分解树其代价都应是最小的。为此，每次选择欲扩展