《人工智能AI3章搜索讲述》由会员分享，可在线阅读，更多相关《人工智能AI3章搜索讲述（70页珍藏版）》请在金锄头文库上搜索。
1、搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。3.1搜索概述3.1.1搜索的含义3.1.2状态空间问题求解方法3.1.3问题归约求解方法3.2搜索的盲目策略3.3状态空间的启发式搜索3.4与或树的启发式搜索3.5博弈树的启发式搜索第3章搜索策略13.1.1搜索的含义概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索适用情况：不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。搜索的类型按是否使用启发式信息：盲目搜索：按预定的控制
2、策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。按问题的表示方式：状态空间搜索：用状态空间法来求解问题所进行的搜索与或树搜索：用问题归约法来求解问题时所进行的搜索23.1.2状态空间问题求解方法1.状态空间问题表示状态(State)是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：Sk=Sk0Sk1当对每一个分量都给以确定的值时，就得到了一个具体的状态。操作(Operator)也称为算符，它是把问题从一种状态变换为另一种状态的手段。它可理解为状态集合上的
3、一个函数，它描述了状态之间的关系。状态空间(Statespace)用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：(SFG)其中，S为问题的所有初始状态集合；F为操作的集合；G为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。3状态空间法求解问题的基本过程：首先，为问题选择适当的“状态”及“操作”的形式化描述方法；然后，从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止；最后，由初始状态到目标状态所使用的算符序列就是该问题的一个解。3.1.2状态空间问
4、题求解方法2.状态空间问题求解4例3.1二阶梵塔问题设有三根钢针，它们的编号分别是1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面。解：设用Sk=(SkASkB)表示问题的状态，其中，SkA表示金片A所在的钢针号，SkB表示金片B所在的钢针号。全部可能的问题状态共有以下9种：S0=(11)S1=(12)S2=(13)S3=(21)S4=(22)S5=(23)S6=(31)S7=(32)S8=(33)3.1.2状态空间问题求解方法3.状态空间的例子(110)
5、5ABABAB123123123图3.1二阶梵塔问题的初始状态和目标状态初始状态集合S=S0目标状态集合G=S4S8初始状态S0和目标状态S4、S8如下图S0=(11)S4=(22)S8=(33)3.1.2状态空间问题求解方法3.状态空间的例子(210)6操作Aij表示把金片A从第i号钢针移到j号钢针上；Bij表示把金片B从第i号钢针一到第j号钢针上。共有12种操作，它们分别是：A12A13A21A23A31A32B12B13B21B23B31B32根据上述9种可能的状态和12种操作，可构成二阶梵塔问题的状态空间图，如下图所示。3.1.2状态空间问题求解方法3.状态空间的例子(310)7从初始
6、节点(11)到目标节点(22)及(33)的任何一条路径都是问题的一个解。其中，最短的路径长度是3，它由3个操作组成。例如，从(11)开始，通过使用操作A13、B12及A32，可到达(33)。(11)B12A13(21)(32)(23)(33)(13)(31)(12)(22)A32A12B13A233.1.2状态空间问题求解方法3.状态空间的例子(410)图3.2二阶梵塔的状态空间图8例3.2修道士(Missionaries)和野人(Cannibals)问题(简称M-C问题)。设在河的一岸有3个野人、3个修道士和1条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：第一，修道士和野人
7、都会划船，但每次船上至多可载2个人；第二，在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。解：先选取描述问题状态的方法。这里，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸，故可用如下三元组来表示状态S=(mcb)其中，m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数。而右岸的状态可由下式确定：右岸修道士数m=3-m右岸野人数c=3-c右岸船数b=1-b在这种表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有442=32种状
8、态。3.1.2状态空间问题求解方法3.状态空间的例子(510)9有效状态在32种状中，除去不合法和修道士被野人吃掉的状态，有效状态只16种：S0=(331)S1=(321)S2=(311)S3=(221)S4=(111)S5=(031)S6=(021)S7=(011)S8=(320)S9=(310)S10=(300)S11=(220)S12=(110)S13=(020)S14=(010)S15=(000)过河操作过河操作是指用船把修道士或野人从河的左岸运到右岸，或从右岸运到左岸的动作。每个操作都应当满足如下条件：第一，船上至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的
9、m和c的增加数目；第二，每次操作船上人数不得超过2个；第三，操作应保证不产生非法状态。操作的结构条件：只有当其条件具备时才能使用动作：刻划了应用此操作所产生的结果。3.1.2状态空间问题求解方法3.状态空间的例子(610)10操作的表示Lij表示有i个修道士和j个野人，从左岸到右岸的操作Rij表示有i个修道士和j个野人，从右岸到左岸的操作操作集本问题有10种操作可供选择，他们的集合称为操作集，即A=L01L10L11L02L20R01R10R11R02R20操作的例子下面以L01和R01为例来说明这些操作的条件和动作。操作符号条件动作L01b=1m=0或3c1b=0c=c-1R01b=0m=0
10、或3，c2b=1c=c+13.1.2状态空间问题求解方法3.状态空间的例子(710)11abc例3.3猴子摘香蕉问题。在讨论谓词逻辑知识表示时，我们曾提到过这一问题，现在用状态空间法来解决这一问题。解：问题的状态可用4元组（wxyz）表示。其中：w表示猴子的水平位置；x表示箱子的水平位置；y表示猴子是否在箱子上，当猴子在箱子上时，y取1；否则y取0；z表示猴子是否拿到香蕉，当拿到香蕉时z取1，否则z取0。3.1.2状态空间问题求解方法3.状态空间的例子(810)12所有可能的状态S0:(ab00)初始状态S1:(bb00)S2:(cc00)S3:(cc10)S4:(cc11)目标状态允许的操作
11、为Goto(u)：猴子走到位置u，即(wx00)(ux00)Pushbox(v):猴子推着箱子到水平位置v，即(xx00)(vv00)Climbbox:猴子爬上箱子，即(xx00)(xx10)Grasp；猴子拿到香蕉，即(cc10)(cc11)问题的状态空间图如下图所示。可见，由初始状态到目标状态的操作序列为：Goto(b)Pushbox(c)ClimbboxGrasp3.1.2状态空间问题求解方法3.状态空间的例子(910)13猴子摘香蕉问题的状态空间图(ab00)(bb00)(cc00)(bb10)(cc10)(aa00)(cc11)Goto(b)Pushbox(c)Grasp初始状态图3
12、.3猴子摘香蕉问题的状态空间图Pushbox(c)ClimbboxClimbboxPushbox(c)Pushbox(a)Pushbox(a)3.1.2状态空间问题求解方法3.状态空间的例子(0110)Goto(b)目标状态14基本思想当一问题较复杂时，可通过分解或变换，将其转化为一系列较简单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。分解如果一个问题P可以归约为一组子问题P1P2Pn，并且只有当所有子问题Pi都有解时原问题P才有解，任何一个子问题Pi无解都会导致原问题P无解，则称此种归约为问题的分解。即分解所得到的子问题的“与”与原问题P等价。等价变换如果一个问题P可以归约为一
13、组子问题P1P2Pn，并且子问题Pi中只要有一个有解则原问题P就有解，只有当所有子问题Pi都无解时原问题P才无解，称此种归约为问题的等价变换，简称变换。即变换所得到的子问题的“或”与原问题P等价。3.1.3问题归约求解方法1.问题的分解与等价变换15PP1P2P3P1P2P3PPP1P2P3P11P12P31P32P33(1)与树分解(2)或树等价变换(3)与或树3.1.3问题归约求解方法2.问题归约的与或树表示与树或树与或树16(4)端节点与终止节点在与或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。可见，终止节点一定是端节点，但端节点却不一定是终止节点。(5)可解节点
14、与不可解节点在与或树中，满足以下三个条件之一的节点为可解节点：任何终止节点都是可解节点。对“或”节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点。对“与”节点，只有当其子节点全部为可解节点时，该与节点才是可解节点。同样，可用类似的方法定义不可解节点：不为终止节点的端节点是不可解节点。对“或”节点，若其全部子节点都为不可解节点，则该或节点是不可解节点。对“与”节点，只要其子节点中有一个为不可解节点，则该与节点是不可解节点。3.1.3问题归约求解方法2.问题归约的与或树表示17Pttt(6)解树由可解节点构成，并且由这些可解节点可以推出初始节点（它对应着原始问题）为可解节点的子树为
15、解树。在解树中一定包含初始节点。例如，右图给出的与或树中，用红线表示的子树是一个解树。在该图中，节点P为原始问题节点，用t标出的节点是终止节点。根据可解节点的定义，很容易推出原始问题P为可解节点。问题归约求解过程就实际上就是生成解树，即证明原始节点是可解节点的过程。这一过程涉及到搜索的问题，对于与或树的搜索将在后面详细讨论。3.1.3问题归约求解方法2.问题归约的与或树表示18例3.4三阶梵塔问题。要求把1号钢针上的3个金片全部移到3号钢针上，如下图所示。解：这个问题也可用状态空间法来解，不过本例主要用它来说明如何用归约法来解决问题。为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设
16、用三元组(ijk)表示问题在任一时刻的状态，用“”表示状态的转换。上述三元组中i代表金片A所在的钢针号j代表金片B所在的钢针号k代表金片C所在的钢针号1231233.1.3问题归约求解方法3.问题归约的例子ABCABC19利用问题归约方法，原问题可分解为以下三个子问题：(1)把金片A及B移到2号钢针上的双金片移动问题。即(111)(221)(2)把金片C移到3号钢针上的单金片移动问题。即(221)(223)(3)把金片A及B移到3号钢针的双金片移动问题。即(223)(333)其中，子问题(1)和(3)都是一个二阶梵塔问题，它们都还可以再继续进行分解；子问题(2)是本原问题，它已不需要再分解。三阶梵塔问题的分解过程可用如下图与或树来表示(111)(333)(111)(221)(221)(223)(223)(333)(111)(311)(311)(321)(321)(221)(223)(123)(123)(133)(133)(333)在该与或树中，有7个终止节点，它们分别对应着7个本原问题。如果把这些本原问
