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

搜索是人工智能中的一个基本问题，并与推理密切相关，搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。搜索策略的优劣，将直接影响到智能系统的性能与推理效率。状态空间的盲目搜索状态空间的盲目搜索状态空间的启发式搜索状态空间的启发式搜索与与/或树的盲目搜索或树的盲目搜索与与/或树的启发式搜索或树的启发式搜索博弈树的启发式搜索博弈树的启发式搜索第第4章章 搜索策略搜索策略14.1 搜索的基本概念搜索的基本概念4.1.1 搜索的含义搜索的含义4.1.2 状态空间法状态空间法4.1.3 问题归约法问题归约法24.1.1 搜索的含义搜索的含义适用情况：适用情况：不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。算法可供求解使用。概念：概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索搜索的类型搜索的类型 按是否使用启发式信息：按是否使用启发式信息：盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。不改变控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。着最有希望的方向前进，加速问题的求解过程并找到最优解。按问题的表示方式：按问题的表示方式：状态空间搜索：用状态空间法来求解问题所进行的搜索状态空间搜索：用状态空间法来求解问题所进行的搜索 与或树搜索：用问题归约法来求解问题时所进行的搜索与或树搜索：用问题归约法来求解问题时所进行的搜索 34.1.2 状态空间法状态空间法1.状态空间表示方法状态空间表示方法状态状态(State)：是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：Sk=Sk0,Sk1,当对每一个分量都给以确定的值时，就得到了一个具体的状态。当对每一个分量都给以确定的值时，就得到了一个具体的状态。操作操作(Operator)也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。个函数，它描述了状态之间的关系。状态空间状态空间(State space)用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：表示为：(S,F,G)其中，其中，S为问题的所有初始状态的集合；为问题的所有初始状态的集合；F为操作的集合；为操作的集合；G为目标状态的集合。为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。空间图中，节点表示问题的状态，有向边表示操作。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)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)6 ABABAB 1 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号钢针上；号钢针上；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)的任何一条路径都是问题的一的任何一条路径都是问题的一个解。其中，最短的路径长度是个解。其中，最短的路径长度是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问题问题)。设在河的一岸有三个野人、三个修道士和一条船，修道士想设在河的一岸有三个野人、三个修道士和一条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：用这条船把所有的人运到河对岸，但受以下条件的约束：一是修道士和野人都会划船，但每次船上至多可载两个人；一是修道士和野人都会划船，但每次船上至多可载两个人；二是在河的任一岸，如果野人数目超过修道士数，修道士会二是在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。被野人吃掉。如果野人会服从任何一次过河安排，请规划一个确保修道士如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。和野人都能过河，且没有修道士被野人吃掉的安全过河计划。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种状态。种状态。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)有了这些状态，还需要考虑可进行的操作。有了这些状态，还需要考虑可进行的操作。操作操作是指用船把修道士或野人从河的左岸运到右岸，或从河的是指用船把修道士或野人从河的左岸运到右岸，或从河的右岸运到左岸。右岸运到左岸。每个操作都应当满足如下条件：每个操作都应当满足如下条件：一是一是船至少有一个人（船至少有一个人（m或或c）操作，离开岸边的）操作，离开岸边的m和和c的减少数的减少数目应该等于到达岸边的目应该等于到达岸边的m和和c的增加数目；的增加数目；二是二是每次操作船上人数不得超过每次操作船上人数不得超过2个；个；三是三是操作应保证不产生非法状态。操作应保证不产生非法状态。因此，因此，操作应由条件部分和动作部分：操作应由条件部分和动作部分：条件：条件：只有当其条件具备时才能使用只有当其条件具备时才能使用 动作：动作：刻划了应用此操作所产生的结果。刻划了应用此操作所产生的结果。12操作的表示：操作的表示：用符号用符号Pij表示从左岸到右岸的运人操作表示从左岸到右岸的运人操作 用符号用符号Qij表示从右岸到左岸的操作表示从右岸到左岸的操作其中：其中：i表示表示船上的修道士人数船上的修道士人数 j表示表示船上的野人数船上的野人数操作集操作集 本问题有本问题有10种操作可供选择：种操作可供选择：F=P01,P10,P11,P02,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+1 13abc 例例4.3 猴子摘香蕉问题。猴子摘香蕉问题。在讨论谓词逻辑知识表示时，我们在讨论谓词逻辑知识表示时，我们曾提到过这一问题，现在用状态空间法来解决这一问题。曾提到过这一问题，现在用状态空间法来解决这一问题。解：解：问题的状态可用问题的状态可用4元组元组 （w,x,y,z）表示。其中：表示。其中：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,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)这个问题的状态空间图如下图所示。不难看出，由初始状这个问题的状态空间图如下图所示。不难看出，由初始状态变为目标状态的操作序列为：态变为目标状态的操作序列为：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基本思想基本思想 当一问题较复杂时，可通过分解或变换，将其转化为一系列较简当一问题较复杂时，可通过分解或变换，将其转化为一系列较简单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。分解分解 如果一个问题如果一个问题P可以归约为一组子问题可以归约为一组子问题P1,P2,Pn，并且只有当所有，并且只有当所有子问题子问题Pi都有解时原问题都有解时原问题P才有解，任何一个子问题才有解，任何一个子问题Pi无解都会导致原无解都会导致原问题问题P无解，则称此种归约为问题的分解。无解，则称此种归约为问题的分解。即分解所得到的子问题的即分解所得到的子问题的“与与”与原问题与原问题P等价。等价。等价变换等价变换 如果一个问题如果一个问题P可以归约为一组子问题可以归约为一组子问题P1,P2,Pn，并且子问题，并且子问题Pi中只要有一个有解则原问题中只要有一个有解则原问题P就有解，只有当所有子问题就有解，只有当所有子问题Pi都无解时都无解时原问题原问题P才无解，称此种归约为问题的等价变换，简称变换。才无解，称此种归约为问题的等价变换，简称变换。即变换所得到的子问题的即变换所得到的子问题的“或或”与原问题与原问题P等价。等价。4.1.3 问题归约法问题归约法1.问题的分解与等价变换问题的分解与等价变换17PP1 P2 P3 与树与树P1 P2 P3 或树或树PPP1 P2 P3 P12 P12 P31 P32 P33 与与/或树或树(1)与树与树 分解分解(2)或树或树 等价变换等价变换(3)与与/或树或树4.1.3 问题归约法问题归约法2.问题的与问题的与/或树表示或树表示18(4)端节点与终止节点端节点与终止节点 在与在与/或树中，没有子节点的节点称为或树中，没有子节点的节点称为端节点端节点；本原问题所对应的节；本原问题所对应的节点称为点称为终止节点终止节点。可见，终止节点一定是端节点，但端节点却不一定是。可见，终止节点一定是端节点，但端节点却不一定是终止节点。终止节点。(5)可解节点与不可解节点可解节点与不可解节点 在与在与/或树中，满足以下三个条件之一的节点为或树中，满足以下三个条件之一的节点为可解节点：可解节点：任何终止节点都是可解节点。任何终止节点都是可解节点。对对“或或”节点，当其子节点中至少有一个为可解节点时，则该或节点节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点。就是可解节点。对对“与与”节点，只有当其子节点全部为可解节点时，该与节点才是可节点，只有当其子节点全部为可解节点时，该与节点才是可解节点。解节点。同样，可用类似的方法定义同样，可用类似的方法定义不可解节点：不可解节点：不为终止节点的端节点是不可解节点。不为终止节点的端节点是不可解节点。对对“或或”节点，若其全部子节点都为不可解节点，则该或节点是不可节点，若其全部子节点都为不可解节点，则该或节点是不可解节点。解节点。对对“与与”节点，只要其子节点中有一个为不可解节点，则该与节点是节点，只要其子节点中有一个为不可解节点，则该与节点是不可解节点。不可解节点。19Pt t t 解树解树(6)解树解树 由可解节点构成，并且由这些可解由可解节点构成，并且由这些可解节点可以推出初始节点（它对应着原节点可以推出初始节点（它对应着原始问题）为可解节点的子树为解树。始问题）为可解节点的子树为解树。在解树中一定包含初始节点。在解树中一定包含初始节点。例如，右图给出的与或树中，用红例如，右图给出的与或树中，用红 线表示的子树是一个解树。在该图中，线表示的子树是一个解树。在该图中，节点节点P为原始问题节点，用为原始问题节点，用t标出的节标出的节点是终止节点。根据可解节点的定义，点是终止节点。根据可解节点的定义，很容易推出原始问题很容易推出原始问题P为可解节点。为可解节点。问题归约求解过程就实际上就是生问题归约求解过程就实际上就是生成解树，即证明原始节点是可解节点成解树，即证明原始节点是可解节点的过程。这一过程涉及到搜索的问题，的过程。这一过程涉及到搜索的问题，对于与对于与/或树的搜索将在后面详细讨论。或树的搜索将在后面详细讨论。20 例例4.4 三阶梵塔问题。要求把三阶梵塔问题。要求把1号钢针上的号钢针上的3个金片全部移到个金片全部移到3号钢针号钢针上，如下图所示。上，如下图所示。解：解：这个问题也可用状态空间法来解，不过本例主要用它来说明如何这个问题也可用状态空间法来解，不过本例主要用它来说明如何用归约法来解决问题。用归约法来解决问题。为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设用三元组用三元组 (i,j,k)表示问题在任一时刻的状态，用表示问题在任一时刻的状态，用“”表示状态的转换。上述三元组中表示状态的转换。上述三元组中 i 代表金片代表金片C所在的钢针号所在的钢针号 j 代表金片代表金片B所在的钢针号所在的钢针号 k 代表金片代表金片A所在的钢针号所在的钢针号1231234.1.3 问题归约法问题归约法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)都是一个二阶梵塔问题，它们都还可以再继续进行分解；都是一个二阶梵塔问题，它们都还可以再继续进行分解；子问题子问题(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个本原问题。如果把个本原问题。如果把这些本原问题从左至右排列起来，即得到了原始问题的解：这些本原问题从左至右排列起来，即得到了原始问题的解：(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 状态空间的盲目搜索状态空间的盲目搜索4.2.1 一般图搜索过程一般图搜索过程4.2.2 广度优先和深度优先搜索广度优先和深度优先搜索4.2.3 代价树搜索代价树搜索24状态空间搜索的基本思想状态空间搜索的基本思想 先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。所谓对一个节点进行节点中或者没有可供操作的节点为止。所谓对一个节点进行“扩展扩展”是指是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。对该节点用某个可用操作进行作用，生成该节点的一组子节点。4.2.1 一般图搜索过程一般图搜索过程算法的数据结构和符号约定算法的数据结构和符号约定 Open表：用于存放刚生成的节点表：用于存放刚生成的节点 Closed表：用于存放已经扩展或将要扩展的节点表：用于存放已经扩展或将要扩展的节点 S0：用表示问题的初始状态：用表示问题的初始状态 G：表示搜索过程所得到的搜索图：表示搜索过程所得到的搜索图 M：表示当前扩展节点新生成的且不为自己先辈的子节点集。：表示当前扩展节点新生成的且不为自己先辈的子节点集。25一般图搜索过程一般图搜索过程 (1)把初始节点把初始节点S0放入放入Open表，并建立目前仅包含表，并建立目前仅包含S0的图的图G；(2)检查检查Open表是否为空，若为空，则问题无解，失败推出；表是否为空，若为空，则问题无解，失败推出；(3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为节点表，并记该节点为节点n；(4)考察节点考察节点n是否为目标节点。若是则得到了问题的解，成功退出；是否为目标节点。若是则得到了问题的解，成功退出；(5)扩展节点扩展节点n，生成一组子节点。把这些子节点中不是节点，生成一组子节点。把这些子节点中不是节点n先辈的那先辈的那部分子节点记入集合部分子节点记入集合M，并把这些子节点作为节点，并把这些子节点作为节点n的子节点加入的子节点加入G中中 (6)针对针对M中子节点的不同情况，分别作如下处理：中子节点的不同情况，分别作如下处理：对那些没有在对那些没有在G中出现过的中出现过的M成员设置一个指向其父节点（即节点成员设置一个指向其父节点（即节点n）的指针，并把它放入的指针，并把它放入Open表。（新生成的）表。（新生成的）对那些原来已在对那些原来已在G中出现过，但还没有被扩展的中出现过，但还没有被扩展的M成员，确定是否需成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的）要修改它指向父节点的指针。（原生成但未扩展的）对于那些先前已在对于那些先前已在G中出现过，并已经扩展了的中出现过，并已经扩展了的M成员，确定是否需成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的）要修改其后继节点指向父节点的指针。（原生成也扩展过的）(7)按某种策略对按某种策略对Open表中的节点进行排序。表中的节点进行排序。(8)转第转第(2)步。步。26算法的几点说明：算法的几点说明：(1)上述过程是状态空间的一般图搜索算法，它具有通用性，后面上述过程是状态空间的一般图搜索算法，它具有通用性，后面所要讨论的各种状态空间搜索策略都是上述过程的一个特例。各种搜索所要讨论的各种状态空间搜索策略都是上述过程的一个特例。各种搜索策略的主要区别在于对策略的主要区别在于对Open表中节点的排列顺序不同。例如，广度优表中节点的排列顺序不同。例如，广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点排在前面。点排在前面。(2)在第在第(5)步对节点步对节点n扩展后，生成并记入扩展后，生成并记入M的子节点有以下三种的子节点有以下三种情况：情况：该子节点来从未被任何节点生成过，由该子节点来从未被任何节点生成过，由n第一次生成；第一次生成；该子节点原来被其他节点生成过，但还没有被扩展，这一次又被该子节点原来被其他节点生成过，但还没有被扩展，这一次又被n再次生成；再次生成；该子节点原来被其他节点生成过，并且已经被扩展过，这一次又该子节点原来被其他节点生成过，并且已经被扩展过，这一次又被被n再次生成。再次生成。以上三种情况是对一般图搜索算法而言的。对于盲目搜索，由于其以上三种情况是对一般图搜索算法而言的。对于盲目搜索，由于其状态空间是树状结构，因此不会出现后两种情况，每个节点经扩展后生状态空间是树状结构，因此不会出现后两种情况，每个节点经扩展后生成的子节点都是第一次出现的节点，不必检查并修改指向父节点的指针。成的子节点都是第一次出现的节点，不必检查并修改指向父节点的指针。27 (3)在第在第(6)步针对步针对M中子节点的不同情况进行处理时，如果发生当第中子节点的不同情况进行处理时，如果发生当第种情况，那么，这个种情况，那么，这个M中的节点究竟应该作为哪一个节点的后继节点呢？中的节点究竟应该作为哪一个节点的后继节点呢？一般是由原始节点到该节点路径上所付出的代价来决定的，哪一条路经一般是由原始节点到该节点路径上所付出的代价来决定的，哪一条路经付出的代价小，相应的节点就作为它的父节点。所谓由原始节点到该节付出的代价小，相应的节点就作为它的父节点。所谓由原始节点到该节点路径上的代价是指这条路经上的所有有向边的代价之和。点路径上的代价是指这条路经上的所有有向边的代价之和。如果发生第种情况，除了需要确定该子节点指向父节点的指针外，如果发生第种情况，除了需要确定该子节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针。其依据也是由原始节点到该还需要确定其后继节点指向父节点的指针。其依据也是由原始节点到该节点的路径上的代价。节点的路径上的代价。(4)在搜索图中，除初始节点外，任意一个节点都含有且只含有一在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树。成的集合是一棵树，称为搜索树。(5)在搜索过程的第在搜索过程的第(4)步，一旦某个被考察的节点是目标节点，则步，一旦某个被考察的节点是目标节点，则搜索过程成功结束。由初始节点到目标节点路径上的所有操作就构成了搜索过程成功结束。由初始节点到目标节点路径上的所有操作就构成了该问题的解，而路径由第该问题的解，而路径由第(6)步所形成的指向父节点的指针来确定。步所形成的指向父节点的指针来确定。(6)如果搜索过程终止在第如果搜索过程终止在第(2)步，即没有达到目标，且步，即没有达到目标，且Open表中已表中已无可供扩展的节点，则失败结束。无可供扩展的节点，则失败结束。28基本思想基本思想 从初始节点从初始节点S0开始逐层向下扩展，在第开始逐层向下扩展，在第n层节点还没有全部搜索完层节点还没有全部搜索完之前，不进入第之前，不进入第n+1层节点的搜索。层节点的搜索。Open表中的节点总是按进入的先表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。后排序，先进入的节点排在前面，后进入的节点排在后面。搜索算法搜索算法 (1)把初始节点把初始节点S0放入放入Open表中；表中；(2)如果如果Open表为空，则问题无解，失败退出；表为空，则问题无解，失败退出；(3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为表，并记该节点为n；(4)考察节点考察节点n是否为目标节点。若是，则得到问题的解，成功退出；是否为目标节点。若是，则得到问题的解，成功退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)扩展节点扩展节点n，将其子节点放入，将其子节点放入Open表的尾部，并为每一个子节表的尾部，并为每一个子节点设置指向父节点的指针，然后转第点设置指向父节点的指针，然后转第(2)步。步。4.2.2 广度优先和深度优先搜索广度优先和深度优先搜索1.广度优先搜索广度优先搜索29 例例4.5 八数码难题。在八数码难题。在33的方格棋盘上，分别放置了表有的方格棋盘上，分别放置了表有数字数字1、2、3、4、5、6、7、8的八张牌，初始状态的八张牌，初始状态S0，目标状，目标状态态Sg，如下图所示。可以使用的操作有，如下图所示。可以使用的操作有 空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，空格下移即只允许把位于空格左、上、右、下方的牌移入空格。要求应即只允许把位于空格左、上、右、下方的牌移入空格。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径用广度优先搜索策略寻找从初始状态到目标状态的解路径。2 8 331 447 6 5 1 2 38 47 6 5 S0 Sg302 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 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 27Sg31算法描述算法描述 (1)(1)把初始节点把初始节点S0放入放入Open表中；表中；(2)(2)如果如果OpenOpen表为空，则问题无解表为空，则问题无解 ，失败退出；，失败退出；(3)(3)把把OpenOpen表的第一个节点取出放入表的第一个节点取出放入ClosedClosed表，并记该节点为表，并记该节点为n n；(4)(4)考察节点考察节点n n是否为目标节点。若是，则得到问题的解，成功退出；是否为目标节点。若是，则得到问题的解，成功退出；(5)(5)若节点若节点n n不可扩展，则转第不可扩展，则转第(2)(2)步；步；(6)(6)扩展节点扩展节点n n，将其子节点放入，将其子节点放入OpenOpen表的首部，并为每一个子节点设置表的首部，并为每一个子节点设置 指向父节点的指针，然后转第指向父节点的指针，然后转第(2)(2)步。步。4.2.2 广度优先和深度优先搜索广度优先和深度优先搜索2.深度优先搜索深度优先搜索基本思想基本思想 从初始节点从初始节点S0开始，在其子节点中选择一个最新生成的节点进行考察，如开始，在其子节点中选择一个最新生成的节点进行考察，如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察，依此向下搜索，直到某点的子节点中选择一个最新生成的节点进行考察，依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察察。322 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 52 8 31 6 4 7 52 8 31 6 47 5 2 8 31 6 7 5 42 8 31 67 5 42 8 1 6 37 5 42 81 6 37 5 4S0 12 3 4 5 6八数码难题的深度优先搜索如右图八数码难题的深度优先搜索如右图 一种改进的深度优先算法是有界深度一种改进的深度优先算法是有界深度优先搜索算法，深度限制为优先搜索算法，深度限制为dm例例4.6 八数码难题八数码难题33 在代价树中，可以用在代价树中，可以用g(n)表示从初始节点表示从初始节点S0到节点到节点n的代价，用的代价，用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表为空，则问题无解表为空，则问题无解，失败退出；，失败退出；(3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为表，并记该节点为n；(4)考察节点考察节点n是否为目标。若是，则找到了问题的解，成功退出；是否为目标。若是，则找到了问题的解，成功退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)扩展节点扩展节点n，生成其子节点，生成其子节点ni(i=1,2,)，将这些子节点放入，将这些子节点放入Open表表中，并为每一个子节点设置指向父节点的指针。按如下公式：中，并为每一个子节点设置指向父节点的指针。按如下公式：g(ni)=g(n)+c(ni)i=1,2,.计算各子结点的代价，并根据各子结点的代价对计算各子结点的代价，并根据各子结点的代价对Open表中的全部结点按表中的全部结点按由小到大的顺序排序。然后转第由小到大的顺序排序。然后转第(2)步。步。34 例例4.7 城市交通问题。设有城市交通问题。设有5个城市，它们之间的交通线路如左图个城市，它们之间的交通线路如左图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从树的广度优先搜索，求从A市出发到市出发到E市，费用最小的交通路线。市，费用最小的交通路线。ABCDE43 4 5232 4 5AC1B1D1D2E1E2B2C2E33 43 4 2 3城市交通图城市交通图 城市交通图的代价树城市交通图的代价树 解：解：代价树如右图所示。其中，代价树如右图所示。其中，红线为最优解，其代价为红线为最优解，其代价为8354.2.3 代价树搜索代价树搜索2.代价树的深度优先搜索代价树的深度优先搜索代价树的深度优先搜索算法：代价树的深度优先搜索算法：(1)把初始节点把初始节点S0放入放入Open表中，置表中，置S0的代价的代价g(S0)=0；(2)如果如果Open表为空，则问题无解表为空，则问题无解，失败退出；，失败退出；(3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点表，并记该节点为为n；(4)考察节点考察节点n是否为目标节点。若是，则找到了问题的解，是否为目标节点。若是，则找到了问题的解，成功退出；成功退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)扩展节点扩展节点n，生成其子节点，生成其子节点ni(i=1,2,)，将这些子节点，将这些子节点按边代价由小到大放入按边代价由小到大放入Open表的首部，并为每一个子节点设置表的首部，并为每一个子节点设置指向父节点的指针。然后转第指向父节点的指针。然后转第(2)步。步。36v搜索的基本概念搜索的基本概念v状态空间的盲目搜索状态空间的盲目搜索v与与/或树的盲目搜索或树的盲目搜索v与与/或树的启发式搜索或树的启发式搜索v博弈树的启发式搜索博弈树的启发式搜索第第4章章 搜索策略搜索策略374.3 状态空间的启发式搜索状态空间的启发式搜索4.3.1 启发性信息和估价函数启发性信息和估价函数4.3.2 A算法算法4.3.3 A*算法算法4.3.4 A*算法应用举例算法应用举例38 启发性信息的概念启发性信息的概念 启发性信息是指那种与具体问题求解过程有关的，并启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。可指导搜索过程朝着最有希望方向前进的控制信息。启发性信息的种类启发性信息的种类 有效地帮助确定扩展节点的信息；有效地帮助确定扩展节点的信息；有效的帮助决定哪些后继节点应被生成的信息；有效的帮助决定哪些后继节点应被生成的信息；能决定在扩展一个节点时哪些节点应从搜索树上删能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。除的信息。启发性信息的作用启发性信息的作用 启发信息的启发能力越强，扩展的无用结点越少。启发信息的启发能力越强，扩展的无用结点越少。4.3.1 启发性信息和估价函数启发性信息和估价函数1.启发性信息启发性信息39 估价函数用来估计节点重要性的函数。估价函数估价函数用来估计节点重要性的函数。估价函数f(n)被定义为被定义为从初始节点从初始节点S0出发，约束经过节点出发，约束经过节点n到达目标节点到达目标节点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)表示节点表示节点n在搜索树中的深度在搜索树中的深度 W(n)表示节点表示节点n中中“不在位不在位”的数码个数。的数码个数。请计算初始状态请计算初始状态S0的估价函数值的估价函数值f(S0)40 解：解：取取g(n)=d(n)，h(n)=W(n)。它说明是用从。它说明是用从S0到到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 S0 Sg41概念：概念：在图搜索算法中，如果能在搜索的每一步都利用估价函数在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对对Open表中的节点进行排序，则该搜索算法为表中的节点进行排序，则该搜索算法为A算法。算法。由于估价函数中带有问题自身的启发性信息，因此，由于估价函数中带有问题自身的启发性信息，因此，A算法算法也被称为启发式搜索算法。也被称为启发式搜索算法。类型：类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。分为全局择优搜索算法和局部择优搜索算法。全局择优：全局择优：从从Open表的所有节点中选择一个估价函数值最表的所有节点中选择一个估价函数值最小的一个进行扩展。小的一个进行扩展。局部择优：局部择优：仅从刚生成的子节点中选择一个仅从刚生成的子节点中选择一个估价函数值最小估价函数值最小的一个进行扩展。的一个进行扩展。4.3.2 A算法算法42全局择优搜索全局择优搜索A A算法描述：算法描述：(1)(1)把初始节点把初始节点S0放入放入Open表中，表中，f(S0)=g(S0)+h(S0)；(2)(2)如果如果Open表为空，则问题无解表为空，则问题无解，失败退出；，失败退出；(3)(3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为表，并记该节点为n；(4)(4)考察节点考察节点n是否为目标节点。若是，则找到了问题的解，成功退是否为目标节点。若是，则找到了问题的解，成功退出；出；(5)(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)(6)扩展节点扩展节点n，生成其子节点，生成其子节点ni(i=1,2,)，计算每一个子节点的，计算每一个子节点的估价值估价值f(ni)(i=1,2,)，并为每一个子节点设置指向父节点的指针，然，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入后将这些子节点放入Open表中；表中；(7)(7)根据各节点的估价函数值，对根据各节点的估价函数值，对Open表中的全部节点按从小到大表中的全部节点按从小到大的顺序重新进行排序；的顺序重新进行排序；(8)(8)转第转第(2)步。步。4.3.2 A算法算法43 例例4.9 八数码难题。设问题的初始状态八数码难题。设问题的初始状态S0和目标状态和目标状态Sg如图所如图所示，估价函数与例示，估价函数与例4.8相同。请用全局择优搜索解决该问题。相同。请用全局择优搜索解决该问题。解：解：该问题的全局择优搜索树如下图所示。在该图中，每个该问题的全局择优搜索树如下图所示。在该图中，每个节点旁边的数字是该节点的估价函数值。节点旁边的数字是该节点的估价函数值。例如，对节点例如，对节点S2，其估价函数值的计算为：，其估价函数值的计算为：f(S2)=d(S2)+W(S2)=1+3=4 2 8 31 47 6 5 1 2 38 47 6 5 S0 Sg442 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 5S0 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 51 2 38 47 6 51 2 37 8 4 6 51 2 3 8 47 6 54 4 5 55 6 4 644SgS1S2八数码难题的全局择优搜索树八数码难题的全局择优搜索树该问题的解为：该问题的解为：S0S1S2S3SgS3645 4.3.3 A*算法算法 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)分别提出如下限制：分别提出如下限制：第一，第一，g(n)是对最小代价是对最小代价g*(n)的估计，且的估计，且g(n)0；第二，第二，h(n)是最小代价是最小代价h*(n)的下界，即对任意节点的下界，即对任意节点n均有均有h(n)h*(n)。即满足上述两条限制的即满足上述两条限制的A算法称为算法称为A*算法。算法。46 4.3.3 A*算法算法1.A*算法的可纳性算法的可纳性(1/6)可纳性的含义：可纳性的含义：对任一状态空间图，当从初始节点到目标节点有路经存在时，如果搜索算对任一状态空间图，当从初始节点到目标节点有路经存在时，如果搜索算法总能在有限步骤内找到一条从初始节点到目标节点的最佳路径，并在此路法总能在有限步骤内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的。径上结束，则称该搜索算法是可采纳的。A*算法可纳性的证明算法可纳性的证明 以下分三步（定理以下分三步（定理4.1、定理、定理4.2、定理、定理4.3，即引理）进行证明。，即引理）进行证明。定理定理4.1 对有限图，如果从初始节点对有限图，如果从初始节点S0到目标节点到目标节点Sg有路径存在，则算法有路径存在，则算法A*一定成功结束。一定成功结束。证明：证明：首先证明算法必然会结束。首先证明算法必然会结束。由于搜索图为有限图，如果算法能找到由于搜索图为有限图，如果算法能找到解，则成功结束；如果算法找不到解，则必然会由于解，则成功结束；如果算法找不到解，则必然会由于Open表变空而结束。因表变空而结束。因此，此，A*算法必然会结束。算法必然会结束。然后证明算法一定会成功结束。然后证明算法一定会成功结束。由于至少存在一条有初始节点到目标节点由于至少存在一条有初始节点到目标节点的路径，设此路径为的路径，设此路径为 S0=n0,n1,nk=Sg算法开始时，节点算法开始时，节点n0在在Open表中，而且路径中任一节点表中，而且路径中任一节点ni离开离开Open表后，其表后，其后继节点后继节点ni+1必然进入必然进入Open表，这样，在表，这样，在Open表变为空之前，目标节点必然表变为空之前，目标节点必然出现在出现在Open表中。因此，算法一定会成功结束。表中。因此，算法一定会成功结束。47 引理引理4.1 对无限图，如果从初始节点对无限图，如果从初始节点S0到目标节点到目标节点Sg有路径存在，有路径存在，则算法则算法A*算法不终止的话，则从算法不终止的话，则从Open表中选出的节点必将具有任意表中选出的节点必将具有任意大的大的f值。值。证明：证明：设设d*(n)是是A*生成的从初始节点生成的从初始节点S0到节点到节点n的最短路经长度，的最短路经长度，由于搜索图中每条边的代价都是一个正数，令这些正数中的最小的一由于搜索图中每条边的代价都是一个正数，令这些正数中的最小的一个数是个数是e，则有，则有 g*(n)d*(n)e因为因为g*(n)是最佳路径的代价，故有是最佳路径的代价，故有 g(n)g*(n)d*(n)e又因为又因为h(n)0，故有，故有 f(n)=g(n)+h(n)