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

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

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

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

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

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

6、最下一行then生格下移 (3) if空格不在最左一列then空格左移 (4) if空格不在最右一列then空格有移,第三章 一般搜索原理 3.2 盲目搜索,11,2020/9/15,不可撤回搜索举例(二),从初始状态出发，应用第一条规则，空格上移可获得爬山函数的最大增加、因此控 制策略选择第一条规则作为当前的操作。 在没有操作能够增加爬山函数的值时可任选一个不减小函数值的操作，如果不存在这样的操作，则过程停止。,目标状态,爬山函数值,第三章 一般搜索原理 3.2 盲目搜索,12,2020/9/15,不可撤回搜索举例(三),对于上例，采用不可撤回策略可以很快得到问题的解。 但一般来讲，如果爬山

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

8、,皇后问题搜索过程（一）,第三章 一般搜索原理 3.2 盲目搜索,16,2020/9/15,Q,皇后问题搜索过程（二）,第三章 一般搜索原理 3.2 盲目搜索,17,2020/9/15,皇后问题搜索过程（三）,第三章 一般搜索原理 3.2 盲目搜索,18,2020/9/15,Q,皇后问题搜索过程（四）,第三章 一般搜索原理 3.2 盲目搜索,19,2020/9/15,皇后问题搜索过程（五）,第三章 一般搜索原理 3.2 盲目搜索,20,2020/9/15,皇后问题搜索过程（六）,第三章 一般搜索原理 3.2 盲目搜索,21,2020/9/15,皇后问题搜索过程（七）,第三章 一般搜索原理 3.

9、2 盲目搜索,22,2020/9/15,Q,皇后问题搜索过程（八）,第三章 一般搜索原理 3.2 盲目搜索,23,2020/9/15,皇后问题搜索过程（九）,第三章 一般搜索原理 3.2 盲目搜索,24,2020/9/15,Q,皇后问题搜索过程（十）,第三章 一般搜索原理 3.2 盲目搜索,25,2020/9/15,皇后问题搜索过程（十一）,第三章 一般搜索原理 3.2 盲目搜索,26,2020/9/15,皇后问题搜索过程（十二）,第三章 一般搜索原理 3.2 盲目搜索,27,2020/9/15,皇后问题搜索过程（十三）,第三章 一般搜索原理 3.2 盲目搜索,28,2020/9/15,回溯搜

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

11、三章 一般搜索原理 3.2 盲目搜索,30,2020/9/15,回溯搜索算法（二）,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, RETURN CONS(R, PATH);,TAIL: 删除头条规则 GEN: 调用规则作用于当前状态 CONS: 获取解路径规则表,第三章 一般搜索原理 3.2 盲目搜索,31,2020/9/1

12、5,存在问题及解决办法,问题： 深度问题:如果深度太深 死循环问题: 如果状态出现重复 解决办法： 对搜索深度加以限制 记录从初始状态到当前状态的路径,第三章 一般搜索原理 3.2 盲目搜索,32,2020/9/15,增加约束后的回溯搜索算法,BACKTRACK1（DATALIST） DATALIST：从初始到当前的状态表（逆向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。,第三章 一般搜索原理 3.2 盲目搜索,33,2020/9/15,增加约束后的回溯搜索算法(一),1, DATA:=FIRST(DATALIST) 2, IF MENBER(DATA, TAI

13、L(DATALIST) RETURN FAIL; 3, IF TERM(DATA) RETURN NIL; 4, IF DEADEND(DATA) RETURN FAIL; 5, IF LENGTH(DATALIST)BOUND RETURN FAIL;,第三章 一般搜索原理 3.2 盲目搜索,34,2020/9/15,增加约束后的回溯搜索算法(二),6, RULES:=APPRULES(DATA); 7, LOOP: IF NULL(RULES) RETURN FAIL; 8,R:=FIRST(RULES); 9,RULES:=TAIL(RULES);,第三章 一般搜索原理 3.2 盲目搜索

14、,35,2020/9/15,增加约束后的回溯搜索算法(三),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,2020/9/15,图搜索策略,图搜索策略就是在图中寻找从起始点到目标点的路径的方法 图搜索的一般过程是构造搜索图的过程。令搜索图开始时只有起始点S0，然后逐步扩展节点，直到将目标点扩展到搜索图里为止。扩展的过程

15、就是搜索的过程 扩展节点的方法不同，就意味着搜索的方法不同，也就是搜索的路径不同。,第三章 一般搜索原理 3.2 盲目搜索,37,2020/9/15,图搜索包括,宽度优先搜索：搜索以接近起始节点的程度依次扩展节点，在对下一层搜索前，必须搜索完本层的所有节点。 深度优先搜索：搜索首先扩展最新产生的节点。 等代价搜索：搜索沿最小代价节点进行扩展。,第三章 一般搜索原理 3.2 盲目搜索,38,2020/9/15,图搜索的一般过程,第三章 一般搜索原理 3.2 盲目搜索,39,2020/9/15,图搜索过程说明,我们在搜索过程中用到了OPEN表和CLOSED表两个数据结构 OPEN表中的节点都是搜索

16、树的端节点，即至今尚未被选作为扩展的节点 CLOSED表中的节点或者是已被扩展而不能生成后继节点的那些端节点，或者是搜索树的非端节点 重排OPEN表，实际上就是在选择搜索顺序，也就是扩展的节点的顺序。,第三章 一般搜索原理 3.2 盲目搜索,40,2020/9/15,节点类型说明,.,mj,扩展的节点OPEN表没有的部分,扩展的节点在已在close表中的部分,扩展的节点已在OPEN表中的部分,选定的扩展节点,第三章 一般搜索原理 3.2 盲目搜索,41,2020/9/15,图搜索过程的图示（一）,现要扩展它,第三章 一般搜索原理 3.2 盲目搜索,42,2020/9/15,图搜索过程的图示（二

17、）,修改父子关系,现要扩展它,第三章 一般搜索原理 3.2 盲目搜索,43,2020/9/15,图搜索过程的图示（三）,修改父子关系,修改父子关系,第三章 一般搜索原理 3.2 盲目搜索,44,2020/9/15,宽度优先搜索,第三章 一般搜索原理 3.2 盲目搜索,45,2020/9/15,目标,2 3 1 8 4 7 6 5,1,2,5,6,7,3,8,4,八数码难题的宽度优先搜索树,按上下左右序走步,第三章 一般搜索原理 3.2 盲目搜索,46,2020/9/15,宽度优先搜索的性质,当问题有解时，一定能找到解 当问题为单位代价值，且问题有解时，一定能找到最优解 方法与问题无关，具有通用

18、性 效率较低,第三章 一般搜索原理 3.2 盲目搜索,47,2020/9/15,深度优先搜索,第三章 一般搜索原理 3.2 盲目搜索,48,2020/9/15,2 3 1 8 4 7 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,目标,。,八数码难题的深度优先搜索树,第三章 一般搜索原理 3.2 盲目搜索,49,2020/9/15,深度优先搜索的性质,一般不能保证找到最优解 当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制 最坏情况时，搜索空间等同于穷举 是一个通用的与问题无关的方法,第三章 一般搜索原理 3.2 盲目搜索,50,2020/9/15,等代价搜索,搜索树

19、的每条弧线上可能有代价值 有些问题要求搜索代价最小的解 当搜索树的每条弧线上的代价值都为1时，宽度优先搜索可以看成是最小代价搜索 推广宽度优先搜索，以获得最小代价的搜索方法称为等代价搜索,第三章 一般搜索原理 3.2 盲目搜索,51,2020/9/15,等代价搜索,第三章 一般搜索原理 3.2 盲目搜索,52,2020/9/15,3.3 启发式搜索,第三章 一般搜索原理 3.3 启发式搜索,53,2020/9/15,为何引入启发式信息,盲目搜索的效率低，耗费过多的计算时间和空间，容易产生组合爆炸。 利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。 对搜索产生帮助的信息称为启发信息,

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

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

22、一个最好的解甚至全部的解 如果没有合适的选择，可考虑两个方面的内容： 一个是时间和空间的折中 保证有一个解,第三章 一般搜索原理 3.3 启发式搜索,58,2020/9/15,有序搜索框图,第三章 一般搜索原理 3.3 启发式搜索,59,2020/9/15,估价函数：f(n)=d(n)+w(n) 其中， d(n):节点的深度 w(n):节点放错棋子数目,八数码难题的有序搜索树,估价函数值,第三章 一般搜索原理 3.3 启发式搜索,60,2020/9/15,A算法,A算法是一种有序搜索的启发式搜索算法。 估价函数的形式： f(n) = g(n) + h(n) g(n)是从初始节点S0到节点n的实

23、际代价 h(n)是从节点n到目标节点Sg的最小路径代价h*(n)的启发式估计 h(n)称为启发函数：,第三章 一般搜索原理 3.3 启发式搜索,61,2020/9/15,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);,第三章 一般

24、搜索原理 3.3 启发式搜索,62,2020/9/15,A算法流程（续）,ADD(mj, OPEN), 标记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 启发式搜索,63,2020/9/15,最佳图搜索算法A*（A*算法）,在A算法中，如果对于任意点n满足条件： h(n)h*(n) 则A算法称为A

25、*算法。 如果存在从初始节点S0目标节点Sg的最小路径， A*算法就一定能搜索到,第三章 一般搜索原理 3.3 启发式搜索,64,2020/9/15,A*算法估价函数举例,在问题求解过程中，不可能明确知道h*(n) ，可根据经验估计下界范围条件 例如，8数码问题 如取h(n) = “不在位”的牌数，可估计出至少要移动h(n) 步，才能达到目标，因此，有h(n) h*(n) 如取h (n) = 每个牌与目标位置的距离和，同样可估计出至少要移动h(n) 步，才能达到目标，因此，有h(n) h*(n),第三章 一般搜索原理 3.3 启发式搜索,65,2020/9/15,3.4 与或树搜索,第三章 一

26、般搜索原理 3.4 与或树搜索,66,2020/9/15,与或树搜索,与或树的搜索是实现用与或树表示的问题的求解。 与或树的搜索过程将形成一棵与或树，这种由搜索过程形成的与或树称为搜索树。 与或树的搜索过程实际上是一个不断寻找解树的过程。,第三章 一般搜索原理 3.4 与或树搜索,67,2020/9/15,几个概念,由可解节点构成，并且由这些可解节点可以推出初始节点为可解节点的子树称为解树，解树中一定包含初始节点。 没有子节点的节点称为端节点。 本原问题所对应的节点称为终止节点。 可解问题所对应的节点称为可解节点。反之为不可解节点。 终止节点是可解节点。 子节点都是可解节点的与节点是可解节点

27、至少一个子节点是可解节点的或节点是可解节点。,第三章 一般搜索原理 3.4 与或树搜索,68,2020/9/15,与或树搜索的一般过程,(1)把原始问题作为初始节点S0，并把它作为当前节点； (2)应用分解或等价变换操作对当前节点进行扩展 (3)为每个子节点设置指向父节点的指针 (4)选择合适的子节点作为当前节点，反复执行第(2)步和第(3)步，多次调用标记过程，直到初始节点被标记。 如果某个节点被标记为可解节点，则其不可解的后继节点就可从搜索树中删去；如果被标记为不可解节点则其后继节点也可从搜索树中删去。,第三章 一般搜索原理 3.4 与或树搜索,69,2020/9/15,宽度优先搜索,是,

28、把第一个节点(n)从OPEN表移至CLOSED表,可扩展处理,把S放入OPEN表,是,否,否,节点(n)是否有可扩展？,不可扩展处理,S标为可解节点？,是,否,S标为不可解节点？,是,否,第三章 一般搜索原理 3.4 与或树搜索,70,2020/9/15,宽度优先搜索（续）,把节点(n)标记为不可解节点,把n的后继节点放入OPEN表的末端，提供返回节点n的指针,若n的后继节点中有终节点，则标记其为可解节点,从OPEN表中删去具有可解先辈的节点,调用可解标记过程，标记其先辈节点,从OPEN表中删去具有不可解先辈的节点,调用不可解标记过程，标记其先辈节点,第三章 一般搜索原理 3.4 与或树搜索,

29、71,2020/9/15,宽度优先搜索举例（一）,t1,t2,t3为终节点 ABC为端节点 搜索过程： 扩展1号生成2、3号节点，都是非终节点 扩展2号生成A、4号节点，都是非终节点 扩展3号生成t1、5号节点，t1是终节点，标记为可解节点，调用可解标记过程，由于t1的父节点是与节点，不能确定其父节点是可解,第三章 一般搜索原理 3.4 与或树搜索,72,2020/9/15,宽度优先搜索举例（二）,A是端节点，不可扩展，调用不可解标记过程，由于A的父节点是或节点，不能确定其父节点是不可解 扩展4号生成t2、B节点，t2是终节点，标记为可解节点，调用可解标记过程，由于t2的父节点是或节点，标节点

30、4为可解，继续向上，标节点2为可解，但无法确定标节点1 扩展5号生成t3、C节点，t3是终节点，标记为可解节点，调用可解标记过程，由于t3的父节点是或节点，标节点5为可解，继续向上，标节点3为可解，最后可确定节点1为可解,第三章 一般搜索原理 3.4 与或树搜索,73,2020/9/15,深度优先搜索,是,把第一个节点(n)从OPEN表移至CLOSED表,可扩展处理,把S放入OPEN表,是,否,否,节点(n)是否有可扩展？,不可扩展处理,S标为可解节点？,是,否,S标为不可解节点？,是,否,节点(n)深度=d？,是,否,第三章 一般搜索原理 3.4 与或树搜索,74,2020/9/15,深度优

31、先搜索（续）,把节点(n)标记为不可解节点,把n的后继节点放入OPEN表的前端，提供返回节点n的指针,若n的后继节点中有终节点，则标记其为可解节点,从OPEN表中删去具有可解先辈的节点,调用可解标记过程，标记其先辈节点,从OPEN表中删去具有不可解先辈的节点,调用不可解标记过程，标记其先辈节点,第三章 一般搜索原理 3.4 与或树搜索,75,2020/9/15,3.5 与或树的启发式搜索,第三章 一般搜索原理 3.5 与或树的启发式搜索,76,2020/9/15,与或树的启发式搜索,与或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。 对搜索的每一步，算法都试图找到一

32、个最有希望成为最优解树的子树。 最优解树是指代价最小的那棵解树。,第三章 一般搜索原理 3.5 与或树的启发式搜索,77,2020/9/15,解树的代价,设n为节点，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)。 解树的代价，为根节点的代价。,第三章

33、 一般搜索原理 3.5 与或树的启发式搜索,78,2020/9/15,解树的代价举例,图中与或树包括两棵解树 左边的解树由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 可见，右边的解树是最优解树。,6,4,2,2,2,3,5,1,第三章 一般搜索原理 3.5 与或树的启发式搜索,79,2020/9/15,希望解树,为了找到最优解树，搜索过程的任何时

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

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

36、记其先辈节点,第三章 一般搜索原理 3.5 与或树的启发式搜索,83,2020/9/15,与或树的启发式搜索举例,在该例子中，搜索过程每次扩展节点时都同时扩展两层，且按一层或节点、一层与节点的间隔方式进行扩展。 后面将要讨论的博弈树就是这种结构。,第三章 一般搜索原理 3.5 与或树的启发式搜索,84,2020/9/15,扩展初始节点S后,S扩展后如图所示 B、C、E、F的h值由启发函数估计 节点S、A、D的h值按和代价法计算。 此时，S的右子树是当前的希望树 接着，对右子树的E节点进行扩展,8,3,3,8,3,7,2,第三章 一般搜索原理 3.5 与或树的启发式搜索,85,2020/9/15

37、,右子树的E节点扩展后,E扩展后如图所示 各端节点h值由启发函数估计 先辈节点的h值按和代价法计算。 此时，S的左子树代价小，因此，当前左子树又变成了希望树 接着，对左子树的B节点进行扩展,8,3,3,9,11,6,3,7,2,2,7,2,第三章 一般搜索原理 3.5 与或树的启发式搜索,2,86,2020/9/15,左子树的B节点扩展后,9,8,3,3,3,7,2,11,7,6,2,2,0,2,0,2,第三章 一般搜索原理 3.5 与或树的启发式搜索,87,2020/9/15,左子树的C节点扩展后,9,8,3,3,3,7,2,11,7,6,2,2,0,2,0,2,0,2,0,9,5,2,第三

38、章 一般搜索原理 3.5 与或树的启发式搜索,88,2020/9/15,3.6 博弈树搜索,第三章 一般搜索原理 3.6 博弈树搜索,89,2020/9/15,博弈,博弈是一类富有智能行为的竞争活动，如下棋、打牌、战争等 博弈可分为双人完备信息博弈奔和机遇性博弈 双人完备信息博弈： 两位选手对垒，轮流走步， 每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。 对弈的结果是一方赢，另一方输；或者双方和局。 例如，有象棋、围棋等。 机遇性博弈： 指存在不可预测性的博弈，例如掷币等。 我们只讨论双人完备信息博弈问题。,第三章 一般搜索原理 3.6 博弈树搜索,90,2020/9/15,

39、博弈过程分析,在博弈过程的每一步，可供双方选择的行动方案都可能有多种。 双方都希望自己能够获胜。 任何一方走步时，都是选泽对自己最为有利，而对另一方最为不利的行动方案。 双方交替选择行动方案，直到一方胜利或双方和局。,第三章 一般搜索原理 3.6 博弈树搜索,91,2020/9/15,从MAX方看博弈,假设博弈的一方为MAX，另一方为MIN。 可供自己选择的行动方案之间是“或”的关系 主动权掌握在自己手里，选择哪个方案完全由自己决定； 可供MIN选择的行动方案之间是“与”的关系 主动权掌握在MIN的手里，任何一个方案都有可能被MIN选中， MAX必须防止那种对自己最为不利的情况的发生。,第三章

40、 一般搜索原理 3.6 博弈树搜索,92,2020/9/15,博弈的表示,博弈过程用图表示，就是一棵与或树 称为博弈树 该MAX走步的节点称为MAX节点， 该MIN走步的节点称为MIN节点,第三章 一般搜索原理 3.6 博弈树搜索,93,2020/9/15,博弈树的特点,博弈的初始状态是初始节点； 博弈树中的“或”节点和“与”节点是逐层交替出现的； 整个博奕树始终站在某一方的立场上，所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。,第三章 一般搜索原理 3.6 博弈树搜索,94,2020/9/15,极小极大搜索,用当前正在考察的节点生成一棵部分博弈树 计算叶节点的值，一般叶节点还不是终节点，因此，利用估价函数f(n)进行估值。一般来说，对MAX有利的节点，取正值；对MIN有利的节点，取负值；使双方均等的节点，取接近于0的值。 计算非叶节点的值，从叶节点向上倒退。MAX节点总是选择其后继