华中科技大学人工智能及其应用第三章一般搜索原理.pptx

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

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

3、方式、图搜索方式不可撤回方式：每一次搜索时，利用局部知识根据最优评价，选出下一状态，选定后不能撤回，只能继续回朔方式：在搜索过程中，有时会发现所选的路径不适合找到目标，这时允许退回去另选一条路径。图搜索方式： 将所有应用过的操作和它们产生的状态描述都以图的形式记录下来。由于当前可继续往下搜索的状态不只一个，因此可以从其中任一个状态往下搜索。图搜索方式与回溯方式的不同之处在于，回溯方式不记亿那些试探失败的操作和它们产生的状态描述，只记忆当前正在搜索的路径。图搜索方式则保存所有试探过的路径，因而可以在任何一条路径上继续搜索第三章 一般搜索原理 3.2 盲目搜索7/15/20226图搜索方式与回溯方

4、式的不同回溯方式不记忆那些试探失败的操作和它们产生的状态描述，只记忆当前正在搜索的路径。图搜索方式则保存所有试探过的路径，因而可以在任何一条路径上继续搜索第三章 一般搜索原理 3.2 盲目搜索7/15/20227不可撤回搜索策略 不可撤回方式的控制策略是，选择一条可应用的操作作用于当前状态，不论后果如何都接着做下去。这个方法类似于高等数学中求函数极值的爬山法。在爬山法中，我们从任一点出发，在该点的最大梯度方向前进一步，得到一个新的点，再在新点的最大梯度方向上前进一步，一直到梯度为0为止，这个点就是函数的极大值点。如果函数只有一个极大值点则这个点就是该函数的最大值点。第三章 一般搜索原理 3.2

5、 盲目搜索7/15/20228不可撤回搜索的实现不可撤回搜索的实现是将状态描述定义成一个实数值的爬山函数。控制策略就利用这个爬山函数来选择一个可应用的操作，施行该操作的结果应使爬山函数的值得到最大限度的增加。第三章 一般搜索原理 3.2 盲目搜索7/15/20229不可撤回搜索举例(一)选择八数码问题我们选取“不在位”的数字个数的负值作为爬山函数 八数码游戏的操作可描述为下面的4条产生式规则 (1) if空格不在最上一行then空格上移 (2) if空格不在最下一行then生格下移 (3) if空格不在最左一列then空格左移 (4) if空格不在最右一列then空格有移2 8 31 6 47

6、 51 2 38 47 6 5目标状态初始状态第三章 一般搜索原理 3.2 盲目搜索7/15/202210不可撤回搜索举例(二)从初始状态出发，应用第一条规则，空格上移可获得爬山函数的最大增加、因此控 制策略选择第一条规则作为当前的操作。在没有操作能够增加爬山函数的值时可任选一个不减小函数值的操作，如果不存在这样的操作，则过程停止。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 盲目搜索7/15/202211不可撤

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

8、2213回溯搜索策略举例例：皇后问题第三章 一般搜索原理 3.2 盲目搜索7/15/202214( )皇后问题搜索过程（一）第三章 一般搜索原理 3.2 盲目搜索7/15/202215Q( )(1,1)皇后问题搜索过程（二）第三章 一般搜索原理 3.2 盲目搜索7/15/202216QQ( )(1,1)(1,1) (2,3)皇后问题搜索过程（三）第三章 一般搜索原理 3.2 盲目搜索7/15/202217Q( )(1,1)(1,1) (2,3)皇后问题搜索过程（四）第三章 一般搜索原理 3.2 盲目搜索7/15/202218QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)皇后问

9、题搜索过程（五）第三章 一般搜索原理 3.2 盲目搜索7/15/202219QQQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后问题搜索过程（六）第三章 一般搜索原理 3.2 盲目搜索7/15/202220QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后问题搜索过程（七）第三章 一般搜索原理 3.2 盲目搜索7/15/202221Q( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后问题搜索过程（八）第三章 一般搜索原理 3.2 盲目搜索7/1

10、5/202222( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后问题搜索过程（九）第三章 一般搜索原理 3.2 盲目搜索7/15/202223Q( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)皇后问题搜索过程（十）第三章 一般搜索原理 3.2 盲目搜索7/15/202224QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)皇后问题搜索过程（十一）第三章 一般搜索原理 3.2 盲目搜索7/15/202225QQQ

11、( )(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 盲目搜索7/15/202226QQQQ( )(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)(1,2) (2,4) (3,1) (4,3)皇后问题搜索过程（十三）第三章 一般搜索原理 3.2 盲目搜索7/15/202227回溯搜索算法回溯搜索可以用递归的方法来实现下面的算法是一个

12、用递归实现的算法：BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。第三章 一般搜索原理 3.2 盲目搜索7/15/202228回溯搜索算法（一）BACKTRACK(DATA)1, IF TERM(DATA) RETURN NIL;2, IF DEADEND(DATA) RETURN FAIL;3, RULES:=APPRULES(DATA);TERM: 找目标DEADEND: 状态不合法,无法继续搜索APPRULES: 取可应用规则集第三章 一般搜索原理 3.2 盲目搜索7/15/202229回溯搜索算法（二）4, LOOP

13、: 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, RETURN CONS(R, PATH);TAIL: 删除头条规则GEN: 调用规则作用于当前状态CONS: 获取解路径规则表第三章 一般搜索原理 3.2 盲目搜索7/15/202230存在问题及解决办法问题：深度问题:如果深度太深死循环问题: 如果状态出现重复解决办法：对搜索深度加以限制记录从初始状态到

14、当前状态的路径第三章 一般搜索原理 3.2 盲目搜索7/15/202231增加约束后的回溯搜索算法BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。第三章 一般搜索原理 3.2 盲目搜索7/15/202232增加约束后的回溯搜索算法(一)1, DATA:=FIRST(DATALIST)2, IF MENBER(DATA, TAIL(DATALIST) RETURN FAIL;3, IF TERM(DATA) RETURN NIL;4, IF DEADEND(DATA) RETURN FAIL

15、;5, IF LENGTH(DATALIST)BOUND RETURN FAIL;第三章 一般搜索原理 3.2 盲目搜索7/15/202233增加约束后的回溯搜索算法(二)6, RULES:=APPRULES(DATA);7, LOOP: IF NULL(RULES) RETURN FAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);第三章 一般搜索原理 3.2 盲目搜索7/15/202234增加约束后的回溯搜索算法(三)10,RDATA:=GEN(R, DATA);11,RDATALIST:=CONS(RDATA, DATALIST);12,PATH:=B

16、ACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R, PATH);第三章 一般搜索原理 3.2 盲目搜索7/15/202235图搜索策略图搜索策略就是在图中寻找从起始点到目标点的路径的方法图搜索的一般过程是构造搜索图的过程。令搜索图开始时只有起始点S0，然后逐步扩展节点，直到将目标点扩展到搜索图里为止。扩展的过程就是搜索的过程扩展节点的方法不同，就意味着搜索的方法不同，也就是搜索的路径不同。第三章 一般搜索原理 3.2 盲目搜索7/15/202236图搜索包括宽度优先搜索：搜索以接近起始节点的程度依次扩展节点，在对下一层搜索前

17、，必须搜索完本层的所有节点。深度优先搜索：搜索首先扩展最新产生的节点。等代价搜索：搜索沿最小代价节点进行扩展。第三章 一般搜索原理 3.2 盲目搜索7/15/202237图搜索的一般过程成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向把S放入OPEN表重排OPEN表是否否OPEN为空？n为目标节点？失败开始第三章 一般搜索原理 3.2 盲目搜索7/15/202238图搜索过程说明我们在搜索过程中用到了OPEN表和CLOSED表两个数据结构OPEN表中的节点都是搜索树的端节点，即至今尚未被选作为扩展的节点CLOSED表中的

18、节点或者是已被扩展而不能生成后继节点的那些端节点，或者是搜索树的非端节点重排OPEN表，实际上就是在选择搜索顺序，也就是扩展的节点的顺序。第三章 一般搜索原理 3.2 盲目搜索7/15/202239节点类型说明.mj.mk.ml扩展的节点OPEN表没有的部分扩展的节点在已在close表中的部分扩展的节点已在OPEN表中的部分选定的扩展节点第三章 一般搜索原理 3.2 盲目搜索7/15/202240图搜索过程的图示（一）现要扩展它第三章 一般搜索原理 3.2 盲目搜索7/15/202241图搜索过程的图示（二）修改父子关系现要扩展它第三章 一般搜索原理 3.2 盲目搜索7/15/202242图搜

19、索过程的图示（三）修改父子关系修改父子关系第三章 一般搜索原理 3.2 盲目搜索7/15/202243宽度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供返回节点n的指针把S放入OPEN表是否否OPEN为空？是否有任何后继节点为目标节点？失败开始第三章 一般搜索原理 3.2 盲目搜索7/15/202244目标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 6 4 7

20、 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 盲目搜索7/15/202245宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位代价值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低第三章 一般搜索原理 3.2 盲目搜索7/15/202246深度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n

21、的后继节点放入OPEN表的前端，提供返回节点n的指针把S放入OPEN表是否否OPEN为空？节点n的深度是否等于深度界限？失败开始是否有任何后继节点为目标节点？是否S是否为目标节点？否成功第三章 一般搜索原理 3.2 盲目搜索7/15/2022472 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 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1

22、2 37 8 4 6 51 2 38 47 6 5123456789abcd1 2 3 8 47 6 5目标。八数码难题的深度优先搜索树第三章 一般搜索原理 3.2 盲目搜索7/15/202248深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举是一个通用的与问题无关的方法第三章 一般搜索原理 3.2 盲目搜索7/15/202249等代价搜索搜索树的每条弧线上可能有代价值有些问题要求搜索代价最小的解当搜索树的每条弧线上的代价值都为1时，宽度优先搜索可以看成是最小代价搜索推广宽度优先搜索，以获得最小代价的搜索方法称为

23、等代价搜索第三章 一般搜索原理 3.2 盲目搜索7/15/202250等代价搜索成功是把具有最小g(i)值的节点i从OPEN表移至CLOSED表计算其后继节点j的g(j)值。把其后继节点放入OPEN表把S放入OPEN表否否OPEN为空？失败开始 i是否为目标节点？是S是否为目标节点？否成功是令g(s)=0第三章 一般搜索原理 3.2 盲目搜索7/15/2022513.3 启发式搜索第三章 一般搜索原理 3.3 启发式搜索7/15/202252为何引入启发式信息盲目搜索的效率低，耗费过多的计算时间和空间，容易产生组合爆炸。利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。对搜索产生帮助

24、的信息称为启发信息第三章 一般搜索原理 3.3 启发式搜索7/15/202253启发式信息对搜索方法的影响启发信息的多少用启发信息强度来表示不同的启发信息对搜索方法带来不同的影响：强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解第三章 一般搜索原理 3.3 启发式搜索7/15/202254启发式搜索类型启发信息按用途可分为3类：用于决定要扩展哪一个节点（这个节点称为最有希望节点），以免像在宽度优先或深度优先搜索中那样盲目地扩展在扩展一个节点的过程中，用于决定要生成哪些其后继节点，以免盲目地生成所有节点。用于决定哪些节点应从搜索树中抛

25、弃或修剪。用来估算节点希望程度的方法为估价函数体现问题自身的启发性信息的函数称为启发函数第三章 一般搜索原理 3.3 启发式搜索7/15/202255对启发式搜索的认识有些启发信息能够大大减少搜索工作量，但不能保证能够得到最小代价路径我们往往希望获得路径代价和求该路径所需的搜索代价的综合为最小由于计算综合代价很困难，因此，比较两种方法的优劣，依赖使用的经验第三章 一般搜索原理 3.3 启发式搜索7/15/202256有序搜索若按估价函数的增序对OPEN表进行排序，这种搜索方法叫做有序搜索或最佳优先搜索有序搜索的有效性取决于估价函数的选择，否则有可能失去一个最好的解甚至全部的解如果没有合适的选择

26、，可考虑两个方面的内容：一个是时间和空间的折中保证有一个解第三章 一般搜索原理 3.3 启发式搜索7/15/202257有序搜索框图成功是选取f值最小的节点i，从OPEN表移至CLOSED表扩展i，计算后继节点j的f(j)，对OPEN表重排序，调整亲子关系把S放入OPEN表，计算f(s)是否否OPEN为空？i是目标节点？失败开始第三章 一般搜索原理 3.3 启发式搜索7/15/202258估价函数：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

27、 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 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 启发式搜索7/15/202259A算法A算法是一种有序搜索的启发式搜索算法。估价函数的形式： f(n) = g(n) + h(n)g(n)是从初始节点S0到节点n的实际代价h(n)是从节点n到目标节点Sg的最小路径代价h*(n)的启发式估计

28、h(n)称为启发函数：第三章 一般搜索原理 3.3 启发式搜索7/15/202260A算法流程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);第三章 一般搜索原理 3.3 启发式搜索7/15/202261A算法流程（续）ADD(mj, OPEN), 标记

29、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；第三章 一般搜索原理 3.3 启发式搜索7/15/202262最佳图搜索算法A*（A*算法）在A算法中，如果对于任意点n满足条件：h(n)h*(n)则A算法称为A*算法。如果存在从初始节点S0目标节点Sg的最小路径， A*算法就一定能搜索到第三章 一般搜索原理 3.3 启发式搜索7/15/20

30、2263A*算法估价函数举例在问题求解过程中，不可能明确知道h*(n) ，可根据经验估计下界范围条件例如，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 启发式搜索7/15/2022643.4 与或树搜索第三章 一般搜索原理 3.4 与或树搜索7/15/202265与或树搜索 与或树的搜索是实现用与或树表示的问题的求

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

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

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

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

35、标节点5为可解，继续向上，标节点3为可解，最后可确定节点1为可解t2A13542BCt1t3第三章 一般搜索原理 3.4 与或树搜索7/15/202272深度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表可扩展处理把S放入OPEN表是否否OPEN为空？节点(n)是否有可扩展？失败开始不可扩展处理S标为可解节点？是否S标为不可解节点？是否失败节点(n)深度=d？是否第三章 一般搜索原理 3.4 与或树搜索7/15/202273深度优先搜索（续）可扩展处理把节点(n)标记为不可解节点把n的后继节点放入OPEN表的前端，提供返回节点n的指针不可扩展处理若n的后继节点中有终节点，则标记

36、其为可解节点从OPEN表中删去具有可解先辈的节点调用可解标记过程，标记其先辈节点从OPEN表中删去具有不可解先辈的节点调用不可解标记过程，标记其先辈节点返回返回第三章 一般搜索原理 3.4 与或树搜索7/15/2022743.5 与或树的启发式搜索第三章 一般搜索原理 3.5 与或树的启发式搜索7/15/202275与或树的启发式搜索 与或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。对搜索的每一步，算法都试图找到一个最有希望成为最优解树的子树。最优解树是指代价最小的那棵解树。第三章 一般搜索原理 3.5 与或树的启发式搜索7/15/202276解树的代价设n为节点

37、，n1，n2，nk为其子节点， h(n)为节点n的代价， c(n，ni)为节点n到其子节点ni的边代价若n为终节点，则h(n)0。若n为或节点，则h(n)min(c(n，ni)+h(ni)若n为与节点，则n的代价可用和代价法或最大代价法。和代价法：h(n)(c(n，ni)+h(ni)最大代价法：h(n)maxc(n，ni)+h(ni) 若n是端节点，但非终节点，则n不可扩展，h(n)。解树的代价，为根节点的代价。第三章 一般搜索原理 3.5 与或树的启发式搜索7/15/202277解树的代价举例图中与或树包括两棵解树左边的解树由S、A、t1、C及t3组成右边的解树由S、B、t2、D及t4组成。

38、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 与或树的启发式搜索7/15/202278希望解树 为了找到最优解树，搜索过程的任何时刻都应该选择那些最有希望成为最优解树一部分的节点进行扩展由于这些节点及其父节点所构成的与或树最有可能成为最优解树的一部分，因此称为希望解树，简称为希望树。需要注意，希望解树是会随搜索过程而不断变化的。希

39、望树定义：初始节点S在希望树T中若n为具有子节点n1，n2，nk的或节点，其子节点ni在希望树T中的充分必要条件： h(ni)min(c(n，nt)+h(nt)若n为与节点，其子节点都在希望树T。第三章 一般搜索原理 3.5 与或树的启发式搜索7/15/202279与或树的启发式搜索过程成功是计算希望树T可扩展处理把S放入OPEN表，计算h(S)是否否节点(n)是否可扩展？开始终节点处理S标为可解节点？是否S标为不可解节点？是否失败把OPEN表中第一个属于T的节点(n)移至CLOSED表节点(n)是终节点？不可扩展处理第三章 一般搜索原理 3.5 与或树的启发式搜索7/15/202280与或树

40、的启发式搜索过程（续1）可扩展处理把节点(n)标记为不可解节点把n的后继节点放入OPEN表的末端，提供返回节点n的指针不可扩展处理计算这些子节点及其先辈节点的h值从OPEN表中删去具有不可解先辈的节点在T上运用不可解标记过程，标记其先辈节点返回返回第三章 一般搜索原理 3.5 与或树的启发式搜索7/15/202281与或树的启发式搜索过程（续2）把节点(n)标记为可解节点终节点处理从OPEN表中删去具有可解先辈的节点在T上运用可解标记过程，标记其先辈节点返回第三章 一般搜索原理 3.5 与或树的启发式搜索7/15/202282与或树的启发式搜索举例 在该例子中，搜索过程每次扩展节点时都同时扩展

41、两层，且按一层或节点、一层与节点的间隔方式进行扩展。后面将要讨论的博弈树就是这种结构。第三章 一般搜索原理 3.5 与或树的启发式搜索7/15/202283扩展初始节点S后S扩展后如图所示B、C、E、F的h值由启发函数估计节点S、A、D的h值按和代价法计算。此时，S的右子树是当前的希望树接着，对右子树的E节点进行扩展SDFCA8338372BE第三章 一般搜索原理 3.5 与或树的启发式搜索7/15/202284右子树的E节点扩展后E扩展后如图所示各端节点h值由启发函数估计先辈节点的h值按和代价法计算。此时，S的左子树代价小，因此，当前左子树又变成了希望树接着，对左子树的B节点进行扩展SDFC

42、A8339116BEF372272第三章 一般搜索原理 3.5 与或树的启发式搜索27/15/202285H左子树的B节点扩展后S9CA833F372DF11E76220206JL22K2IGB第三章 一般搜索原理 3.5 与或树的启发式搜索7/15/202286H左子树的C节点扩展后9833F372DF11E76220206JL22K2SIGBN020952PMCA第三章 一般搜索原理 3.5 与或树的启发式搜索7/15/2022873.6 博弈树搜索第三章 一般搜索原理 3.6 博弈树搜索7/15/202288博弈博弈是一类富有智能行为的竞争活动，如下棋、打牌、战争等博弈可分为双人完备信息

43、博弈奔和机遇性博弈双人完备信息博弈：两位选手对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。对弈的结果是一方赢，另一方输；或者双方和局。例如，有象棋、围棋等。机遇性博弈：指存在不可预测性的博弈，例如掷币等。我们只讨论双人完备信息博弈问题。第三章 一般搜索原理 3.6 博弈树搜索7/15/202289博弈过程分析在博弈过程的每一步，可供双方选择的行动方案都可能有多种。双方都希望自己能够获胜。任何一方走步时，都是选泽对自己最为有利，而对另一方最为不利的行动方案。双方交替选择行动方案，直到一方胜利或双方和局。第三章 一般搜索原理 3.6 博弈树搜索7/15/202290从MAX方看博弈假设博弈的一方为MAX，另一方为MIN。可供自己选择的行动方案之间是“或”的关系主动权掌握在自己手里，选择哪个方案完全由自己决定；可供MIN选择的行动方案之间是“与”的关系主动权掌握在MIN的手里，任何一个方案都有可能被MIN选中，MAX必须防止那种对自己最为不利的情况的发生。第三章 一般搜索原理 3.6 博弈树搜索