搜索策略讲义课件criu.pptx

《搜索策略讲义课件criu.pptx》由会员分享，可在线阅读，更多相关《搜索策略讲义课件criu.pptx（152页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 搜索策略搜索策略 搜索搜索是人工智能中的一个基本问题人工智能中的一个基本问题，是推理不可分割的一部分，它直接关系到智能系关系到智能系统的性能与运行效率统的性能与运行效率，因而尼尔逊把它列入人人工智能研究的四个核心问题之一工智能研究的四个核心问题之一。1第七章 搜索策略l 7.1 基本概念基本概念l 7.2 状态空间的搜索技术状态空间的搜索技术l 7.3 与与/或图的搜索策略或图的搜索策略l 7.4 博弈树搜索博弈树搜索2第七章 搜索策略l 7.1 基本概念l 7.2 状态空间的搜索技术l 7.3 与/或图的搜索策略l 7.4 博弈树搜索 7.1.1 什么是搜索 7.1.2 状态空

2、间表示法 7.1.3 与/或图表示法3第七章第七章 搜索策略搜索策略根据问题的实际情况不断寻找可利用的知识不断寻找可利用的知识，从而构造一条代价较少的推理路线构造一条代价较少的推理路线，从而使问题圆使问题圆满得到解决的过程满得到解决的过程称为搜索搜索。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 7.1.1 7.1.1 什么是搜索什么是搜索博弈树搜索博弈树搜索4第七章第七章 搜索策略搜索策略搜索分为盲目搜索盲目搜索和启发式搜索启发式搜索。盲目搜索盲目搜索（或称非启发式搜索）（或称非启发式搜索）是按预定的控制策预定的控制策略进行搜索略进行搜索，在搜索过程

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

4、)。7.1.2 状态图表示法状态图表示法反正反反正正正反反初始状态初始状态目标状态目标状态基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索问题是允许每次只能且必须翻转一个钱币，连翻三次，问题是允许每次只能且必须翻转一个钱币，连翻三次，问能否达到目标状态？问能否达到目标状态？6第七章第七章 搜索策略搜索策略【解】要求解这个问题，可通过引入一个维变量将【解】要求解这个问题，可通过引入一个维变量将问题表示出来。问题表示出来。设维变量为：设维变量为：Q=q1,q2.q3 其中：其中：q i=0 表示正，表示正，qi=1表示反（表示反（i=1,

5、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第七章第七章 搜索策略搜索策略由图可得解有可得

6、解有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、而两节点之间的连线之间的连线表示两节点之间的联系两节点之间的联系，它可视为某种某种操操作、规则、变换等作、规则、变换等。在状态图中，从初始节点到目标节点从初始节点到目标节点的一条路径一条路径是一个解一个解。7.1.2 状态图表示法基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索10第七章第七章 搜索策略搜索策略2、问题的状态空间表示法、问题的状态空间表示法1)状态：状态：描述问题求解过程问题求解过程中任一时刻状况的数据结构任一时刻状况的数据结构，一般用一组变量的有序组合一组变量的有序组合表示：Sk=(Sk0，Sk1，),当给每一个分量

8、以确定的值时，就得到了一个具体的状态每一个分量以确定的值时，就得到了一个具体的状态。2)操作：操作：亦称算符算符/算子算子/运算符运算符。引起状态中某些分量发状态中某些分量发生变化生变化，从而使问题由一个状态变为另一个状态由一个状态变为另一个状态。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索11第七章第七章 搜索策略搜索策略 3)状态空间：状态空间：由问题的全部状态及一切可用算符所问题的全部状态及一切可用算符所构成的集合构成的集合称为问题的状态空间问题的状态空间，一般用一个三元组表示：(S,F,G)其中S是是问题的所有初始状态构成

9、的集合问题的所有初始状态构成的集合；F是是算符的集合算符的集合；G是是目标状态的集合目标状态的集合。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索12第七章第七章 搜索策略搜索策略例例7.2 二阶梵塔问题二阶梵塔问题。设有 3 个钢针个钢针，在1号钢针上穿有号钢针上穿有A、B两个金两个金片，片，A小于小于B，A位于位于B的上面的上面。要求把这两个金片这两个金片全部移到另一根钢针上全部移到另一根钢针上，而且规定每次只能移动一规定每次只能移动一片片，任何时刻都不能使都不能使B位于位于A的上面的上面。基本概念基本概念状态空间的搜索策略状态

10、空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索12313第七章第七章 搜索策略搜索策略解：解：设用Sk=(Sk0,Sk1)表示问题的状态表示问题的状态。其中Sk0表示金片表示金片A所在的钢针号所在的钢针号，Sk1表示金片表示金片B所在的钢针号。所在的钢针号。全部可能的状态有九种全部可能的状态有九种：基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索14第七章第七章 搜索策略搜索策略基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索问题的初始状态集合为问题的

11、初始状态集合为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种算符种算符，可构成二阶梵塔问题的状态二阶梵塔问

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）s k0=1 s k0=1 s k0=2 s k0=2 s k0=3 s k0=3 s

13、 k0=3 且且 s k1=1 s k0=2 且且 s k1=1 s k0=3 且且 s k1=2 s k0=1 且且 s k1=2 s k0=2 且且 s k1=3 s k0=1 且且 s k1=3s k0=2s k0=3s k0=1s k0=3s k0=1s k0=2s k1=2s k1=3s k1=1s k1=3s k1=1s k1=2表表7-1 二阶梵塔问题的二阶梵塔问题的12种操作种操作 17第七章第七章 搜索策略搜索策略 7.1.2 状态图表示法3,11,12,33,22,21,31,23,32,1基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策

14、略 博弈树搜索博弈树搜索（，）（，）（，）（，）（，）（，）（，）（，）B B（3 3，），）（3，2）18第七章第七章 搜索策略搜索策略状态空间图中，从初始节点从初始节点(1,1)到目标节到目标节点点(2,2)及及(3,3)的任何一条通路都是问题的一的任何一条通路都是问题的一个解个解，其中最短的路径长度是最短的路径长度是3，它由它由3个算符个算符组成，例如组成，例如A(1,3)，B(1,2)，A(3,2)。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索19第七章第七章 搜索策略搜索策略由此例可以看出：1)用状态空间方法表示问题时用

15、状态空间方法表示问题时，首先首先必须定义状态的描述形式，可必须定义状态的描述形式，可把问题把问题的一切状态都表示出来的一切状态都表示出来。其次其次，还要定义一组算符，通过使用算符还要定义一组算符，通过使用算符可把可把问题的一种状态转变为另一种状态问题的一种状态转变为另一种状态。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索20第七章第七章 搜索策略搜索策略2)问题的求解过程问题的求解过程是一个不断把算符作用于不断把算符作用于状态的过程状态的过程。如果在使用某个算符后得到的在使用某个算符后得到的新状态是目新状态是目标状态，就得到了问题

16、的一个解标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用算符从初始状态到目标状态所用算符构成一个的序列构成一个的序列。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索21第七章第七章 搜索策略搜索策略3)问题从初始状态到目标状态可能得到从初始状态到目标状态可能得到多个解多个解，我们把使用算符最少的解把使用算符最少的解称为最优解最优解。评价解的优劣解的优劣不仅要看使用算符的数量不仅要看使用算符的数量，还要看使用算符所付出使用算符所付出的代价的代价。4)对任何一个状态任何一个状态，可使用的算符可能不止一个可使用的算符可能不止

17、一个，这样由一个状态所生成的后继状态就可能有多个由一个状态所生成的后继状态就可能有多个。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索22第七章第七章 搜索策略搜索策略当对这些后继状态使用算符生成更进一步的状这些后继状态使用算符生成更进一步的状态时，首先应对哪一个状态进行操作呢？态时，首先应对哪一个状态进行操作呢？这取决于搜索策略搜索策略，不同搜索策略的操作顺序是不相同的不同搜索策略的操作顺序是不相同的，这正是本章要讨论的问题本章要讨论的问题。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博

18、弈树搜索博弈树搜索23第七章第七章 搜索策略搜索策略 与/或图示用于表示问题及其求解过程的又一种形式化用于表示问题及其求解过程的又一种形式化方法方法，通常用于表示比较复杂问题的求解比较复杂问题的求解。1 1、什么是与、什么是与/或图或图 例如要证明两个四角形相等证明两个四角形相等，可先分别将其分成两个分别将其分成两个三角形三角形，在证三角形相等的基础上再证四角形相等证三角形相等的基础上再证四角形相等。2 2、对于一个复杂问题复杂问题，直接求解往往比较困难直接求解往往比较困难。此时，可通过下面方法进行简化：7.1.3 7.1.3 与与/或图表示法或图表示法基本概念基本概念状态空间的搜索策略状态空

19、间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索24第七章第七章 搜索策略搜索策略1)1)分解分解把一个复杂问题分解为若干个较为简单的子问题复杂问题分解为若干个较为简单的子问题，每个子每个子问题又可继续分解为若干更为简单的子问题问题又可继续分解为若干更为简单的子问题，重复此过程，直到不需要再分解或者不能再分解为之不需要再分解或者不能再分解为之。然后对每个子问题分别对每个子问题分别进行求解进行求解，最后把各子问题的解复合起来就得到了原问题的解把各子问题的解复合起来就得到了原问题的解。例如：例如：P1 ，P2 ，P3 是问题是问题P的三个子问题的三个子问题，只有当这三个子这三个

20、子问题有解时，问题问题有解时，问题P才有解才有解，称P1 ，P2 ，P3之间存在之间存在“与与”关系；称节点节点P为为“与与”节点节点；基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索25由P，P1 ，P2 ，P3所构成的图所构成的图称为“与与”树树。在图中，为了标明某个节点是“与”节点，通常用一条弧把各条边连接起用一条弧把各条边连接起来。来。7.1.3 与/或图表示法PP2P3P1第七章第七章 搜索策略搜索策略基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索262 2）等价

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

22、时的图称为“与与/或或”树树。其中既有既有“与与”节点，又有节点，又有“或或”节点节点。注意：注意：状态图是与状态图是与/或图的特殊形式或图的特殊形式，即与与/或图中既有与关或图中既有与关系又有或关系，而状态图只有或关系系又有或关系，而状态图只有或关系。把一个问题经一个问题经“分解分解”得到的子问题以及经得到的子问题以及经“变换变换”得得到的新问题到的新问题统称为子问题子问题；把“与与”树及树及“或或”树树统称为“与与/或或”树树；把子问题所对应的节点把子问题所对应的节点称为子节点子节点。第七章第七章 搜索策略搜索策略基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图

23、的搜索策略 博弈树搜索博弈树搜索283 3、基本概念：、基本概念：1)1)根节点：根节点：无父节点的节点无父节点的节点，为初始节点为初始节点，对应初始问题下对应初始问题下的描述的描述；2)2)叶节点：叶节点：无子节点的节点无子节点的节点，亦称端节点端节点；3)3)终止节点：终止节点：有解的叶节点有解的叶节点，对应本原问题对应本原问题。即终止节点一终止节点一定是端节点，但端节点不一定是终止节点定是端节点，但端节点不一定是终止节点。第七章第七章 搜索策略搜索策略基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索294)4)可解节点：可解节点

24、：满足下列条件之一者：它是一个终止节点是一个终止节点。它是一个是一个“或或”节点节点，且其子节点中至少有一个是可解节点子节点中至少有一个是可解节点。它是一个是一个“与与”节点节点，且其子节点全部是可解节点子节点全部是可解节点。5)5)不可解节点：不可解节点：关于可解节点的三个条件全部不满足的节点可解节点的三个条件全部不满足的节点。6)6)解树：解树：由可解节点所构成由可解节点所构成，并且由这些可解节点可推出初由这些可解节点可推出初始节点（它对于原始问题）为可解节点的子树始节点（它对于原始问题）为可解节点的子树称为解树。第七章第七章 搜索策略搜索策略基本概念基本概念状态空间的搜索策略状态空间的搜

25、索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索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又可进一步分解为若干个相关的子问题又可进一步分解为若干个相关的子问题，第七章第七章 搜索策略搜索策略基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜

26、索策略 博弈树搜索博弈树搜索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 )本原问题本原问题第七章第七章 搜索策略搜索策略基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜

27、索博弈树搜索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问题有解，且有两个解问题有解，且有两个解。第七章第七章 搜索策略搜索策略基本概念基本概念状态空间的搜索

28、策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索33与与/或图的方法二阶梵塔问题：或图的方法二阶梵塔问题：第七章第七章 搜索策略搜索策略PP111P2P1P11P12P212P22P211P21P11234课堂练习课堂练习以与以与/或图的方法表示例或图的方法表示例7-1的钱币翻转问题。的钱币翻转问题。35课堂练习参考答案课堂练习参考答案以与以与/或图的方法表示例或图的方法表示例7-1的钱币翻转问题。的钱币翻转问题。解解:原始问题为：原始问题为：P:(Q5，F，Q0，Q7)对对P等价变换（即等价变换（即“或或”）后为）后为:P1:(Q5，F，Q0)P2:(Q5，F，

29、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:

30、(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)P3

31、4:(Q5,b,Q7)而对P33又可分解（即“与”)得P331:(Q5,c,Q4)P332:(Q4,c,Q5)40 PP2P1P26P21P24P22P25P23P211P212P231P23241第七章 搜索策略l 7.1 基本概念l 7.2 状态空间的搜索技术l 7.3 与/或图的搜索策略l 7.4 博弈树搜索7.2.1 图搜索的基本概念 7.2.2 宽度优先搜索7.2.3 深度优先搜索7.2.4 有限深度优先搜索7.2.5 启发式搜索42第七章第七章 搜索策略搜索策略1、显式图与隐式图 为了求解问题，需要把有关的知识存储在计算机的知识库有关的知识存储在计算机的知识库中，有以下两种存储方式

32、。1)显式存储显式存储 把与问题有关的全部状态空间图与问题有关的全部状态空间图，即相应的全部有关知相应的全部有关知识识（叙述性知识、过程性知识和控制性知识），都直接存入都直接存入知识库知识库，这种存储方式称为显式存储显式存储或显式图显式图。7.2.1 图搜索的基本概念图搜索的基本概念基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索43第七章第七章 搜索策略搜索策略2)隐式存储隐式存储只存储与问题求解有关的部分知识存储与问题求解有关的部分知识(即部分状态空间)，这种存储方式称为隐式存储隐式存储。在求解过程中，由初始状态出发，运用相应的知

33、识，逐步生成所需的部分状态空间图，通过搜索推理，逐步转移到要求的目标状态，只需在知识库中存储局部状态空间图，这种图称为隐式图。为了节约计算机的存储容量，提高搜索推理效率节约计算机的存储容量，提高搜索推理效率，通常采通常采用隐式存储方式用隐式存储方式，进行隐式图搜索推理。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索44第七章第七章 搜索策略搜索策略2、图搜索的基本思想、图搜索的基本思想 图搜索就是一种在图中寻找路径在图中寻找路径的方法。这种寻找过程寻找过程从图中的初始节点开始，至目标节点为止从图中的初始节点开始，至目标节点为止。其中

34、，初初始始节节点点和目目标标节节点点分别代代表表产产生生式式系系统统的初初始始数数据库据库和满足终止条件的数据库满足终止条件的数据库。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索45第七章第七章 搜索策略搜索策略方法是方法是先把问题的初始状态作为当前状态问题的初始状态作为当前状态，选择适用的算适用的算符对其进行操作符对其进行操作，生成一组子状态一组子状态，检查目标状态是否在其中目标状态是否在其中出现出现。若出现若出现，则搜索成功搜索成功，找到了问题的解找到了问题的解；若不出现若不出现，则按某种搜索策略按某种搜索策略从已生成的状态中

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

36、。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索47第七章第七章 搜索策略搜索策略OPEN表表用于存放刚生成的节点存放刚生成的节点，这些节点将作为以后待这些节点将作为以后待考察的对象考察的对象。OPEN表是一个“有进有出有进有出”的动态数据结构的动态数据结构。节点进入节点进入OPEN表的排列顺序，也是出表的顺序表的排列顺序，也是出表的顺序。而节点进入节点进入OPEN表的排列顺序表的排列顺序是由搜索策略决定由搜索策略决定；基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索48第

37、七章第七章 搜索策略搜索策略CLOSED表表用于存放将要扩展或者已经扩展的节点存放将要扩展或者已经扩展的节点，这些节点记录着求解中的信息记录着求解中的信息。CLOSED表是一个“有进无出有进无出”的动态数据结构的动态数据结构，当前节当前节点进入点进入CLOSED表的最后表的最后。OPEN表和表和CLOSED表的结构表的结构如下所示。节节点点父父节节点点编编号号节节点点父父节节点点OPEN表表CLOSED表表基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索49第七章第七章 搜索策略搜索策略宽度优先搜索宽度优先搜索(Breadth-Fir

38、st Search)又称为广度优先搜索广度优先搜索。1、宽度优先搜索的基本思想、宽度优先搜索的基本思想 宽度优先搜索宽度优先搜索是指从初始节点从初始节点S0开始，向下逐层搜索开始，向下逐层搜索。在在n层节点未搜索完之前，不进入层节点未搜索完之前，不进入n+1层搜索层搜索。同层节点的搜索次序可以任意同层节点的搜索次序可以任意。7.2.2 宽度优先搜索宽度优先搜索基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索50第七章第七章 搜索策略搜索策略具体就是：具体就是：先按生成规则生成第一层节点先按生成规则生成第一层节点，在该层全部节点该层全部

39、节点中沿宽（广）沿宽（广）度进行横向扫描度进行横向扫描，检查目标节点检查目标节点Sg是否在这些子节点中是否在这些子节点中。若没有若没有，则再将所有第一层节点逐一扩展，得到第二层节点再将所有第一层节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含有逐一检查第二层节点中是否包含有Sg，如此依次按照先生成、依次按照先生成、先检查、先扩展的原则进行下去先检查、先扩展的原则进行下去，直到发现直到发现Sg为止为止。所以宽度优先搜索宽度优先搜索是完备的完备的。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索51第七章第七章 搜索策略搜索策

40、略基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索广度优先搜索的示例广度优先搜索的示例 52第七章第七章 搜索策略搜索策略2、宽度优先搜索的流程、宽度优先搜索的流程 把初始节点初始节点S0放入放入OPEN表表；如果如果OPEN表为空，则问题无解，失败并退出表为空，则问题无解，失败并退出。否则往下。把把OPEN表中的第一个节点取出放入表中的第一个节点取出放入CLOSED表表中，并按按顺序冠以编号顺序冠以编号n；考察节点考察节点n是否为目标节点是否为目标节点。若是，则求得了问题的解，成若是，则求得了问题的解，成功并退出功并退出。否则往下。

41、若节点若节点n不可扩展，则转第不可扩展，则转第步步；扩展节点扩展节点n，将其子节点放到，将其子节点放到OPEN表的尾部表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第转第步步。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索53第七章第七章 搜索策略搜索策略 在宽度优先搜索宽度优先搜索下，如果问题有解，如果问题有解，OPEN表中必然出表中必然出现目标节点现目标节点Sg，而且算法一定在在停止，这表示解已找到停止，这表示解已找到。从该目标节点该目标节点Sg根据返回指针根据返回指针往回追溯往回追溯，直到初始节点，直到初始节点S0，

42、所得到的一条路径，所得到的一条路径就是问题的解问题的解。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索54第七章第七章 搜索策略搜索策略例例7.4 重排九宫问题重排九宫问题。在33的方格棋盘的方格棋盘上,分别放置着标有标有数字数字1,2,3,4,5,6,7,8的八张纸牌的八张纸牌,并留一个空格留一个空格。要求是：要求是：只允许把空格上、下、左、右的纸牌移入空格空格上、下、左、右的纸牌移入空格，而空格移至该纸牌原有的位置空格移至该纸牌原有的位置。要求寻找从初始状态转移到寻找从初始状态转移到目标状态的最短途径目标状态的最短途径。如图 (

43、a)初始状态初始状态 (b)目标状态目标状态2 8 31 47 6 512 38 47 6 5S0Sg基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索55第七章第七章 搜索策略搜索策略解：解：用宽度优先搜索法，生成规则为生成规则为：纸牌移入空格的次纸牌移入空格的次序是由空格左边开始，顺时针方向移动，不允许斜方向移动，序是由空格左边开始，顺时针方向移动，不允许斜方向移动，不允许返回不允许返回。所生成的搜索树如搜索树如P113例例7.4图图(图图7-15)所示所示。由图可知，从初始状态初始状态S0转移到目标状态转移到目标状态Sg的最短路径

44、的最短路径为：S0381626（Sg）即为重排九宫问题的解重排九宫问题的解。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索56第七章第七章 搜索策略搜索策略1、深度优先搜索的基本思想、深度优先搜索的基本思想 深度优先搜索深度优先搜索(Depth-First Search)是一种一直向下的搜索策略。它是从初始节点从初始节点S0开始开始,按生成规则按生成规则生成下一级各子节生成下一级各子节点点，检查是否出现目标节点检查是否出现目标节点Sg；若未出现若未出现，则按“最晚生成的子节点优先扩展最晚生成的子节点优先扩展”的原则原则，再生成再下一

45、级的子节点，再检查是否出现再生成再下一级的子节点，再检查是否出现Sg；若仍未出若仍未出现，则再现，则再沿着最晚生成的子节点分枝生成子节点沿着最晚生成的子节点分枝生成子节点，如此下如此下去去，即逐级即逐级“纵向纵向”深入搜索深入搜索。7.2.3 深度优先搜索深度优先搜索基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索57第七章第七章 搜索策略搜索策略 由于一个有解的问题常常含有一个有解的问题常常含有无穷分枝无穷分枝，深度优先搜索过程如果误入无穷分枝，就不可能找到目标节点如果误入无穷分枝，就不可能找到目标节点，所以它是不完备的不完备的。与

46、宽度优先搜索不同与宽度优先搜索不同，深度优先搜索找到的解也不一定解也不一定是最佳的是最佳的。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索58第七章第七章 搜索策略搜索策略基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索深度优先搜索的示例深度优先搜索的示例 59第七章第七章 搜索策略搜索策略2、深度优先搜索的流程、深度优先搜索的流程 深度优先搜索的搜索过程如下深度优先搜索的搜索过程如下：把初始节点初始节点S0放入放入OPEN表表；如果如果OPEN表为空，则问题无解，失败并退

47、出表为空，则问题无解，失败并退出。把OPEN表中的第一个节点取出放入表中的第一个节点取出放入CLOSED表中表中，并按顺序冠以编号n；考察节点考察节点n是否为目标节点是否为目标节点。若是，则求得了问题的解，成功若是，则求得了问题的解，成功并退出并退出。若节点若节点n不可扩展，则转第不可扩展，则转第步步；扩展节点扩展节点n，将其子节点放到，将其子节点放到OPEN表的首部表的首部，并为其配置指向父节点的指针，然后转第步。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索60第七章第七章 搜索策略搜索策略如果问题有解如果问题有解，且问题树没有

48、无穷分枝问题树没有无穷分枝，则必在必在OPEN表表中出现中出现Sg，过程必将在，过程必将在停止，搜索成功停止，搜索成功。所以深度优先搜索法仅对有限状态空间类问题来说具有算仅对有限状态空间类问题来说具有算法性法性，但无可采纳性无可采纳性。一般说来它仅是一个过程，需要进一步改进需要进一步改进。例例7.5：参见P115基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索61第七章第七章 搜索策略搜索策略1、有限深度优先搜索的基本思想、有限深度优先搜索的基本思想 在深度优先搜索法中，若目标节点Sg恰好处在最晚生成的子节点分枝树中，则可以较快地求得

49、问题的解，效率比宽度优先搜索法高。但是，若误陷入无穷分枝，进入死循环，则搜索过程无法收敛，不能找到目标节点不能找到目标节点。7.2.4 有限深度优先搜索有限深度优先搜索基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索62第七章第七章 搜索策略搜索策略为了改进深度优先搜索法改进深度优先搜索法，以免搜索过程陷入无穷分枝的以免搜索过程陷入无穷分枝的死循环死循环，可以引入搜索深度界限（设为引入搜索深度界限（设为dm）。当沿沿“最晚最晚”分枝纵向搜索，达到深度分枝纵向搜索，达到深度dm时时，尚未出现目尚未出现目标节点标节点Sg，则返回，对，则返

50、回，对“次晚次晚”分枝进行搜索，分枝进行搜索，如此按有限深有限深度度(d dm)搜索下去搜索下去，直到找到目标节点找到目标节点Sg为止为止。基本概念基本概念状态空间的搜索策略状态空间的搜索策略与与/或图的搜索策略或图的搜索策略 博弈树搜索博弈树搜索63第七章第七章 搜索策略搜索策略因此，若问题有解若问题有解（在问题树中存在目标节点Sg，且处在有限深度范围内），当所选取的搜索深度限制值（当所选取的搜索深度限制值（dm）大于或等于）大于或等于目标节点目标节点Sg所处实际深度时所处实际深度时，则有界深度优先搜索法一定可以找一定可以找到目标节点到目标节点Sg，保证推理过程的收敛性，求得问题的解。具有完