1、1搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。劣，将直接影响到智能系统的性能与推理效率。 3.1 搜索概述搜索概述3.1.1 搜索的含义搜索的含义 3.1.2 状态空间问题求解方法状态空间问题求解方法 3.1.3 问题归约求解方法问题归约求解方法3.2 搜索的盲目策略搜索的盲目策略3.3 状态空间的启发式搜索状态空间的启发式搜索3.4 与与/或树的启发式搜索或树的启发式搜索3.5 博弈树的启发式搜索博弈树的启发式搜索第第3章章 搜索策略搜索策略23.1.1 搜索的含义搜索的
2、含义概念：概念： 依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索适用情况：适用情况： 不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。算法可供求解使用。搜索的类型搜索的类型 按是否使用启发式信息：按是否使用启发式信息： 盲目搜索：盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息按预定的
3、控制策略进行搜索，在搜索过程中获得的中间信息并并不改变控制策略不改变控制策略。 启发式搜索：启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。着最有希望的方向前进，加速问题的求解过程并找到最优解。 按问题的表示方式：按问题的表示方式： 状态空间搜索：状态空间搜索：用状态空间法来求解问题所进行的搜索用状态空间法来求解问题所进行的搜索 与或树搜索：与或树搜索：用问题归约法来求解问题时所进行的搜索用问题归约法来求解问题时所进行的搜索33.1.2 状态空间问题求解方法状态空间问题求解
4、方法1. 状态空间问题表示状态空间问题表示状态状态(State) 是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为： Sk=Sk0, Sk1, 当对每一个分量都给以确定的值时，就得到了一个具体的状态。当对每一个分量都给以确定的值时，就得到了一个具体的状态。操作操作(Operator) 也称为算符，它是把问题从一种状态变换为另一种状态的手段。它可理解也称为算符，它是把问题从一种状态变换为另一种状态的手段。它可理解为状态集合上的一个函数，它描述了状态之间的关系。为状态集合上的一个函数，它描述了状态之间的关系。状态空间状态
5、空间(State space) 用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：元组表示为： (S, F, G)其中，其中，S为问题的所有初始状态集合；为问题的所有初始状态集合；F为操作的集合；为操作的集合；G为目标状态的集合。为目标状态的集合。 状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。状态空间图中，节点表示问题的状态，有向边表示操作。4状态空间法求解问题的基本过程：
6、状态空间法求解问题的基本过程： 首先，为问题选择适当的首先，为问题选择适当的“状态状态”及及“操作操作”的形式化描述方法；的形式化描述方法； 然后，从某个初始状态出发，每次使用一个然后，从某个初始状态出发，每次使用一个“操作操作”，递增地建立起操，递增地建立起操作序列，直到达到目标状态为止；作序列，直到达到目标状态为止； 最后，由初始状态到目标状态所使用的算符序列就是该问题的一个解。最后，由初始状态到目标状态所使用的算符序列就是该问题的一个解。 3.1.2 状态空间问题求解方法状态空间问题求解方法2. 状态空间问题求解状态空间问题求解5 例例3.1 二阶梵塔问题二阶梵塔问题 设有三根钢针，它们
7、的编号分别是设有三根钢针，它们的编号分别是1号、号、2号和号和3号。在初始情况下，号。在初始情况下，1号钢号钢针上穿有针上穿有A、B两个金片，两个金片，A比比B小，小，A位于位于B的上面。要求把这两个金片全部的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面的位于小的上面。 解：解：设用设用Sk=(SkA, SkB)表示问题的状态，其中，表示问题的状态，其中，SkA表示金片表示金片A所在的钢针所在的钢针号，号，SkB表示金片表示金片B所在的钢针号。所在的钢针号。 全部可能
8、的问题状态共有以下全部可能的问题状态共有以下9种：种： S0=(1, 1) S1=(1, 2) S2=(1, 3) S3=(2, 1) S4=(2, 2) S5=(2, 3) S6=(3, 1) S7=(3, 2) S8=(3, 3) 3.1.2 状态空间问题求解方法状态空间问题求解方法3. 状态空间的例子状态空间的例子(1/10)6 ABABAB 1 2 3 1 2 3 1 2 3图图3.1 二阶梵塔问题的初始状态和目标状态二阶梵塔问题的初始状态和目标状态初始状态集合初始状态集合 S=S0目标状态集合目标状态集合 G=S4, S8 初始状态初始状态S0和目标状态和目标状态S4、S8如下图如下
9、图 S0=(1, 1)S4=(2, 2)S8=(3, 3)3.1.2 状态空间问题求解方法状态空间问题求解方法3. 状态空间的例子状态空间的例子(2/10)7操作操作 Aij 表示把金片表示把金片A从第从第i号钢针移到号钢针移到j号钢针上；号钢针上； Bij 表示把金片表示把金片B从第从第i号钢针一到第号钢针一到第j号钢针上。号钢针上。共有共有12种操作，它们分别是：种操作，它们分别是： A12 A13 A21 A23 A31 A32 B12 B13 B21 B23 B31 B32 根据上述根据上述9种可能的状态和种可能的状态和12种操作，可构成二阶梵塔问题的状态空间图，种操作，可构成二阶梵塔
10、问题的状态空间图，如下图所示。如下图所示。3.1.2 状态空间问题求解方法状态空间问题求解方法3. 状态空间的例子状态空间的例子(3/10)8 从初始节点从初始节点(1, 1)到目标节点到目标节点(2, 2)及及(3, 3)的任何一条路径都是问题的一个的任何一条路径都是问题的一个解。其中，最短的路径长度是解。其中，最短的路径长度是3，它由，它由3个操作组成。例如，从个操作组成。例如，从 (1, 1)开始，开始，通过使用操作通过使用操作A13、B12及及A32，可到达，可到达 (3, 3)。(1,1)B12A13(2,1)(3,2)(2,3)(3,3)(1,3)(3,1)(1,2)(2,2)A3
11、2A12B13A233.1.2 状态空间问题求解方法状态空间问题求解方法3. 状态空间的例子状态空间的例子(4/10)图图3.2 二阶梵塔的状态空间图二阶梵塔的状态空间图9 例例3.2 修道士修道士(Missionaries)和野人和野人(Cannibals)问题问题(简称简称M-C问题问题)。 设在河的一岸有设在河的一岸有3个野人、个野人、3个修道士和个修道士和1条船，修道士想用这条船把所有的条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：人运到河对岸，但受以下条件的约束： 第一，修道士和野人都会划船，但每次船上至多可载第一，修道士和野人都会划船，但每次船上至多可载2个人；个
12、人； 第二，在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。第二，在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。 如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。河，且没有修道士被野人吃掉的安全过河计划。 解：解：先选取描述问题状态的方法。这里，需要考虑两岸的修道士人数和野先选取描述问题状态的方法。这里，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸，故可用如下三元组来表示状态人数，还需要考虑船在左岸还是在右岸，故可用如下三元组来表
13、示状态 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种状态。种状态。 3.1.2 状态空间问题求解方法状态空间问题求解方法3. 状态空间的例子状态空间的例子(5/10)10有效状态有效
14、状态 在在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)过河操作过河操作 过河操作是指用船把修道
15、士或野人从河的左岸运到右岸，或从右岸运到左过河操作是指用船把修道士或野人从河的左岸运到右岸，或从右岸运到左岸的动作。每个操作都应当满足如下条件：岸的动作。每个操作都应当满足如下条件： 第一，船上至少有一个人（第一，船上至少有一个人（m或或c）操作，离开岸边的）操作，离开岸边的m和和c的减少数目应该的减少数目应该等于到达岸边的等于到达岸边的m和和c的增加数目；的增加数目； 第二，每次操作船上人数不得超过第二，每次操作船上人数不得超过2个；个； 第三，操作应保证不产生非法状态。第三，操作应保证不产生非法状态。操作的结构操作的结构 条件：条件：只有当其条件具备时才能使用只有当其条件具备时才能使用 动
16、作：动作：刻划了应用此操作所产生的结果。刻划了应用此操作所产生的结果。 3.1.2 状态空间问题求解方法状态空间问题求解方法3. 状态空间的例子状态空间的例子(6/10)11操作的表示操作的表示 Lij 表示有表示有i个修道士和个修道士和j个野人，从左岸到右岸的操作个野人，从左岸到右岸的操作 Rij 表示有表示有i个修道士和个修道士和j个野人，从右岸到左岸的操作个野人，从右岸到左岸的操作操作集操作集 本问题有本问题有10种操作可供选择，他们的集合称为操作集，即种操作可供选择，他们的集合称为操作集，即 A=L01, L10, L11, L02, L20,R01, R10, R11, R02, R
17、20操作的例子操作的例子 下面以下面以L01和和R01为例来说明这些操作的条件和动作。为例来说明这些操作的条件和动作。 操作符号操作符号 条件条件 动作动作 L01 b=1, m=0或或3, c1 b=0, c=c-1 R01 b=0, m=0或或3，c2 b=1, c=c+1 3.1.2 状态空间问题求解方法状态空间问题求解方法3. 状态空间的例子状态空间的例子(7/10)12abc 例例3.3 猴子摘香蕉问题。猴子摘香蕉问题。在讨论谓词逻辑知识表示时，我们曾提到过这一问在讨论谓词逻辑知识表示时，我们曾提到过这一问题，现在用状态空间法来解决这一问题。题，现在用状态空间法来解决这一问题。 解：
18、解：问题的状态可用问题的状态可用4元组元组 （w, x, y, z）表示。其中：表示。其中： w 表示猴子的水平位置；表示猴子的水平位置； x 表示箱子的水平位置；表示箱子的水平位置； y 表示猴子是否在箱子上，当猴表示猴子是否在箱子上，当猴子在箱子上时，子在箱子上时，y取取1；否则；否则y取取0； z 表示猴子是否拿到香蕉，当拿表示猴子是否拿到香蕉，当拿到香蕉时到香蕉时z取取1，否则，否则z取取0。3.1.2 状态空间问题求解方法状态空间问题求解方法3. 状态空间的例子状态空间的例子(8/10)13所有可能的状态所有可能的状态 S0: (a, b, 0, 0) 初始状态初始状态 S1: (b
19、, 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
20、)问题的状态空间图问题的状态空间图 如下图所示。可见，由初始状态到目标状态的操作序列为：如下图所示。可见，由初始状态到目标状态的操作序列为： Goto(b), Pushbox(c), Climbbox, Grasp3.1.2 状态空间问题求解方法状态空间问题求解方法3. 状态空间的例子状态空间的例子(9/10)14猴子摘香蕉问题的状态空间图猴子摘香蕉问题的状态空间图(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)Pushbox(c)Grasp 初始状态初始状态图图3.3 猴子摘香蕉问题的状态空间图猴子
21、摘香蕉问题的状态空间图Pushbox(c)ClimbboxClimbboxPushbox(c)Pushbox(a)Pushbox(a)3.1.2 状态空间问题求解方法状态空间问题求解方法3. 状态空间的例子状态空间的例子(01/10)Goto(b)目标状态目标状态15基本思想基本思想 当一问题较复杂时，可通过分解或变换，将其转化为一系列较简单的子问当一问题较复杂时，可通过分解或变换，将其转化为一系列较简单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。题，然后通过对这些子问题的求解来实现对原问题的求解。分解分解 如果一个问题如果一个问题P可以归约为一组子问题可以归约为一组子问题P1,
22、P2,Pn，并且只有当所有子问题，并且只有当所有子问题Pi都有解时原问题都有解时原问题P才有解，任何一个子问题才有解，任何一个子问题Pi无解都会导致原问题无解都会导致原问题P无解，无解，则称此种归约为问题的分解。则称此种归约为问题的分解。 即分解所得到的即分解所得到的子问题的子问题的“与与”与原问题与原问题P等价等价。等价变换等价变换 如果一个问题如果一个问题P可以归约为一组子问题可以归约为一组子问题P1,P2,Pn，并且子问题，并且子问题Pi中只要有中只要有一个有解则原问题一个有解则原问题P就有解，只有当所有子问题就有解，只有当所有子问题Pi都无解时原问题都无解时原问题P才无解，才无解，称此
23、种归约为问题的等价变换，简称变换。称此种归约为问题的等价变换，简称变换。 即变换所得到的子问题的即变换所得到的子问题的“或或”与原问题与原问题P等价。等价。 3.1.3 问题归约求解方法问题归约求解方法1. 问题的分解与等价变换问题的分解与等价变换16P P1 P2 P3 P1 P2 P3PP P1 P2 P3 P11 P12 P31 P32 P33(1)与树与树 分解分解(2) 或树或树 等价变换等价变换(3) 与与/或树或树3.1.3 问题归约求解方法问题归约求解方法2. 问题归约的与问题归约的与/或树表示或树表示与树与树或树或树与与/或树或树17(4) 端节点与终止节点端节点与终止节点
24、在与在与/或树中，没有子节点的节点称为或树中，没有子节点的节点称为端节点端节点；本原问题所对应的节点称；本原问题所对应的节点称为为终止节点终止节点。可见，终止节点一定是端节点，但端节点却不一定是终止节点。可见，终止节点一定是端节点，但端节点却不一定是终止节点。(5) 可解节点与不可解节点可解节点与不可解节点 在与在与/或树中，满足以下三个条件之一的节点为或树中，满足以下三个条件之一的节点为可解节点：可解节点： 任何终止节点都是可解节点。任何终止节点都是可解节点。 对对“或或”节点，当其子节点中至少有一个为可解节点时，则该或节点就节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点。
25、是可解节点。 对对“与与”节点，只有当其子节点全部为可解节点时，该与节点才是可解节点，只有当其子节点全部为可解节点时，该与节点才是可解节点。节点。 同样，可用类似的方法定义同样，可用类似的方法定义不可解节点：不可解节点： 不为终止节点的端节点是不可解节点。不为终止节点的端节点是不可解节点。 对对“或或”节点，若其全部子节点都为不可解节点，则该或节点是不可解节点，若其全部子节点都为不可解节点，则该或节点是不可解节点。节点。 对对“与与”节点，只要其子节点中有一个为不可解节点，则该与节点是不节点，只要其子节点中有一个为不可解节点，则该与节点是不可解节点。可解节点。3.1.3 问题归约求解方法问题归
26、约求解方法2. 问题归约的与问题归约的与/或树表示或树表示18Pt t t (6) 解树解树 由可解节点构成，并且由这些可解节由可解节点构成，并且由这些可解节点可以推出初始节点（它对应着原始问点可以推出初始节点（它对应着原始问题）为可解节点的子树为解树。在解树题）为可解节点的子树为解树。在解树中一定包含初始节点。中一定包含初始节点。 例如，右图给出的与或树中，用红例如，右图给出的与或树中，用红 线线表示的子树是一个解树。在该图中，节表示的子树是一个解树。在该图中，节点点P为原始问题节点，用为原始问题节点，用t标出的节点是标出的节点是终止节点。根据可解节点的定义，很容终止节点。根据可解节点的定义
27、，很容易推出原始问题易推出原始问题P为可解节点。为可解节点。 问题归约求解过程就实际上就是生成问题归约求解过程就实际上就是生成解树，即证明原始节点是可解节点的过解树，即证明原始节点是可解节点的过程。程。这一过程涉及到搜索的问题，对于这一过程涉及到搜索的问题，对于与与/或树的搜索将在后面详细讨论。或树的搜索将在后面详细讨论。3.1.3 问题归约求解方法问题归约求解方法2. 问题归约的与问题归约的与/或树表示或树表示19 例例3.4 三阶梵塔问题。要求把三阶梵塔问题。要求把1号钢针上的号钢针上的3个金片全部移到个金片全部移到3号钢针上，号钢针上，如下图所示。如下图所示。 解：解：这个问题也可用状态
28、空间法来解，不过本例主要用它来说明如何这个问题也可用状态空间法来解，不过本例主要用它来说明如何用归约法来解决问题。用归约法来解决问题。 为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设用三元组用三元组 (i, j, k)表示问题在任一时刻的状态，用表示问题在任一时刻的状态，用“”表示状态的转换。上述三元组中表示状态的转换。上述三元组中 i 代表金片代表金片A所在的钢针号所在的钢针号 j 代表金片代表金片B所在的钢针号所在的钢针号 k 代表金片代表金片C所在的钢针号所在的钢针号1231233.1.3 问题归约求解方法问题归约
29、求解方法3. 问题归约的例子问题归约的例子ABCABC20利用问题归约方法，原问题可分解为以下利用问题归约方法，原问题可分解为以下三个子问题：三个子问题： (1) 把金片把金片A及及B移到移到2号钢针上的双金片移动问题。即号钢针上的双金片移动问题。即(1, 1, 1)(2, 2, 1) (2) 把金片把金片C移到移到3号钢针上的单金片移动问题。即号钢针上的单金片移动问题。即 (2, 2, 1)(2, 2, 3) (3) 把金片把金片A及及B移到移到3号钢针的双金片移动问题。即号钢针的双金片移动问题。即(2, 2, 3)( (3, 3, 3)其中，子问题其中，子问题(1)和和(3)都是一个二阶梵
30、塔问题，它们都还可以再继续进行分解；都是一个二阶梵塔问题，它们都还可以再继续进行分解；子问题子问题(2)是本原问题，它已不需要再分解。是本原问题，它已不需要再分解。 三阶梵塔问题的分解过程可用如下图与三阶梵塔问题的分解过程可用如下图与/或树来表示或树来表示 (1,1,1)(3,3,3) (1,1,1)(2,2,1) (2,2,1)(2,2,3) (2,2,3)(3,3,3)(1,1,1)(3,1,1) (3,1,1)(3,2,1) (3,2,1)(2,2,1) (2,2,3)(1,2,3) (1,2,3)(1,3,3) (1,3,3)(3,3,3) 在该与在该与/或树中，有或树中，有7个终止节
31、点，它们分别对应着个终止节点，它们分别对应着7个本原问题。如果把个本原问题。如果把这些本原问题从左至右排列起来，即得到了原始问题的解：这些本原问题从左至右排列起来，即得到了原始问题的解： (1, 1, 1)(3, 1, 1) (3, 1, 1)(3, 2, 1) (3, 2, 1)(2, 2, 1) (2, 2, 1)(2, 2, 3) (2, 2, 3)(1, 2, 3) (1, 2, 3)(1, 3, 3) (1, 3, 3)(3, 3, 3) 21搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智
32、能系统的性能与推理效率。劣，将直接影响到智能系统的性能与推理效率。 3.1 搜索概述搜索概述3.2 搜索的盲目策略搜索的盲目策略 3.2.1状态空间的盲目搜索状态空间的盲目搜索 3.2.2 代价树的盲目搜索代价树的盲目搜索3.3 状态空间的启发式搜索状态空间的启发式搜索3.4 与与/或树的启发式搜索或树的启发式搜索3.5 博弈树的启发式搜索博弈树的启发式搜索第第3章章 搜索策略搜索策略22状态空间搜索的基本思想状态空间搜索的基本思想 先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节
33、点中。若出现，节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。已生成的子节点中选择一个节点作为当前扩展节点。 重复上述过程，直到目标状态出现在子节点中或者没有可供操作的重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。所谓对一个节点进行节点为止。所谓对一个节点进行“扩展扩展”是指对该节点用某个可用操是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。作进行作用，生成该节点的一组子节点。 算法的
34、数据结构和符号约定算法的数据结构和符号约定 Open表：用于存放刚生成的节点表：用于存放刚生成的节点 Closed表：用于存放已经扩展或将要扩展的节点表：用于存放已经扩展或将要扩展的节点 S0：用表示问题的初始状态：用表示问题的初始状态3.2.1 状态空间的盲目搜索状态空间的盲目搜索基本思想基本思想23基本思想基本思想 从初始节点从初始节点S0开始逐层向下扩展，开始逐层向下扩展，在第在第n层节点还没有全部搜索完之层节点还没有全部搜索完之前，不进入第前，不进入第n+1层节点的搜索层节点的搜索。Open表中的节点总是按进入的先后表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在
35、后面。排序，先进入的节点排在前面，后进入的节点排在后面。搜索算法搜索算法 (1)把初始节点把初始节点S0放入放入Open表中；表中； (2)如果如果Open表为空，则问题无解，失败退出；表为空，则问题无解，失败退出； (3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为表，并记该节点为n； (4)考察考察n是否为目标节点。若是，则得到问题的解，成功退出；是否为目标节点。若是，则得到问题的解，成功退出； (5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步； (6)扩展节点扩展节点n，将其子节点放入，将其子节点放入Open表的尾部，并为每一个子节
36、点表的尾部，并为每一个子节点设置设置指向父节点的指针指向父节点的指针，然后转第，然后转第(2)步。步。 3.2.1 状态空间的盲目搜索状态空间的盲目搜索广度优先搜索（广度优先搜索（1/3）24 例例3.5 八数码难题。在八数码难题。在33的方格棋盘上，分别放置了表有数字的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态的八张牌，初始状态S0，目标状态，目标状态Sg，如下图，如下图所示。可以使用的操作有所示。可以使用的操作有 空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，空格下移即只允许把位于空格左、上、右、下方的牌移入空格。要求应用广度即只允
37、许把位于空格左、上、右、下方的牌移入空格。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径优先搜索策略寻找从初始状态到目标状态的解路径。 2 8 31 47 6 5 1 2 38 47 6 5 S0 Sg3.2.1 状态空间的盲目搜索状态空间的盲目搜索广度优先搜索（广度优先搜索（2/3）252 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 52 8 1 4 37 6 52 8 31 4 57 6 2
38、 8 31 6 4 7 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 46 58 3 2 1 47 6 58 1 32 47 6 52 8 37 46 1 52 8 37 1 46 5 1 2 38 47 6 51 2 37 8 4 6 51 2 3 8 47 6 52 3 41 8 7 6 52 81 4 37 6 52 8 31 4 57 62 8 3 6 41 7 52 8 31 6 7 5 4S0 12 3 4 56 7 8 9 10 11 12 1314 15 16 17 18 19 20 2122 23 24 25 26 27Sg3.2.1 状态空间的盲
39、目搜索状态空间的盲目搜索广度优先搜索（广度优先搜索（3/3）263.2.1 状态空间的盲目搜索状态空间的盲目搜索深度优先搜索深度优先搜索 深度优先搜索算法和广度优先搜索算法的步骤基本相同，它深度优先搜索算法和广度优先搜索算法的步骤基本相同，它们之间的主要差别在于们之间的主要差别在于Open表中的节点排序不同。在深度优先表中的节点排序不同。在深度优先搜索算法中，搜索算法中，最后进人最后进人Open表的节点总是排在最前面，即后生表的节点总是排在最前面，即后生成的节点先扩展成的节点先扩展。 深度优先搜索是一种深度优先搜索是一种非完备策略非完备策略。对某些问题，它有可能找。对某些问题，它有可能找不到最
40、优解，或者根本就找不到解。常用的解决方法是增加一不到最优解，或者根本就找不到解。常用的解决方法是增加一个深度限制，当搜索达到规定深度但没找到解时向宽度搜索，个深度限制，当搜索达到规定深度但没找到解时向宽度搜索，称为有界深度优先搜索。它们的具体算法描述和例子省略。称为有界深度优先搜索。它们的具体算法描述和例子省略。273.2.2 代价树的盲目搜索代价树的盲目搜索代价树的代价及广度优先搜索代价树的代价及广度优先搜索(1/2) 代价树的代价：代价树的代价：用用g(n)表示从初始节点表示从初始节点S0到节点到节点n的代价，用的代价，用c(n, n1)表示从表示从父节点父节点n到其子节点到其子节点n1的
41、代价。这样，对节点的代价。这样，对节点n1的代价有：的代价有： g(n1)=g(n)+c(n, n1)。 代价树搜索的目的是为了找到最佳解，即找到一条代价最小的解路径。代价树搜索的目的是为了找到最佳解，即找到一条代价最小的解路径。 代价树的广度优先搜索算法：代价树的广度优先搜索算法： (1) 把初始节点把初始节点S0放入放入Open表中，置表中，置S0的代价的代价g(S0)=0； (2) 如果如果Open表为空，则问题无解表为空，则问题无解 ，失败退出；，失败退出； (3) 把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为表，并记该节点为n； (4) 考察节
42、点考察节点n是否为目标。若是，则找到了问题的解，成功退出；是否为目标。若是，则找到了问题的解，成功退出； (5) 若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步； (6) 扩展节点扩展节点n，生成其子节点，生成其子节点ni(i=1, 2, )，将这些子节点放入，将这些子节点放入Open表中，表中，并为每一个子节点设置指向父节点的指针。按如下公式：并为每一个子节点设置指向父节点的指针。按如下公式： g(ni)=g (n) +c (n , ni) i=1,2,.计算各子结点的代价，并根据各子结点的代价对计算各子结点的代价，并根据各子结点的代价对Open表中的表中的全部结点全部结点按由小
43、按由小到大的顺序排序。然后转第到大的顺序排序。然后转第(2)步。步。28 例例3.6 城市交通问题。设有城市交通问题。设有5个城市，它们之间的交通线路如左图所示，图个城市，它们之间的交通线路如左图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从索，求从A市出发到市出发到E市，费用最小的交通路线。市，费用最小的交通路线。 ABCDE43 4 523 2 4 5AC1B1D1D2E1E2B2C2E33 43 4 2 3城市交通图城市交通图 城市交通图的代价树城市交通图的代价树 解：解：代价树如右图所示。
44、其中，红线代价树如右图所示。其中，红线为最优解，其代价为为最优解，其代价为83.2.2 代价树的盲目搜索代价树的盲目搜索代价树的代价及广度优先搜索代价树的代价及广度优先搜索(2/2)293.2.3 代价树的盲目搜索代价树的盲目搜索代价树的深度优先搜索代价树的深度优先搜索 代价树的深度优先搜索算法和代价树的广度优先搜索算法的代价树的深度优先搜索算法和代价树的广度优先搜索算法的步骤也基本相同，它们之间的主要差别在于步骤也基本相同，它们之间的主要差别在于Open表中的节点排表中的节点排序不同。在代价树的深度优先搜索算法中，每当扩展一个节点序不同。在代价树的深度优先搜索算法中，每当扩展一个节点后，后，
45、仅是把刚生成的子节点按照其边代价由小到大放入仅是把刚生成的子节点按照其边代价由小到大放入Open表表的首部的首部，而不需要对，而不需要对Open表中的全部节点再重新进行排序。表中的全部节点再重新进行排序。 代价树的深度优先搜索是一种非完备策略。对某些问题，它代价树的深度优先搜索是一种非完备策略。对某些问题，它有可能找不到最优解，或者根本找不到解。为此，也可增加一有可能找不到最优解，或者根本找不到解。为此，也可增加一个深度限制，个深度限制，当搜索达到规定深度但仍没找到解时向宽度搜索当搜索达到规定深度但仍没找到解时向宽度搜索，称为代价树的有界深度优先搜索。它们的具体算法描述和例子称为代价树的有界深
46、度优先搜索。它们的具体算法描述和例子省略。省略。 30搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。劣，将直接影响到智能系统的性能与推理效率。 3.1 搜索概述搜索概述3.2 搜索的盲目策略搜索的盲目策略3.3 状态空间的启发式搜索状态空间的启发式搜索 3.3.1启发性信息和估价函数启发性信息和估价函数 3.3.2 A算法算法 3.3.3 A*算法算法 3.3.4 A*算法应用举例算法应用举例3.4 与与/或树的启发式搜索或树的启发式搜索3.5 博弈树的启发式搜索博弈树的启发
47、式搜索第第3章章 搜索策略搜索策略31启发性信息启发性信息 启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。最有希望方向前进的控制信息。 启发信息的启发信息的启发能力越强，扩展的无用结点越少启发能力越强，扩展的无用结点越少。包括以下。包括以下3种：种： 有效地帮助确定扩展节点的信息；有效地帮助确定扩展节点的信息； 有效的帮助决定哪些后继节点应被生成的信息；有效的帮助决定哪些后继节点应被生成的信息； 能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。能决定在扩展一个节点时哪些节点应从搜
48、索树上删除的信息。 估价函数估价函数 用来估计节点重要性，定义为从初始节点用来估计节点重要性，定义为从初始节点S0出发，约束经过节点出发，约束经过节点n到达目标到达目标节点节点Sg的所有路径中最小路径代价的估计值。一般形式：的所有路径中最小路径代价的估计值。一般形式： f(n)=g(n)+h(n)其中，其中，g(n)是从初始节点是从初始节点S0到节点到节点n的实际代价；的实际代价；h(n)是从节点是从节点n到目标节点到目标节点Sg的的最优路径最优路径的估计代价。的估计代价。 3.3.1 启发性信息和估价函数启发性信息和估价函数概念概念32 解：解：即即g(n)=d(n)，h(n)=W(n)。
49、d(n)说明用从说明用从S0到到n的路径上的单位代价表的路径上的单位代价表示实际代价；示实际代价； W(n)说明用结点说明用结点n中中“不在位不在位”的数码个数作为启发信息。的数码个数作为启发信息。 可见，某节点中的可见，某节点中的“不在位不在位”的数码个数越多，说明它离目标节点越远。的数码个数越多，说明它离目标节点越远。 对初始节点对初始节点S0，由于，由于d(S0)=0，W(S0)=3，因此有，因此有 f(S0)=0+3=3 2 8 31 47 6 5 1 2 38 47 6 5 S0Sg 例例3.7 八数码难题。设问题的初始状态八数码难题。设问题的初始状态S0和目标状态和目标状态Sg如下
50、图所示，且估价如下图所示，且估价函数为函数为 f(n)=d(n)+W(n)其中：其中：d(n)表示节点表示节点n在搜索树中的深度在搜索树中的深度 W(n)表示节点表示节点n中中“不在位不在位”的数码个数。的数码个数。请计算初始状态请计算初始状态S0的估价函数值的估价函数值f(S0)3.3.1 启发性信息和估价函数启发性信息和估价函数例子例子33 在状态空间搜索中，如果每一步都利用估价函数在状态空间搜索中，如果每一步都利用估价函数f(n)=g(n)+h(n)对对Open表表中的节点进行排序，则称中的节点进行排序，则称A算法。它是一种为启发式搜索算法。算法。它是一种为启发式搜索算法。类型：类型：
