《搜索是人工智能中的一个基本问题》由会员分享，可在线阅读，更多相关《搜索是人工智能中的一个基本问题（90页珍藏版）》请在金锄头文库上搜索。
1、搜索是人工智能中的一个基本问题，并与推理密切相关，搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。搜索策略的优劣，将直接影响到智能系统的性能与推理效率。搜索的基本概念搜索的基本概念状态空间的盲目搜索状态空间的盲目搜索状态空间的启发式搜索状态空间的启发式搜索与与/或树的盲目搜索或树的盲目搜索与与/或树的启发式搜索或树的启发式搜索博弈树的启发式搜索博弈树的启发式搜索第第4章章搜索策略搜索策略14.1搜索的基本概念搜索的基本概念4.1.1搜索的含义搜索的含义4.1.2状态空间法状态空间法4.1.3问题归约法问题归约法24.1.1搜索的含义搜索的
2、含义适用情况：适用情况：不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。法可供求解使用。概念：概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索搜索的类型搜索的类型按是否使用启发式信息：按是否使用启发式信息：盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并盲目搜索：按预定的控制策
3、略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。不改变控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。着最有希望的方向前进，加速问题的求解过程并找到最优解。按问题的表示方式：按问题的表示方式：状态空间搜索：用状态空间法来求解问题所进行的搜索状态空间搜索：用状态空间法来求解问题所进行的搜索与或树搜索：用问题归约法来求解问题时所进行的搜索与或树搜索：用问题归约法来求解问题时所进行的搜索34.1.2状态空间法状态空间法1.状态空间表示方法状态空间表示
4、方法状态状态(State)：是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：Sk=Sk0,Sk1,当对每一个分量都给以确定的值时，就得到了一个具体的状态。当对每一个分量都给以确定的值时，就得到了一个具体的状态。操作操作(Operator)也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一个函数，它
5、描述了状态之间的关系。个函数，它描述了状态之间的关系。状态空间状态空间(Statespace)用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：表示为：(S,F,G)其中，其中，S为问题的所有初始状态的集合；为问题的所有初始状态的集合；F为操作的集合；为操作的集合；G为目标状态的集合。为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。空间图中，节点表示问
6、题的状态，有向边表示操作。4状态空间法求解问题的基本过程：状态空间法求解问题的基本过程： 首先为问题选择适当的首先为问题选择适当的“状态状态”及及“操作操作”的形式化的形式化描述方法；描述方法； 然后从某个初始状态出发，每次使用一个然后从某个初始状态出发，每次使用一个“操作操作”，递增地建立起操作序列，直到达到目标状态为止；递增地建立起操作序列，直到达到目标状态为止； 此时，由初始状态到目标状态所使用的算符序列就是此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。该问题的一个解。 4.1.2状态空间法状态空间法2.状态空间问题求解状态空间问题求解5例例4.1二二阶阶梵梵塔塔问问题题
7、。设设有有三三根根钢钢针针，它它们们的的编编号号分分别别是是1号号、2号号和和3号号。在在初初始始情情况况下下，1号号钢钢针针上上穿穿有有A、B两两个个金金片片，A比比B小小，A位位于于B的的上上面面。要要求求把把这这两两个个金金片片全全部部移移到到另另一一根根钢钢针针上上，而而且且规规定定每每次次只只能能移移动动一一个个金金片片，任任何何时时刻都不能使大的位于小的上面刻都不能使大的位于小的上面。 解：解：设用设用Sk=(Sk0, Sk1)表示问题的状态，其中，表示问题的状态，其中，Sk0表示金表示金片片A所在的钢针号，所在的钢针号，Sk1表示金片表示金片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) 4.1.2状态空间法状态空间法3.状态空间的例子状态空间的例子(1/11)6ABABAB123123123二阶梵塔问题的初始状态和目标状态二阶梵塔问题的初始状态和目标状态问题的初始状态集合问题的初始状态集合为为S=S0 目标状态集合目标状态集合为为G=S4, S5初始状态初始状态S0和目标状态和目标状态S4、S8如图所示如图所示 S0=(1, 1)S4=(2,
9、2)S8=(3, 3)4.1.2状态空间法状态空间法3.状态空间的例子状态空间的例子(2/11)7 操作分别用操作分别用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) 根据上述根
10、据上述9种可能的状态和种可能的状态和12种操作，可构成二阶梵塔问题的种操作，可构成二阶梵塔问题的状态空间图，如下图所示。状态空间图，如下图所示。4.1.2状态空间法状态空间法3.状态空间的例子状态空间的例子(3/11)8(3,3)(1,3)(1,2)(2,2)二阶梵塔的状态空间图从初始节点从初始节点(1,1)到目标节点到目标节点(2,2)及及(3,3)的任何一条路径都是问题的的任何一条路径都是问题的一个解。其中，最短的路径长度是一个解。其中，最短的路径长度是3，它由，它由3个操作组成。例如，从个操作组成。例如，从(1,1)开开始，通过使用操作始，通过使用操作A(1,3)、B(1,2)及及A(3
11、,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问题问题)。设在河的一岸有三个野人、三个修道士和一条船，修道士想设在河的一岸有三个野人、三个修道士和一条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：用这条船把所有的人运到河对岸，但受以下条件的约束：一是修道士和野人都会划船，但每次船上至多可载两个人；一是修道士和野人都会划船，但每次船上至多可载两个人；二是在河的任一
12、岸，如果野人数目超过修道士数，修道士会二是在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。被野人吃掉。如果野人会服从任何一次过河安排，请规划一个确保修道士如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。和野人都能过河，且没有修道士被野人吃掉的安全过河计划。4.1.2状态空间法状态空间法3.状态空间的例子状态空间的例子(5/11)10 解：解：首先选取描述问题状态的方法。在这个问题中，需要首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在考虑两岸的修道士人数和野人数，还需要考虑
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种状态。种状态。 4.1.2状态空间法状态空间法3.状态空
14、间的例子状态空间的例子(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,
15、1, 0) S15=(0, 0, 0)有了这些状态，还需要考虑可进行的操作。有了这些状态，还需要考虑可进行的操作。 操作操作是指用船把修道士或野人从河的左岸运到右岸，或从河的是指用船把修道士或野人从河的左岸运到右岸，或从河的右岸运到左岸。右岸运到左岸。 每个操作都应当满足如下条件：每个操作都应当满足如下条件： 一是一是船至少有一个人（船至少有一个人（m或或c）操作，离开岸边的）操作，离开岸边的m和和c的减少数的减少数目应该等于到达岸边的目应该等于到达岸边的m和和c的增加数目；的增加数目； 二是二是每次操作船上人数不得超过每次操作船上人数不得超过2个；个； 三是三是操作应保证不产生非法状态。操作
16、应保证不产生非法状态。 因此，因此，操作应由条件部分和动作部分：操作应由条件部分和动作部分： 条件：条件：只有当其条件具备时才能使用只有当其条件具备时才能使用 动作：动作：刻划了应用此操作所产生的结果。刻划了应用此操作所产生的结果。12操作的表示：操作的表示： 用符号用符号Pij表示从左岸到右岸的运人操作表示从左岸到右岸的运人操作 用符号用符号Qij表示从右岸到左岸的操作表示从右岸到左岸的操作其中：其中： i表示表示船上的修道士人数船上的修道士人数 j表示表示船上的野人数船上的野人数操作集操作集 本问题有本问题有10种操作可供选择：种操作可供选择： F=P01, P10, P11, P02,
17、P20,Q01, Q10, Q11, Q02, Q20 下面以下面以P01和和Q01为例来说明这些操作的条件和动作。为例来说明这些操作的条件和动作。 操作符号操作符号 条件条件 动作动作 P01 b=1, m=0或或3, c1 b=0, c=c-1 Q01 b=0, m=0或或3，c2 b=1, c=c+113abc 例例4.3猴子摘香蕉问题。猴子摘香蕉问题。在讨论谓词逻辑知识表示时，我们曾在讨论谓词逻辑知识表示时，我们曾提到过这一问题，现在用状态空间法来解决这一问题。提到过这一问题，现在用状态空间法来解决这一问题。解：解：问题的状态可用问题的状态可用4元组元组 （w, x, y, z）表示。
18、其中：表示。其中： w表示猴子的水平位置；表示猴子的水平位置； x表示箱子的水平位置；表示箱子的水平位置； y表示猴子是否在箱子上，表示猴子是否在箱子上，当猴子在箱子上时，当猴子在箱子上时，y取取1，否则否则y取取0； z表示猴子是否拿到香蕉，表示猴子是否拿到香蕉，当拿到香蕉时当拿到香蕉时z取取1，否则，否则z取取0。4.1.2状态空间法状态空间法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,
19、 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, 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)ClimbboxClimbboxPushbox(c)Pushbox(a)Pushbox(a)16基
21、本思想基本思想 当一问题较复杂时，可通过分解或变换，将其转化为一系列较简当一问题较复杂时，可通过分解或变换，将其转化为一系列较简单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。分解分解 如果一个问题如果一个问题P可以归约为一组子问题可以归约为一组子问题P1,P2,Pn，并且只有当所，并且只有当所有子问题有子问题Pi都有解时原问题都有解时原问题P才有解，任何一个子问题才有解，任何一个子问题Pi无解都会导致无解都会导致原问题原问题P无解，则称此种归约为问题的分解。无解，则称此种归约为问题的分解。 即分解所得到的子问题的即分解所
22、得到的子问题的“与与”与原问题与原问题P等价。等价。等价变换等价变换如果一个问题如果一个问题P可以归约为一组子问题可以归约为一组子问题P1,P2,Pn，并且子问题，并且子问题Pi中只要有一个有解则原问题中只要有一个有解则原问题P就有解，只有当所有子问题就有解，只有当所有子问题Pi都无解时都无解时原问题原问题P才无解，称此种归约为问题的等价变换，简称变换。才无解，称此种归约为问题的等价变换，简称变换。即变换所得到的子问题的即变换所得到的子问题的“或或”与原问题与原问题P等价。等价。4.1.3问题归约法问题归约法1.问题的分解与等价变换问题的分解与等价变换17PP1P2P3与树与树P1P2P3或树
23、或树PPP1P2P3P12P12P31P32P33与与/或树或树(1)与树与树分解分解(2)或树或树等价变换等价变换(3)与与/或或树树4.1.3问题归约法问题归约法2.问题的与问题的与/或树表示或树表示18(4)端节点与终止节点端节点与终止节点在与在与/或树中，没有子节点的节点称为或树中，没有子节点的节点称为端节点端节点；本原问题所对应的节；本原问题所对应的节点称为点称为终止节点终止节点。可见，终止节点一定是端节点，但端节点却不一定是。可见，终止节点一定是端节点，但端节点却不一定是终止节点。终止节点。(5)可解节点与不可解节点可解节点与不可解节点在与在与/或树中，满足以下三个条件之一的节点为
24、或树中，满足以下三个条件之一的节点为可解节点：可解节点：任何终止节点都是可解节点。任何终止节点都是可解节点。对对“或或”节点，当其子节点中至少有一个为可解节点时，则该或节点节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点。就是可解节点。对对“与与”节点，只有当其子节点全部为可解节点时，该与节点才是可节点，只有当其子节点全部为可解节点时，该与节点才是可解节点。解节点。同样，可用类似的方法定义同样，可用类似的方法定义不可解节点：不可解节点：不为终止节点的端节点是不可解节点。不为终止节点的端节点是不可解节点。 对对“或或”节点，若其全部子节点都为不可解节点，则该或节点是不可节点，若其
25、全部子节点都为不可解节点，则该或节点是不可解节点。解节点。 对对“与与”节点，只要其子节点中有一个为不可解节点，则该与节点是节点，只要其子节点中有一个为不可解节点，则该与节点是不可解节点。不可解节点。19Pttt解树解树(6)解树解树由可解节点构成，并且由这些可解由可解节点构成，并且由这些可解节点可以推出初始节点（它对应着原节点可以推出初始节点（它对应着原始问题）为可解节点的子树为解树。始问题）为可解节点的子树为解树。在解树中一定包含初始节点。在解树中一定包含初始节点。例如，右图给出的与或树中，用红例如，右图给出的与或树中，用红线表示的子树是一个解树。在该图中，线表示的子树是一个解树。在该图中
26、，节点节点P为原始问题节点，用为原始问题节点，用t标出的节标出的节点是终止节点。根据可解节点的定义，点是终止节点。根据可解节点的定义，很容易推出原始问题很容易推出原始问题P为可解节点。为可解节点。问题归约求解过程就实际上就是生问题归约求解过程就实际上就是生成解树，即证明原始节点是可解节点成解树，即证明原始节点是可解节点的过程。这一过程涉及到搜索的问题，的过程。这一过程涉及到搜索的问题，对于与对于与/或树的搜索将在后面详细讨或树的搜索将在后面详细讨论。论。20例例4.4三阶梵塔问题。要求把三阶梵塔问题。要求把1号钢针上的号钢针上的3个金片全部移到个金片全部移到3号钢针号钢针上，如下图所示。上，如
27、下图所示。解：解：这个问题也可用状态空间法来解，不过本例主要用它来说明如何这个问题也可用状态空间法来解，不过本例主要用它来说明如何用归约法来解决问题。用归约法来解决问题。为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设用三元组用三元组(i,j,k)表示问题在任一时刻的状态，用表示问题在任一时刻的状态，用“”表示状态的转换。上述三元组中表示状态的转换。上述三元组中i代表金片代表金片C所在的钢针号所在的钢针号j代表金片代表金片B所在的钢针号所在的钢针号k代表金片代表金片A所在的钢针号所在的钢针号1231234.1.3问题归约法
28、问题归约法2.问题的与问题的与/或树表示或树表示ABCABC21利用问题归约方法，原问题可分解为以下利用问题归约方法，原问题可分解为以下三个子问题：三个子问题：(1)把金片把金片A及及B移到移到2号钢针上的双金片移动问题。即号钢针上的双金片移动问题。即(1,1,1)(1,2,2)(2)把金片把金片C移到移到3号钢针上的单金片移动问题。即号钢针上的单金片移动问题。即(1,2,2)(3,2,2)(3)把金片把金片A及及B移到移到3号钢针的双金片移动问题。即号钢针的双金片移动问题。即(3,2,2)(3,3,3)其中，子问题其中，子问题(1)和和(3)都是一个二阶梵塔问题，它们都还可以再继续进行分解；
29、都是一个二阶梵塔问题，它们都还可以再继续进行分解；子问题子问题(2)是本原问题，它已不需要再分解。是本原问题，它已不需要再分解。三阶梵塔问题的分解过程可用如下图与三阶梵塔问题的分解过程可用如下图与/或树来表示或树来表示 (1,1,1)(3,3,3)(1,1,1)(1,2,2)(1,2,2)(3,2,2)(3,2,2)(3,3,3)(1,1,1)(1,1,3)(1,1,3)(1,2,3)(1,2,3)(1,2,2)(3,2,2)(3,2,1)(3,2,1)(3,3,1)(3,3,1)(3,3,3)在该与在该与/或树中，有或树中，有7个终止节点，它们分别对应着个终止节点，它们分别对应着7个本原问题
30、。如果把个本原问题。如果把这些本原问题从左至右排列起来，即得到了原始问题的解：这些本原问题从左至右排列起来，即得到了原始问题的解：(1,1,1)(1,3,3)(1,3,3)(1,2,3)(1,2,3)(1,2,2)(1,2,2)(3,2,2)(3,2,2)(3,2,1)(3,2,1)(3,3,1)(3,3,1)(3,3,3) 22v搜索的基本概念搜索的基本概念 状态空间的盲目搜索状态空间的盲目搜索v状态空间的启发式搜索状态空间的启发式搜索v与与/或树的盲目搜索或树的盲目搜索v与与/或树的启发式搜索或树的启发式搜索v博弈树的启发式搜索博弈树的启发式搜索第第4章章搜索策略搜索策略234.2状态空间
31、的盲目搜索状态空间的盲目搜索4.2.1一般图搜索过程一般图搜索过程4.2.2广度优先和深度优先搜索广度优先和深度优先搜索4.2.3代价树搜索代价树搜索24状态空间搜索的基本思想状态空间搜索的基本思想 先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节
32、点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。所谓对一个节点进行中或者没有可供操作的节点为止。所谓对一个节点进行“扩展扩展”是指对该节是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。点用某个可用操作进行作用，生成该节点的一组子节点。 4.2.1一般图搜索过程一般图搜索过程算法的数据结构和符号约定算法的数据结构和符号约定Open表：用于存放刚生成的节点表：用于存放刚生成的节点Closed表：用于存放已经扩展或将要扩展的节点表：用于存放已经扩展或将要扩展的节点S0：用表示问题的初
33、始状态：用表示问题的初始状态G：表示搜索过程所得到的搜索图：表示搜索过程所得到的搜索图M：表示当前扩展节点新生成的且不为自己先辈的子节点集。：表示当前扩展节点新生成的且不为自己先辈的子节点集。25一般图搜索过程一般图搜索过程 (1) 把初始节点把初始节点S0放入放入Open表，并建立目前仅包含表，并建立目前仅包含S0的图的图G； (2) 检查检查Open表是否为空，若为空，则问题无解，失败推出；表是否为空，若为空，则问题无解，失败推出； (3) 把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为节点表，并记该节点为节点n； (4)考察节点考察节点n是否为目标节
34、点。若是则得到了问题的解，成功退出；是否为目标节点。若是则得到了问题的解，成功退出；(5)扩展节点扩展节点n，生成一组子节点。把这些子节点中不是节点，生成一组子节点。把这些子节点中不是节点n先辈的那先辈的那部分子节点记入集合部分子节点记入集合M，并把这些子节点作为节点，并把这些子节点作为节点n的子节点加入的子节点加入G中中(6)针对针对M中子节点的不同情况，分别作如下处理：中子节点的不同情况，分别作如下处理：对那些没有在对那些没有在G中出现过的中出现过的M成员设置一个指向其父节点（即节点成员设置一个指向其父节点（即节点n）的指针，并把它放入）的指针，并把它放入Open表。（新生成的）表。（新生
35、成的）对那些原来已在对那些原来已在G中出现过，但还没有被扩展的中出现过，但还没有被扩展的M成员，确定是否需成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的）要修改它指向父节点的指针。（原生成但未扩展的）对于那些先前已在对于那些先前已在G中出现过，并已经扩展了的中出现过，并已经扩展了的M成员，确定是否需成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的）要修改其后继节点指向父节点的指针。（原生成也扩展过的）(7)按某种策略对按某种策略对Open表中的节点进行排序。表中的节点进行排序。(8)转第转第(2)步。步。26算法的几点说明：算法的几点说明：(1)上述过程是状态
36、空间的一般图搜索算法，它具有通用性，后面上述过程是状态空间的一般图搜索算法，它具有通用性，后面所要讨论的各种状态空间搜索策略都是上述过程的一个特例。各种搜索所要讨论的各种状态空间搜索策略都是上述过程的一个特例。各种搜索策略的主要区别在于对策略的主要区别在于对Open表中节点的排列顺序不同。例如，广度优先表中节点的排列顺序不同。例如，广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点排在前面。排在前面。(2)在第在第(5)步对节点步对节点n扩展后，生成并记入扩展后，生成并记入M的子节点有以下三种的子节点有以下三种情
37、况：情况：该子节点来从未被任何节点生成过，由该子节点来从未被任何节点生成过，由n第一次生成；第一次生成；该子节点原来被其他节点生成过，但还没有被扩展，这一次又被该子节点原来被其他节点生成过，但还没有被扩展，这一次又被n再次生成；再次生成；该子节点原来被其他节点生成过，并且已经被扩展过，这一次又该子节点原来被其他节点生成过，并且已经被扩展过，这一次又被被n再次生成。再次生成。以上三种情况是对一般图搜索算法而言的。对于盲目搜索，由于其以上三种情况是对一般图搜索算法而言的。对于盲目搜索，由于其状态空间是树状结构，因此不会出现后两种情况，每个节点经扩展后生状态空间是树状结构，因此不会出现后两种情况，每
38、个节点经扩展后生成的子节点都是第一次出现的节点，不必检查并修改指向父节点的指针。成的子节点都是第一次出现的节点，不必检查并修改指向父节点的指针。27 (3)在第在第(6)步针对步针对M中子节点的不同情况进行处理时，如果发生当第中子节点的不同情况进行处理时，如果发生当第种情况，那么，这个种情况，那么，这个M中的节点究竟应该作为哪一个节点的后继节点呢中的节点究竟应该作为哪一个节点的后继节点呢？一般是由原始节点到该节点路径上所付出的代价来决定的，哪一条路？一般是由原始节点到该节点路径上所付出的代价来决定的，哪一条路经付出的代价小，相应的节点就作为它的父节点。所谓由原始节点到该经付出的代价小，相应的节
39、点就作为它的父节点。所谓由原始节点到该节点路径上的代价是指这条路经上的所有有向边的代价之和。节点路径上的代价是指这条路经上的所有有向边的代价之和。如果发生第如果发生第种情况，除了需要确定该子节点指向父节点的指针外，种情况，除了需要确定该子节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针。其依据也是由原始节点到该还需要确定其后继节点指向父节点的指针。其依据也是由原始节点到该节点的路径上的代价。节点的路径上的代价。 (4)在搜索图中，除初始节点外，任意一个节点都含有且只含有一在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针
40、所构个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树。成的集合是一棵树，称为搜索树。(5)在搜索过程的第在搜索过程的第(4)步，一旦某个被考察的节点是目标节点，则步，一旦某个被考察的节点是目标节点，则搜索过程成功结束。由初始节点到目标节点路径上的所有操作就构成了搜索过程成功结束。由初始节点到目标节点路径上的所有操作就构成了该问题的解，而路径由第该问题的解，而路径由第(6)步所形成的指向父节点的指针来确定。步所形成的指向父节点的指针来确定。(6)如果搜索过程终止在第如果搜索过程终止在第(2)步，即没有达到目标，且步，即没有达到目标，且Open表中已表中已
41、无可供扩展的节点，则失败结束。无可供扩展的节点，则失败结束。 28基本思想基本思想 从初始节点从初始节点S0开始逐层向下扩展，在第开始逐层向下扩展，在第n层节点还没有全部搜索完层节点还没有全部搜索完之前，不进入第之前，不进入第n+1层节点的搜索。层节点的搜索。Open表中的节点总是按进入的先表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。后排序，先进入的节点排在前面，后进入的节点排在后面。搜索算法搜索算法(1)把初始节点把初始节点S0放入放入Open表中；表中；(2)如果如果Open表为空，则问题无解，失败退出；表为空，则问题无解，失败退出；(3)把把Open表的第
42、一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为表，并记该节点为n；(4)考察节点考察节点n是否为目标节点。若是，则得到问题的解，成功退出；是否为目标节点。若是，则得到问题的解，成功退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)扩展节点扩展节点n，将其子节点放入，将其子节点放入Open表的尾部，并为每一个子节点表的尾部，并为每一个子节点设置指向父节点的指针，然后转第设置指向父节点的指针，然后转第(2)步。步。 4.2.2广度优先和深度优先搜索广度优先和深度优先搜索1.广度优先搜索广度优先搜索29 例例4.5 八八数数码码难难题题。在在33的的方
43、方格格棋棋盘盘上上，分分别别放放置置了了表表有有数数字字1、2、3、4、5、6、7、8的的八八张张牌牌，初初始始状状态态S0，目目标标状状态态Sg，如下图所示。可以使用的操作有，如下图所示。可以使用的操作有 空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，空格下移即只允许把位于空格左、上、右、下方的牌移入空格。要求应即只允许把位于空格左、上、右、下方的牌移入空格。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径用广度优先搜索策略寻找从初始状态到目标状态的解路径。2 8 331 447 6 5 1 2 38 47 6 5 S0 Sg302831476528314765
44、23184765283147652831647583214765283714652318476523184765281437652831457628316475283164758321476528371465832147658132476528374615283714651238476512378465123847652341876528143765283145762836417528316754S0123456789101112131415161718192021222324252627Sg31算法描述算法描述 (1) (1) 把初始节点把初始节点S0放入放入Open表中；表中； (2) (
45、2) 如果如果OpenOpen表为空，则问题无解表为空，则问题无解 ，失败退出；，失败退出； (3) (3) 把把OpenOpen表的第一个节点取出放入表的第一个节点取出放入ClosedClosed表，并记该节点为表，并记该节点为n n； (4) (4) 考察节点考察节点n n是否为目标节点。若是，则得到问题的解，成功退出；是否为目标节点。若是，则得到问题的解，成功退出； (5) (5) 若节点若节点n n不可扩展，则转第不可扩展，则转第(2)(2)步；步； (6) (6) 扩展节点扩展节点n n，将其子节点放入，将其子节点放入OpenOpen表的首部，并为每一个子节点设置表的首部，并为每一个
46、子节点设置 指向父节点的指针，然后转第指向父节点的指针，然后转第(2)(2)步。步。 4.2.2广度优先和深度优先搜索广度优先和深度优先搜索2.深度优先搜索深度优先搜索基本思想基本思想 从初始节点从初始节点S0开始，在其子节点中选择一个最新生成的节点进行考察，如开始，在其子节点中选择一个最新生成的节点进行考察，如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察，依此向下搜索，直到某个子的子节点中选择一个最新生成的节点进行考察，依此向下搜索，直到某个子节点既不是目标节点，又
47、不能继续扩展时，才选择其兄弟节点进行考察节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。322831476528314765231847652831476528316475283164752831647528316754283167542816375428163754S0123456八数码难题的深度优先搜索如右图八数码难题的深度优先搜索如右图一种改进的深度优先算法是有界深度一种改进的深度优先算法是有界深度优先搜索算法，深度限制为优先搜索算法，深度限制为dm例例4.6八数码难题八数码难题33 在在代代价价树树中中，可可以以用用g(n)表表示示从从初初始始节节点点S0到到节节点点n
48、的的代代价价，用用c(n1, n2)表表示示从从父父节节点点n1到到其其子子节节点点n2的的代代价价。这这样样，对对节节点点n2的的代代价价有有：g(n2)=g(n1)+c(n1, n2)。代代价价树树搜搜索索的的目目的的是是为为了了找找到到最最佳佳解解，即即找找到到一一条代价最小的解路径。条代价最小的解路径。4.2.3代价树搜索代价树搜索1.代价树的广度优先搜索代价树的广度优先搜索代价树的广度优先搜索算法：代价树的广度优先搜索算法： (1) 把初始节点把初始节点S0放入放入Open表中，置表中，置S0的代价的代价g(S0)=0； (2) 如果如果Open表为空，则问题无解表为空，则问题无解
49、，失败退出；，失败退出； (3) 把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为表，并记该节点为n； (4) 考察节点考察节点n是否为目标。若是，则找到了问题的解，成功退出；是否为目标。若是，则找到了问题的解，成功退出； (5) 若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步； (6) 扩展节点扩展节点n，生成其子节点，生成其子节点ni(i=1, 2, )，将这些子节点放入，将这些子节点放入Open表中，并为每一个子节点设置指向父节点的指针。按如下公式：表中，并为每一个子节点设置指向父节点的指针。按如下公式： g(ni)=g(n)+c(ni)
50、i=1,2,.计算各子结点的代价，并根据各子结点的代价对计算各子结点的代价，并根据各子结点的代价对Open表中的全部结点按表中的全部结点按由小到大的顺序排序。然后转第由小到大的顺序排序。然后转第(2)步。步。34 例例4.7 城市交通问题。设有城市交通问题。设有5个城市，它们之间的交通线路如左图个城市，它们之间的交通线路如左图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从的广度优先搜索，求从A市出发到市出发到E市，费用最小的交通路线。市，费用最小的交通路线。ABCDE434523245AC1B1D1D
51、2E1E2B2C2E3343423城市交通图城市交通图 城市交通图的代价树城市交通图的代价树解：解：代价树如右图所示。其中，代价树如右图所示。其中，红线为最优解，其代价为红线为最优解，其代价为8354.2.3代价树搜索代价树搜索2.代价树的深度优先搜索代价树的深度优先搜索代价树的深度优先搜索算法：代价树的深度优先搜索算法：(1)把初始节点把初始节点S0放入放入Open表中，置表中，置S0的代价的代价g(S0)=0；(2)如果如果Open表为空，则问题无解表为空，则问题无解，失败退出；，失败退出；(3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点表，并记该节
52、点为为n；(4)考察节点考察节点n是否为目标节点。若是，则找到了问题的解，是否为目标节点。若是，则找到了问题的解，成功退出；成功退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)扩展节点扩展节点n，生成其子节点，生成其子节点ni(i=1,2,)，将这些子节点，将这些子节点按边代价由小到大放入按边代价由小到大放入Open表的首部，并为每一个子节点设置表的首部，并为每一个子节点设置指向父节点的指针。然后转第指向父节点的指针。然后转第(2)步。步。36v搜索的基本概念搜索的基本概念v状态空间的盲目搜索状态空间的盲目搜索 状态空间的启发式搜索状态空间的启发式搜索v与与/或树
53、的盲目搜索或树的盲目搜索v与与/或树的启发式搜索或树的启发式搜索v博弈树的启发式搜索博弈树的启发式搜索第第4章章搜索策略搜索策略374.3状态空间的启发式搜索状态空间的启发式搜索4.3.1启发性信息和估价函数启发性信息和估价函数4.3.2A算法算法4.3.3A*算法算法4.3.4A*算法应用举例算法应用举例38 启发性信息的概念启发性信息的概念 启启发发性性信信息息是是指指那那种种与与具具体体问问题题求求解解过过程程有有关关的的，并并可指导搜索过程朝着最有希望方向前进的控制信息。可指导搜索过程朝着最有希望方向前进的控制信息。 启发性信息的种类启发性信息的种类 有效地帮助确定扩展节点的信息；有效
54、地帮助确定扩展节点的信息； 有效的帮助决定哪些后继节点应被生成的信息；有效的帮助决定哪些后继节点应被生成的信息； 能能决决定定在在扩扩展展一一个个节节点点时时哪哪些些节节点点应应从从搜搜索索树树上上删删除的信息。除的信息。 启发性信息的作用启发性信息的作用 启发信息的启发能力越强，扩展的无用结点越少。启发信息的启发能力越强，扩展的无用结点越少。4.3.1启发性信息和估价函数启发性信息和估价函数1.启发性信息启发性信息39 估估价价函函数数用用来来估估计计节节点点重重要要性性的的函函数数。估估价价函函数数f(n)被被定定义义为为从从初初始始节节点点S0出出发发，约约束束经经过过节节点点n到到达达
55、目目标标节节点点Sg的的所所有有路路径径中最小路径代价的估计值。它的一般形式为：中最小路径代价的估计值。它的一般形式为： f(n)=g(n)+h(n)其中，其中，g(n)是从初始节点是从初始节点S0到节点到节点n的实际代价；的实际代价；h(n)是从节点是从节点n到目标节点到目标节点Sg的最优路径的估计代价。的最优路径的估计代价。 4.3.1启发性信息和估价函数启发性信息和估价函数2.估价函数估价函数 例例4.8 八数码难题。设问题的初始状态八数码难题。设问题的初始状态S0和目标状态和目标状态Sg如下图如下图所示，且估价函数为所示，且估价函数为 f(n)=d(n)+W(n)其中：其中：d(n)表
56、示节点表示节点n在搜索树中的深度在搜索树中的深度 W(n)表示节点表示节点n中中“不在位不在位”的数码个数。的数码个数。请计算初始状态请计算初始状态S0的估价函数值的估价函数值f(S0)40 解解：取取g(n)=d(n)，h(n)=W(n)。它它说说明明是是用用从从S0到到n的的路路径径上上的的单单位位代代价价表表示示实实际际代代价价，用用结结点点n中中“不不在在位位”的的数数码码个个数数作为启发信息。作为启发信息。 一一般般来来说说，某某节节点点中中的的“不不在在位位”的的数数码码个个数数越越多多，说说明明它它离目标节点越远。离目标节点越远。 对初始节点对初始节点S0，由于，由于d(S0)=
57、0，W(S0)=3，因此有，因此有 f(S0)=0+3=3 2 8 31 47 6 5 1 2 38 47 6 5 S0 Sg41概念：概念： 在图搜索算法中，如果能在搜索的每一步都利用估价函数在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对对Open表中的节点进行排序，则该搜索算法为表中的节点进行排序，则该搜索算法为A算法。算法。 由于估价函数中带有问题自身的启发性信息，因此，由于估价函数中带有问题自身的启发性信息，因此，A算法算法也被称为启发式搜索算法。也被称为启发式搜索算法。类型：类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法可根据搜索过程中选
58、择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。分为全局择优搜索算法和局部择优搜索算法。全局择优：全局择优：从从Open表的所有节点中选择一个估价函数值最表的所有节点中选择一个估价函数值最小的一个进行扩展。小的一个进行扩展。局部择优：局部择优：仅从刚生成的子节点中选择一个仅从刚生成的子节点中选择一个估价函数值最小估价函数值最小的一个进行扩展。的一个进行扩展。4.3.2A算法算法42全局择优搜索全局择优搜索A A算法描述：算法描述： (1) (1)把初始节点把初始节点S0放入放入Open表中，表中，f(S0)=g(S0)+h(S0)； (2) (2)如果如果Open表为
59、空，则问题无解表为空，则问题无解 ，失败退出；，失败退出； (3) (3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为表，并记该节点为n； (4) (4)考察节点考察节点n是否为目标节点。若是，则找到了问题的解，成功退是否为目标节点。若是，则找到了问题的解，成功退出；出； (5) (5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步； (6) (6)扩展节点扩展节点n，生成其子节点，生成其子节点ni(i=1, 2, )，计算每一个子节点的，计算每一个子节点的估价值估价值f(ni)(i=1, 2, )，并为每一个子节点设置指向父节点的指针，并为
60、每一个子节点设置指向父节点的指针，然后将这些子节点放入然后将这些子节点放入Open表中；表中； (7) (7)根据各节点的估价函数值，对根据各节点的估价函数值，对Open表中的全部节点按从小到大表中的全部节点按从小到大的顺序重新进行排序；的顺序重新进行排序； (8) (8)转第转第(2)步。步。 4.3.2A算法算法43 例例4.9 八八数数码码难难题题。设设问问题题的的初初始始状状态态S0和和目目标标状状态态Sg如如图图所所示，估价函数与例示，估价函数与例4.8相同。请用全局择优搜索解决该问题。相同。请用全局择优搜索解决该问题。 解解：该该问问题题的的全全局局择择优优搜搜索索树树如如下下图图
61、所所示示。在在该该图图中中，每每个个节点旁边的数字是该节点的估价函数值。节点旁边的数字是该节点的估价函数值。 例例如如，对对节节点点S2，其其估估价价函函数数值值的的计计算算为为：f(S2)=d(S2)+W(S2) =1+3=42 8 31 47 6 5 1 2 38 47 6 5 S0Sg442831476528314765231847652831476528316475S0832147652837146523184765231847651238476512378465123847654455564644SgS1S2八数码难题的全局择优搜索树八数码难题的全局择优搜索树该问题的解为：该问题的解
62、为： S0S1S2S3SgS3645 4.3.3A*算法算法 A*算法是对算法是对A算法的算法的估价函数估价函数f(n)=g(n)+h(n)加上某些限制后加上某些限制后得到的一种启发式搜索算法得到的一种启发式搜索算法 假设假设f*(n)是从初始节点出发，约束经过节点是从初始节点出发，约束经过节点n达到目标节点达到目标节点的最小代价，估价函数的最小代价，估价函数f(n)是对是对f*(n)的估计值。且的估计值。且 f*(n)=g*(n)+h*(n) A*算法算法对对A算法（全局择优的启发式搜索算法）中的算法（全局择优的启发式搜索算法）中的g(n)和和h(n)分别提出如下限制：分别提出如下限制： 第
63、一，第一，g(n)是对最小代价是对最小代价g*(n)的估计，且的估计，且g(n)0； 第二，第二，h(n)是最小代价是最小代价h*(n)的下界，即对任意节点的下界，即对任意节点n均有均有h(n)h*(n)。 即满足上述两条限制的即满足上述两条限制的A算法称为算法称为A*算法。算法。46 4.3.3A*算法算法1.A*算法的可纳性算法的可纳性(1/6) 可纳性的含义：可纳性的含义： 对任一状态空间图，当从初始节点到目标节点有路经存在时，如果搜索算对任一状态空间图，当从初始节点到目标节点有路经存在时，如果搜索算法总能在有限步骤内找到一条从初始节点到目标节点的最佳路径，并在此路法总能在有限步骤内找到
64、一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的。径上结束，则称该搜索算法是可采纳的。A*算法可纳性的证明算法可纳性的证明 以下分三步（定理以下分三步（定理4.1、定理、定理4.2、定理、定理4.3 ，即引理）进行证明。，即引理）进行证明。 定理定理4.1 对有限图，如果从初始节点对有限图，如果从初始节点S0到目标节点到目标节点Sg有路径存在，则算法有路径存在，则算法A*一定成功结束。一定成功结束。 证明：证明：首先证明算法必然会结束。首先证明算法必然会结束。由于搜索图为有限图，如果算法能找到由于搜索图为有限图，如果算法能找到解，则成功结束；如果算法找不到解，则必
65、然会由于解，则成功结束；如果算法找不到解，则必然会由于Open表变空而结束。因表变空而结束。因此，此，A*算法必然会结束。算法必然会结束。 然后证明算法一定会成功结束。然后证明算法一定会成功结束。由于至少存在一条有初始节点到目标节点由于至少存在一条有初始节点到目标节点的路径，设此路径为的路径，设此路径为 S0=n0, n1, , nk=Sg算法开始时，节点算法开始时，节点n0在在Open表中，而且路径中任一节点表中，而且路径中任一节点ni离开离开Open表后，其表后，其后继节点后继节点ni+1必然进入必然进入Open表，这样，在表，这样，在Open表变为空之前，目标节点必然表变为空之前，目标节
66、点必然出现在出现在Open表中。因此，算法一定会成功结束。表中。因此，算法一定会成功结束。47 引理引理4.1 对无限图，如果从初始节点对无限图，如果从初始节点S0到目标节点到目标节点Sg有路径存在，有路径存在，则算法则算法A*算法不终止的话，则从算法不终止的话，则从Open表中选出的节点必将具有任意表中选出的节点必将具有任意大的大的f值。值。 证明：证明：设设d*(n)是是A*生成的从初始节点生成的从初始节点S0到节点到节点n的最短路经长度，的最短路经长度，由于搜索图中每条边的代价都是一个正数，令这些正数中的最小的一由于搜索图中每条边的代价都是一个正数，令这些正数中的最小的一个数是个数是e，
67、则有，则有 g*(n)d*(n)e因为因为g*(n)是最佳路径的代价，故有是最佳路径的代价，故有 g(n)g*(n)d*(n)e又因为又因为h(n)0，故有，故有 f(n)=g(n)+h(n)g(n)d*(n)e 如果如果A*算法不终止的话，从算法不终止的话，从Open表中选出的节点必将具有任意大表中选出的节点必将具有任意大的的d*(n)值，因此，也将具有任意大的值，因此，也将具有任意大的f值。值。 4.3.3A*算法算法1.A*算法的可纳性算法的可纳性(2/6)48 引理引理4.2 在在A*算法终止前的任何时刻，算法终止前的任何时刻，Open表中总存在节点表中总存在节点n，它是从初始，它是从
68、初始节点节点S0到目标节点的最佳路径上的一个节点，且满足到目标节点的最佳路径上的一个节点，且满足f(n)f*(S0)。 证明：证明：设从初始节点设从初始节点S0到目标节点到目标节点t的一条最佳路径序列为的一条最佳路径序列为S0=n0,n1,nk=Sg算法开始时，节点算法开始时，节点S0在在Open表中，当节点表中，当节点S0离开离开Open表进入表进入Closed表时，表时，节点节点n1进入进入Open表。因此，表。因此，A*没有结束以前，在没有结束以前，在Open表中必存在最佳路径表中必存在最佳路径上的节点。设这些节点中排在最前面的节点为上的节点。设这些节点中排在最前面的节点为n，则有，则有
69、f(n)=g(n)+h(n)由于由于n在最佳路径上，故有在最佳路径上，故有g(n)=g*(n)，从而，从而f(n)=g*(n)+h(n)又由于又由于A*算法满足算法满足h(n)h*(n)，故有，故有f(n)g*(n)+h*(n)=f*(n)因为在最佳路径上的所有节点的因为在最佳路径上的所有节点的f*值都应相等，因此有值都应相等，因此有f(n)f*(S0)4.3.3A*算法算法1.A*算法的可纳性算法的可纳性(3/6)49 定理定理4.2 对无限图，若从初始节点对无限图，若从初始节点S0到目标节点到目标节点Sg有路径存在，有路径存在，则则A*算法必然会结束。算法必然会结束。 证明：证明：（反证法
70、）假设（反证法）假设A*不结束，由引理不结束，由引理4.1知知Open表中的表中的节点有任意大的节点有任意大的f值，这与引理值，这与引理4.2的结论相矛盾，因此，的结论相矛盾，因此，A*算算法只能成功结束。法只能成功结束。 推论推论4.1 Open表中任一具有表中任一具有f(n)f*(S0)但由引理但由引理4.2可知，在可知，在A*算法结束前，必有最佳路径上的一个节点算法结束前，必有最佳路径上的一个节点n在在Open表表中，且有中，且有 f(n)f*(S0)h1(n)则在搜索过程中，被则在搜索过程中，被A2*扩展的节点也必然被扩展的节点也必然被A1*扩展，即扩展，即A1*扩展的扩展的节点不会比
71、节点不会比A2*扩展的节点少，亦即扩展的节点少，亦即A2*扩展的节点集是扩展的节点集是A1*扩展的节扩展的节点集的子集。点集的子集。 4.3.3A*算法算法2.A*算法的最优性算法的最优性(1/2)53 4.3.3A*算法算法2.A*算法的最优性算法的最优性(2/2)证明证明：（用数学归纳法：（用数学归纳法） (1) 对深度对深度d(n)=0的节点，即的节点，即n为初始节点为初始节点S0，如，如n为目标节点，则为目标节点，则A1*和和A2*都都不扩展不扩展n；如果；如果n不是目标节点，则不是目标节点，则A1*和和A2*都要扩展都要扩展n。 (2) 假设对假设对A2 *中中d(n)=k的任意节点
72、的任意节点n结论成立，即结论成立，即A1 *也扩展了这些节点。也扩展了这些节点。 (3) 证明证明A2 *中中d(n)=k+1的任意节点的任意节点n，也要由，也要由A1 *扩展。（用反证法）扩展。（用反证法） 假设假设A2搜索树上有一个满足搜索树上有一个满足d(n)=k+1的节点的节点n，A2 *扩展了该节点，但扩展了该节点，但A1 *没没有扩展它。根据第有扩展它。根据第(2)条的假设，知道条的假设，知道A1 *扩展了节点扩展了节点n的父节点。因此，的父节点。因此，n必定必定在在A1 *的的Open表中。既然节点表中。既然节点n没有被没有被A1 *扩展，则有扩展，则有 f1(n)f*(S0)即
73、即 g1(n)+h1(n)f*(S0)。但由于。但由于d=k时，时，A2 *扩展的节点扩展的节点A1 *也一定扩展，故有也一定扩展，故有 g1(n)g2(n)因此有因此有h1(n)f*(S0)-g2(n) 另一方面，由于另一方面，由于A2 *扩展了扩展了n，因此有，因此有 f2(n)f*(0)即即 g2(n)+h2(n)f*(S0)，亦即，亦即 h2(n)f*(S0)-g2(n)，所以有，所以有 h1(n)h2(n) 这与我们最初假设的这与我们最初假设的h1(n)h2(n)矛盾，因此反证法的假设不成立。矛盾，因此反证法的假设不成立。54 在在A*算法中，每当扩展一个节点算法中，每当扩展一个节点
74、n时，都需要检查其子节点是否已在时，都需要检查其子节点是否已在Open表或表或Closed表中。表中。 对已在对已在Open表中的子节点，需要决定是否调整指向其父节点的指针；表中的子节点，需要决定是否调整指向其父节点的指针； 对已在对已在Closed表中的子节点，除需要决定是否调整其指向父节点的指针表中的子节点，除需要决定是否调整其指向父节点的指针外，还需要决定是否调整其子节点的后继节点的父指针。外，还需要决定是否调整其子节点的后继节点的父指针。 如果能够保证，每当扩展一个节点时就已经找到了通往这个节点的最如果能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径，就没有必要再去作上述
75、检查佳路径，就没有必要再去作上述检查 为满足这一要求，我们需要对启发函数为满足这一要求，我们需要对启发函数h(n)增加单调性限制。增加单调性限制。 定义定义4.1 如果启发函数满足以下两个条件如果启发函数满足以下两个条件: (1) h(Sg)=0; (2) 对任意节点对任意节点ni及其任一子节点及其任一子节点nj，都有，都有 0h(ni)-h(nj)c(ni, nj)其中其中c(ni, nj)是是ni到其子节点到其子节点nj的边代价，则称的边代价，则称h(n)满足单调限制。满足单调限制。4.3.3A*算法算法3.h(n)的单调限制的单调限制(1/3)55 定理定理4.5 如果如果h满足单调条件
76、，则当满足单调条件，则当A*算法扩展节点算法扩展节点n时，该节点就已经找时，该节点就已经找到了通往它的最佳路径，即到了通往它的最佳路径，即g(n)=g*(n)。 证明：证明：设设A*正要扩展节点正要扩展节点n，而节点序列，而节点序列 S0=n0, n1, ,nk=n是由初始节点是由初始节点S0到节点到节点n的最佳路径。其中，的最佳路径。其中，ni是这个序列中最后一个位于是这个序列中最后一个位于Closed表中的节点，则上述节点序列中的表中的节点，则上述节点序列中的ni+1节点必定在节点必定在Open表中，则有表中，则有 g*(ni)+h(ni)g*(ni) +c(ni, ni+1) +h(ni
77、+1)由于节点由于节点ni和和ni+1都在最佳路径上，故有都在最佳路径上，故有 g*( ni+1)=g*(ni)+c(ni, ni+1)所以所以 g*(ni)+h(ni)g*( ni+1) +h(ni+1)一直推导下去可得一直推导下去可得 g*( ni+1)+h(ni+1)g*( nk) +h(nk)由于节点由于节点ni+1在最佳路径上，故有在最佳路径上，故有 f( ni+1)g*( n) +h(n)因为这时因为这时A*扩展节点扩展节点n而不扩展节点而不扩展节点ni+1，则有，则有 f(n)=g(n)+h(n)f( ni+1)g*(n)+h(n)即即 g(n)g*(n)但是但是g*(n)是最小
78、代价值，应当有是最小代价值，应当有 g(n)g*(n)所以有所以有 g(n)=g*(n)4.3.3A*算法算法3.h(n)的单调限制的单调限制(2/3)56 定理定理4.6 如果如果h(n)满足单调限制，则满足单调限制，则A*算法扩展的节点序列的算法扩展的节点序列的f 值是非递减的，即值是非递减的，即f(ni)f(ni+1)。 证明：证明：假设节点假设节点ni+1在节点在节点ni之后立即扩展，由单调限制条件之后立即扩展，由单调限制条件可知可知 h(ni)-h(ni+1)c(ni, ni+1)即即 f(ni)-g(ni)-f(ni+1)+g(ni+1)c(ni, ni+1)亦即亦即 f(ni)-
79、g(ni)-f(ni+1)+g(ni)+c(ni, ni+1)c(ni, ni+1) 所以所以 f(ni)-f(ni+1)0即即 f(ni)f(ni+1) 以上两个定理都是在以上两个定理都是在h(n)满足单调性限制的前提下才成立的。满足单调性限制的前提下才成立的。如果如果h(n)不满足单调性限制，则它们不一定成立。不满足单调性限制，则它们不一定成立。 在在h(n)满足单调性限制下的满足单调性限制下的A*算法常被称为改进的算法常被称为改进的A*算法。算法。4.3.3A*算法算法3.h(n)的单调限制的单调限制(3/3)57例例4.10 八数码难题。八数码难题。283147652831476523
80、18476528314765283164752318476523184765123847651237846512384765S0f=6g*=1h*=3f=6f=6g*=2h*=2f=6f=4g*=3h*=1f=4g*=4h*=0f=4f=6Sg八数码难题h(n)=P(n)的搜索树f(n)=d(n)+P(n)d(n) 深度深度P(n)与目标距离与目标距离显然满足显然满足P(n) h*(n)即即f*=g*+h*f=44.3.4A*算法应用举例算法应用举例h*=4f=458例例4.11 修道士和野人问题。修道士和野人问题。 解解：用用m表表示示左左岸岸的的修修道道士士人人数数，c表表示示左左岸岸的的
81、野野人人数数，b表示左岸的船数，用三元组表示左岸的船数，用三元组(m, c, b)表示问题的状态。表示问题的状态。 对对A*算算法法，首首先先需需要要确确定定估估价价函函数数。设设g(n)=d(n)，h(n)=m+c-2b，则有，则有 f(n)=g(n)+h(n)=d(n)+m+c-2b其中，其中，d(n)为节点的深度。通过分析可知为节点的深度。通过分析可知h(n)h*(n)，满足，满足A*算法的限制条件。算法的限制条件。 M-C问题的搜索过程如下图所示。问题的搜索过程如下图所示。 4.3.4A*算法应用举例算法应用举例59(3,3,1)h=4f=4(3,2,0)(3,1,0)(2,2,0)(
82、3,2,1)(2,1,0)(3,0,0)(2,2,1)(3,1,1)(0,2,0)(1,1,0)(0,3,1)(0,1,0)(0,2,1)(0,0,0)h=5f=6h=3f=5h=3f=6h=3f=6h=2f=6h=2f=7h=1f=7h=1f=8h=0f=8传教士和野人问题的搜索图问题状态：(m,c,b)估价函数：h(n)=m+c-2bh=4f=5h=4f=5h=2f=6h=2f=760v搜索的基本概念搜索的基本概念v状态空间的盲目搜索状态空间的盲目搜索v状态空间的启发式搜索状态空间的启发式搜索 与与/或树的盲目搜索或树的盲目搜索v与与/或树的启发式搜索或树的启发式搜索v博弈树的启发式搜索博
83、弈树的启发式搜索61 与与/或树的搜索过程实际上是一个不断寻找解树的过程。其或树的搜索过程实际上是一个不断寻找解树的过程。其一般搜索过程如下：一般搜索过程如下： (1) (1) 把原始问题作为初始节点把原始问题作为初始节点S S0 0，并把它作为当前节点；，并把它作为当前节点； (2) (2) 应用分解或等价变换操作对当前节点进行扩展；应用分解或等价变换操作对当前节点进行扩展； (3) (3) 为每个子节点设置指向父节点的指针；为每个子节点设置指向父节点的指针； (4) (4) 选择合适的子节点作为当前节点，反复执行第选择合适的子节点作为当前节点，反复执行第(2)(2)步和步和第第(3)(3)
84、步，在此期间需要多次调用可解标记过程或不可解标记步，在此期间需要多次调用可解标记过程或不可解标记过程，直到初始节点被标记为可解节点或不可解节点为止。过程，直到初始节点被标记为可解节点或不可解节点为止。 上述搜索过程将形成一颗与上述搜索过程将形成一颗与/ /或树，这种由搜索过程所形成或树，这种由搜索过程所形成的与的与/ /或树称为搜索树。或树称为搜索树。 4.4.1与与/或树的一般搜索或树的一般搜索62 与与/或树的广度优先搜索与状态空间的广度优先搜索的主或树的广度优先搜索与状态空间的广度优先搜索的主要差别是，需要在搜索过程中需要多次调用可解标识过程或要差别是，需要在搜索过程中需要多次调用可解标
85、识过程或不可解标识过程。不可解标识过程。 其搜索算法如下：其搜索算法如下： (1)把初始节点把初始节点S0放入放入Open表中；表中； (2)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点表，并记该节点为为n； (3)如果节点如果节点n可扩展，则做下列工作：可扩展，则做下列工作： 扩展节点扩展节点n，将其子节点放入，将其子节点放入Open表的尾部，并为每一表的尾部，并为每一个子节点设置指向父节点的指针；个子节点设置指向父节点的指针；4.4.1与与/或树的广度优先和深度优先搜索或树的广度优先和深度优先搜索1.广度优先搜索广度优先搜索63 考考察察这这些些子子节
86、节点点中中有有否否终终止止节节点点。若若有有，则则标标记记这这些些终终止止节节点点为为可可解解节节点点，并并用用可可解解标标记记过过程程对对其其父父节节点点及及先先辈辈节节点点中中的的可可解解解解节节点点进进行行标标记记。如如果果初初始始解解节节点点S0能能够够被被标标记记为为可可解解节节点点，就就得得到到了了解解树树，搜搜索索成成功功，退退出出搜搜索索过过程程；如如果果不不能能确确定定S0为可解节点，则从为可解节点，则从Open表中删去具有可解先辈的节点。表中删去具有可解先辈的节点。 转第转第(2)步。步。 (4) 如果节点如果节点n不可扩展，则作下列工作：不可扩展，则作下列工作： 标记节点
87、标记节点n为不可解节点；为不可解节点； 应应用用不不可可解解标标记记过过程程对对节节点点n的的先先辈辈中中不不可可解解解解的的节节点点进进行行标标记记。如如果果初初始始解解节节点点S0也也被被标标记记为为不不可可解解节节点点，则则搜搜索索失失败败，表表明明原原始始问问题题无无解解，退退出出搜搜索索过过程程；如如果果不不能能确确定定S0为为不不可可解解节点，则从节点，则从Open表中删去具有不可解先辈的节点。表中删去具有不可解先辈的节点。 转第转第(2)步。步。 64 例例4.13 设有下图所示的与设有下图所示的与/或树，节点按标注顺序进行扩展，其中或树，节点按标注顺序进行扩展，其中表有表有t1
88、、t2、t3的节点是终止节点，的节点是终止节点，A、B、C为不可解的端节点。为不可解的端节点。 123A4t15t2Bt3C与/或树的广度优先搜索搜索过程为：搜索过程为： (1) 先扩展先扩展1号号节点，生成节点，生成2号节号节点和点和3号节点。号节点。 (2) 扩展扩展2号节号节点，生成点，生成A节点和节点和4号节点。号节点。 (3) 扩展扩展3号节点，号节点，生成生成t1节点和节点和5号号节点。由于节点。由于t1为终为终止节点，则标记止节点，则标记它为可解节点，它为可解节点，并应用可解标记并应用可解标记过程，不能确定过程，不能确定3号节点是否可解。号节点是否可解。 (6) 扩展扩展5号节点
89、，生成号节点，生成t3节点和节点和C节点。由于节点。由于t3为终为终止节点，则标记它为可解止节点，则标记它为可解节点，并应用可解标记过节点，并应用可解标记过程，可标记程，可标记1号节点为可解号节点为可解节点。节点。 (7) 搜索成功，搜索成功，得到由得到由1、2、3、4、5号节点即号节点即t1、t2、t3节点构成的节点构成的解树。解树。 (4) 扩展节点扩展节点A，由于，由于A是端节点，因此不可扩展。调是端节点，因此不可扩展。调用不可解标记过程用不可解标记过程。 (5) 扩展扩展4号节点，生成号节点，生成t2节点和节点和B节点。由于节点。由于t2为终止节为终止节点，则标记它为可解节点，并应用可
90、解标记过程，可标点，则标记它为可解节点，并应用可解标记过程，可标记记2号节点为可解，但不能标记号节点为可解，但不能标记1号节点为可解。号节点为可解。65 与与/或树的深度优先搜索和与或树的深度优先搜索和与/或树的广度优先搜索过程基本相或树的广度优先搜索过程基本相同，其主要区别在于同，其主要区别在于Open表中节点的排列顺序不同。在扩展节点表中节点的排列顺序不同。在扩展节点时，与时，与/或树的深度优先搜索过程总是把刚生成的节点放在或树的深度优先搜索过程总是把刚生成的节点放在Open表的首部。表的首部。 与与/或树的深度优先搜索也可以带有深度限制或树的深度优先搜索也可以带有深度限制dm，其搜索算法
91、，其搜索算法如下：如下： (1)把初始节点把初始节点S0放入放入Open表中；表中； (2)把把Open表第一个节点取出放入表第一个节点取出放入Closed表，并记该节点为表，并记该节点为n； (3)如果节点如果节点n的深度等于的深度等于dm，则转第，则转第(5)步的第步的第点；点； (4)如果节点如果节点n可扩展，则做下列工作：可扩展，则做下列工作： 扩展展节点点n，将其子节点放入，将其子节点放入Open表的首部，并为每一个子表的首部，并为每一个子节点设置指向父节点的指针；节点设置指向父节点的指针； 4.4.1与与/或树的广度优先和深度优先搜索或树的广度优先和深度优先搜索2.深度优先搜索深度
92、优先搜索66 考考察察这这些些子子节节点点中中是是否否有有终终止止节节点点。若若有有，则则标标记记这这些些终终止止节节点点为为可可解解节节点点，并并用用可可解解标标记记过过程程对对其其父父节节点点及及先先辈辈节节点点中中的的可可解解解解节节点点进进行行标标记记。如如果果初初始始解解节节点点S0能能够够被被标标记记为为可可解解节节点点，就就得得到到了了解解树树，搜搜索索成成功功，退退出出搜搜索索过过程程；如如果果不不能能确确定定S0为可解节点，则从为可解节点，则从Open表中删去具有可解先辈的节点。表中删去具有可解先辈的节点。 转第转第(2)步。步。 (5)如果节点如果节点n不可扩展，则作下列工
93、作：不可扩展，则作下列工作： 标记节点标记节点n为不可解节点；为不可解节点； 应应用用不不可可解解标标记记过过程程对对节节点点n的的先先辈辈中中不不可可解解解解的的节节点点进进行行标标记记。如如果果初初始始解解节节点点S0也也被被标标记记为为不不可可解解节节点点，则则搜搜索索失失败败，表表明明原原始始问问题题无无解解，退退出出搜搜索索过过程程；如如果果不不能能确确定定S0为为不不可可解解节节点，则从点，则从Open表中删去具有不可解先辈的节点。表中删去具有不可解先辈的节点。 转第转第(2)步。步。 67 对上例，对上例， 若按有界深度优先，且若按有界深度优先，且设设dm=4dm=4，则其节点扩
94、展顺序为：，则其节点扩展顺序为：1 1，3 3，5 5，2 2，4 4。 123A4t15t2Bt3C与/或树的有界深度优先搜索搜索过程为：搜索过程为： (1) 先扩展先扩展1号节号节点，生成点，生成2号节点和号节点和3号节点。号节点。 (2)扩展扩展3号节点，号节点，生成生成t1节点和节点和5号节号节点。由于点。由于t1为终止为终止节点，则标记它为节点，则标记它为可解节点，并应用可解节点，并应用可解标记过程，不可解标记过程，不能确定能确定3号节点是否号节点是否可解。可解。 (6) 搜索成功，搜索成功，得到由得到由1、3、5、2、4号节点即号节点即t1、t2、t3节点构成节点构成的解树。的解树
95、。 (4) 扩展扩展2号节点，生成号节点，生成A节点和节点和4号节点。号节点。 (5) 扩展扩展4号节点，生成号节点，生成t2节节点和点和B节点。由于节点。由于t2为终止节点，为终止节点，则标记它为可解节点，并应用则标记它为可解节点，并应用可解标记过程，可标记可解标记过程，可标记2号节号节点为可解，再往上又可标记点为可解，再往上又可标记1号节点为可解。号节点为可解。(3)扩展扩展5号节点，生成号节点，生成t3节点和节点和C节点。由于节点。由于t3为终止节点，为终止节点，则标记它为可解节点，并应用可解标记过程，可标记则标记它为可解节点，并应用可解标记过程，可标记3号节号节点为可解节点，但不能标记
96、点为可解节点，但不能标记1号为可解。号为可解。68v搜索的基本概念搜索的基本概念v状态空间的盲目搜索状态空间的盲目搜索v状态空间的启发式搜索状态空间的启发式搜索v与与/或树的盲目搜索或树的盲目搜索 与与/或树的启发式搜索或树的启发式搜索v博弈树的启发式搜索博弈树的启发式搜索69与与/或树的启发式搜索过程实际上是一种利用搜索过程所或树的启发式搜索过程实际上是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。得到的启发性信息寻找最优解树的过程。算法的每一步都试图找到一个最有希望成为最优解树的子算法的每一步都试图找到一个最有希望成为最优解树的子树。树。最优解树是指代价最小的那棵解树。最优解树是指
97、代价最小的那棵解树。它涉及到解树的代价与希望树。它涉及到解树的代价与希望树。4.5与与/或树的启发式搜索或树的启发式搜索70 解树的代价可按如下规则计算：解树的代价可按如下规则计算： (1)若若n为终止节点，则其代价为终止节点，则其代价b(n)=0； (2)若若n为或节点，且子节点为为或节点，且子节点为n1, n2, ,nk，则，则n的代价为：的代价为：其中，其中，c(n, ni)是节点是节点n到其子节点到其子节点ni的边代价。的边代价。 (3)若若n为与节点，且子节点为为与节点，且子节点为n1, n2, ,nk，则，则n的代价可用和代价的代价可用和代价法或最大代价法。法或最大代价法。 若用和
98、代价法，则其计算公式为：若用和代价法，则其计算公式为： 若用最大代价法，则其计算公式为：若用最大代价法，则其计算公式为： (4)若若n是端节点，但又不是终止节点，则是端节点，但又不是终止节点，则n不可扩展，其代价定义为不可扩展，其代价定义为h(n)=。 (5)根节点的代价即为解树的代价。根节点的代价即为解树的代价。4.4.1解树的代价与希望树解树的代价与希望树1.解树的代价解树的代价71 例例4.13 设设下下图图是是一一棵棵与与/或或树树，它它包包括括两两可可解解树树，左左边边的的解解树树由由S0、A、t1、C及及t2组组成成；右右边边的的解解树树由由S0、B、t2、D及及t4组组成成。在在
99、此此与与或或树树中中，t1、t2、t3、t4为为终终止止节节点点；E、F是端节点；边上的数字是该边的代价。请计算解树的代价。是端节点；边上的数字是该边的代价。请计算解树的代价。解：先计算左边的解树解：先计算左边的解树按和代价：按和代价：h(S0)=2+4+6+2=14按最大代价：按最大代价：h(S0)=(2+6)+2=10再计算右边的解树再计算右边的解树按和代价：按和代价：h(S0)=1+5+3+2=11按最大代价：按最大代价：h(S0)=(1+5)+2=8 S02ABt1Ct2Dt3Et4F 与与/或树的代价或树的代价246231572 希望树是希望树是指搜索过程中最有可能成为最优解树的那棵
100、树。指搜索过程中最有可能成为最优解树的那棵树。 与与/或树的启发式搜索过程就是不断地选择、修正希望树的或树的启发式搜索过程就是不断地选择、修正希望树的过程，过程，在该过程中，希望树是不断变化的。在该过程中，希望树是不断变化的。 定义定义4.2 希望解树希望解树 (1) 初始节点初始节点S0在希望树在希望树T (2) 如果如果n是具有子节点是具有子节点n1, n2, , nk的或节点，则的或节点，则n的某个的某个子节点子节点ni在希望树在希望树T中的充分必要条件是中的充分必要条件是 (3) 如果如果n是与节点，则是与节点，则n的全部子节点都在希望树的全部子节点都在希望树T中。中。 4.4.1解树
101、的代价与希望树解树的代价与希望树2.希望树希望树73 与与/或树的启发式搜索过程如下：或树的启发式搜索过程如下： (1) 把初始节点把初始节点S0放入放入Open表中，计算表中，计算h(S0)； (2) 计算希望树计算希望树T； (3) 依次在依次在Open表中取出表中取出T的端节点放入的端节点放入Closed表，并记该节点为表，并记该节点为n； (4)如果节点如果节点n为终止节点，则做下列工作：为终止节点，则做下列工作： 标记节点标记节点n为可解节点；为可解节点； 在在T上应用可解标记过程，对上应用可解标记过程，对n的先辈节点中的所有可解解节点进的先辈节点中的所有可解解节点进行标记；行标记；
102、 如果初始解节点如果初始解节点S0能够被标记为可解节点，则能够被标记为可解节点，则T就是最优解树，就是最优解树，成功退出；成功退出； 否则，从否则，从Open表中删去具有可解先辈的所有节点。表中删去具有可解先辈的所有节点。 转第转第(2)步。步。4.4.2与与/或树的启发式搜索过程或树的启发式搜索过程74(5) 如果节点如果节点n不是终止节点，但可扩展，则做下列工作：不是终止节点，但可扩展，则做下列工作： 扩展节点扩展节点n，生成，生成n的所有子节点；的所有子节点； 把这些子节点都放入把这些子节点都放入Open表中，并为每一个子节点设置指表中，并为每一个子节点设置指向父节点向父节点n的指针的指
103、针 计算这些子节点及其先辈节点的计算这些子节点及其先辈节点的h值；值； 转第转第(2)步。步。 (6) 如果节点如果节点n不是终止节点，且不可扩展，则做下列工作：不是终止节点，且不可扩展，则做下列工作： 标记节点标记节点n为不可解节点；为不可解节点； 在在T上应用不可解标记过程，对上应用不可解标记过程，对n的先辈节点中的所有不可的先辈节点中的所有不可解解节点进行标记；解解节点进行标记； 如果初始解节点如果初始解节点S0能够被标记为不可解节点，则问题无解，能够被标记为不可解节点，则问题无解，失败退出；失败退出； 否则，从否则，从Open表中删去具有不可解先辈的所有节点。表中删去具有不可解先辈的所
104、有节点。 转第转第(2)步。步。75例子例子要求搜索过程每次扩展要求搜索过程每次扩展节点时都同时扩展两层，节点时都同时扩展两层，且按一层或节点、一层与且按一层或节点、一层与节点的间隔方式进行扩展。节点的间隔方式进行扩展。它实际上就是下一节将要它实际上就是下一节将要讨论的博弈树的结构。讨论的博弈树的结构。设初始节点为设初始节点为S0，对，对S0扩展后得到的与扩展后得到的与/或树如右或树如右图所示。其中，端节点图所示。其中，端节点B、C、E、F，下面的数字是，下面的数字是用启发函数估算出的用启发函数估算出的h值，值，节点节点S0、A、D旁边的数字旁边的数字是按和代价法计算出来的是按和代价法计算出来
105、的节点代价。节点代价。此时，此时，S0的右子树是当的右子树是当前的希望树。前的希望树。S08A8D7BCEF3332按和代价法：按和代价法：例，节点例，节点A的值的值=3+1+2+1+1=8扩展扩展S0后得到的与后得到的与/或树或树76扩扩展展节节点点E，得得到到如如右右图图所所示示的的与与/或树。或树。此此时时，由由右右子子树树 求求 出出 的的h(S0)=12。 但但 是是 ，由由左左子子树树求求出出的的h(S0)=9。显显然然，左左子子树树的的代代价价小小。因因此此，当当前前的的希希望望树树应应改改为为左左子子树。树。S09A8D11BCEF3372322276扩展节点扩展节点E后得到的
106、与后得到的与/或树或树77对对节节点点B进进行行扩扩展展，扩扩展展两两层层后后得得到到的的与与/或或树树如如下下图图所所示示。由由于于节节点点H和和I是是可可解解节节点点，故故调调用用可可解解标标记记过过程程，得得节节点点G、B也也为为可可解解节节点点，但但不不能能标标记记S0为为可可解解节节点点，须须继继续续扩扩展展。当当前前的的希希望望树树仍仍然然是是左子树。左子树。S09A8D11BCEF3372322276GJHIKL002226扩展节点扩展节点B后得到的与后得到的与/或树或树78对对节节点点C进进行行扩扩展展，扩扩展展两两层层后后得得到到的的与与/或或树树如如右右图图所所示示。由由于
107、于节节点点N和和P是是可可解解节节点点，故故调调用用可可解解标标记记过过程程，得得节节点点M、C、A也也为为可可解解节节点点，进进而而可可标标记记S0为为可可解解节节点点，这这就就的的到到了了代代价价最最小小的的解解树树。按按和和代代价价法法，该该最最优优解的代价为解的代价为9。S09A8D11BCEF3372322276GJHIKL002226MNP005229扩展节点扩展节点C后得到的与后得到的与/或树或树79v搜索的基本概念搜索的基本概念v状态空间的盲目搜索状态空间的盲目搜索v状态空间的启发式搜索状态空间的启发式搜索v与与/或树的盲目搜索或树的盲目搜索v与与/或树的启发式搜索或树的启发式
108、搜索 博弈树的启发式搜索博弈树的启发式搜索804.6.1概述概述博弈的概念博弈的概念博弈是一类具有智能行为的竞争活动，如下棋、战争等。博弈是一类具有智能行为的竞争活动，如下棋、战争等。博弈的类型博弈的类型双人完备信息博弈：两位选手（例如双人完备信息博弈：两位选手（例如MAX和和MIN ）对垒，轮流走步，每一）对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。机遇性博弈：存在不可预测性的博弈，例如掷币等。机遇性博弈：存在不可预测性的博弈，例如掷币等。博弈树博弈树若把双人完备信息博弈过程用图表示出来，就得到一
109、棵与若把双人完备信息博弈过程用图表示出来，就得到一棵与/或树，这种与或树，这种与/或树被称为博弈树。在博弈树中，那些下一步该或树被称为博弈树。在博弈树中，那些下一步该MAX走步的节点称为走步的节点称为MAX节节点，下一步该点，下一步该MIN走步的节点称为走步的节点称为MIN节点。节点。博弈树的特点博弈树的特点(1)博弈的初始状态是初始节点；博弈的初始状态是初始节点；(2)博弈树中的博弈树中的“或或”节点和节点和“与与”节点是逐层交替出现的；节点是逐层交替出现的；(3)整个博弈过程始终站在某一方的立场上，例如整个博弈过程始终站在某一方的立场上，例如MAX方。所有能使自己一方。所有能使自己一方获胜
110、的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。局都是不可解节点。814.6.2极大极小过程极大极小过程 对简单的博弈问题，可生成整个博弈树，找到必胜的策略。对简单的博弈问题，可生成整个博弈树，找到必胜的策略。 对于复杂的博弈问题，不可能生成整个搜索树，如国际象棋，大约对于复杂的博弈问题，不可能生成整个搜索树，如国际象棋，大约有有10120个节点。个节点。 一种可行的方法是用当前正在考察的节点生成一棵部一种可行的方法是用当前正在考察的节点生成一棵部分博弈树，并利用估价函数分博弈树，并利用估价函数f(
111、n)对叶节点进行静态估值。对叶节点进行静态估值。 对叶节点的估值方法是：那些对对叶节点的估值方法是：那些对MAX有利的节点，其估价函数取正有利的节点，其估价函数取正值；那些对值；那些对MIN有利的节点，其估价函数取负值；那些使双方均等的有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于节点，其估价函数取接近于0的值。的值。 为非叶节点的值，必须从叶节点开始向上倒退。其倒退方法是：为非叶节点的值，必须从叶节点开始向上倒退。其倒退方法是： 对于对于MAX节点，由于节点，由于MAX 方总是选择估值最大的走步，因此，方总是选择估值最大的走步，因此，MAX节点的倒退值应该取其后继节点
112、估值的最大值。节点的倒退值应该取其后继节点估值的最大值。 对于对于MIN节点，由于节点，由于MIN方总是选择使估值最小的走步，因此方总是选择使估值最小的走步，因此MIN节点的倒推值应取其后继节点估值的最小值。节点的倒推值应取其后继节点估值的最小值。 这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。这这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。这一过程称为极大极小过程。一过程称为极大极小过程。82 例例4.14 一子棋游戏一子棋游戏 设设有有一一个个三三行行三三列列的的棋棋盘盘，如如下下图图所所示示，两两个个棋棋手手轮轮流流走走步步，每每个个棋棋手手走走步步时时往往空空格格上
113、上摆摆一一个个自自己己的的棋棋子子，谁谁先先使使自自己己的的棋棋子子成成三三子子一一线线为为赢赢。设设MAX方方的的棋棋子子用用标标记记，MIN方方的的棋棋子子用用标记，并规定标记，并规定MAX方先走步。方先走步。一子棋棋盘棋局1解：解：估价函数估价函数e(+P)：P上有可能使上有可能使成三子为一线的数目；成三子为一线的数目；e(-P)：P上有可能使上有可能使成三子为一线的数目；成三子为一线的数目；当当MAX必胜必胜e(P)为正无穷大为正无穷大,MIN必胜必胜e(P)为负无穷大为负无穷大e(P)=e(+P)-e(-P)4.6.2极大极小过程极大极小过程83 棋局即估价函数棋局即估价函数 具有对
114、称性的棋盘可认为是同一棋盘。如下图所示：具有对称性的棋盘可认为是同一棋盘。如下图所示：其其e(P)=e(+P)-e(-P)=5-4=14.6.2极大极小过程极大极小过程84S01S1S2S3-16-5=15-5=06-5=15-5=04-5=-15-4=16-4=25-6=-15-5=05-6=-16-6=04-6=-2一子棋的极大极小搜索一子棋的极大极小搜索S4S5-2185剪枝的概念剪枝的概念 极大极小过程是先生成与极大极小过程是先生成与/或树，然后再计算各节点的估值，这种生或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节成节点和计算估值相分
115、离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率较低。点，因此搜索效率较低。 如果能边生成节点边对节点估值，并剪去一些没用的分枝，这种技如果能边生成节点边对节点估值，并剪去一些没用的分枝，这种技术被称为术被称为-剪枝。剪枝。剪枝方法剪枝方法 (1) MAX节点（或节点）的节点（或节点）的值为当前子节点的最大到推值；值为当前子节点的最大到推值； (2) MIN节点（与节点）的节点（与节点）的值为当前子节点的最小倒推值；值为当前子节点的最小倒推值； (3) -剪枝的规则如下：剪枝的规则如下： 任何任何MAX节点节点n的的值大于或等于它先辈节点的值大于或等于它先辈节点的值，则值，则n 以下的
116、分以下的分枝可停止搜索，并令节点枝可停止搜索，并令节点n的倒推值为的倒推值为。这种剪枝称为。这种剪枝称为剪枝。剪枝。 任何任何MIN节点节点n的的值小于或等于它先辈节点的值小于或等于它先辈节点的值，则值，则n 以下的分枝以下的分枝可停止搜索，并令节点可停止搜索，并令节点n的倒推值为的倒推值为。这种剪枝称为。这种剪枝称为剪枝。剪枝。4.6.3-剪枝剪枝86一一个个-剪剪枝枝的的具具体体例例子子，如如下下图图所所示示。其其中中最最下下面面一一层层端端节节点点旁旁边边的的数数字字是是假假设设的的估值。估值。4S04A011450CDE0-6IJ41KLN461FG5P58HM8值值值值QR0-6S在
117、该图中，在该图中，L、M、N的估值推出节的估值推出节点点F的到推值为的到推值为4，即，即F的的值为值为4，由，由此可推出节点此可推出节点C的到推值的到推值4。 由节点由节点N的估值推知节点的估值推知节点G的倒推值小于的倒推值小于1,无论无论G的其它子节点的估只是多少，的其它子节点的估只是多少，G的倒推值都不可能比的倒推值都不可能比1大。因此，大。因此，1是是G的倒推值的上界，所以的倒推值的上界，所以G的值的值1。另已知。另已知C的倒推值的倒推值4，G的其它子节点又不可能使的其它子节点又不可能使C的倒推值增大。因此对的倒推值增大。因此对G的其它分支不必的其它分支不必再搜索，相当于把这些分枝剪去。
118、再搜索，相当于把这些分枝剪去。由由F、G的倒推值可推出节点的倒推值可推出节点C的倒推值的倒推值4，再由，再由C可推出节点可推出节点A的倒推值的倒推值4，即，即A的的值为值为4。另外，由节点另外，由节点P、Q推出的节点推出的节点I的倒推的倒推值为值为5，因此，因此D的倒推值的倒推值5，即，即D的的值为值为5。此时，。此时，D的其它子节点的倒推值无论是的其它子节点的倒推值无论是多少都不能使多少都不能使D及及A的倒推值减少或增大，所以的倒推值减少或增大，所以D的其他分枝被减去，并可确定的其他分枝被减去，并可确定A的的倒推值为倒推值为4。以此类推，最终推出。以此类推，最终推出S0的倒推值为的倒推值为4
119、。 记记C的到推值的下界的到推值的下界为为4，不可能再比，不可能再比4小，小，故故C的的值为值为4。87作 业4.10 何谓估价函数，在估价函数中，g(n)和h(n)各起什么作用？4.11 设有如下结构的移动将牌游戏：其中，B表示黑色将牌，W表是白色将牌，E表示空格。游戏的规定走法是： (1) 任意一个将牌可移入相邻的空格，规定其代价为1； (2) 任何一个将牌可相隔1个其它的将牌跳入空格，其代价为跳过将牌的数目加1。 游戏要达到的目标什是把所有W都移到B的左边。对这个问题，请定义一个启发函数h(n)，并给出用这个启发函数产生的搜索树。你能否判别这个启发函数是否满足下界要求？在求出的搜索树中，
120、对所有节点是否满足单调限制？BBWWE88分章实验分章实验3（选作）（选作）简单的一字棋游戏简单的一字棋游戏 1. 实验目的实验目的 理解和掌握博弈树的启发式搜索过程，能够用选定的程序语言理解和掌握博弈树的启发式搜索过程，能够用选定的程序语言建立简单的博弈游戏。建立简单的博弈游戏。 2. 实验环境实验环境 在微型计算机上，任选一种编程语言在微型计算机上，任选一种编程语言 3. 实验内容和要求实验内容和要求 (1) 以一字棋游戏为例，设计一个不少于以一字棋游戏为例，设计一个不少于3行行3列的棋盘，自己列的棋盘，自己给出估价函数，采用极大极小搜索方法。给出估价函数，采用极大极小搜索方法。 (2)
121、采用人机对弈方式，一方走步后等待对方，对弈过程的棋采用人机对弈方式，一方走步后等待对方，对弈过程的棋局变化在屏幕上显示。局变化在屏幕上显示。89智能五子棋游戏智能五子棋游戏 1. 实验目的实验目的 理解和掌握博弈树的启发式搜索过程和理解和掌握博弈树的启发式搜索过程和-剪枝技术，能够用某种程序语言剪枝技术，能够用某种程序语言开发一个五子棋博弈游戏。开发一个五子棋博弈游戏。 2. 实验环境实验环境 在微型计算机上，任选一种编程语言。在微型计算机上，任选一种编程语言。 3. 实验要求实验要求 (1) 设计一个设计一个15行行15列棋盘，要求自行给出估价函数，按极大极小搜索方法，列棋盘，要求自行给出估
122、价函数，按极大极小搜索方法，并采用并采用-剪枝技术。剪枝技术。 (2) 采用人机对弈方式，对弈双方设置不同颜色的棋子，一方走完一步后，采用人机对弈方式，对弈双方设置不同颜色的棋子，一方走完一步后，等待对方走步，对弈过程的每个棋局都在屏幕上显示出来。当某一方在横、等待对方走步，对弈过程的每个棋局都在屏幕上显示出来。当某一方在横、竖或斜方向上先有竖或斜方向上先有5个棋子连成一线时，该方为赢。个棋子连成一线时，该方为赢。 (3) 提交提交1篇实验报告，以及完整的软件系统和相关文档，包括源程序和可篇实验报告，以及完整的软件系统和相关文档，包括源程序和可执行程序。执行程序。综合实验综合实验1（选作）（选作）90
