搜索是人工智能中的一个基本问题

《搜索是人工智能中的一个基本问题》由会员分享，可在线阅读，更多相关《搜索是人工智能中的一个基本问题（90页珍藏版）》请在金锄头文库上搜索。

1、 搜索是人工智能中的一个基本问题，并与推理密切相关， 搜索策略的优劣，将直接影响到智能系统的性能与推理效率。 搜索的基本概念搜索的基本概念状态空间的盲目搜索状态空间的启发式搜索与/或树的盲目搜索与/或树的启发式搜索博弈树的启发式搜索第4章 搜索策略14.1 搜索的基本概念4.1.1 搜索的含义4.1.2 状态空间法4.1.3 问题归约法24.1.1 搜索的含义适用情况：不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算 法可供求解使用。 概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从 而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索搜索的类型

2、按是否使用启发式信息：盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并 不改变控制策略。 启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝 着最有希望的方向前进，加速问题的求解过程并找到最优解。 按问题的表示方式：状态空间搜索：用状态空间法来求解问题所进行的搜索 与或树搜索：用问题归约法来求解问题时所进行的搜索 34.1.2 状态空间法 1. 状态空间表示方法状态(State)：是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：Sk=Sk0, Sk1, 当对每一个分量都给以确定的值时，就得到了一个具体的状态。 操作(Operator)也称为算符，它

3、是把问题从一种状态变换为另一种状态的手段。操作可以是 一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一 个函数，它描述了状态之间的关系。 状态空间(State space)用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组 表示为：(S, F, G) 其中，S为问题的所有初始状态的集合；F为操作的集合；G为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态 空间图中，节点表示问题的状态，有向边表示操作。4状态空间法求解问题的基本过程：首先为问题选择适当的“状态”及“操作”的形式化 描述方法；然后从某个初始状态出发，每次使

4、用一个“操作”， 递增地建立起操作序列，直到达到目标状态为止；此时，由初始状态到目标状态所使用的算符序列就是 该问题的一个解。 4.1.2 状态空间法 2. 状态空间问题求解5例4.1 二阶梵塔问题。设有三根钢针，它们的编号分别是 1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个 金片，A比B小，A位于B的上面。要求把这两个金片全部移 到另一根钢针上，而且规定每次只能移动一个金片，任何时 刻都不能使大的位于小的上面。解：设用Sk=(Sk0, Sk1)表示问题的状态，其中，Sk0表示金 片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能 的问题状态共有以下9种：S0=(1, 1)

5、S1=(1, 2) S2=(1, 3) S3=(2, 1) S4=(2, 2) S5=(2, 3) S6=(3, 1) S7=(3, 2) S8=(3, 3) 4.1.2 状态空间法 3. 状态空间的例子(1/11)6ABABAB1 2 3 1 2 3 1 2 3二阶梵塔问题的初始状态和目标状态问题的初始状态集合为S=S0目标状态集合为G=S4, S5 初始状态S0和目标状态S4、S8如图所示 S0=(1, 1)S4=(2, 2)S8=(3, 3)4.1.2 状态空间法 3. 状态空间的例子(2/11)7操作分别用A(i, j)和B(i, j)表示A(i, j)表示把金片A从第i号钢针移到j号

6、钢针上；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种操作，可构成二阶梵塔问题的 状态空间图，如下图所示。4.1.2 状态空间法 3. 状态空间的例子(3/11)8(3,3) (1,3) (1,2) (2,2)二阶梵塔的状态空间图从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条路径都是问题的一 个解。其中，最短的路径

7、长度是3，它由3个操作组成。例如，从 (1, 1)开始 ，通过使用操作A(1, 3)、B(1, 2)及A(3, 2)，可到达 (3, 3)。A(1,2 )B(1,3 )A(2,3 )(1,1)(3,1)(3,2)(2,1 )(2,3)A(1,3 )B(1,2 )A(3,2 )9例4.2 修道士(Missionaries)和野人(Cannibals)问题(简称M -C问题)。设在河的一岸有三个野人、三个修道士和一条船，修道士想 用这条船把所有的人运到河对岸，但受以下条件的约束：一是修道士和野人都会划船，但每次船上至多可载两个人；二是在河的任一岸，如果野人数目超过修道士数，修道士会 被野人吃掉。如

8、果野人会服从任何一次过河安排，请规划一个确保修道士 和野人都能过河，且没有修道士被野人吃掉的安全过河计划。 4.1.2 状态空间法 3. 状态空间的例子(5/11)10解：首先选取描述问题状态的方法。在这个问题中，需要 考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在 右岸。从而可用一个三元组来表示状态S=(m, c, b) 其中，m表示左岸的修道士人数，c表示左岸的野人数，b表示 左岸的船数。右岸的状态可由下式确定：右岸修道士数 m=3-m右岸野人数 c=3-c右岸船数 b=1-b在这种表示方式下，m和c都可取0、1、2、3中之一，b可取 0和1中之一。因此，共有442=32种状态。

9、4.1.2 状态空间法 3. 状态空间的例子(6/11)11这32种状态并非全有意义，除去不合法状态和修道士被野人吃 掉的状态，有意义的状态只有16种：S0=(3, 3, 1) S1=(3, 2, 1) S2=(3, 1, 1) S3=(2, 2, 1)S4=(1, 1, 1) S5=(0, 3, 1) S6=(0, 2, 1) S7=(0, 1, 1)S8=(3, 2, 0) S9=(3, 1, 0) S10=(3, 0, 0) S11=(2, 2, 0)S12=(1, 1,0) S13=(0, 2, 0) S14=(0, 1, 0) S15=(0, 0, 0) 有了这些状态，还需要考虑可进

10、行的操作。操作是指用船把修道士或野人从河的左岸运到右岸，或从河的 右岸运到左岸。每个操作都应当满足如下条件：一是船至少有一个人（m或c）操作，离开岸边的m和c的减少数 目应该等于到达岸边的m和c的增加数目；二是每次操作船上人数不得超过2个；三是操作应保证不产生非法状态。因此，操作应由条件部分和动作部分：条件：只有当其条件具备时才能使用动作：刻划了应用此操作所产生的结果。 12操作的表示： 用符号Pij表示从左岸到右岸的运人操作用符号Qij表示从右岸到左岸的操作其中：i表示船上的修道士人数 j表示船上的野人数操作集本问题有10种操作可供选择：F=P01, P10, P11, P02, P20,Q

11、01, Q10, Q11, Q02, Q20下面以P01和Q01为例来说明这些操作的条件和动作。操作符号 条件 动作P01 b=1, m=0或3, c1 b=0, c=c-1Q01 b=0, m=0或3，c2 b=1, c=c+1 13abc例4.3 猴子摘香蕉问题。在讨论谓词逻辑知识表示时，我们曾 提到过这一问题，现在用状态空间法来解决这一问题。解：问题的状态可用4元组（w, x, y, z） 表示。其中：w表示猴子的水平位置；x表示箱子的水平位置；y表示猴子是否在箱子上 ，当猴子在箱子上时，y取1 ，否则y取0；z表示猴子是否拿到香蕉， 当拿到香蕉时z取1，否则z取 0。4.1.2 状态空

12、间法 3. 状态空间的例子(9/11)14所有可能的状态为S0: (a, b, 0, 0) 初始状态S1: (b, b, 0, 0)S2: (c, c, 0, 0)S3: (c, c, 1, 0)S4: (c, c, 1, 1) 目标状态 允许的操作为Goto(u)：猴子走到位置u，即(w, x, 0, 0)(u, x, 0, 0)Pushbox(v): 猴子推着箱子到水平位置v，即(x, x, 0, 0)(v, v, 0, 0)Climbbox: 猴子爬上箱子，即(x, x, 0, 0)(x, x, 1, 0)Grasp；猴子拿到香蕉，即(c, c, 1, 0 )(c, c, 1, 1)这个

13、问题的状态空间图如下图所示。不难看出，由初始状态 变为目标状态的操作序列为：Goto(b), Pushbox(c), Climbbox, Grasp15猴子摘香蕉问题的解(a,b,0,0)(b,b,0,0)(c,c,0,0)(b ,b,1,0)(c,c,1,0)(a,a,0,0)(c,c,1,1)初始状态Goto(b) Goto(b )Pushbox(c )Grasp 目标状态猴子摘香蕉问题的状态空间图解序列为： Goto(b), Pushbox(c), Climbbox, GraspPushbox(c )ClimbboxClimbbox Pushbox(c)Pushbox(a )Pushbo

14、x(a )16基本思想当一问题较复杂时，可通过分解或变换，将其转化为一系列较简 单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。 分解 如果一个问题P可以归约为一组子问题P1,P2,Pn，并且只有当所有 子问题Pi都有解时原问题P才有解，任何一个子问题Pi无解都会导致原 问题P无解，则称此种归约为问题的分解。即分解所得到的子问题的“与”与原问题P等价。 等价变换如果一个问题P可以归约为一组子问题P1,P2,Pn，并且子问题Pi 中只要有一个有解则原问题P就有解，只有当所有子问题Pi都无解时 原问题P才无解，称此种归约为问题的等价变换，简称变换。即变换所得到的子问题的“或”与原问题P

15、等价。4.1.3 问题归约法 1. 问题的分解与等价变换17PP1 P2 P3与树P1 P2 P3或树PPP1 P2 P3P12 P12 P31 P32 P33与/或树(1)与树 分解(2) 或树 等价变换(3) 与/或树4.1.3 问题归约法 2. 问题的与/或树表示18(4) 端节点与终止节点在与/或树中，没有子节点的节点称为端节点；本原问题所对应的节 点称为终止节点。可见，终止节点一定是端节点，但端节点却不一定是 终止节点。(5) 可解节点与不可解节点在与/或树中，满足以下三个条件之一的节点为可解节点：任何终止节点都是可解节点。对“或”节点，当其子节点中至少有一个为可解节点时，则该或节点就 是可解节点。对“与”节点，只有当其子节点全部为可解节点时，该与节点才是可解 节点。同样，可用类似的方法定义不可解节点：