搜索策略人工智能原理及其应学习教案.pptx

《搜索策略人工智能原理及其应学习教案.pptx》由会员分享，可在线阅读，更多相关《搜索策略人工智能原理及其应学习教案.pptx（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1搜索策略人工智能搜索策略人工智能(rnnzhnn)原原理及其应理及其应第一页，共88页。2搜索搜索(susu)的含义的含义适用情况：适用情况：不良结构或非结构化问题不良结构或非结构化问题(wnt)；难以获得求解所需的全部信息；更没有现成的算法；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。可供求解使用。概念：概念：依靠经验，利用已有知识，根据问题依靠经验，利用已有知识，根据问题(wnt)的实际情况，不断寻找可利用知识，从而的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题构造一条代价最小的推理路线，使问题(wnt)得以解决的过程称为搜索得以解决的过程称为

2、搜索搜索的类型搜索的类型按是否使用按是否使用(shyng)启发式信息：启发式信息：盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。不改变控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。着最有希望的方向前进，加速问题的求解过程并找到最优解。按问题的表示方式：按问题的表示方式：状态空间搜索：用状态空间法来求解问题所进行的搜索状态空间搜索：用状态空间法来求解问题所

3、进行的搜索与或树搜索：用问题归约法来求解问题时所进行的搜索与或树搜索：用问题归约法来求解问题时所进行的搜索第2页/共88页第二页，共88页。3状态状态(zhungti)空间法空间法1.状态状态(zhungti)空间表示方空间表示方法法状态状态(State)：是表示问题求解过程中每一步问题状况是表示问题求解过程中每一步问题状况(zhungkung)的数据结构，它可形式地表示为：的数据结构，它可形式地表示为：Sk=Sk0,Sk1,当对每一个分量都给以确定的值时，就得到了一个具体的状态。当对每一个分量都给以确定的值时，就得到了一个具体的状态。操作操作(Operator)也称为算符，它是把问题从一种状

4、态变换为另一种状态的手段。操作可以是一个机械步也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。之间的关系。状态空间状态空间(Statespace)用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：(S,F,G)其中，其中，S为问题的所有初始状态的集合；为问题的所有初始状态的集合；F为操作的集合；为

5、操作的集合；G为目标状态的集合。为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。节点表示问题的状态，有向边表示操作。第3页/共88页第三页，共88页。4状态空间法求解状态空间法求解(qi ji)(qi ji)问题的基本过程：问题的基本过程：首先为问题选择适当的首先为问题选择适当的“状态状态”及及“操作操作”的形式化描的形式化描述方法；述方法；然后从某个初始状态出发，每次使用一个然后从某个初始状态出发，每次使用一个“操作操作”，递，递增

6、地建立起操作序列，直到达到目标状态为止；增地建立起操作序列，直到达到目标状态为止；此时，由初始状态到目标状态所使用的算符序列就是该此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。问题的一个解。状态空间状态空间(kngjin)法法2.状态空间状态空间(kngjin)问题问题求解求解第4页/共88页第四页，共88页。5例例4.1二二阶阶梵梵塔塔问问题题。设设有有三三根根钢钢针针，它它们们的的编编号号分分别别是是1号号、2号号和和3号号。在在初初始始(chsh)情情况况下下，1号号钢钢针针上上穿穿有有A、B两两个个金金片片，A比比B小小，A位位于于B的的上上面面。要要求求把把这这两两个

7、个金金片片全全部部移移到到另另一一根根钢钢针针上上，而而且且规规定定每每次次只只能能移移动动一一个个金金片片，任任何何时时刻刻都都不不能能使使大大的的位于小的上面。位于小的上面。解：设用解：设用Sk=Sk0,Sk1表示问题的状态，其中，表示问题的状态，其中，Sk0表示金片表示金片A所在所在的钢针号，的钢针号，Sk1表示金片表示金片B所在的钢针号。全部可能的问题状态共有所在的钢针号。全部可能的问题状态共有(n yu)以下以下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)状态空间状态空间(k

8、ngjin)法法3.状态空间状态空间(kngjin)的例的例子子第5页/共88页第五页，共88页。6ABABAB123123123二阶梵塔问题的初始状态和目标二阶梵塔问题的初始状态和目标(mbio)状态状态问题的初始状态集合问题的初始状态集合(jh)为为S=S0 目标状态集合目标状态集合(jh)为为G=S4,S5 初始状态初始状态S0和目标和目标(mbio)状态状态S4、S8如图所示如图所示 S0=(1,1)S4=(2,2)S8=(3,3)状态空间法状态空间法3.状态空间的例子状态空间的例子第6页/共88页第六页，共88页。7 操作操作(cozu)分别用分别用A(i,j)和和B(i,j)表示表

9、示 A(i,j)表示把金片表示把金片A从第从第i号钢针移到号钢针移到j号钢针上；号钢针上；B(i,j)表示把金片表示把金片B从第从第i号钢针一到第号钢针一到第j号钢针上。共有号钢针上。共有12种种操作操作(cozu)，它们分别是：，它们分别是：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种操作种操作(cozu)，可构成二阶梵，可构成二阶梵塔问题的状态空间图，如下图所示。塔问题的状态空间图，如下图所示。状态空间状态空间(kngjin)法法3.状态空

10、间状态空间(kngjin)的例的例子子第7页/共88页第七页，共88页。8(3,3)(1,3)(1,2)(2,2)二阶梵塔的状态(zhungti)空间图从初始节点从初始节点(1,1)到目标节点到目标节点(2,2)及及(3,3)的任何一条路径都是问题的一个解。其中，的任何一条路径都是问题的一个解。其中，最短的路径长度是最短的路径长度是3，它由，它由3个操作个操作(cozu)组成。例如，从组成。例如，从(1,1)开始，通过使用操作开始，通过使用操作(cozu)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

11、,1)(2,3)A(1,3)B(1,2)A(3,2)第8页/共88页第八页，共88页。9例例4.2修道士修道士(Missionaries)和野人和野人(Cannibals)问题问题(简称简称M-C问题问题)。设在河的一岸有三个野人、三个修道士和一条船，修道士想设在河的一岸有三个野人、三个修道士和一条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：用这条船把所有的人运到河对岸，但受以下条件的约束：一是修道士和野人都会划船，但每次船上至多可载两个人；一是修道士和野人都会划船，但每次船上至多可载两个人；二是在河的任一岸，如果野人数目超过修道士数，修道士会二是在河的任一岸，如果野人数目超

12、过修道士数，修道士会被野人吃掉。被野人吃掉。如果野人会服从任何一次过河安排，请规划一个确保如果野人会服从任何一次过河安排，请规划一个确保(qubo)修道士和野人都能过河，且没有修道士被野人吃掉修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。的安全过河计划。状态空间状态空间(kngjin)法法3.状态空间状态空间(kngjin)的例的例子子第9页/共88页第九页，共88页。10 解：首先选取描述问题状态的方法解：首先选取描述问题状态的方法(fngf)。在这个问题中，。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是需要考虑两岸的修道士人数和野人数，还需要考虑船在

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种状态。种状态。状态状态(zhungti)空间法空间法3.状态状态(

14、zhungti)空间的例空间的例子子第10页/共88页第十页，共88页。11 这这32种状态并非全有意义种状态并非全有意义(yy)，除去不合法状态和修道士被野人吃掉的状态，有意义，除去不合法状态和修道士被野人吃掉的状态，有意义(yy)的状态只有的状态只有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、部分：因此，操作应由条件部分和动作部分：条件：只有当其条件具备时才能使用条件：只有当其条件具备时才能使用 动作：刻划了应用此操作所产生的结果。动作：刻划了应用此操作所产生的结果。第11页/共88页第十一页，共88页。12操作的表示：操作的表示：用符号用符号Pij表示从左岸到右岸的运人操作表示从左岸到右岸的运人操作 用符号用符号Qij表示从右岸到左岸的操作表示从右岸到左岸的操作其中：其中：i表示船上的修道士人数表示船上的修道士人数(rn sh)j表示船上的野人数表示船上的野人数(rn sh)操作集操作集 本问题有本问题有10种操作可供选择：种操作可供选择：F=P01,P10,P11,P02,P2

17、0,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 第12页/共88页第十二页，共88页。13abc 例4.3 猴子摘香蕉问题。在讨论谓词(wi c)逻辑知识表示时，我们曾提到过这一问题，现在用状态空间法来解决这一问题。解：问题的状态可用4元组（w,x,y,z）表示(biosh)。其中：w表示(biosh)猴子的水平位置；x表示(biosh)箱子的水平位置；y表示

18、(biosh)猴子是否在箱子上，当猴子在箱子上时，y取1，否则y取0；z表示(biosh)猴子是否拿到香蕉，当拿到香蕉时z取1，否则z取0。状态状态(zhungti)空间法空间法3.状态状态(zhungti)空间的例空间的例子子第13页/共88页第十三页，共88页。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)目标状态目标状态允许的操作允许的操作(cozu)为为 Goto(u)：猴子走到位置：猴子走到位置u，即，即 (w,x,0,0)(u,x,0,0)Pushbox

19、(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)这个问题的状态空间图如下图所示。不难看出，由初始状态变这个问题的状态空间图如下图所示。不难看出，由初始状态变为目标状态的操作为目标状态的操作(cozu)序列为：序列为：Goto(b),Pushbox(c),Climbbox,Grasp第14页/共88页第十四页，共88页。15猴子摘香蕉猴子摘香蕉(xingjio)(xingji

20、o)问题的解问题的解(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目标(mbio)状态猴子摘香蕉问题的状态(zhungti)空间图解序列为：解序列为：Goto(b),Pushbox(c),Climbbox,GraspPushbox(c)ClimbboxClimbboxPushbox(c)Pushbox(a)Pushbox(a)第15页/共88页第十五页，共88页。16基本思想基本思想 当一问题较复杂时，可通过分解或变换，将其转化当一问题较复杂时，可通

21、过分解或变换，将其转化(zhunhu)(zhunhu)为为一系列较简单的子问题，然后通过对这些子问题的求解来实现对原问一系列较简单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。题的求解。分解分解 如果一个问题如果一个问题P P可以归约为一组子问题可以归约为一组子问题P1,P2,PnP1,P2,Pn，并且只有当所，并且只有当所有子问题有子问题PiPi都有解时原问题都有解时原问题P P才有解，任何一个子问题才有解，任何一个子问题PiPi无解无解(w(w ji)ji)都会导致原问题都会导致原问题P P无解无解(w ji)(w ji)，则称此种归约为问题的分解。，则称此种归约为问题的分解。

22、即分解所得到的子问题的即分解所得到的子问题的“与与”与原问题与原问题P P等价。等价。等价变换等价变换 如果一个问题如果一个问题P P可以归约为一组子问题可以归约为一组子问题P1,P2,PnP1,P2,Pn，并且子问题，并且子问题PiPi中只要有一个有解则原问题中只要有一个有解则原问题P P就有解，只有当所有子问题就有解，只有当所有子问题PiPi都无解都无解(w ji)(w ji)时原问题时原问题P P才无解才无解(w ji)(w ji)，称此种归约为问题的等价变换，称此种归约为问题的等价变换，简称变换。简称变换。即变换所得到的子问题的即变换所得到的子问题的“或或”与原问题与原问题P P等价。

23、等价。问题归约法问题归约法1.问题的分解问题的分解(fnji)与等与等价变换价变换第16页/共88页第十六页，共88页。17PP1P2P3与树与树P1P2P3或树或树PPP1P2P3P12P12P31P32P33与与/或树或树(1)与树与树分解分解(fnji)(2)或树或树等价等价(dngji)变换变换(3)与与/或树或树问题问题(wnt)归约法归约法2.问题问题(wnt)的与的与/或树表或树表示示第17页/共88页第十七页，共88页。18(4)端节点与终止节点端节点与终止节点在与在与/或树中，没有子节点的节点称为端节点；本原或树中，没有子节点的节点称为端节点；本原(bnyun)问题所对问题所

24、对应的节点称为终止节点。可见，终止节点一定是端节点，但端节点却不一定应的节点称为终止节点。可见，终止节点一定是端节点，但端节点却不一定是终止节点。是终止节点。(5)可解节点与不可解节点可解节点与不可解节点在与在与/或树中，满足以下三个条件之一的节点为可解节点：或树中，满足以下三个条件之一的节点为可解节点：任何终止节点都是可解节点。任何终止节点都是可解节点。对对“或或”节点，当其子节点中至少有一个为可解节点时，则该或节点就是可节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点。解节点。对对“与与”节点，只有当其子节点全部为可解节点时，该与节点才是可解节点。节点，只有当其子节点全部为

25、可解节点时，该与节点才是可解节点。同样，可用类似同样，可用类似(lis)的方法定义不可解节点：的方法定义不可解节点：不为终止节点的端节点是不可解节点。不为终止节点的端节点是不可解节点。对对“或或”节点，若其全部子节点都为不可解节点，则该或节点是不可解节点。节点，若其全部子节点都为不可解节点，则该或节点是不可解节点。对对“与与”节点，只要其子节点中有一个为不可解节点，则该与节点是不可解节节点，只要其子节点中有一个为不可解节点，则该与节点是不可解节点。点。第18页/共88页第十八页，共88页。19Pttt解树解树(6)解树解树由可解节点构成，并且由这些可解由可解节点构成，并且由这些可解节点可以推出

26、初始节点（它对应着原始节点可以推出初始节点（它对应着原始问题）为可解节点的子树为解树。在解问题）为可解节点的子树为解树。在解树中一定包含初始节点。树中一定包含初始节点。例如，右图给出的与或树中，用红例如，右图给出的与或树中，用红线表示的子树是一个解树。在该图中，线表示的子树是一个解树。在该图中，节点节点P为原始问题节点，用为原始问题节点，用t标出的节点标出的节点是终止是终止(zhngzh)节点。根据可解节点节点。根据可解节点的定义，很容易推出原始问题的定义，很容易推出原始问题P为可解为可解节点。节点。问题归约求解过程就实际上就是生问题归约求解过程就实际上就是生成解树，即证明原始节点是可解节点的

27、成解树，即证明原始节点是可解节点的过程。这一过程涉及到搜索的问题，对过程。这一过程涉及到搜索的问题，对于与于与/或树的搜索将在后面详细讨论。或树的搜索将在后面详细讨论。第19页/共88页第十九页，共88页。20例例4.4三阶梵塔问题。要求把三阶梵塔问题。要求把1号钢针上的号钢针上的3个金片全部移到个金片全部移到3号钢针上，号钢针上，如下图所示。如下图所示。解：这个问题也可用状态空间法来解，不过本例主要用它来说明如何用归解：这个问题也可用状态空间法来解，不过本例主要用它来说明如何用归约法来解决问题。约法来解决问题。为了能够解决这一问题，首先需要定义该问题的形式化表示为了能够解决这一问题，首先需要

28、定义该问题的形式化表示(biosh)方法。方法。设用三元组设用三元组(i,j,k)表示表示(biosh)问题在任一时刻的状态，用问题在任一时刻的状态，用“”表示表示(biosh)状态的转换。上状态的转换。上述三元组中述三元组中i代表金片代表金片C所在的钢针号所在的钢针号j代表金片代表金片B所在的钢针号所在的钢针号k代表金片代表金片A所在的钢针号所在的钢针号123123问题问题(wnt)归约法归约法2.问题问题(wnt)的与的与/或树表示或树表示第20页/共88页第二十页，共88页。21利用问题归约方法，原问题可分解为以下利用问题归约方法，原问题可分解为以下(yxi)三个子问题：三个子问题：(1

29、)把金片把金片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)是本原问题，它已不需要再分解。是本原问题，它已不需要再分解。三阶梵塔问题的分解过程可用如下图与三

30、阶梵塔问题的分解过程可用如下图与/或树来表示或树来表示(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个本原问题。如果把这些本原问个本原问题。如果把这些本原问题从左至右排列起来题从左至右排列起来(qli)，即得到了原始问题的解：，即得到了原始问题的解：(1,1,1)(1,3,3

31、)(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)第21页/共88页第二十一页，共88页。22v搜索搜索(su su)的基本概念的基本概念v 状态空间的盲目搜索状态空间的盲目搜索(su su)v状态空间的启发式搜索状态空间的启发式搜索(su su)v与与/或树的盲目搜索或树的盲目搜索(su su)v与与/或树的启发式搜索或树的启发式搜索(su su)v博弈树的启发式搜索博弈树的启发式搜索(su su)第第4章章搜索搜索(susu)策略策略第22页/共88页第二十二页，共88页

32、。234.2状态空间的盲目状态空间的盲目(mngm)搜索搜索一般图搜索过程一般图搜索过程广度优先和深度广度优先和深度(shnd)优先搜索优先搜索代价树搜索代价树搜索第23页/共88页第二十三页，共88页。24状态空间搜索的基本思想状态空间搜索的基本思想 先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点问题

33、的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止操作的节点为止(wizh)(wizh)。所谓对一个节点进行。所谓对一个节点进行“扩展扩展”是指对该节点用某个可是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。用操作进行作用，生成该节点的一组子节点。一般图搜索一般图搜索(susu)过程过程算法的数据结构和符号算法的数据结构和符号(fho)约定约定Open表：用于存放刚生成的节点表：用于存放刚生成的节点Closed表：

34、用于存放已经扩展或将要扩展的节点表：用于存放已经扩展或将要扩展的节点S0：用表示问题的初始状态：用表示问题的初始状态G：表示搜索过程所得到的搜索图：表示搜索过程所得到的搜索图M：表示当前扩展节点新生成的且不为自己先辈的子节点集。：表示当前扩展节点新生成的且不为自己先辈的子节点集。第24页/共88页第二十四页，共88页。25一般图搜索过程一般图搜索过程 (1)(1)把初始节点把初始节点S0S0放入放入OpenOpen表，并建立目前仅包含表，并建立目前仅包含S0S0的图的图G G；(2)(2)检查检查OpenOpen表是否为空，若为空，则问题无解，失败推出；表是否为空，若为空，则问题无解，失败推出

35、；(3)(3)把把OpenOpen表的第一个节点取出放入表的第一个节点取出放入ClosedClosed表，并记该节点为节点表，并记该节点为节点n n；(4)(4)考察考察(koch)(koch)节点节点n n是否为目标节点。若是则得到了问题的解，成功退出；是否为目标节点。若是则得到了问题的解，成功退出；(5)(5)扩展节点扩展节点n n，生成一组子节点。把这些子节点中不是节点，生成一组子节点。把这些子节点中不是节点n n先辈的那部分子节点记先辈的那部分子节点记入集合入集合M M，并把这些子节点作为节点，并把这些子节点作为节点n n的子节点加入的子节点加入G G中中 (6)(6)针对针对M M中

36、子节点的不同情况，分别作如下处理：中子节点的不同情况，分别作如下处理：对那些没有在对那些没有在G G中出现过的中出现过的M M成员设置一个指向其父节点（即节点成员设置一个指向其父节点（即节点n n）的指针，并把）的指针，并把它放入它放入OpenOpen表。（新生成的）表。（新生成的）对那些原来已在对那些原来已在G G中出现过，但还没有被扩展的中出现过，但还没有被扩展的M M成员，确定是否需要修改它指向父成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的）节点的指针。（原生成但未扩展的）对于那些先前已在对于那些先前已在G G中出现过，并已经扩展了的中出现过，并已经扩展了的M M成员，确

37、定是否需要修改其后继节成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的）点指向父节点的指针。（原生成也扩展过的）(7)(7)按某种策略对按某种策略对OpenOpen表中的节点进行排序。表中的节点进行排序。(8)(8)转第转第(2)(2)步。步。第25页/共88页第二十五页，共88页。26算法的几点说明：算法的几点说明：(1)上述过程是状态空间的一般图搜索算法，它具有通用性，后面所要讨论的各种状态空上述过程是状态空间的一般图搜索算法，它具有通用性，后面所要讨论的各种状态空间搜索策略都是上述过程的一个特例。各种搜索策略的主要区别在于对间搜索策略都是上述过程的一个特例。各种搜索策

38、略的主要区别在于对Open表中节点的排列顺表中节点的排列顺序不同。例如，广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点序不同。例如，广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点排在前面。排在前面。(2)在第在第(5)步对节点步对节点n扩展后，生成并记入扩展后，生成并记入M的子节点有以下三种情况：的子节点有以下三种情况：该子节点来从未被任何节点生成过，由该子节点来从未被任何节点生成过，由n第一次生成；第一次生成；该子节点原来被其他节点生成过，但还没有被扩展，这一次又被该子节点原来被其他节点生成过，但还没有被扩展，这一次又被n再次生成；再次生成；该

39、子节点原来被其他节点生成过，并且已经被扩展过，这一次又被该子节点原来被其他节点生成过，并且已经被扩展过，这一次又被n再次生成。再次生成。以上三种情况是对一般图搜索算法而言的。对于盲目搜索，由于其状态空间是树状结构，以上三种情况是对一般图搜索算法而言的。对于盲目搜索，由于其状态空间是树状结构，因此不会出现因此不会出现(chxin)后两种情况，每个节点经扩展后生成的子节点都是第一次出现后两种情况，每个节点经扩展后生成的子节点都是第一次出现(chxin)的节点，不必检查并修改指向父节点的指针。的节点，不必检查并修改指向父节点的指针。第26页/共88页第二十六页，共88页。27 (3)在第(6)步针对

40、M中子节点的不同情况进行处理时，如果发生当第种情况，那么，这个M中的节点究竟应该作为哪一个节点的后继节点呢？一般是由原始节点到该节点路径上所付出的代价来决定的，哪一条路经付出的代价小，相应的节点就作为它的父节点。所谓由原始节点到该节点路径上的代价是指这条路经上的所有有向边的代价之和。如果发生第种情况，除了需要确定该子节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针。其依据也是由原始节点到该节点的路径上的代价。(4)在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树。(5)在搜索过程的第(4

41、)步，一旦(ydn)某个被考察的节点是目标节点，则搜索过程成功结束。由初始节点到目标节点路径上的所有操作就构成了该问题的解，而路径由第(6)步所形成的指向父节点的指针来确定。(6)如果搜索过程终止在第(2)步，即没有达到目标，且Open表中已无可供扩展的节点，则失败结束。第27页/共88页第二十七页，共88页。28基本思想基本思想 从初始节点从初始节点S0S0开始逐层向下扩展，在第开始逐层向下扩展，在第n n层节点还没有全部搜索完之前，不进入层节点还没有全部搜索完之前，不进入第第n+1n+1层节点的搜索。层节点的搜索。OpenOpen表中的节点总是按进入的先后排序，先进入的节点排在表中的节点总

42、是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。前面，后进入的节点排在后面。搜索算法搜索算法 (1)(1)把初始节点把初始节点S0S0放入放入OpenOpen表中；表中；(2)(2)如果如果OpenOpen表为空，则问题无解，失败表为空，则问题无解，失败(shbi)(shbi)退出；退出；(3)(3)把把OpenOpen表的第一个节点取出放入表的第一个节点取出放入ClosedClosed表，并记该节点为表，并记该节点为n n；(4)(4)考察节点考察节点n n是否为目标节点。若是，则得到问题的解，成功退出；是否为目标节点。若是，则得到问题的解，成功退出；(5)(5)若节点若节点

43、n n不可扩展，则转第不可扩展，则转第(2)(2)步；步；(6)(6)扩展节点扩展节点n n，将其子节点放入，将其子节点放入OpenOpen表的尾部，并为每一个子节点设置指向父表的尾部，并为每一个子节点设置指向父节点的指针，然后转第节点的指针，然后转第(2)(2)步。步。广度优先广度优先(yuxin)和深度优先和深度优先(yuxin)搜索搜索1.广度优先广度优先(yuxin)搜索搜索第28页/共88页第二十八页，共88页。29 例例4.5 八八数数码码难难题题。在在33的的方方格格棋棋盘盘上上，分分别别放放置置了了表表有有数数字字1、2、3、4、5、6、7、8的的八八张张牌牌，初初始始状状态态

44、S0，目目标标状状态态Sg，如如下下图图所所示示。可可以使用的操作有以使用的操作有 空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，空格下移即即只只允允许许把把位位于于空空格格左左、上上、右右、下下方方的的牌牌移移入入空空格格。要要求求应应用用广广度度优优先先搜索策略寻找搜索策略寻找(xnzho)从初始状态到目标状态的解路径。从初始状态到目标状态的解路径。2 8 31 47 6 5 1 2 38 47 6 5 S0 Sg第29页/共88页第二十九页，共88页。3028314765283147652318476528314765283164758321476528371465

45、2318476523184765281437652831457628316475283164758321476528371465832147658132476528374615283714651238476512378465123847652341876528143765283145762836417528316754S0123456789101112131415161718192021222324252627Sg第30页/共88页第三十页，共88页。31算法描述算法描述(1)把初始节点把初始节点S0放入放入Open表中；表中；(2)如果如果Open表为空，则问题无解表为空，则问题无解，失败退

46、出；，失败退出；(3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为表，并记该节点为n；(4)考察节点考察节点n是否为目标节点。若是，则得到问题的解，成功退出；是否为目标节点。若是，则得到问题的解，成功退出；(5)若节点若节点n不可不可(bk)扩展，则转第扩展，则转第(2)步；步；(6)扩展节点扩展节点n，将其子节点放入，将其子节点放入Open表的首部，并为每一个子节点设置表的首部，并为每一个子节点设置指向父节点指向父节点的指针，然后转第的指针，然后转第(2)步。步。广度优先和深度广度优先和深度(shnd)优先搜优先搜索索2.深度深度(shnd)优先搜索优

47、先搜索基本思想基本思想从初始节点从初始节点S0开始，在其子节点中选择一个最新生成的节点进行考察，如果该子节点不是开始，在其子节点中选择一个最新生成的节点进行考察，如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察，依此向下节点进行考察，依此向下(xinxi)搜索，直到某个子节点既不是目标节点，又不能继续扩搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。展时，才选择其兄弟节点进行考察。第31页/共88页第三十一页，共88页。32

48、2831476528314765231847652831476528316475283164752831647528316754283167542816375428163754S0123456八数码难题的深度八数码难题的深度(shnd)优先搜索如右优先搜索如右图图一种改进的深度优先一种改进的深度优先(yuxin)算法是有界算法是有界深度优先深度优先(yuxin)搜索算法，深度限制为搜索算法，深度限制为dm例例4.6八数码八数码(shm)难题难题第32页/共88页第三十二页，共88页。33 在在代代价价树树中中，可可以以用用g(n)表表示示(biosh)从从初初始始节节点点S0到到节节点点n的的

49、代代价价，用用c(n1,n2)表表示示(biosh)从从父父节节点点n1到到其其子子节节点点n2的的代代价价。这这样样，对对节节点点n2的的代代价价有有：g(n2)=g(n1)+c(n1,n2)。代代价价树树搜搜索索的的目目的的是是为为了了找找到到最最佳佳解，即找到一条代价最小的解路径。解，即找到一条代价最小的解路径。代价代价(diji)树搜索树搜索1.代价代价(diji)树的广度优先搜索树的广度优先搜索代价树的广度优先搜索算法：代价树的广度优先搜索算法：(1)把初始节点把初始节点S0放入放入Open表中，置表中，置S0的代价的代价g(S0)=0；(2)如果如果Open表为空，则问题无解表为空

50、，则问题无解，失败退出，失败退出(tuch)；(3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为表，并记该节点为n；(4)考察节点考察节点n是否为目标。若是，则找到了问题的解，成功退出是否为目标。若是，则找到了问题的解，成功退出(tuch)；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)扩展节点扩展节点n，生成其子节点，生成其子节点ni(i=1,2,)，将这些子节点放入，将这些子节点放入Open表表中，并为每一个子节点设置指向父节点的指针。按如下公式：中，并为每一个子节点设置指向父节点的指针。按如下公式：g(ni)=g(n)+c