搜索
1第七章搜索策略搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关系到智能系统的性能与运行效率，因而尼尔逊把它列入人工智能研究的四个核心问题之一。2第七章搜索策略7.1基本概念7.2状态空间的搜索技术7.3与/或图的搜索策略7.4博弈树搜索3第七章搜索策略7.1基本概念7.2状态空间的搜索技术7.3与/或图的搜索策略7.4博弈树搜索7.1.1什么是搜索7.1.2状态空间表示法7.1.3与/或图表示法4第七章搜索策略根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，从而使问题圆满得到解决的过程称为搜索。基本概念状态空间的搜索策略与/或图的搜索策略7.1.1什么是搜索博弈树搜索5第七章搜索策略搜索分为盲目搜索和启发式搜索。盲目搜索（或称非启发式搜索）是按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进搜索策略。启发式搜索（或称非盲目搜索）是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并且找到最优解。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索6第七章搜索策略1、什么是状态图例题7.1设有三个钱币，其初始状态为(反、正、反),欲得的目标状态为(正、正、正)或(反、反、反)。7.1.2状态图表示法反正反反正正正反反初始状态目标状态基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索问题是允许每次只能且必须翻转一个钱币，连翻三次，问能否达到目标状态？7第七章搜索策略【解】要求解这个问题，可通过引入一个３维变量将问题表示出来。设３维变量为：Q=[q1,q2.q3]其中：qi=0表示正，qi=1表示反（i=1,2,3）基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索8第七章搜索策略共有八种组合：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基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索9第七章搜索策略由图可得解有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)Q2Q7(1,1,1)Q5(1,0,1)cbaacbbacabc基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索10第七章搜索策略把这种描述得到的有向图称为状态（空间）图。其中的节点代表一种格局（或称为状态），而两节点之间的连线表示两节点之间的联系，它可视为某种操作、规则、变换等。在状态图中，从初始节点到目标节点的一条路径是一个解。7.1.2状态图表示法基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索11第七章搜索策略2、问题的状态空间表示法1)状态：描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：Sk=(Sk0，Sk1，…),当给每一个分量以确定的值时，就得到了一个具体的状态。2)操作：亦称算符/算子/运算符。引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索12第七章搜索策略3)状态空间：由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：(S,F,G)其中S是问题的所有初始状态构成的集合；F是算符的集合；G是目标状态的集合。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索13第七章搜索策略例7.2二阶梵塔问题。设有3个钢针，在1号钢针上穿有A、B两个金片，A小于B，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一片，任何时刻都不能使B位于A的上面。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索123ＢＡ14第七章搜索策略解：设用Sk=(Sk0,Sk1)表示问题的状态。其中Sk0表示金片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能的状态有九种：基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索15第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索问题的初始状态集合为S={S0}，目标状态集合为G={S4，S8}。16第七章搜索策略算符分别用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）。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索17第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索操作符条件操作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种操作18第七章搜索策略7.1.2状态图表示法3,11,12,33,22,21,31,23,32,1基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索Ａ（２，１）Ａ（１，３）Ａ（３，２）Ｂ（１，２）B（3，１）Ａ（3，2）19第七章搜索策略状态空间图中，从初始节点(1,1)到目标节点(2,2)及(3,3)的任何一条通路都是问题的一个解，其中最短的路径长度是3，它由3个算符组成，例如A(1,3)，B(1,2)，A(3,2)。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索20第七章搜索策略由此例可以看出：1)用状态空间方法表示问题时，首先必须定义状态的描述形式，可把问题的一切状态都表示出来。其次，还要定义一组算符，通过使用算符可把问题的一种状态转变为另一种状态。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索21第七章搜索策略2)问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用算符构成一个的序列。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索22第七章搜索策略3)问题从初始状态到目标状态可能得到多个解，我们把使用算符最少的解称为最优解。评价解的优劣不仅要看使用算符的数量，还要看使用算符所付出的代价。4)对任何一个状态，可使用的算符可能不止一个，这样由一个状态所生成的后继状态就可能有多个。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索23第七章搜索策略当对这些后继状态使用算符生成更进一步的状态时，首先应对哪一个状态进行操作呢？这取决于搜索策略，不同搜索策略的操作顺序是不相同的，这正是本章要讨论的问题。基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索24第七章搜索策略与/或图示用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较复杂问题的求解。1、什么是与/或图例如要证明两个四角形相等，可先分别将其分成两个三角形，在证三角形相等的基础上再证四角形相等。2、对于一个复杂问题，直接求解往往比较困难。此时，可通过下面方法进行简化：7.1.3与/或图表示法基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索25第七章搜索策略1)分解把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解为若干更为简单的子问题，重复此过程，直到不需要再分解或者不能再分解为之。然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。例如：P1，P2，P3是问题P的三个子问题，只有当这三个子问题有解时，问题P才有解，称P1，P2，P3之间存在“与”关系；称节点P为“与”节点；基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索26由P，P1，P2，P3所构成的图称为“与”树。在图中，为了标明某个节点是“与”节点，通常用一条弧把各条边连接起来。7.1.3与/或图表示法PP2P3P1第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索272）等价变换对于一个复杂问题，除了可用“分解”方法进行分解外，还可利用同构或同态的等价变换，把它变换为若干个较容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。问题的等价变换过程，也可用一个图表示出来，称为“或”树。PP2P3P1第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索283)“与/或”树：上述两种方法也可结合起来使用，此时的图称为“与/或”树。其中既有“与”节点，又有“或”节点。注意：状态图是与/或图的特殊形式，即与/或图中既有与关系又有或关系，而状态图只有或关系。把一个问题经“分解”得到的子问题以及经“变换”得到的新问题统称为子问题；把“与”树及“或”树统称为“与/或”树；把子问题所对应的节点称为子节点。第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索293、基本概念：1)根节点：无父节点的节点，为初始节点，对应初始问题下的描述；2)叶节点：无子节点的节点，亦称端节点；3)终止节点：有解的叶节点，对应本原问题。即终止节点一定是端节点，但端节点不一定是终止节点。第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索304)可解节点：满足下列条件之一者：①它是一个终止节点。②它是一个“或”节点，且其子节点中至少有一个是可解节点。③它是一个“与”节点，且其子节点全部是可解节点。5)不可解节点：关于可解节点的三个条件全部不满足的节点。6)解树：由可解节点所构成，并且由这些可解节点可推出初始节点（它对于原始问题）为可解节点的子树称为解树。第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索31例7.3利用与/或图的方法二阶梵塔问题如下:根据例7.2的讨论，初始状态为:P：({S0}，F，{S4，S8})而P可等价变换为两个彼此独立的子问题：P1：({S0}，F，{S4})P2：({S0}，F，{S8})任何一个子问题得解，P问题就有解，即：P=P1∨P2而P1和P2又可进一步分解为若干个相关的子问题，第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索32例如在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})本原问题第七章搜索策略基本概念状态空间的搜索策略与/或图的搜索策略博弈树搜索33至此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问题有解，且有两个解。第七章搜索策略基本概念状