搜索与求解人工智能导论课件.ppt

1、1第第 2 2 章章 搜搜 索索2搜索策略搜索策略搜索的基本概念搜索的基本概念状态空间搜索状态空间搜索博弈树搜索博弈树搜索盲目搜索盲目搜索启发式搜索启发式搜索宽度优先搜索宽度优先搜索深度优先搜索深度优先搜索有界深度有界深度优先搜索优先搜索局部择优搜索局部择优搜索全局择优搜索全局择优搜索A*算法算法极大极小极大极小分析法分析法 剪枝技术剪枝技术与或图搜索与或图搜索3l 理解搜索及回溯的概念，掌握启发式搜索和盲理解搜索及回溯的概念，掌握启发式搜索和盲目搜索的概念；目搜索的概念；l 掌握宽度优先搜索算法和深度优先搜索算法，掌握宽度优先搜索算法和深度优先搜索算法，并了解二者的区别；并了解二者的区别；l

2、 了解了解A*算法。算法。42.1 2.1 搜索概述搜索概述2.2 2.2 状态空间搜索状态空间搜索2.3 2.3 状态空间盲目搜索状态空间盲目搜索2.4 2.4 状态空间启发式搜索状态空间启发式搜索2.5 2.5 代价树的搜索代价树的搜索2.6 2.6 与与/或树搜索或树搜索2.7 2.7 博弈树的启发式搜索博弈树的启发式搜索5 现实世界中的大多数问题都是非结构化问题，现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法，而只能利用已有知一般不存在现成的求解方法，而只能利用已有知识一步一步摸索前进。识一步一步摸索前进。根据问题的实际情况，按照一定的策略或规则，根据问题的实际情况，

3、按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程，就称为使问题获得解决的推理路线的过程，就称为搜索搜索。6 搜索包含两层含义：搜索包含两层含义：（1 1）要找到从初始事实到问题最终答案的一条推理）要找到从初始事实到问题最终答案的一条推理路线；路线；（2 2）找到的这条路线是时间和空间复杂程度最小的）找到的这条路线是时间和空间复杂程度最小的求解路线。求解路线。7 搜索是人工智能技术中进行问题求解的基本技搜索是人工智能技术中进行问题求解的基本技术，也是人工智能中的一个核心技术，是推理不术，也是人工智能中的一个核

4、心技术，是推理不可分隔的一部分，它直接关系到智能系统的性能可分隔的一部分，它直接关系到智能系统的性能和运行效率。和运行效率。人工智能进行问题求解的两种基本技术：人工智能进行问题求解的两种基本技术：1.1.图搜索图搜索2.2.搜索算法搜索算法8 运用领域知识，以运用领域知识，以符号推演符号推演的方式，顺的方式，顺序地在序地在问题空间问题空间进行搜索。其中的问题空进行搜索。其中的问题空间表示为某种状态图（空间）或与或图的间表示为某种状态图（空间）或与或图的形式。形式。该方法模拟人脑分析问题。该方法模拟人脑分析问题。9 以计算的方法，随机地在问题的以计算的方法，随机地在问题的解空间解空间中进行搜索。

5、中进行搜索。该方法是借鉴或模拟自然现象或生命现该方法是借鉴或模拟自然现象或生命现象。象。10 根据搜索过程中是否使用启发式信息，可以把根据搜索过程中是否使用启发式信息，可以把搜索的类型分为两种：搜索的类型分为两种：1.1.盲目搜索（无信息搜索）盲目搜索（无信息搜索）2.2.启发式搜索（有信息搜索）启发式搜索（有信息搜索）11 指在搜索过程中，按照原来规定的搜索策略进指在搜索过程中，按照原来规定的搜索策略进行搜索，而没有加入任何中间信息来改变这些控行搜索，而没有加入任何中间信息来改变这些控制策略。制策略。搜索带有盲目性、效率低。搜索带有盲目性、效率低。该方法通常只用于解决比较简单的问题。该方法通

6、常只用于解决比较简单的问题。12 指在搜索过程中，根据问题本身的特性或一些指在搜索过程中，根据问题本身的特性或一些在搜索过程中产生的信息来不断修改或调整搜索在搜索过程中产生的信息来不断修改或调整搜索的方向，是搜索向着最有利的方向前进，加快问的方向，是搜索向着最有利的方向前进，加快问题求解的速度，并找到最优解。题求解的速度，并找到最优解。该方法是更易于求解复杂的问题。该方法是更易于求解复杂的问题。132.1 2.1 搜索概述搜索概述2.2 2.2 状态空间搜索状态空间搜索2.3 2.3 状态空间盲目搜索状态空间盲目搜索2.4 2.4 状态空间启发式搜索状态空间启发式搜索2.5 2.5 代价树的搜

7、索代价树的搜索2.6 2.6 与与/或树搜索或树搜索2.7 2.7 博弈树的启发式搜索博弈树的启发式搜索14Sgl 内容：内容：状态空间的搜索问题状态空间的搜索问题l 搜索策略：搜索策略：盲目搜索盲目搜索启发式搜索启发式搜索l 关键问题：关键问题：如何利用知识，尽可能有效如何利用知识，尽可能有效地找到问题的解（最佳解）。地找到问题的解（最佳解）。S015讨论的问题：讨论的问题：l 如何用状态空间法表示问题和问题的求解过程？如何用状态空间法表示问题和问题的求解过程？l 使用状态空间法求解问题的具体过程如何？使用状态空间法求解问题的具体过程如何？16【准备知识准备知识1：状态空间定义：状态空间定义

8、】（参见教材（参见教材62页）页）l 状态：状态：描述问题求解过程中不同时刻状况的数据结描述问题求解过程中不同时刻状况的数据结构。一般用一组变量的有序集合表示：构。一般用一组变量的有序集合表示：Q=(qQ=(q0 0,q,q1 1,q,q2 2,q qn n)l 算符（操作）：算符（操作）：引起状态中某些分量发生变化，从而使问题引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作。由一个状态变为另一个状态的操作。17l 状态空间状态空间 由表示一个问题的全部状态及一切可用算符构由表示一个问题的全部状态及一切可用算符构成的集合称为该问题的状态空间。成的集合称为该问题的状态空间。状

9、态空间可以用空间三元组状态空间可以用空间三元组(S,F,G)(S,F,G)表示：表示：S-S-问题初始状态的集合问题初始状态的集合F-F-操作或算符的集合操作或算符的集合G-G-目标状态的集合目标状态的集合 状态空间的图示形式称为状态空间的图示形式称为状态空间图状态空间图。其中的。其中的节点表示状态，有向边（弧）表示算符。节点表示状态，有向边（弧）表示算符。18【状态空间的例子状态空间的例子1迷宫问题迷宫问题】以例以例3.13.1中的迷宫为例。我们以每个格子作为一个状态中的迷宫为例。我们以每个格子作为一个状态,并并用其标识符作为其表示。那么用其标识符作为其表示。那么,两个标识符组成的序对就是一

10、两个标识符组成的序对就是一个状态转换规则。于是个状态转换规则。于是,该迷宫的状态空间表示为该迷宫的状态空间表示为 S：SoF：(So,S4),(S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S2,S3),(S3,S2),(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S6),(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)G：Sg 19迷宫问题的空间状态图为：迷宫问题的空间状态图为：S0S4S1S6S7S2S5S8S9SgS320l 问题求解问题求解 从问题的初始状态集从问题的初始状态集Qs

11、Qs出发，经过一系列的出发，经过一系列的算符运算，到达目标状态算符运算，到达目标状态QgQg。该过程中所用算符。该过程中所用算符的序列的序列f f构成问题的一个解。构成问题的一个解。QsSQsS,QgGQgG,算子序列算子序列f f：f=f1,f2,f=f1,f2,fn fn 使得使得 QgQg=fn(=fn(f2(f1(Qs)(f2(f1(Qs)21【问题求解的例子问题求解的例子-八数码难题八数码难题】在在3 3*3 3的方格棋盘上，分别放置了标有数字的方格棋盘上，分别放置了标有数字1 1、2 2、3 3、4 4、5 5、6 6、7 7、8 8的八张牌，初始状态的八张牌，初始状态So,So,

12、目目标状态为标状态为SgSg。操作规则是：与空格相邻的数码可通过左移、操作规则是：与空格相邻的数码可通过左移、上移、下移、右移来移入空格。上移、下移、右移来移入空格。237 51486586 12743123 84765初始状态初始状态SoSo目标状态目标状态SgSg22n 状态转移状态转移-规则规则237 51486237 45186数码数码上移上移23l 路径路径-状态序列状态序列l 搜索搜索-寻找从初始状态到目标状态的路径寻找从初始状态到目标状态的路径;S0Sg24状态空间237 514861238476525l 难点难点2375148612384765可用操作冲突可用操作冲突如何消解？

13、如何消解？如何搜索到最优解？如何搜索到最优解？26【状态空间及问题求解的例子状态空间及问题求解的例子梵塔问题梵塔问题】(P64)设有三根宝石杆设有三根宝石杆,在在1 1号杆上穿有号杆上穿有A A、B B两个金两个金盘盘,A A小于小于B B,A,A位于位于B B的上面。要求把这两个金盘的上面。要求把这两个金盘全部移到另一根杆上全部移到另一根杆上,而且规定每次只能移动一个而且规定每次只能移动一个盘子盘子,任何时刻都不能使任何时刻都不能使B B位于位于A A的上面。的上面。27 设用二元组设用二元组(S(SA A,S,SB B)表示问题的状态表示问题的状态,S,SA A表示表示金盘金盘A A所在的

14、杆号所在的杆号,S,SB B表示金盘表示金盘B B所在的杆号所在的杆号,这这样样,全部可能的状态有全部可能的状态有9 9种种,可表示如下：可表示如下：(1,1),(1,2),(1,3)(1,1),(1,2),(1,3)(2,1),(2,2),(2,3)(2,1),(2,2),(2,3)(3,1),(3,2),(3,3)(3,1),(3,2),(3,3)28二阶梵塔的全部状态二阶梵塔的全部状态29这里的状态转换规则就是金盘的搬动规则，分别这里的状态转换规则就是金盘的搬动规则，分别用用A(i,jA(i,j)及及B(i,jB(i,j)表示：表示：A(i,jA(i,j)表示把表示把A A盘从第盘从第i

15、 i号号杆移到第杆移到第j j号杆上号杆上;B(i,jB(i,j)表示把表示把B B盘从第盘从第i i号杆移到号杆移到第第j j号杆上。经分析，共有号杆上。经分析，共有1212个操作，它们分别是：个操作，它们分别是：A(1,2),A(1,2),A(1,3),A(1,3),A(2,1),A(2,1),A(2,3),A(2,3),A(3,1),A(3,1),A(3,2)A(3,2)B(1,2),B(1,2),B(1,3),B(1,3),B(2,1),B(2,1),B(2,3),B(2,3),B(3,1),B(3,1),B(3,2)B(3,2)30 由这由这9 9种可能的状态和种可能的状态和1212

16、种操作种操作,二阶梵塔问二阶梵塔问题的状态空间图如图所示：题的状态空间图如图所示：S0S3S6S5S8S2S1S4S7311.使用状态空间表示法表示问题时：使用状态空间表示法表示问题时：l首先定义状态的描述形式，并使用这种描述形式把问首先定义状态的描述形式，并使用这种描述形式把问题的状态全部表示出来；题的状态全部表示出来；l其次定义一组操作，通过使用这些操作把问题从一种其次定义一组操作，通过使用这些操作把问题从一种状态变为另一种状态。状态变为另一种状态。2.问题的求解过程实际是一个不断操作作用于状态的过程。问题的求解过程实际是一个不断操作作用于状态的过程。如果使用某种操作得到的新状态就是目标状

17、态，就得到了如果使用某种操作得到的新状态就是目标状态，就得到了问题的一个解。这个解是从问题初始状态到目标状态的操问题的一个解。这个解是从问题初始状态到目标状态的操作序列。作序列。32课课 堂堂 练练 习习 题题 设有三只琴键开关一字排开设有三只琴键开关一字排开,初始状态为初始状态为“关、开、关、开、关关”,问连按三次后是否会出现问连按三次后是否会出现“开、开、开、开开、开”或或“关、关、关关、关、关”的状态？要求每次必的状态？要求每次必须按下一个开关须按下一个开关,而且只能按一个开关。而且只能按一个开关。请画出状态空间图。请画出状态空间图。【注：琴键开关有这样的特点注：琴键开关有这样的特点,若

18、第一次按下时它为若第一次按下时它为“开开”,则第二次按下时它就变成了则第二次按下时它就变成了“关关”。】33【准备知识准备知识2 2：状态图搜索方式：状态图搜索方式】（参见教材（参见教材5050页）页）l 树式搜索树式搜索 在搜索过程中记录所经过的在搜索过程中记录所经过的所有节点和边所有节点和边，记，记录轨迹为一棵录轨迹为一棵“树树”。l 线式搜索线式搜索 在搜索过程中只记录那些当前认为在搜索过程中只记录那些当前认为处在所找路处在所找路径上的节点和边径上的节点和边，记录轨迹是一条，记录轨迹是一条“线线”（折（折线）。线）。34【准备知识准备知识3 3：状态图搜索策略：状态图搜索策略】（参见教材

19、（参见教材5151页）页）l 盲目搜索策略盲目搜索策略 就是无就是无“向导向导”的搜索。的搜索。l 启发式搜索策略启发式搜索策略 就是有就是有“向导向导”的搜索。的搜索。“启发式启发式”信息信息启发式启发式搜索搜索全局最优全局最优搜索搜索局部择优局部择优搜索搜索最佳图最佳图搜索搜索35【准备知识准备知识4 4：状态图搜索基本概念：状态图搜索基本概念】l 节点深度：节点深度：根节点深度根节点深度=0=0；其它节点深度其它节点深度=父节点深度父节点深度+1+1。012336l 路径路径 设一节点序列为设一节点序列为(n(n0 0,n,n1 1,n nk k)，对于，对于 i=1,i=1,k,k，若

20、节点，若节点n ni-1i-1具有一个后继节点具有一个后继节点n ni i，则该，则该序列称为从序列称为从n n0 0到到n nk k的路径。的路径。l 路径的耗散值路径的耗散值 一条路径的耗散值等于连接这条路径各节点间一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用所有耗散值的总和。用C(nC(ni i,n nj j)表示从表示从n ni i到到n nj j的路的路径的耗散值。径的耗散值。37l 扩展一个节点扩展一个节点 生成出该节点的所有后继节点，并给出它们生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为之间的耗散值。这一过程称为“扩展一个节点扩展一个节点”。3

21、82.2.1 2.2.1 状态空间搜索的一般过程状态空间搜索的一般过程状态空间搜索实际上就是对状态空间搜索实际上就是对有向图的搜索有向图的搜索。先把问题的初始状态当作当前扩展节点对其先把问题的初始状态当作当前扩展节点对其进行进行扩展扩展，生成一组子节点，然后，生成一组子节点，然后检查问题的目检查问题的目标状态是否出现标状态是否出现在这些子节点中。若出现，则搜在这些子节点中。若出现，则搜索成功，找到了该问题的解；若没有出现，则按索成功，找到了该问题的解；若没有出现，则按照某种搜索策略从已生成的子节点中选择一个作照某种搜索策略从已生成的子节点中选择一个作为当前扩展节点。重复上述过程，为当前扩展节点

22、。重复上述过程，直到目标状态直到目标状态出现出现在子节点中在子节点中或没有可供扩展的节点为止或没有可供扩展的节点为止。392.2.2 2.2.2 状态空间图搜索的一般算法状态空间图搜索的一般算法（参见教材（参见教材P51P51）l OpenOpen表用于存放还没有扩展表用于存放还没有扩展的节点，因此，的节点，因此，OpenOpen表称为表称为未扩展的节点表未扩展的节点表。l ClosedClosed表用于存放已经扩展表用于存放已经扩展或将要扩展的节点，因此，或将要扩展的节点，因此，ClosedClosed称为已扩展的节点表称为已扩展的节点表。l 用用S0S0表示问题的初始状态，表示问题的初始状

23、态，G G表示搜索过程所得到的搜表示搜索过程所得到的搜索图，索图，M M表示当前扩展节点表示当前扩展节点新生成的且不为自己先辈新生成的且不为自己先辈的的子节点集。子节点集。401.G=G0(G0=s0),OPEN:=(s0);%建立一个只有起始节点建立一个只有起始节点S0S0组成组成的图的图G,G,把把S0S0放到放到OPENOPEN表中；表中；2.CLOSED:=();%建立一个建立一个CLOSEDCLOSED表，置为空；表，置为空；3.LOOP:IF OPEN=()THEN EXIT(FAIL);%判断判断OPENOPEN表是表是否为空否为空,若为空若为空,则问题无解则问题无解,退出退出;

24、4.n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);%);%从从OPENOPEN表中取出第一个节点表中取出第一个节点n n放入放入CLOSEDCLOSED表。表。5.IF GOAL(n)THEN EXIT(SUCCESS);%如果如果n n是目标节点，是目标节点，成功结束；成功结束；6.EXPAND(n)mi,G:=ADD(mi,G);%;%扩展节点扩展节点n,n,后继节点后继节点记为记为M=miM=mi，把，把M M加入加入G G中；中；417.7.标记和修改指针：标记和修改指针：ADD(mADD(mj j,OPEN),OPEN),并标记并标记m mj

25、 j到到n n的指针；的指针；计算是否要修改计算是否要修改m mk k、m ml l到到n n的指针；的指针；计算是否要修改计算是否要修改m ml l到其后继节点的指针；到其后继节点的指针；8 8.对对OPENOPEN中的节点按某种原则重新排序；中的节点按某种原则重新排序；9.GO LOOP9.GO LOOP；42开始初始化：把S0放入OPEN表，CLOSED表置空OPEN表为空表？把OPEN表的第1个节点（记为n）移至CLOSED表节点n为目标节点？若节点n的后继节点未曾在搜索图G中出现，则把其放入OPEN表的末端，并提供返回节点n的指针根据后继节点曾在搜索图G中的出现情况修改指针方向重排O

26、PEN表失败，退出成功，退出YYNN状态空间一般搜索流程图状态空间一般搜索流程图43 修改返回指针修改返回指针原有返回指针：原有返回指针：D DC CB BS0S0修改后返回指针：修改后返回指针：D DA AS0S044 修改指针举例修改指针举例123456s指针返回路径：指针返回路径：4 42 23 3B BA AS0S0BA45123456sBADC原有指针返回路径：原有指针返回路径：4 42 23 3B BA AS0S0修改后指针返回路径：修改后指针返回路径：4 46 6D DC CS0S046原有指针返回路径：原有指针返回路径：4 46 6D DC CS0S0修改后指针返回路径：修改后

27、指针返回路径：4 42 21 1S0S0123456sDCAB47u 搜索图搜索图123456s 在搜索过程中，生成一个图在搜索过程中，生成一个图G G，它是问题状态空间图，它是问题状态空间图的一部分。的一部分。48u 搜索树：搜索树：123456s 由搜索图由搜索图G G中所有节点及指向父节点的反向指针所中所有节点及指向父节点的反向指针所构成的集合。构成的集合。492.1 2.1 搜索概述搜索概述2.2 2.2 状态空间搜索状态空间搜索2.3 2.3 状态空间盲目搜索状态空间盲目搜索2.4 2.4 状态空间启发式搜索状态空间启发式搜索2.5 2.5 代价树的搜索代价树的搜索2.6 2.6 与

28、与/或树搜索或树搜索2.7 2.7 博弈树的启发式搜索博弈树的启发式搜索50 在搜索过程中，只按在搜索过程中，只按预定的预定的搜索控制策略进行搜索控制策略进行搜索，搜索，没有任何中间信息没有任何中间信息来改变搜索控制策略。来改变搜索控制策略。由于问题本身的特性对搜索控制策略没有任何由于问题本身的特性对搜索控制策略没有任何影响，使得这样的搜索带有盲目性，效率不高。只影响，使得这样的搜索带有盲目性，效率不高。只适用于解决比较简单的问题。适用于解决比较简单的问题。51 盲目搜索的方法：盲目搜索的方法：主要的盲目搜索方法有：主要的盲目搜索方法有：l 宽度宽度(广度广度)优先搜索优先搜索l 深度优先搜索

29、深度优先搜索l 有界深度优先搜索有界深度优先搜索52(Breadth-first Search)又称为广度优先搜索，是一种盲目搜索策略。又称为广度优先搜索，是一种盲目搜索策略。宽度优先搜索的基本思想是：从初始节点宽度优先搜索的基本思想是：从初始节点S S0 0开开始，始，逐层地对节点进行扩展逐层地对节点进行扩展并考察它是否为目标节并考察它是否为目标节点，在第点，在第n n层的节点没有全部扩展并考察之前，不层的节点没有全部扩展并考察之前，不对第对第n n1 1层的节点进行扩展。层的节点进行扩展。OPENOPEN表中的节点总是表中的节点总是按进入的先后顺序排列按进入的先后顺序排列，先进入的节点排在

30、前面，后进入的排在后面。先进入的节点排在前面，后进入的排在后面。531.G:=G0(G0=s),OPEN:=(s),CLOSED:=();2.LOOP:IF OPEN=()THEN EXIT(FAIL);3.n:=FIRST(OPEN);4.IF GOAL(n)THEN EXIT(SUCCESS);5.REMOVE(n,OPEN),ADD(n,CLOSED);6.EXPAND(n)mi,G:=ADD(mi,G);7.IF 目标在目标在mi中中 THEN EXIT(SUCCESS);8.ADD(OPEN,mj),并标记并标记 mj 到到 n 的指针的指针;9.GO LOOP;54开始初始化：把S

31、0放入OPEN表，CLOSED表置空OPEN表为空表？把OPEN表的第1个节点（记为n）移至CLOSED表节点n为目标节点？扩展节点n，将其后继节点放入OPEN表的末端末端，为每个后继节点设置指向节点n的指针无解，退出成功，退出YYNN宽度优先搜索算法流程图宽度优先搜索算法流程图节点n可扩展吗？回溯求解路径NY5523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标点目标点82

32、341876549【例例】宽度优先求解八数码问题宽度优先求解八数码问题1011121314151617解路径：解路径：S03817起始点起始点56u 宽度优先搜索的性质宽度优先搜索的性质l 当问题有解时，一定能找到解当问题有解时，一定能找到解l 搜索效率较低搜索效率较低l 方法与问题无关，具有通用性方法与问题无关，具有通用性l 搜索得到的解是搜索树中路径最短的解搜索得到的解是搜索树中路径最短的解（最优解）（最优解）l 属于属于完备完备搜索策略搜索策略57(Depth-first Search)在深度优先搜索中，首先扩展最新产生的在深度优先搜索中，首先扩展最新产生的(即最深的即最深的)节点。深度

33、相等的节点可以任意排节点。深度相等的节点可以任意排列。列。58u 深度优先搜索的基本思想深度优先搜索的基本思想 从初始节点从初始节点S0S0开始扩展，若没有得到目标节开始扩展，若没有得到目标节点，则选择最后产生的子节点进行扩展，若还是点，则选择最后产生的子节点进行扩展，若还是不能到达目标节点，则再对刚才最后产生的子节不能到达目标节点，则再对刚才最后产生的子节点进行扩展，一直如此向下搜索。点进行扩展，一直如此向下搜索。当到达某个子节点，且该子节点既不是目标当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行节点又不能继续扩展时，才选择其兄弟节点进行考察。考察。59u

34、深度优先搜索算法：深度优先搜索算法：1.G:=G0(G0=s),OPEN:=(s),CLOSED:=();2.LOOP:IF OPEN=()THEN EXIT(FAIL);3.n:=FIRST(OPEN);4.IF GOAL(n)THEN EXIT(SUCCESS);5.REMOVE(n,OPEN),ADD(n,CLOSED);6.EXPAND(n)mi,G:=ADD(mi,G);7.ADD(mj,OPEN),并标记并标记mj到到n的指针的指针;8.GO LOOP;60开始初始化：把S0放入OPEN表，CLOSED表置空OPEN表为空表？把OPEN表的第1个节点（记为n）移至CLOSED表节点

35、n为目标节点？扩展节点n，将其后继节点放入OPEN表的前端前端，为每个后继节点设置指向节点n的指针无解，退出成功，退出YYNN深度优先搜索算法流程图深度优先搜索算法流程图节点n可扩展吗？回溯求解路径NY61231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123412384765目标目标 例例 深度优先求解八数码

36、问题深度优先求解八数码问题解路径：解路径：S023462 深度优先搜索的性质深度优先搜索的性质l 一般不能保证找到最优解一般不能保证找到最优解l 最坏情况时，搜索空间等同于穷举最坏情况时，搜索空间等同于穷举l 是一个通用的与问题无关的方法是一个通用的与问题无关的方法63u 深度优先搜索不完备问题深度优先搜索不完备问题 为了解决深度优先搜索不完备问题，避免搜为了解决深度优先搜索不完备问题，避免搜索过程陷入无穷分支的死循环，提出了索过程陷入无穷分支的死循环，提出了有界深度有界深度优先搜索方法优先搜索方法。64 有界深度优先搜索的基本思想是：对深度优有界深度优先搜索的基本思想是：对深度优先搜索方法引

37、入先搜索方法引入搜索深度的界限搜索深度的界限（设（设d dm m），当搜），当搜索深度达到了深度界线，而尚未出现目标节点时，索深度达到了深度界线，而尚未出现目标节点时，就换一个分支进行搜索。就换一个分支进行搜索。65u 有界深度优先搜索算法：有界深度优先搜索算法：1.G:=G0(G0=s),OPEN:=(s),CLOSED:=();2.LOOP:IF OPEN=()THEN EXIT(FAIL);3.n:=FIRST(OPEN);4.IF GOAL(n)THEN EXIT(SUCCESS);5.REMOVE(n,OPEN),ADD(n,CLOSED);6.IF DEPTH(n)Dm GO LO

38、OP;(有界深度限制）有界深度限制）7.EXPAND(n)mi,G:=ADD(mi,G);8.IF 目标在目标在mi中中 THEN EXIT(SUCCESS);9.ADD(mj,OPEN),并标记并标记mj到到n的指针的指针;10.GO LOOP;66开始初始化：把S0放入OPEN表，CLOSED表置空OPEN表为空表？把OPEN表的第1个节点（记为n）移至CLOSED表节点n为目标节点？扩展节点n，将其后继节点放入OPEN表的前端前端，为每个后继节点设置指向节点n的指针，深度加深度加1 1无解，退出成功，退出YYNN有界深度优先搜索算法流程图有界深度优先搜索算法流程图节点n可扩展吗？NY节点

39、节点n n的深度的深度=dm?YN67 有界有界深度优先搜索的性质深度优先搜索的性质l 不能保证找到最优解不能保证找到最优解l 当深度限制不合理时，可能找不到解，可以当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制将算法改为可变深度限制l 是不完备搜索是不完备搜索深度界限深度界限dm的选择很重要！的选择很重要！68对节点对节点n进行扩展时，其后继节点进行扩展时，其后继节点在在OPEN表中的存放位置表中的存放位置宽度优先搜索宽度优先搜索:末端末端深度优先搜索深度优先搜索:前端前端69盲目搜索策略盲目搜索策略完备搜索策略完备搜索策略不完备搜索策略不完备搜索策略宽度优先搜索宽度优先搜索深

40、度优先搜索深度优先搜索有界深度有界深度优先搜索优先搜索70课课 堂堂 练练 习习 题题 对于如图所示的状对于如图所示的状态空间图，请给出宽度态空间图，请给出宽度优先搜索和深度优先搜优先搜索和深度优先搜索的索的OPENOPEN表和表和CLOSEDCLOSED表表的变化情况。的变化情况。（假设（假设N N为目标状态）为目标状态）HABCDEFGIJKLMNOP712.1 2.1 搜索概述搜索概述2.2 2.2 状态空间搜索状态空间搜索2.3 2.3 状态空间盲目搜索状态空间盲目搜索2.4 2.4 状态空间启发式搜索状态空间启发式搜索2.5 2.5 代价树的搜索代价树的搜索2.6 2.6 与与/或树

41、搜索或树搜索2.7 2.7 博弈树的启发式搜索博弈树的启发式搜索72l 定义：定义：利用问题自身特性信息来提高搜索效率的搜利用问题自身特性信息来提高搜索效率的搜索策略，称为索策略，称为启发式搜索启发式搜索或或有信息搜索有信息搜索。可用于指导搜索过程且与具体问题求解有关可用于指导搜索过程且与具体问题求解有关的控制信息称为的控制信息称为启发信息启发信息。73l 启发信息的分类：启发信息的分类：按其用途划分按其用途划分,启发性信息可分为以下启发性信息可分为以下三类三类：(1)用于扩展节点的选择用于扩展节点的选择,即用于决定应先扩展即用于决定应先扩展哪一个节点哪一个节点,以免盲目扩展。以免盲目扩展。(

42、2)用于生成节点的选择用于生成节点的选择,即用于决定应生成哪即用于决定应生成哪些后续节点些后续节点,以免盲目地生成过多无用节点。以免盲目地生成过多无用节点。(3)用于删除节点的选择用于删除节点的选择,即用于决定应删除哪即用于决定应删除哪些无用节点些无用节点,以免造成进一步的时空浪费。以免造成进一步的时空浪费。74l 引入启发信息的目的：引入启发信息的目的：引入启发信息，在保证找到最佳解的情况引入启发信息，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。下，尽可能减少搜索范围，提高搜索效率。l 启发信息的强度启发信息的强度n强：降低搜索工作量，但可能导致找不到最强：降低搜索工作量，但

43、可能导致找不到最优解。优解。n弱：一般导致工作量加大，极限情况下变为弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。盲目搜索，但可能可以找到最优解。75l 估价函数估价函数（教材（教材P60）我们将要介绍的启发式搜索算法中，采用的启我们将要介绍的启发式搜索算法中，采用的启发式信息属于发式信息属于第一种第一种，即决定哪个节点是下一步，即决定哪个节点是下一步要扩展的节点。要扩展的节点。通常构造一个函数来表示节点要扩展的通常构造一个函数来表示节点要扩展的“希望希望”程度，称这种函数为程度，称这种函数为估价函数估价函数。估价函数的任务就是估计待搜索节点的重要程估价函数的任务就是估

44、计待搜索节点的重要程度，给它们排定次序。度，给它们排定次序。76估价函数的一般形式：估价函数的一般形式：f(x)=g(x)+h(x)已经付出的代价已经付出的代价将要付出的代价将要付出的代价启发函数！启发函数！估价函数是针对具体问题构造的，与问题特性密估价函数是针对具体问题构造的，与问题特性密切相关。在构造估价函数时，启发函数切相关。在构造估价函数时，启发函数h(x)的构造尤的构造尤为重要。为重要。代价函数！代价函数！77 最佳优先搜索最佳优先搜索又称为有序搜索或择优搜索，又称为有序搜索或择优搜索，它总是选择最有希望的节点作为下一个要扩展的它总是选择最有希望的节点作为下一个要扩展的节点，而这种最

45、有希望的节点是按估价函数节点，而这种最有希望的节点是按估价函数f(xf(x)的值来挑选的。的值来挑选的。一般估价函数值越小，它的希望程度越大。一般估价函数值越小，它的希望程度越大。最佳优先搜索分为两种：最佳优先搜索分为两种：P 局部择优搜索局部择优搜索P 全局择优搜索全局择优搜索78（1 1）局部择优搜索）局部择优搜索 当对某以节点扩展之后，对其每一个后继节点当对某以节点扩展之后，对其每一个后继节点计算估价函数计算估价函数f(x)的值，并在这些的值，并在这些后继节点的范围后继节点的范围内内，选择一个，选择一个f(x)最小的节点作为下一个要考察的最小的节点作为下一个要考察的节点。节点。它每次只在

46、后继节点的范围内选择下一个要考它每次只在后继节点的范围内选择下一个要考察的节点，范围比较小，所以称为局部择优搜索。察的节点，范围比较小，所以称为局部择优搜索。79开始初始化：把S0放入OPEN表，计算f(S0)OPEN表为空表？把OPEN表的第1个节点（记为n）移至CLOSED表节点n为目标节点？扩展节点n，并对节点节点n n的后继节点的后继节点计算估价函数值，依从小到大排序小到大排序依次放入OPEN表的前端前端无解，退出成功，退出YYNN局部择优搜索算法流程图局部择优搜索算法流程图节点n可扩展吗？NY为每个后继节点设置指向节点n的指针80（2 2）全局择优搜索）全局择优搜索 在确定下一个扩展

47、节点时，在在确定下一个扩展节点时，在OPEN表中全部表中全部节点节点中选择一个估价函数中选择一个估价函数f(x)值最小的节点作为下值最小的节点作为下一个要考察的节点。一个要考察的节点。它每次选择的范围是它每次选择的范围是OPEN表中的全部节点，表中的全部节点，所以称为全局择优搜索。所以称为全局择优搜索。81开始初始化：把S0放入OPEN表，计算f(S0)OPEN表为空表？把OPEN表的第1个节点（记为n）移至CLOSED表节点n为目标节点？扩展节点n，并计算所有后继节点所有后继节点的估价函数值，为每个后继节点设置指向节点n的指针无解，退出成功，退出YYNN全局择优搜索算法流程图全局择优搜索算法

48、流程图节点n可扩展吗？NY把后继节点送入OPEN表,对其中的所有节点按估价函数值从小到大排序从小到大排序82 例例 全局最佳优先求解八数码问题（教材全局最佳优先求解八数码问题（教材P57P57）解路径：解路径：S0S1S2S3Sg83 一种基于估价函数一种基于估价函数f(xf(x)的加权状态图启发式的加权状态图启发式搜索算法。搜索算法。84开始初始化：把S0放入OPEN表，计算f(S0)OPEN表为空表？把OPEN表的第1个节点（记为n）移至CLOSED表节点n为目标节点？扩展节点n，并对n n节点的后继节点节点的后继节点计算估价函数值，为每个后继节点设置指向节点n的指针无解，退出成功，退出Y

49、YNNA算法流程图算法流程图节点n可扩展吗？NY把后继节点送入OPEN表,对其中的所有节点所有节点按估价函数值从小到大排序从小到大排序85A A算法（加权状态图启发式搜索算法）算法（加权状态图启发式搜索算法）1.OPEN:=(s),f(s):=g(s)+h(s);2.LOOP:IF OPEN=()THEN EXIT(FAIL);3.n:=FIRST(OPEN);4.IF GOAL(n)THEN EXIT(SUCCESS);5.REMOVE(n,OPEN),ADD(n,CLOSED);6.EXPAND(n)mi,计算计算f(n,mi):=g(n,mi)+h(mi);86 ADD(mj,OPEN)

50、,标记标记mj到到n的指针；的指针；IF f(n,mk)f(mk)THEN f(mk):=f(n,mk),标记标记mk到到n的指针；的指针；IF f(n,ml)f(ml,)THEN f(ml):=f(n,ml),标记标记ml到到n的指针的指针;ADD(ml,OPEN);7.OPEN中的节点按中的节点按f值从小到大排序；值从小到大排序；8.GO LOOP；87A A算法的例子算法的例子 定义估价函数：定义估价函数：f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的耗散值（节点深度）为从初始节点到当前节点的耗散值（节点深度）h(n)为当前节点为当前节点“不在位不在位”的将牌数的将牌数28