(完整版)3.3-启发式搜索(2)

1、1人工智能人工智能第第3 3章章 搜索策略搜索策略3.3 3.3 启发式搜索启发式搜索(2)(2)3.1 3.1 引言引言3.2 3.2 盲目搜索盲目搜索 23.3.33.3.3 通用图搜索算法（通用图搜索算法（a算法）算法） 图搜索算法只记录状态空间中那些被搜索图搜索算法只记录状态空间中那些被搜索过的状态，它们组成一个过的状态，它们组成一个搜索图搜索图g g。搜索图搜索图g g由两种节点组成：由两种节点组成：openopen节点：一个节点称为节点：一个节点称为openopen，如果该节点已，如果该节点已经生成，而且启发式函数值经生成，而且启发式函数值h(x)已经计算出来，已经计算出来，但是它

2、没有扩展。这些节点也称为但是它没有扩展。这些节点也称为未考察节点。未考察节点。closedclosed节点：一个节点称为节点：一个节点称为closedclosed，如果该节，如果该节点已经扩展并生成了其子节点。点已经扩展并生成了其子节点。closedclosed节点是节点是已经考察过的节点。已经考察过的节点。 3这样，可以给出两个数据结构这样，可以给出两个数据结构open和和closed表，分别存放了表，分别存放了open 节点和节点和closed节点。节点。节点节点x 总的费用函数总的费用函数f (x) 是是g (x) 和和h (x) 之和。之和。生成费用生成费用 g (x) 可以比较容易地

3、得到，如可以比较容易地得到，如: 如果节如果节点点 x 是从初始节点经过是从初始节点经过m步得到，则步得到，则g (x) 应该和应该和 m 成正比（或者就是成正比（或者就是m）。）。如何计算如何计算h(x)呢呢? h (x) 只是一个预测值。只是一个预测值。 3.3.33.3.3 通用图搜索算法（通用图搜索算法（a算法）算法） 4procedure graph-searchbegin 建立一个只含有初始节点建立一个只含有初始节点s0的搜索图的搜索图g，把把s0放入放入open表；计算表；计算f(s0)=g(s0)+h(s0); 假定初始时假定初始时closed表为空。表为空。 while op

4、en 表不空表不空 do begin 从从open表中取出表中取出f值最小的节点值最小的节点(第一节点第一节点),并放入并放入closed表中表中.假设该节点假设该节点 的编号为的编号为n。 if n是目标是目标,则停止则停止;返回返回n,并根据并根据n的反向指针指出的从初始节点到的反向指针指出的从初始节点到n的路径。的路径。 else do begin (1) 生成生成n的子节点集合的子节点集合mi,把把mi作为作为n的后继节点加入到的后继节点加入到g中中,并计算并计算 f(mi)。 (2) if mi未曾在未曾在g中出现过中出现过(即未曾在即未曾在open和和closed表中出现过表中出现

5、过),then 将将 它们配上刚计算过的它们配上刚计算过的f值值,设置返回到设置返回到n的指针的指针,并把它们放入并把它们放入open表中。表中。图搜索算法（图搜索算法（a a算法）算法）(p78:(p78:算法算法3.8)3.8)5 (3) if mi已经在已经在open表中表中,则该节点一定有多个父节点则该节点一定有多个父节点,在这种情在这种情 况下况下,计算当前的路径计算当前的路径g值值,并和原有路径的并和原有路径的g值相比较值相比较: 若前若前 者大于后者者大于后者,则不做任何更改则不做任何更改;如果前者小于后者如果前者小于后者,则将则将open表表 中该节点的中该节点的f值更改为刚计

6、算的值更改为刚计算的f值值,返回指针更改为返回指针更改为n。 (4) if mi已经存在于已经存在于closed表中表中,则该节点一样也有多个父节点则该节点一样也有多个父节点. 在这种情况下在这种情况下,同样计算当前的路径同样计算当前的路径g值和原来路径的值和原来路径的g值值. 如如 果当前的果当前的g值小于原来的值小于原来的g值值,则将表中该节点的则将表中该节点的g、f值及返回值及返回 指针进行类似指针进行类似(3)步的修改步的修改,并要考虑修改表中通过该节点的并要考虑修改表中通过该节点的 后继节点的后继节点的g、f值及返回指针。值及返回指针。 (5) 按按f值从小到大的次序值从小到大的次序

7、,对对open表中的节点进行重新排序。表中的节点进行重新排序。 end if; end else; end while;end.图搜索算法图搜索算法6上述图搜索算法生成一个明确的图上述图搜索算法生成一个明确的图g（称为搜索图）和一个（称为搜索图）和一个g的子集的子集t（称为搜索树），图（称为搜索树），图g中的每一个节点也在树中的每一个节点也在树t上。上。搜索树搜索树是由返回指针来确定的。是由返回指针来确定的。g中的每一个节点（除了初始节点中的每一个节点（除了初始节点s0）都有一个指向）都有一个指向g中一中一个父辈节点的指针。该父辈节点就是树中那个节点的唯一父个父辈节点的指针。该父辈节点就是树中

8、那个节点的唯一父辈节点。辈节点。算法中算法中(3)、(4)步保证对每一个扩展的新节点，其返回指针步保证对每一个扩展的新节点，其返回指针的指向是已经产生的路径中代价最小的。的指向是已经产生的路径中代价最小的。这可用下图来说明。这可用下图来说明。 图搜索算法说明图搜索算法说明7设搜索算法已生成如下图（设搜索算法已生成如下图（a a）所示的搜索图和搜索树（带返）所示的搜索图和搜索树（带返回指针的部分）。图中实心圆点表示在回指针的部分）。图中实心圆点表示在 closed closed 表中的节点，表中的节点，空心圆点表示在空心圆点表示在openopen表中还未扩展的节点。表中还未扩展的节点。下图（下图

9、（a a）是扩展节点）是扩展节点1 1之前的搜索图和搜索树，而（之前的搜索图和搜索树，而（b b）是扩）是扩展节点展节点1 1之后的搜索图和搜索树。之后的搜索图和搜索树。 节点节点1扩展之前扩展之前节点节点1扩展之后扩展之后8节点节点1扩展之前扩展之前节点节点1扩展之后扩展之后同时要考虑修改节点同时要考虑修改节点2的后继节点的后继节点4的返回的返回指针和指针和g (4)的值，将的值，将节点节点4指向节点指向节点2，并，并把原来指向节点把原来指向节点6的的指针断开。指针断开。当节点当节点1扩展时，产生节点扩展时，产生节点2。而节点。而节点2是是closed 表中的节点，节点表中的节点，节点2的新

10、的新g(2)值为值为2（设相邻两节点（设相邻两节点之间的代价均为之间的代价均为1），而原来），而原来g(2) 值为值为4，故将节，故将节点点2的指针指向节点的指针指向节点1，将原来指向节点，将原来指向节点3的指针断的指针断开。开。9例1：水壶问题 给定4l和3l的水壶各一个，水壶上没有刻度，可以向水壶中加水。如何在4l的壶中准确地得到2l水？ 这里：用(x,y)4l壶里的水有xl，3l壶里的水有yl，n表示搜索空间中的任一节点。则给出下面的启发式函数： 10 h(n) = 2 如果0 x 4并且0 y 3 = 4 如果0 x 4或者0 y 0 （2）h (n)是是h*(n)的下界，即对任意节点

11、的下界，即对任意节点n均有均有h(n)h*(n)则称这样得到的算法为则称这样得到的算法为a*算法算法。h(n)h* (n)的限制十分重要，它保证的限制十分重要，它保证a*算法能算法能够找到最优解。够找到最优解。a*算法算法19在下图所示的八数码问题中，假定在下图所示的八数码问题中，假定h(n) = w(n)(w(n)表示节点表示节点n中不在目标状态中的相应位置的数码个中不在目标状态中的相应位置的数码个数数)。尽管我们并不知道。尽管我们并不知道h*(n)具体为多少，但当采具体为多少，但当采用单位代价时，通过对用单位代价时，通过对“不在目标状态中相应位不在目标状态中相应位置的数码个数置的数码个数”

12、的估计，可以得出至少需要移动的估计，可以得出至少需要移动w(n)步才能够到达目标，显然步才能够到达目标，显然w(n)w*(n)。因此它满足因此它满足a*算法的要求，所以如图所示的路径算法的要求，所以如图所示的路径是最短路径。是最短路径。 a*算法算法20图 八数码问题的全局择优搜索树 初始：0+421在八数码问题中，还可以定义启发函数在八数码问题中，还可以定义启发函数h(n) = p(n)(p(n)为节点为节点n的每一数码与其目标位置之间的每一数码与其目标位置之间的距离总和。显然有的距离总和。显然有w(n)p(n)w*(n)，相应的搜，相应的搜索过程也是索过程也是a*算法。算法。然而然而p(n

13、)比比w(n)有更强的启发性信息，因为由有更强的启发性信息，因为由h(n) = p(n)构造的启发式搜索树，比构造的启发式搜索树，比h(n) = w(n)构造的构造的启发式搜索树节点数要少。启发式搜索树节点数要少。注意：启发函数h(n)可以有多种设计方法。223.3.53.3.5 迭代加深迭代加深a*算法算法 由于由于a a* *算法把所有生成的节点保存在内存中，所算法把所有生成的节点保存在内存中，所以以a a* *算法在耗尽计算时间之前一般早已经把空间算法在耗尽计算时间之前一般早已经把空间耗尽了。耗尽了。目前开发了一些新的算法，它们的目的是为了克目前开发了一些新的算法，它们的目的是为了克服空

14、间问题。服空间问题。但一般不满足最优性或完备性，如迭代加深但一般不满足最优性或完备性，如迭代加深a a* *算算法法idaida* *、简化内存受限、简化内存受限a a* *算法算法smasma* *等。等。下面简单介绍迭代加深下面简单介绍迭代加深a a* *算法（算法（idaida* *算法）。算法）。 23迭代加深迭代加深a*算法算法迭代加深搜索算法的基本思想迭代加深搜索算法的基本思想 它以深度优先的方式在有限制的深它以深度优先的方式在有限制的深度内搜索目标节点。度内搜索目标节点。 在每个深度上，该算法在这个深度在每个深度上，该算法在这个深度上检查目标节点是否出现，如果出现则上检查目标节点

15、是否出现，如果出现则停止，否则深度加停止，否则深度加1 1继续搜索。继续搜索。24而而a a* *算法算法是选择具有最小估价函数值是选择具有最小估价函数值的节点扩展。的节点扩展。迭代加深迭代加深a a* *搜索算法搜索算法idaida* *是上述两种是上述两种算法的结合。算法的结合。这里启发式函数用做深度的限制，而这里启发式函数用做深度的限制，而不是选择扩展节点的排序。不是选择扩展节点的排序。迭代加深迭代加深a*算法算法25迭代加深迭代加深a*算法（算法（ida*算法）算法）procedure ida*算法算法begin (1) 初始化当前的深度限制初始化当前的深度限制c=1 (2) 把初始节

16、点压入栈把初始节点压入栈; 并假定并假定 (3) while 栈不空桥栈不空桥do begin 弹出栈顶元素弹出栈顶元素n if n=goal, then 结束结束, 返回返回n以及从初始节点到以及从初始节点到n的路径的路径 else do begin for n 的每个子节点的每个子节点 if , then 把把 压入栈压入栈 else end for end end while (4) if 栈为空并且栈为空并且 , then 停止并退出停止并退出 (5) if 栈为空并且栈为空并且 , then , 并返回并返回2 end cncnf)(n)(,min(nfcc c ccc26上述算法涉

17、及了两个深度限制上述算法涉及了两个深度限制: : (1)(1)如果栈中所含节点的所有子节点的如果栈中所含节点的所有子节点的f f值小于值小于限制值限制值c,c,则把这些子节点压如栈中以满足迭代则把这些子节点压如栈中以满足迭代加深算法的加深算法的深度优先准则深度优先准则. . (2)(2)如果不这样如果不这样, ,即节点即节点n n的一个或多个子节点的一个或多个子节点 的的f f值大于限制值值大于限制值c,c,则节点则节点n n的的 值设置为值设置为该算法终止的条件为该算法终止的条件为: : (1) (1)找到目标节点找到目标节点( (成功结束成功结束); ); (2) (2)栈为空并且限制值栈

18、为空并且限制值 。迭代加深迭代加深a*算法算法nc)(,min(nfc c27idaida* *算法和算法和a a* *算法相比，主要优点是对于内存算法相比，主要优点是对于内存的需求。的需求。a a* *算法需要指数级数量的存储空间，算法需要指数级数量的存储空间，因为没有深度方面的限制。而因为没有深度方面的限制。而idaida* *算法只有当算法只有当节点节点n n的所有子节点的所有子节点 的的 小于限制值小于限制值c c时才时才扩展它扩展它, ,这样就可以节省大量的内存。这样就可以节省大量的内存。另一问题是当启发式函数是最优的时候，另一问题是当启发式函数是最优的时候，idaida* *算法和算法和a a* *算法扩展相同的节点，并且可以找到算法扩展相同的节点，并且可以找到最优路径。最优路径。迭代加深迭代加深a*算法算法n)(nf28作业作业 1. 如何理解如何理解a*算法？它与通用图搜索算法算法？它与通用图搜索算法有什么关系？有什么关系？ 2. 对于八数码问题，设初始状态和目标状态对于八数码问题，设初始状态和目标状态如下图所示：如下图所示：29作业作业 若用若用d (x)表示节点表示节点x在搜索树中的深度，在搜索树中的深度，