机器人第六章 迷宫比赛与搜索算法

1、机器人第六章 迷宫比赛与搜索算法第1页，共110页，2022年，5月20日，2点19分，星期四本章内容1. 迷宫比赛简介2. 搜索的基本知识3. 状态空间的搜索策略4. 与/或树的搜索策略5. 搜索策略性能的评价第2页，共110页，2022年，5月20日，2点19分，星期四1、迷宫比赛简介比赛内容 制造一个自主控制的机器人，能在迷宫模型中运动，并尽快找到出口离开迷宫。第3页，共110页，2022年，5月20日，2点19分，星期四场地1、迷宫比赛简介起始区终止区（迷宫场地参考图）第4页，共110页，2022年，5月20日，2点19分，星期四场地1、迷宫比赛简介起始区终止区红色色块黄色色块黑色色块

2、（机器人经过相应的色块将被加时间）第5页，共110页，2022年，5月20日，2点19分，星期四简单的行走策略左手规则（障碍在机器人的左边）1、前方没有发现障碍，左边发现障碍，机器人继续前进2、如果机器人前方发现障碍，则原地右转避开障碍3、如果机器人前方和左边都没有发现障碍，左转，寻找左侧障碍1、迷宫比赛简介第6页，共110页，2022年，5月20日，2点19分，星期四简单的行走策略左手规则1、迷宫比赛简介第7页，共110页，2022年，5月20日，2点19分，星期四简单的行走策略右手规则（障碍在机器人的右边）1、前方没有发现障碍，右边发现障碍，机器人继续前进2、如果机器人前方发现障碍，则原地

3、左转避开障碍3、如果机器人前方和右边都没有发现障碍，右转，寻找右侧障碍1、迷宫比赛简介第8页，共110页，2022年，5月20日，2点19分，星期四简单的行走策略1、迷宫比赛简介第9页，共110页，2022年，5月20日，2点19分，星期四简单的行走策略1、迷宫比赛简介怎样找到路径和最佳路径？第10页，共110页，2022年，5月20日，2点19分，星期四2、搜索的基本知识搜索的概念根据问题的实际情况，不断寻找可利用的知识，从而构造一条可行的推理路线，使问题得到解决的过程。第11页，共110页，2022年，5月20日，2点19分，星期四2、搜索的基本知识搜索的使用场合1、在知识不完全，没有成熟

4、的算法可使用。2、理论上有算法，但问题的复杂度高，用计算机求解有时间、空间的局限性。第12页，共110页，2022年，5月20日，2点19分，星期四2、搜索的基本知识搜索的分类盲目搜索启发式搜索第13页，共110页，2022年，5月20日，2点19分，星期四2、1 搜索的分类盲目搜索按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。通用，效率低，不便于复杂问题的求解。是一种不得已而采取的方法第14页，共110页，2022年，5月20日，2点19分，星期四2、1 搜索的分类启发式搜索在搜索过程中，根据问题本身的特性或搜索过程中产生的一些与问题有关的启发信息，指导搜索朝着最有

5、希望的推理方向前进，加速问题的求解过程，并找到最优解。 第15页，共110页，2022年，5月20日，2点19分，星期四2、1 搜索的分类查找第16页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法状态空间表示法用来表示问题及其搜索过程的一种方法。包含三个元素：状态、算符、状态空间。第17页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法状态描述问题求解过程中不同时刻的状况。 Sk = (Sk0, Sk1 , Skn) Skn：代表每个具体的状态。 其中还包括初始状态、目标状态。第18页，共110页，2022年，5月20日，2点19分

6、，星期四2、2 状态空间表示法算符使问题从一种状态变化为另一种状态的操作。状态空间由问题的全部状态及一切可用算符所构成的集合。状态空间图状态空间的图示形式。是一个有向图，节点表示状态，有向边表示算符。第19页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法(举例)二阶汉诺塔问题 要求把A、B两块金片全部移到另一个钢针上。规定每次只能移动一片，并且任何时刻不能出现B在A的上面。第20页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法(举例)二阶汉诺塔问题 用二元组SK=(SA,SB)表示问题的状态, SA表示金盘A所在的杆号, SB表示

7、金盘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)问题的初始状态集合为S=S0,目标状态集合为G=S4,S8。第21页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法(举例)二阶汉诺塔问题9种状态第22页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法(举例)二阶汉诺塔问题算符分别用A(i,j)及B(i,j)表示： A(i,j)表示把A盘从第i号杆移到第j

8、号杆上; 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)第23页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法(举例)二阶汉诺塔问题 由9种可能的状态和12个算符, 二阶汉诺塔问题的状态空间图如下：从(1,1)到(2,2)或(3,3)的任何一条通路都是问题的一个解。第24页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法(举例)猴子和香蕉在一个房间内

9、有一只猴子、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢? 第25页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法(举例)猴子和香蕉用一个四元表列(W,x,Y,z)来表示这个问题的状态， 其中W猴子的水平位置x当猴子在箱子顶上时取x=1；否则取x=0Y箱子的水平位置z当猴子摘到香蕉时取z=1；否则取z=0 。 第26页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法(举例)猴子和香蕉 全部可能的状态有13种, 可表示如下： S0=(a,0,b,0), S1=(a,0,c,0) ,

10、S2=(a,0,a,0), S3=(c,0,b,0) , S4=(c,0,c,0), S5=(c,0,a,0), S6=(b,0,b,0), S7=(b,0,c,0), S8=(b,0,a,0), S9=(a,1,a,0), S10=(b,1,b,0), S11=(c,1,c,0),S12=(c,1,c,1)问题的初始状态集合为S=S0,目标状态集合为G=S12。第27页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法(举例)猴子和香蕉算符用下面的表示： (1) goto(U)猴子走到相邻的水平位置U (2) pushbox(V)猴子把箱子推到相邻的水平位置V (

11、3) climbbox猴子爬上箱顶 (4) godownbox猴子爬下箱子 (5) grasp猴子摘到香蕉 则，算符共有11个，包括猴子移动的4个，箱子移动的4个，猴子爬上箱子1个、爬下箱子1个，猴子摘到香蕉1个。第28页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法(举例)猴子和香蕉 由13种可能的状态和11个算符, 猴子和香蕉问题的状态空间图如下：第29页，共110页，2022年，5月20日，2点19分，星期四2、2 状态空间表示法需要定义状态、算符。问题的求解过程，是一个不断把算符作用于状态的过程。问题的解是从初始状态到目标状态所用算符构成的序列。使用算符

12、最少的解是最优解。对一个状态选取哪个算符操作，取决于搜索策略。不同的搜索策略，操作顺序不一定相同。(重点讨论的问题)第30页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法与/或树表示法用于表示问题及其求解过程的一种方法，通常用于表示比较复杂问题的求解。对于一个复杂问题，直接求解往往比较困难，可以对其进行简化。简化使用的两个操作：分解、等价变换第31页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法分解把一个复杂问题分解为若干个较为容易求解的子问题。每个子问题又可继续分解。不断重复，直到不需要或者不能再分解为止。复合各子问题的解就得到

13、原问题的解。第32页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法分解PP1P2P3与树分解形成“与”树第33页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法等价变换把一个原问题变换为若干个较为容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。第34页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法等价变换等价变换形成“或”树PP1P2P3或树第35页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法分解、等价变换结合使用两种方法结合使用形成“与/或”树第36

14、页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法本原问题不能再分解或变换，而且是直接可解的子问题。端节点没有子节点的节点终止节点本原问题对应的节点Pttt第37页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法可解节点是一个终止节点。是一个”或“节点，并且子节点中至少有一个是可解节点。是一个”与“节点，并且子节点全部是可解节点。不可解节点不属于可解节点的节点。第38页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法解树要判断原问题是否可解，就必须要找出一棵解树。解树：由可解节点构成，并且由这些可解节点能

15、够推出初始节点为可解节点的子树。第39页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法PtttPttt解树第40页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法(举例)三阶汉诺塔问题 要求把A、B、C三块金片全部移到另一个钢针上。规定每次只能移动一片，并且任何时刻不能出现大的金片在小的金片上面。第41页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法(举例)三阶汉诺塔问题可把三阶梵塔问题分解为下面的三个子问题： (1) 把A、B盘从1号杆移到2号杆。 (2) 把C盘从1号杆移到3号杆。 (3) 把A、

16、B盘从2号杆移到3号杆。其中子问题(1)、(3)又分别可分解为三个子问题。 第42页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法(举例)三阶汉诺塔问题用三元组表示问题在任一时刻的状态：(i, j, k)其中，i,j,k分别表示金片A、B、C所在的杆号。第43页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法(举例)三阶汉诺塔问题三阶汉诺塔问题的与/或树 第44页，共110页，2022年，5月20日，2点19分，星期四2、3 与/或树表示法(举例)三阶汉诺塔问题问题的解：(1, 1, 1)(3, 1, 1)(3, 1, 1)(3,

17、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) 第45页，共110页，2022年，5月20日，2点19分，星期四3、 状态空间的搜索策略使用搜索求解问题时的状态关系图。第46页，共110页，2022年，5月20日，2点19分，星期四3、 状态空间的搜索策略基本思想：通过搜索寻找一个操作算符的调用序列，使问题从初始状态变迁到目标状态。变迁过程中的状态序列，或相应的操作算符调用序列称为从初始状态到目标状态的解答路径。搜索空间的压缩程度取决于采用的搜索算法

18、。第47页，共110页，2022年，5月20日，2点19分，星期四3、 状态空间的搜索策略分类第48页，共110页，2022年，5月20日，2点19分，星期四3、1 状态空间的一般搜索过程搜索过程要使用的两个表OPEN表-存放待扩展节点CLOSED表-存放已被扩展节点s-指示初始状态节点G-指示搜索图，其中的节点存放在OPEN表或CLOSED表中第49页，共110页，2022年，5月20日，2点19分，星期四3、1 状态空间的一般搜索过程一般搜索过程 1) G:=s; /算法开始时搜索图只包括初始状态节点；2) OPEN:=(s), CLOSED:=( ); /此时仅有作为待扩展节点，而CLO

19、SED表为空；3) 若OPEN是空表，则搜索失败，结束；/因为此时并未搜索到解答（目标状态），但又无法继续搜索；第50页，共110页，2022年，5月20日，2点19分，星期四3、1 状态空间的一般搜索过程一般搜索过程 4) 取OPEN表的首节点作为当前要被扩展的节点n，同时将节点n移至CLOSED表； 5) 若n是目标状态节点，则搜索成功结束，给出解答路径； 6) 扩展节点n，将节点n的子节点置于子节点集合，并加入搜索图G中；第51页，共110页，2022年，5月20日，2点19分，星期四3、1 状态空间的一般搜索过程7) 标记和修改指针：全新节点未曾在G中出现过（加入OPEN表，并建立从子

20、节点到父节点n的指针）已在OPEN表的节点（比较子节点经由新、老父节点到达初始状态节点s的路径代价，若经由新父节点的代价较小，则修改子节点的指针，指向新父节点）已在CLOSED表的节点（与第2类同样的处理，并把这些子节点从CLOSED表中移出，重新加入OPEN表）第52页，共110页，2022年，5月20日，2点19分，星期四3、1 状态空间的一般搜索过程8) 按某种原则重新排序OPEN表中的节点；9） 返回 3）第53页，共110页，2022年，5月20日，2点19分，星期四3、1 状态空间的一般搜索过程开始把S放入OPEN表OPEN表为空表？是失败否把第一个节点（n）从OPEN移至CLOS

21、ED表n为目标节点？是成功否把n的后继节点放入OPEN表，提供返回节点n的指针修改指针方向重排OPEN表第54页，共110页，2022年，5月20日，2点19分，星期四3、1 状态空间的一般搜索过程二阶汉诺塔的一般搜索过程第55页，共110页，2022年，5月20日，2点19分，星期四3、1 状态空间的一般搜索过程一些说明上述是一个通用过程，各种搜索策略的主要区别是对OPEN表中节点排序的准则不同。如果子节点的算符有多个，则扩展时会生成一组子节点。但不能把该节点的先辈节点作为它当前扩展的子节点。一个新生成的节点，它可能是第一次被生成，也可能是被再次生成的。此时，一般由原始节点到该节点的代价来决

22、定其父节点，代价小的相应节点就作为父节点。(例)第56页，共110页，2022年，5月20日，2点19分，星期四3、1 状态空间的一般搜索过程一些说明在搜索过程中，一旦某个被考察的节点是目标节点，就得到了一个解。该解由从初始节点到该目标节点路径上的算符构成。如果在搜索中一直找不到目标节点，而且OPEN表中不再有可供扩展的节点，则搜索失败。第57页，共110页，2022年，5月20日，2点19分，星期四3、1 状态空间的一般搜索过程修改父节点指针示例 返回第58页，共110页，2022年，5月20日，2点19分，星期四3、2 广度优先搜索基本思想从初始节点开始，逐层对节点进行扩展并考察是否为目标

23、节点，在第n层的节点没有全部扩展前，不对第n+1层的节点进行扩展。可使用一般搜索过程，但OPEN表中的节点进行先进先出排序。第59页，共110页，2022年，5月20日，2点19分，星期四3、2 广度优先搜索开始把S放入OPEN表OPEN表为空表？是失败否把第一个节点（n）从OPEN移至CLOSED表n为目标节点？是成功否把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表第60页，共110页，2022年，5月20日，2点19分，星期四3、2 广度优先搜索八数码问题初始状态目标状态第61页，共110页，2022年，5月20日，2点19分，星期四3、2 广度优先搜索

24、八数码问题第62页，共110页，2022年，5月20日，2点19分，星期四3、2 广度优先搜索解路径：So 3 8 16 Sg 第63页，共110页，2022年，5月20日，2点19分，星期四3、2 广度优先搜索特点只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。广度优先搜索盲目性较大，当目标节点离初始节点较远时将会产生许多无用节点，搜索效率低。第64页，共110页，2022年，5月20日，2点19分，星期四3、3 深度优先搜索基本思想从初始节点开始，一直在节点的子节点中查找目标，如果某节点的子节点没有全部扩展前，不对它的兄弟节点进行扩展。可使用一般搜索过程，但OPEN表中

25、的节点进行先进后出排序。第65页，共110页，2022年，5月20日，2点19分，星期四3、3 深度优先搜索开始把S放入OPEN表OPEN表为空表？是失败否把第一个节点（n）从OPEN移至CLOSED表n为目标节点？是成功否把n的后继节点放入OPEN表的前端，提供返回节点n的指针修改指针方向重排OPEN表第66页，共110页，2022年，5月20日，2点19分，星期四3、3 深度优先搜索八数码问题初始状态目标状态第67页，共110页，2022年，5月20日，2点19分，星期四3、3 深度优先搜索第68页，共110页，2022年，5月20日，2点19分，星期四3、3 深度优先搜索特点搜索一旦进入

26、某个分支，就将从该分支一直往下搜索。求得的解不一定是路径最短的解。如果进入的是无穷分支，则可能得不到解。第69页，共110页，2022年，5月20日，2点19分，星期四3、3 深度优先搜索八数码问题进入无穷分支第70页，共110页，2022年，5月20日，2点19分，星期四3、4 有界深度优先搜索基本思想在深度优先搜索的基础上，引入搜索深度界限(dm)。当搜索深度达到界限，但未出现目标节点时，就换一个分支搜索。第71页，共110页，2022年，5月20日，2点19分，星期四2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 4

27、7 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目标ef第72页，共110页，2022年，5月20日，2点19分，星期四3、4 有界深度优先搜索特点若问题

28、有解，则其路径长度 dm ，则一定可求得解。若其路径长度 dm ，则一定求不出解。dm 较难确定。可进行改进，使dm在搜索过程中能够动态变化。第73页，共110页，2022年，5月20日，2点19分，星期四3、5 代价树边上标有代价的树，称为代价树。代价一般指使用某个算符使从一个状态变为另一个状态的付出，例如时间、费用等。第74页，共110页，2022年，5月20日，2点19分，星期四3、5 代价树代价的计算g(x)表示从初始节点So到节点x的代价用c(xi,xj)表示父节点xi到子节点xj的代价,即边(xi,xj)的代价。从而有 g(xj)g(xi)c(xi, xj) 而 g(So)0 第7

29、5页，共110页，2022年，5月20日，2点19分，星期四3、5 代价树的广度优先搜索基本思想在广度优先搜索的基础上，每次都从OPEN表中取出代价最小的节点放入CLOSED表。第76页，共110页，2022年，5月20日，2点19分，星期四3、5 代价树的广度优先搜索旅行问题设A城是出发地,E城是目的地, 边上的数字代表两城之间的交通费。试求从A到E最小费用的旅行路线。 ABCDE432345交通图第77页，共110页，2022年，5月20日，2点19分，星期四3、5 代价树的广度优先搜索旅行问题最佳解路径：A C1 D1 E2 最小费用路线：A C D E第78页，共110页，2022年，

30、5月20日，2点19分，星期四3、5 代价树的深度优先搜索基本思想在深度优先搜索的基础上，每次都从刚扩展的子节点中取出代价最小的节点放入CLOSED表。第79页，共110页，2022年，5月20日，2点19分，星期四3、5 代价树的深度优先搜索旅行问题最佳解路径：A C1 D1 E2 最小费用路线：A C D E第80页，共110页，2022年，5月20日，2点19分，星期四3、6 启发式搜索搜索过程中用到问题自身的某些特征信息，指导搜索朝着最有希望的方向进行。用于指导搜索过程的信息称为启发信息。启发信息的强度强，降低搜索工作量，可能导致找不到最优解弱，极限情况下变为盲目搜索第81页，共110

31、页，2022年，5月20日，2点19分，星期四3、6 启发式搜索基本思想定义一个估价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来进行扩展。 f(x)=g(x)+h(x)g(x)是从初始节点到节点x已经实际付出的代价h(x)是从节点x到目标节点的最优路径的估计代价（启发信息）第82页，共110页，2022年，5月20日，2点19分，星期四3、6 启发式搜索例子设有如下结构的移动将牌游戏：DDDWWWE其中，E代表该位置为空。该游戏规则：1、当一个牌移入相邻的空位置时，费用为一个单位。2、一个牌至多可跳过两个牌进入空位置，其费用等于跳过的牌数加1。要求把所有的都移至W的右边。第83页

32、，共110页，2022年，5月20日，2点19分，星期四3、6 启发式搜索例子解：根据要求可知，W左边的越少越接近目标，因此可用W左边的个数作为h(x),即h(x)=3(每个W左边个数的总和)这里乘以系数3是为了扩大h(x)在f(x)中的比重。第84页，共110页，2022年，5月20日，2点19分，星期四3、6、1 局部择优搜索基本思想 当一个节点x被扩展以后，按f(x)对x的每个子节点计算估计值，并从扩展的子节点中选择估计值最小的节点作为下一个考察对象。 深度优先搜索、代价树的深度优先搜索以及局部择优搜索都是以子节点作为考察范围的。但是前二者可以看作局部择优搜索的特例。第85页，共110页

33、，2022年，5月20日，2点19分，星期四3、6、2 全局择优搜索基本思想 每次总是从OPEN表的全体节点中选取一个估计值最小的节点。 广度优先搜索、代价树的广度优先搜索以及全局择优搜索都是以当前所有节点作为考察范围的。但是前二者可以看作全局择优搜索的特例。第86页，共110页，2022年，5月20日，2点19分，星期四3、6、2 全局择优搜索例子 用全局择优搜索求八数码问题。2 8 31 6 47 51 2 3457 6 81 2 38 47 6 51 2 3457 6 8g(x)表示节点x的深度h(x)表示节点x的格局与目标节点的格局不同的牌数。第87页，共110页，2022年，5月20

34、日，2点19分，星期四2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)123456目标第88页，共110页，2022年，5月20日，2点19分，星期四4、 与

35、/或树的搜索策略基本思想用分解或等价变换算符通过搜索生成与或树，最终应能标识出初始节点（对应于原问题）为可解节点（原问题有解）或不可解节点（原问题无解）。与/或树搜索的目标是寻找解树，从而求得原问题的解。第89页，共110页，2022年，5月20日，2点19分，星期四4、1 与/或树的一般搜索过程可解标识过程：由可解子节点来确定其父节点、祖父节点等为可解节点的过程。不可解标识过程：由不可解子节点来确定其父节点、祖父节点等为不可解节点的过程。与/或树的搜索过程将反复使用上述两个过程，直到初始节点被标示为可解或不可解节点为止。搜索形成的节点和指针结构称为搜索树。第90页，共110页，2022年，5

36、月20日，2点19分，星期四4、1 与/或树的一般搜索过程一般过程(1)把原始问题作为初始节点S0，并把它作为当前节点。(2)应用分解或等价变换算符对当前节点进行扩充。(3)为每个子节点设置指向父节点的指针。(4)选择合适的子节点作为当前节点，反复执行第（2）、（3）步。在此其间要多次调用可解标识过程和不可解标识过程，直到初始节点被标识为可解或不可解节点为止。第91页，共110页，2022年，5月20日，2点19分，星期四4、1 与/或树的一般搜索过程搜索过程中的注意点某个节点不能扩展，也不是终止节点，则该节点是不可解节点。如果已经确定某个节点为可解节点，则其不可解的子节点就不再有用，可从搜索

37、树中删去。如果已经确定某个节点为不可解节点，则其全部子节点就不再有用，可从搜索树中删去；但当前这个不可解节点还不能删去，以后它还要用来判断其先辈节点的可解性。第92页，共110页，2022年，5月20日，2点19分，星期四4、2 与/或树的广度优先搜索基本思想跟状态空间的广度优先搜索类似，但在搜索过程中要多次调用可解标示过程和不可解标示过程。第93页，共110页，2022年，5月20日，2点19分，星期四开始把S放入OPEN表OPEN表为空表？是失败否把第一个节点（n）从OPEN移至CLOSED表节点n可扩展？是成功否标示节点n为不可解节点，应用不可解标示过程从OPEN表中删除具有不可解先辈的

38、节点S为不可解节点？是失败否将节点n的子节点放入OPEN表，并为子节点配置指针子节点有终止节点？否标示节点n为可解节点，应用可解标示过程是S为可解节点？是从OPEN表中删除具有可解先辈的节点否第94页，共110页，2022年，5月20日，2点19分，星期四4、2 与/或树的广度优先搜索例子设有如图所示的与/或树，节点按图中所标注的顺序进行扩展。其中，t1,t2,t3,t4为终止节点，A和B为不可解节点。12345ABt1t2t3t4第95页，共110页，2022年，5月20日，2点19分，星期四4、2 与/或树的广度优先搜索12345ABt1t2t3t412345ABt1t2t3t4扩展顺序为

39、：1，2，3，4，5第96页，共110页，2022年，5月20日，2点19分，星期四4、3 与/或树的深度优先搜索基本思想跟状态空间的深度优先搜索类似，但在搜索过程中要多次调用可解标示过程和不可解标示过程。第97页，共110页，2022年，5月20日，2点19分，星期四4、3 与/或树的深度优先搜索12345ABt1t2t3t412345ABt1t2t3t4扩展顺序为：1 ，2，4 ，3，5第98页，共110页，2022年，5月20日，2点19分，星期四4、4 与/或树的有序搜索基本思想是用来求代价最小的解树的一种搜索方法。在确定下一个要扩展的节点时，先计算需要付出的代价，选择代价最小的节点进

40、行扩展。第99页，共110页，2022年，5月20日，2点19分，星期四4、4 与/或树的有序搜索解树的代价C(x,y)表示节点x到其子节点y的代价。(1) 如果x是终止节点，h(x)=0(2)如果x是“或”节点，h(x)=(3)如果x是“与”节点， h(x)= (4)如果x不可扩展，且又不是终止节点，h(x)=第100页，共110页，2022年，5月20日，2点19分，星期四4、4 与/或树的有序搜索解树的代价(例子)如图是一棵与/或解树，求该树的代价。h(A)= 11， h(S0)=13h(B)= 6， h(S0)=8S0ABFt2Ct3t4t5DEt1226521212113G第101页，共110页，2022年，5月20日，2点19分，星期四4、4 与/或树的有序搜索解树的代价当计算某一节点x的代价h(x)时，都要求已知它的子节点yi代价，但搜索是从上到下进行的，因此一般使用启发函数估算yi 。当yi