华中科技大学人工智能 第三章一般搜索原理

1、12021-11-5第三章第三章 一般搜索原理一般搜索原理第三章 一般搜索原理 22021-11-5搜索技术搜索技术l搜索搜索是人工智能中进行问题求解的一大类方法l根据是否使用启发式信息可分为 ：1，盲目搜索；2，启发式搜索；l根据问题的表示方式分为：1，状态空间搜索；2，与或树搜索。 l例如例如：用状态空间法来求解问题时，采用的是状态空间搜索；用问题归约方法来求解问题时，采用的是与或树搜索。 第三章 一般搜索原理 3.1概述32021-11-5搜索的特点搜索的特点l和通常的搜索空间不同，人工智能中大多数问题的状态空间在问题求解之前不是全部知道的。l所以，人工智能中的搜索可以分成两个阶段：状态

2、空间的生成阶段和在该状态空间中对所求解问题状态的搜索。l由于一个问题的整个空间可能会非常的大，在搜索之前生成整个空间会占用太大的存储空间。为此，状态空间一般是逐渐扩展的l“目标”状态是在每次扩展的时候进行搜索的。第三章 一般搜索原理 3.1概述42021-11-53.2 盲目盲目搜索搜索第三章 一般搜索原理 3.2 盲目搜索52021-11-5盲目搜索盲目搜索l 盲目搜索盲目搜索是按预定的控制策赂进行搜索，没有任何关于问题本身的信息，在搜索过程中获得的中间信息并不改变控制策略。由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，因此这种搜索具有盲目性，效率不高，不便于复杂问题的求解。第

3、三章 一般搜索原理 3.2 盲目搜索62021-11-5盲目搜索分类盲目搜索分类l搜索策略可分为三大类搜索策略可分为三大类不可撤回方式、回朔方式、图搜索方式l不可撤回方式不可撤回方式：每一次搜索时，利用局部知识根据最优评价，选出下一状态，选定后不能撤回，只能继续l回朔方式回朔方式：在搜索过程中，有时会发现所选的路径不适合找到目标，这时允许退回去另选一条路径。l图搜索方式：图搜索方式： 将所有应用过的操作和它们产生的状态描述都以图的形式记录下来。由于当前可继续往下搜索的状态不只一个，因此可以从其中任一个状态往下搜索。l图搜索方式与回溯方式的不同之处在于，回溯方式不记亿那些图搜索方式与回溯方式的不

4、同之处在于，回溯方式不记亿那些试探失败的操作和它们产生的状态描述，只记忆当前正在搜索试探失败的操作和它们产生的状态描述，只记忆当前正在搜索的路径。图搜索方式则保存所有试探过的路径，因而可以在任的路径。图搜索方式则保存所有试探过的路径，因而可以在任何一条路径上继续搜索何一条路径上继续搜索第三章 一般搜索原理 3.2 盲目搜索72021-11-5图搜索方式与回溯方式的不同图搜索方式与回溯方式的不同l回溯方式不记忆那些试探失败的操作和它们产生的状态描述，只记忆当前正在搜索的路径。l图搜索方式则保存所有试探过的路径，因而可以在任何一条路径上继续搜索第三章 一般搜索原理 3.2 盲目搜索82021-11

5、-5不可撤回搜索策略不可撤回搜索策略l 不可撤回方式的控制策略是，选择一条可应用的操作作用于当前状态，不论后果如何都接着做下去。这个方法类似于高等数学中求函数极值的爬山法。l在爬山法中，我们从任一点出发，在该点的最大梯度方向前进一步，得到一个新的点，再在新点的最大梯度方向上前进一步，一直到梯度为0为止，这个点就是函数的极大值点。如果函数只有一个极大值点则这个点就是该函数的最大值点。第三章 一般搜索原理 3.2 盲目搜索92021-11-5不可撤回搜索的实现不可撤回搜索的实现l不可撤回搜索的实现是将状态描述定义成一个实数值的爬山函数。l控制策略就利用这个爬山函数来选择一个可应用的操作，施行该操作

6、的结果应使爬山函数的值得到最大限度的增加。第三章 一般搜索原理 3.2 盲目搜索102021-11-5不可撤回搜索举例不可撤回搜索举例(一一)l选择八数码问题l我们选取“不在位”的数字个数的负值作为爬山函数l 八数码游戏的操作可描述为下面的4条产生式规则l (1) if空格不在最上一行then空格上移l (2) if空格不在最下一行then生格下移l (3) if空格不在最左一列then空格左移l (4) if空格不在最右一列then空格有移2 8 31 6 47 51 2 38 47 6 5目标状态初始状态第三章 一般搜索原理 3.2 盲目搜索112021-11-5不可撤回搜索举例不可撤回搜

7、索举例(二二)l从初始状态出发，应用第一条规则，空格上移可获得爬山函数的最大增加、因此控 制策略选择第一条规则作为当前的操作。l在没有操作能够增加爬山函数的值时可任选一个不减小函数值的操作，如果不存在这样的操作，则过程停止。2 8 31 6 47 52 31 8 47 6 52 8 31 47 6 51 2 38 47 6 5 2 31 8 47 6 5-3-3-4-2-101 2 3 8 47 6 5目标状态爬山函数值第三章 一般搜索原理 3.2 盲目搜索122021-11-5不可撤回搜索举例不可撤回搜索举例(三三)l对于上例，采用不可撤回策略可以很快得到问题的解。l但一般来讲，如果爬山函数

8、有多个局部极大值存在，该策略可能会引导到局部极大值点，而达不到目标状态。l例如当八数码问题的初始状态和目标状态分别如下时，任意一个可应用的操作都会降低爬山函数的值，因此，得不到目标：1 2 3 7 48 6 51 2 57 48 6 3目标初始状态第三章 一般搜索原理 3.2 盲目搜索132021-11-5回溯搜索策略回溯搜索策略l回溯策略是一种试探性方式。在选择一个操作时要建立一个回溯点。l在搜索过程中，如果遇到了困难，则要返回到最近的一个回溯点，换一个操作继续进行搜索。第三章 一般搜索原理 3.2 盲目搜索142021-11-5回溯搜索策略举例回溯搜索策略举例l例：皇后问题QQQQ第三章

9、一般搜索原理 3.2 盲目搜索152021-11-5( )皇后问题搜索过程（一）皇后问题搜索过程（一）第三章 一般搜索原理 3.2 盲目搜索162021-11-5Q( )(1,1)皇后问题搜索过程（二）皇后问题搜索过程（二）第三章 一般搜索原理 3.2 盲目搜索172021-11-5QQ( )(1,1)(1,1) (2,3)皇后问题搜索过程（三）皇后问题搜索过程（三）第三章 一般搜索原理 3.2 盲目搜索182021-11-5Q( )(1,1)(1,1) (2,3)皇后问题搜索过程（四）皇后问题搜索过程（四）第三章 一般搜索原理 3.2 盲目搜索192021-11-5QQ( )(1,1)(1,

10、1) (2,3)(1,1) (2,4)皇后问题搜索过程（五）皇后问题搜索过程（五）第三章 一般搜索原理 3.2 盲目搜索202021-11-5QQQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后问题搜索过程（六）皇后问题搜索过程（六）第三章 一般搜索原理 3.2 盲目搜索212021-11-5QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后问题搜索过程（七）皇后问题搜索过程（七）第三章 一般搜索原理 3.2 盲目搜索222021-11-5Q( )(1,1)(1,1) (2,3)(1,1)

11、(2,4)(1,1) (2,4) (3.2)皇后问题搜索过程（八）皇后问题搜索过程（八）第三章 一般搜索原理 3.2 盲目搜索232021-11-5( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后问题搜索过程（九）皇后问题搜索过程（九）第三章 一般搜索原理 3.2 盲目搜索242021-11-5Q( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)皇后问题搜索过程（十）皇后问题搜索过程（十）第三章 一般搜索原理 3.2 盲目搜索252021-11-5QQ( )(1,1)(1,1) (2,3)(

12、1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)皇后问题搜索过程（十一）皇后问题搜索过程（十一）第三章 一般搜索原理 3.2 盲目搜索262021-11-5QQQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)(1,2) (2,4) (3,1)皇后问题搜索过程（十二）皇后问题搜索过程（十二）第三章 一般搜索原理 3.2 盲目搜索272021-11-5QQQQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4

13、)(1,2) (2,4) (3,1)(1,2) (2,4) (3,1) (4,3)皇后问题搜索过程（十三）皇后问题搜索过程（十三）第三章 一般搜索原理 3.2 盲目搜索282021-11-5回溯搜索算法回溯搜索算法l回溯搜索可以用递归的方法来实现l下面的算法是一个用递归实现的算法：BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。第三章 一般搜索原理 3.2 盲目搜索292021-11-5回溯搜索算法（一）回溯搜索算法（一）BACKTRACK(DATA)1, IF TERM(DATA) RETURN NIL;2, IF DEA

14、DEND(DATA) RETURN FAIL;3, RULES:=APPRULES(DATA);TERM: 找目标DEADEND: 状态不合法,无法继续搜索APPRULES: 取可应用规则集第三章 一般搜索原理 3.2 盲目搜索302021-11-5回溯搜索算法（二）回溯搜索算法（二）4, LOOP: IF NULL(RULES) RETURN FAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R, DATA);8, PATH:=BACKTRACK(RDATA);9, IF PATH=FAIL GO LOOP;10, RET

15、URN CONS(R, PATH);TAIL: 删除头条规则GEN: 调用规则作用于当前状态CONS: 获取解路径规则表第三章 一般搜索原理 3.2 盲目搜索312021-11-5存在问题及解决办法存在问题及解决办法l问题：深度问题:如果深度太深死循环问题: 如果状态出现重复l解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径第三章 一般搜索原理 3.2 盲目搜索322021-11-5增加约束后的回溯搜索算法增加约束后的回溯搜索算法BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。第

16、三章 一般搜索原理 3.2 盲目搜索332021-11-5增加约束后的回溯搜索算法增加约束后的回溯搜索算法(一一)1, DATA:=FIRST(DATALIST)2, IF MENBER(DATA, TAIL(DATALIST) RETURN FAIL;3, IF TERM(DATA) RETURN NIL;4, IF DEADEND(DATA) RETURN FAIL;5, IF LENGTH(DATALIST)BOUND RETURN FAIL;第三章 一般搜索原理 3.2 盲目搜索342021-11-5增加约束后的回溯搜索算法增加约束后的回溯搜索算法(二二)6, RULES:=APPRU

17、LES(DATA);7, LOOP: IF NULL(RULES) RETURN FAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);第三章 一般搜索原理 3.2 盲目搜索352021-11-5增加约束后的回溯搜索算法增加约束后的回溯搜索算法(三三)10,RDATA:=GEN(R, DATA);11,RDATALIST:=CONS(RDATA, DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R, PATH);第三章 一般搜索原理 3.2 盲目搜索36

18、2021-11-5图搜索策略图搜索策略l图搜索策略就是在图中寻找从起始点到目标点的路径的方法l图搜索的一般过程是构造搜索图的过程。令搜索图开始时只有起始点S0，然后逐步扩展节点，直到将目标点扩展到搜索图里为止。扩展的过程就是搜索的过程l扩展节点的方法不同，就意味着搜索的方法不同，也就是搜索的路径不同。第三章 一般搜索原理 3.2 盲目搜索372021-11-5图搜索包括图搜索包括宽度优先搜索宽度优先搜索：搜索以接近起始节点的程度依次扩展节点，在对下一层搜索前，必须搜索完本层的所有节点。深度优先搜索深度优先搜索：搜索首先扩展最新产生的节点。等代价搜索等代价搜索：搜索沿最小代价节点进行扩展。第三章

19、 一般搜索原理 3.2 盲目搜索382021-11-5图搜索的一般过程图搜索的一般过程成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向把S放入OPEN表重排OPEN表是否否OPEN为空？n为目标节点？失败开始第三章 一般搜索原理 3.2 盲目搜索392021-11-5图搜索过程说明图搜索过程说明l我们在搜索过程中用到了OPEN表和CLOSED表两个数据结构lOPEN表中的节点都是搜索树的端节点，即至今尚未被选作为扩展的节点lCLOSED表中的节点或者是已被扩展而不能生成后继节点的那些端节点，或者是搜索树的非端节点l重排O

20、PEN表，实际上就是在选择搜索顺序，也就是扩展的节点的顺序。第三章 一般搜索原理 3.2 盲目搜索402021-11-5节点类型说明节点类型说明.mj.mk.ml扩展的节点OPEN表没有的部分扩展的节点在已在close表中的部分扩展的节点已在OPEN表中的部分选定的扩展节点第三章 一般搜索原理 3.2 盲目搜索412021-11-5图搜索过程的图示（一）图搜索过程的图示（一）现要扩展它第三章 一般搜索原理 3.2 盲目搜索422021-11-5图搜索过程的图示（二）图搜索过程的图示（二）修改父子关系现要扩展它第三章 一般搜索原理 3.2 盲目搜索432021-11-5图搜索过程的图示（三）图搜

21、索过程的图示（三）修改父子关系修改父子关系第三章 一般搜索原理 3.2 盲目搜索442021-11-5宽度优先搜索宽度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供返回节点n的指针把S放入OPEN表是否否OPEN为空？是否有任何后继节点为目标节点？失败开始第三章 一般搜索原理 3.2 盲目搜索452021-11-5目标2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31

22、 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 51256731 2 3 8 47 6 582 3 41 8 7 6 54八数码难题的宽度优先搜索树八数码难题的宽度优先搜索树按上下左右序走步第三章 一般搜索原理 3.2 盲目搜索462021-11-5宽度优先搜索的性质宽度优先搜索的性质l当问题有解时，一定能找到解l当问题为单位代价值，且问题有解时，一定能找到最优解l方法与问题无关，具有通用性l效率较低第三章 一般搜索原理 3.2 盲目搜索472021-11-5深度优

23、先搜索深度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的前端，提供返回节点n的指针把S放入OPEN表是否否OPEN为空？节点n的深度是否等于深度界限？失败开始是否有任何后继节点为目标节点？是否S是否为目标节点？否成功第三章 一般搜索原理 3.2 盲目搜索482021-11-52 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 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

24、 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 5123456789abcd1 2 3 8 47 6 5目标。八数码难题的深度优先搜索树八数码难题的深度优先搜索树第三章 一般搜索原理 3.2 盲目搜索492021-11-5深度优先搜索的性质深度优先搜索的性质l一般不能保证找到最优解l当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制l最坏情况时，搜索空间等同于穷举l是一个通用的与问题无关的方法第三章 一般搜索原理 3.2 盲目搜索502021-11-5等代价搜索等代价搜索l搜索树的每条弧线上可能有代价值l有些

25、问题要求搜索代价最小的解l当搜索树的每条弧线上的代价值都为1时，宽度优先搜索可以看成是最小代价搜索l推广宽度优先搜索，以获得最小代价的搜索方法称为等代价搜索第三章 一般搜索原理 3.2 盲目搜索512021-11-5等代价搜索等代价搜索成功是把具有最小g(i)值的节点i从OPEN表移至CLOSED表计算其后继节点j的g(j)值。把其后继节点放入OPEN表把S放入OPEN表否否OPEN为空？失败开始 i是否为目标节点？是S是否为目标节点？否成功是令g(s)=0第三章 一般搜索原理 3.2 盲目搜索522021-11-53.3 启发式搜索启发式搜索第三章 一般搜索原理 3.3 启发式搜索53202

26、1-11-5为何引入启发式信息为何引入启发式信息l盲目搜索的效率低，耗费过多的计算时间和空间，容易产生组合爆炸。l利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。l对搜索产生帮助的信息称为启发信息第三章 一般搜索原理 3.3 启发式搜索542021-11-5启发式信息对搜索方法的影响启发式信息对搜索方法的影响l启发信息的多少用启发信息强度来表示l不同的启发信息对搜索方法带来不同的影响：强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解第三章 一般搜索原理 3.3 启发式搜索552021-11-5启发式搜索类型启发式搜索类型

27、l启发信息按用途可分为3类：用于决定要扩展哪一个节点（这个节点称为最有希望最有希望节点节点），以免像在宽度优先或深度优先搜索中那样盲目地扩展在扩展一个节点的过程中，用于决定要生成哪些其后继节点，以免盲目地生成所有节点。用于决定哪些节点应从搜索树中抛弃或修剪。l用来估算节点希望程度的方法为估价函数l体现问题自身的启发性信息的函数称为启发函数第三章 一般搜索原理 3.3 启发式搜索562021-11-5对启发式搜索的认识对启发式搜索的认识l有些启发信息能够大大减少搜索工作量，但不能保证能够得到最小代价路径l我们往往希望获得路径代价和求该路径所需的搜索代价的综合为最小l由于计算综合代价很困难，因此，

28、比较两种方法的优劣，依赖使用的经验l用来估算节点希望程度的方法为估价函数l使用估价函数实际是对OPEN表进行排序，再按顺序扩展节点，进行搜索第三章 一般搜索原理 3.3 启发式搜索572021-11-5有序搜索有序搜索l若按估价函数的增序对OPEN表进行排序，这种搜索方法叫做有序搜索或最佳优先搜索l有序搜索的有效性取决于估价函数的选择，否则有可能失去一个最好的解甚至全部的解l如果没有合适的选择，可考虑两个方面的内容：一个是时间和空间的折中保证有一个解第三章 一般搜索原理 3.3 启发式搜索582021-11-5有序搜索框图有序搜索框图成功是选取f值最小的节点i，从OPEN表移至CLOSED表扩

29、展i，计算后继节点j的f(j)，对OPEN表重排序，调整亲子关系把S放入OPEN表，计算f(s)是否否OPEN为空？i是目标节点？失败开始第三章 一般搜索原理 3.3 启发式搜索592021-11-5估价函数：f(n)=d(n)+w(n) 其中， d(n):节点的深度 w(n):节点放错棋子数目八数码难题的有序搜索树八数码难题的有序搜索树2 8 31 6 47 52 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 51 2 38 47 6 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4

30、6 5 8 32 1 47 6 51 2 37 8 4 6 5 2 31 8 47 6 554646677567551 2 3 8 47 6 5目标5估价函数值第三章 一般搜索原理 3.3 启发式搜索602021-11-5A算法算法lA算法是一种有序搜索的启发式搜索算法。l估价函数的形式： f(n) = g(n) + h(n)g(n)是从初始节点S0到节点n的实际代价h(n)是从节点n到目标节点Sg的最小路径代价h*(n)的启发式估计lh(n)称为启发函数：第三章 一般搜索原理 3.3 启发式搜索612021-11-5A算法流程算法流程1, OPEN:=(s), f(s):=g(s)+h(s)

31、;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);第三章 一般搜索原理 3.3 启发式搜索622021-11-5A算法流程（续）算法流程（续）ADD(mj, OPEN), 标记mj到n的指针；IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 标记mk到n的指针；IF f(n, ml)f

32、(ml,) THEN f(ml):=f(n, ml),标记ml到n的指针, ADD(ml, OPEN);7, OPEN中的节点按f值从小到大排序；8, GO LOOP；第三章 一般搜索原理 3.3 启发式搜索632021-11-5最佳图搜索算法最佳图搜索算法A* *（A* *算法）算法）l在A算法中，如果对于任意点n满足条件：h(n)h*(n)则A算法称为A*算法。l如果存在从初始节点S0目标节点Sg的最小路径， A*算法就一定能搜索到第三章 一般搜索原理 3.3 启发式搜索642021-11-5A*算法算法估价函数举例估价函数举例l在问题求解过程中，不可能明确知道h*(n) ，可根据经验估计

33、下界范围条件l例如，8数码问题如取h(n) = “不在位”的牌数，可估计出至少要移动h(n) 步，才能达到目标，因此，有h(n) h*(n) 如取h (n) = 每个牌与目标位置的距离和，同样可估计出至少要移动h(n) 步，才能达到目标，因此，有h(n) h*(n) 2 8 31 6 47 51 2 38 47 6 5第三章 一般搜索原理 3.3 启发式搜索652021-11-53.4 与或树搜索与或树搜索第三章 一般搜索原理 3.4 与或树搜索662021-11-5与或树搜索与或树搜索l 与或树的搜索是实现用与或树表示的问题的求解。l与或树的搜索过程将形成一棵与或树，这种由搜索过程形成的与或

34、树称为搜索树。l与或树的搜索过程实际上是一个不断寻找解树的过程。第三章 一般搜索原理 3.4 与或树搜索672021-11-5几个概念几个概念l由可解节点构成，并且由这些可解节点可以推出初始节点为可解节点的子树称为解树，解树中一定包含初始节点。l没有子节点的节点称为端节点。l本原问题所对应的节点称为终止节点。l可解问题所对应的节点称为可解节点。反之为不可解节点。l终止节点是可解节点。l子节点都是可解节点的与节点是可解节点l至少一个子节点是可解节点的或节点是可解节点。第三章 一般搜索原理 3.4 与或树搜索682021-11-5与或树搜索的一般过程与或树搜索的一般过程l(1)把原始问题作为初始节

35、点S0，并把它作为当前节点；l(2)应用分解或等价变换操作对当前节点进行扩展l(3)为每个子节点设置指向父节点的指针l(4)选择合适的子节点作为当前节点，反复执行第(2)步和第(3)步，多次调用标记过程，直到初始节点被标记。l如果某个节点被标记为可解节点，则其不可解的后继节点就可从搜索树中删去；如果被标记为不可解节点则其后继节点也可从搜索树中删去。第三章 一般搜索原理 3.4 与或树搜索692021-11-5宽度优先搜索宽度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表可扩展处理把S放入OPEN表是否否OPEN为空？节点(n)是否有可扩展？失败开始不可扩展处理S标为可解节点？是

36、否S标为不可解节点？是否失败第三章 一般搜索原理 3.4 与或树搜索702021-11-5宽度优先搜索（续）宽度优先搜索（续）可扩展处理把节点(n)标记为不可解节点把n的后继节点放入OPEN表的末端，提供返回节点n的指针不可扩展处理若n的后继节点中有终节点，则标记其为可解节点从OPEN表中删去具有可解先辈的节点调用可解标记过程，标记其先辈节点从OPEN表中删去具有不可解先辈的节点调用不可解标记过程，标记其先辈节点返回返回第三章 一般搜索原理 3.4 与或树搜索712021-11-5宽度优先搜索举例（一）宽度优先搜索举例（一）l t1,t2,t3为终节点lABC为端节点l搜索过程：扩展1号生成2

37、、3号节点，都是非终节点扩展2号生成A、4号节点，都是非终节点 扩展3号生成t1、5号节点，t1是终节点，标记为可解节点，调用可解标记过程，由于t1的父节点是与节点，不能确定其父节点是可解t2A13542BCt1t3第三章 一般搜索原理 3.4 与或树搜索722021-11-5宽度优先搜索举例（二）宽度优先搜索举例（二）A是端节点，不可扩展，调用不可解标记过程，由于A的父节点是或节点，不能确定其父节点是不可解扩展4号生成t2、B节点，t2是终节点，标记为可解节点，调用可解标记过程，由于t2的父节点是或节点，标节点4为可解，继续向上，标节点2为可解，但无法确定标节点1扩展5号生成t3、C节点，t

38、3是终节点，标记为可解节点，调用可解标记过程，由于t3的父节点是或节点，标节点5为可解，继续向上，标节点3为可解，最后可确定节点1为可解t2A13542BCt1t3第三章 一般搜索原理 3.4 与或树搜索732021-11-5深度优先搜索深度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表可扩展处理把S放入OPEN表是否否OPEN为空？节点(n)是否有可扩展？失败开始不可扩展处理S标为可解节点？是否S标为不可解节点？是否失败节点(n)深度=d？是否第三章 一般搜索原理 3.4 与或树搜索742021-11-5深度优先搜索（续）深度优先搜索（续）可扩展处理把节点(n)标记为不可解节

39、点把n的后继节点放入OPEN表的前端，提供返回节点n的指针不可扩展处理若n的后继节点中有终节点，则标记其为可解节点从OPEN表中删去具有可解先辈的节点调用可解标记过程，标记其先辈节点从OPEN表中删去具有不可解先辈的节点调用不可解标记过程，标记其先辈节点返回返回第三章 一般搜索原理 3.4 与或树搜索752021-11-53.5 与或树的启发式搜索与或树的启发式搜索第三章 一般搜索原理 3.5 与或树的启发式搜索762021-11-5与或树的启发式搜索与或树的启发式搜索l 与或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。l对搜索的每一步，算法都试图找到一个最有希望

40、成为最优解树的子树。l最优解树是指代价最小的那棵解树。第三章 一般搜索原理 3.5 与或树的启发式搜索772021-11-5解树的代价解树的代价l设n为节点，n1，n2，nk为其子节点， h(n)为节点n的代价， c(n，ni)为节点n到其子节点ni的边代价l若n为终节点，则h(n)0。l若n为或节点，则h(n)min(c(n，ni)+h(ni)l若n为与节点，则n的代价可用和代价法或最大代价法。和代价法：h(n)(c(n，ni)+h(ni)最大代价法：h(n)maxc(n，ni)+h(ni) l若n是端节点，但非终节点，则n不可扩展，h(n)。l解树的代价，为根节点的代价。第三章 一般搜索原

41、理 3.5 与或树的启发式搜索782021-11-5解树的代价举例解树的代价举例图中与或树包括两棵解树左边的解树由S、A、t1、C及t3组成右边的解树由S、B、t2、D及t4组成。t1、t2、t3、t4为终节点E 、 F是端节点左边的解树:按和代价：h(S)2+4+6+214按最大代价：h(S)2+6+210右边的解树:按和代价：h(S)1+5+3+211按最大代价：h(S)1+5+28可见，右边的解树是最优解树。t2SBDCAEFt1t3t464222351第三章 一般搜索原理 3.5 与或树的启发式搜索792021-11-5希望解树希望解树l 为了找到最优解树，搜索过程的任何时刻都应该选择

42、那些最有希望成为最优解树一部分的节点进行扩展l由于这些节点及其父节点所构成的与或树最有可能成为最优解树的一部分，因此称为希望解树，简称为希望树。l需要注意，希望解树是会随搜索过程而不断变化的。l希望树定义：初始节点S在希望树T中若n为具有子节点n1，n2，nk的或节点，其子节点ni在希望树T中的充分必要条件： h(ni)min(c(n，nt)+h(nt)若n为与节点，其子节点都在希望树T。第三章 一般搜索原理 3.5 与或树的启发式搜索802021-11-5与或树的与或树的启发式启发式搜索过程搜索过程成功是计算希望树T可扩展处理把S放入OPEN表，计算h(S)是否否节点(n)是否可扩展？开始终

43、节点处理S标为可解节点？是否S标为不可解节点？是否失败把OPEN表中第一个属于T的节点(n)移至CLOSED表节点(n)是终节点？不可扩展处理第三章 一般搜索原理 3.5 与或树的启发式搜索812021-11-5与或树的与或树的启发式启发式搜索过程（续搜索过程（续1）可扩展处理把节点(n)标记为不可解节点把n的后继节点放入OPEN表的末端，提供返回节点n的指针不可扩展处理计算这些子节点及其先辈节点的h值从OPEN表中删去具有不可解先辈的节点在T上运用不可解标记过程，标记其先辈节点返回返回第三章 一般搜索原理 3.5 与或树的启发式搜索822021-11-5与或树的与或树的启发式启发式搜索过程（

44、续搜索过程（续2）把节点(n)标记为可解节点终节点处理从OPEN表中删去具有可解先辈的节点在T上运用可解标记过程，标记其先辈节点返回第三章 一般搜索原理 3.5 与或树的启发式搜索832021-11-5与或树的与或树的启发式启发式搜索举例搜索举例l 在该例子中，搜索过程每次扩展节点时都同时扩展两层，且按一层或节点、一层与节点的间隔方式进行扩展。l后面将要讨论的博弈树就是这种结构。第三章 一般搜索原理 3.5 与或树的启发式搜索842021-11-5扩展初始扩展初始节点节点S S后后S扩展后如图所示B、C、E、F的h值由启发函数估计节点S、A、D的h值按和代价法计算。此时，S的右子树是当前的希望

45、树接着，对右子树的E节点进行扩展SDFCA8338372BE第三章 一般搜索原理 3.5 与或树的启发式搜索852021-11-5右子树的右子树的E节点扩展节点扩展后后E扩展后如图所示各端节点h值由启发函数估计先辈节点的h值按和代价法计算。此时，S的左子树代价小，因此，当前左子树又变成了希望树接着，对左子树的B节点进行扩展SDFCA8339116BEF372272第三章 一般搜索原理 3.5 与或树的启发式搜索862021-11-5H左子树的左子树的B节点扩展节点扩展后后S9CA833F372DF11E 76220206JL22K2IGB第三章 一般搜索原理 3.5 与或树的启发式搜索8720

46、21-11-5H左子树的左子树的C节点扩展节点扩展后后9833F372DF11E 76220206JL22K2SIGBN020952PMCA第三章 一般搜索原理 3.5 与或树的启发式搜索882021-11-53.6 博弈树搜索博弈树搜索第三章 一般搜索原理 3.6 博弈树搜索892021-11-5博弈博弈l博弈是一类富有智能行为的竞争活动，如下棋、打牌、战争等l在博弈过程的每一步，可供双方选择的行动方案都可能有多种。l双方都希望自己能够获胜。因此，当任何一方走步时，都是选泽对自己最为有利，而对另一方最为不利的行动方案。l双方交替选择行动方案，直到一方胜利或双方和局。第三章 一般搜索原理 3.6 博弈树搜索902021-11-5从一方看博弈从一方看博弈l假设博弈的一方为MAX，另一方为MIN。l从MAX方的观点看，可供自己选择的行动方案之间是“或”的关系，因为主动权掌握在MAX手里，选择哪个方案完全由自己决定；l而对那些可供MIN选择的行动方案之间则是“与”的关系，因为主动权掌握在MIN的手里，任何一个方案都有可能被MIN选中，lMAX必须防止那种对自己最为不利的情况的发生。第三章 一般搜索原理 3.2与或树搜索博弈树的启发式搜索912021-11-5博弈的表示博弈的表示l博弈过程用