第二章2启发式搜索

1、问题求解的基本方法启发式搜索 2盲目搜索 3盲目搜索算法的缺点：盲目应对之道：应对之道：引入与应用领域相关的启发式知识来指导引入与应用领域相关的启发式知识来指导OPEN表中节点的排序表中节点的排序 4 局部排序局部排序-这是对深度优先法的改进，仅这是对深度优先法的改进，仅对新扩展出来的子节点排序，使这些节点中对新扩展出来的子节点排序，使这些节点中最有希望者能优先取出考察和扩展最有希望者能优先取出考察和扩展 全局排序全局排序-对对OPEN表中的所有节点排表中的所有节点排序，使最有希望的节点排在表首序，使最有希望的节点排在表首 5启发式搜索启发式搜索 概念：在搜索过程中，引入启发式知识减少搜索的盲

2、概念：在搜索过程中，引入启发式知识减少搜索的盲目性，提高搜索的效率，称之为启发式搜索目性，提高搜索的效率，称之为启发式搜索启发式知识对搜索的作用：启发式知识对搜索的作用： 选择下一个要被扩展的节点，对选择下一个要被扩展的节点，对OPEN表进行排序表进行排序 在扩展一个节点时，仅仅有选择性的生成部分有用的节在扩展一个节点时，仅仅有选择性的生成部分有用的节点点 修剪掉某些估计不可能导致成功的子节点修剪掉某些估计不可能导致成功的子节点 6启发式搜索启发式搜索-算法算法A应用评价函数来实现启发式搜索的典型是算法应用评价函数来实现启发式搜索的典型是算法A ，评，评价函数价函数f(n)： f(n)= g(

3、n) + h(n)n-搜索图中的某个当前被扩展的节点；搜索图中的某个当前被扩展的节点；f(n)-从初始状态节点从初始状态节点s, 经由节点经由节点n到达目标状态节点到达目标状态节点n ng，估计的最小路径代价，估计的最小路径代价g(n)-从从s到到n ,估计的最小路径代价；估计的最小路径代价；h(n)-从从n到到ng,估计的最小路径代价；估计的最小路径代价； 7g(n)是已知的h(n)是未知的，需要采用启发式函数来估算，称为启发式函数 8算法算法A搜索算法搜索算法A的一般过程：的一般过程：1） G := s； 2） OPEN := (s), CLOSE := ()； 3） 若若OPEN是空表，

4、则算法以失败结束；是空表，则算法以失败结束； 4） n := MOVE-FIRST(OPEN)；5） 若若n是目标状态节点，则搜索成功结束，并给出解答路是目标状态节点，则搜索成功结束，并给出解答路径；径；6） 扩展节点扩展节点n,将非节点将非节点n祖先的子节点置于子节点集合祖先的子节点置于子节点集合SNS中，中， 并插入搜索图并插入搜索图G中，对于中，对于SNS中每个子节点中每个子节点n ni,计算计算 f(n,n ni) = g(n,ni) + h(ni); 97） 标记和修改指针标记和修改指针 把把SNS中的子节点分为三类（同一般图搜索算法）中的子节点分为三类（同一般图搜索算法） 加第加第

5、1类子节点于类子节点于OPEN表（同一般图搜索算法）表（同一般图搜索算法） 比较第比较第2类子节点类子节点ni经由新、老父节点的评价函数值经由新、老父节点的评价函数值f(n,ni)、f(ni);若若f(n,ni) f(ni)点点,则令则令f(ni) = f(n,ni),并移动子节点指并移动子节点指向老父节点的指针，改为指向新父节点向老父节点的指针，改为指向新父节点 对第对第3类子节点作与第类子节点作与第2类同样的处理，并把这些子节点从类同样的处理，并把这些子节点从CLOSE表中移出，重新加入表中移出，重新加入OPEN表。表。8）按）按f值从小到大排序值从小到大排序OPEN表中的节点表中的节点

6、9) 返回语句返回语句3）；）； 10启发式搜索算法启发式搜索算法A结论结论按按f(n)排序排序OPEN表中的节点表中的节点 f(n)值最小者排在首位，优先加以扩展值最小者排在首位，优先加以扩展 体现了最佳优先体现了最佳优先(best-first)搜索策略的思想搜索策略的思想 11算法算法A举例：举例：8数码游戏数码游戏f(n) = g(n) + h(n)g(n)=d(n)-当前被考察和扩展的节点当前被考察和扩展的节点n在搜索图中的在搜索图中的节点深度节点深度 h(n)=w(n) -节点节点n与目标状态节点与目标状态节点n ng相比较，错位的相比较，错位的棋牌个数棋牌个数 12初始节点：初始节

7、点： f(n) = 0 + 4 = 4 13 14 二二 实现启发式搜索的关键因素实现启发式搜索的关键因素（1）搜索算法的可采纳性）搜索算法的可采纳性(Admissibility) 在搜索图存在从初始状态节点到目标状态节点在搜索图存在从初始状态节点到目标状态节点解答路径的情况下，若一个搜索法总能找到解答路径的情况下，若一个搜索法总能找到最短最短（代价最小）的解答路径，则称算法具有可采纳性（代价最小）的解答路径，则称算法具有可采纳性 宽度优先的搜索算法就是可采纳的宽度优先的搜索算法就是可采纳的 15引入评价函数引入评价函数f f* *: f f* *(n)=g(n)=g * *(n)+h(n)+

8、h * *(n)(n) f f*(n)(n)、g g*(n)(n)、h h*(n)(n)分别指示当经由节点分别指示当经由节点n的的最短最短（代价最小）解答路径找到时（代价最小）解答路径找到时实际的实际的路经代价路经代价（长度）、该路径前段（自初始状态节点到节点（长度）、该路径前段（自初始状态节点到节点n）代价和后段（自节点代价和后段（自节点n到目标状态节点）代价。到目标状态节点）代价。 将评价函数将评价函数f与与f f*相比较，实际上，相比较，实际上，f(n)f(n)、g(n)和和h(n)分别是分别是f f*(n)、g g*(n)(n)和和h h*(n)(n)的近似值。的近似值。 在理想的情况

9、下，设计评价函数在理想的情况下，设计评价函数f时可以让时可以让g(n)g(n) = g g*(n)(n),h(n) = h h*(n)(n) 16如何挖掘贴切的启发式知识如何挖掘贴切的启发式知识(h(n)是设计评价函数乃是设计评价函数乃至算法至算法A的关键的关键 在前述的八数码游戏中，在前述的八数码游戏中，h(n)采用了采用了w(n)现在采用现在采用p(n)-节节点点n与目标状态节点相比较，每与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和状态相应位置所需走步（移动次数）的总和 17 18可以

10、证明，若确保对于搜索图中的节点可以证明，若确保对于搜索图中的节点n n，总是，总是有有h(n) h(n) h h* * (n), (n), 则算法则算法A A具有可采纳性具有可采纳性即总能搜索到最短（代价最小）的解答路径即总能搜索到最短（代价最小）的解答路径我们称满足我们称满足h(n) h(n) h h* * (n) (n)的算法的算法A A为为A A* *宽度优先算法，是一种特殊的宽度优先算法，是一种特殊的A*算法算法h(n) 0 19实例实例传教士和野人问题传教士和野人问题N=5,K h(n) h h* * (n), (n),则则h(n)h(n)过强，使算法过强，使算法A A失去可采纳失去

11、可采纳性，从而不能确保找到最短解答路径性，从而不能确保找到最短解答路径设计接近、又总是设计接近、又总是 h h* * (n) (n)的的h(n)h(n)成为应用成为应用A A* *算法搜索算法搜索问题解答的关键，以压缩搜索图，提高搜索效率问题解答的关键，以压缩搜索图，提高搜索效率 23(3) (3) 设计设计h(n)h(n)的实用考虑的实用考虑f(n) = g(n) + h(n)使用评价函数使用评价函数f(n) = g(n) + wh(n)f(n) = g(n) + wh(n)w w用作加权用作加权 在搜索图的浅层（上部），可让在搜索图的浅层（上部），可让w w取较大值，以使取较大值，以使g(

12、n)g(n)所占比例很小，从而突出启发式函数的作用，加速向纵深所占比例很小，从而突出启发式函数的作用，加速向纵深方向搜索；一旦搜索到较深的层次，又让方向搜索；一旦搜索到较深的层次，又让w w取较小值，以取较小值，以使使g(n)g(n)所占比例很大，并确保所占比例很大，并确保wh(n)wh(n)h h* * (n), (n),从而引导搜从而引导搜索向横广方向发展，寻找到较短的解答路径。索向横广方向发展，寻找到较短的解答路径。 24三三 回溯策略和回溯策略和 爬山法爬山法 在在g(n)0的情况下，若限制只用评价函数的情况下，若限制只用评价函数 f(n)= h(n)去去排序新扩展出来的子节点排序新扩

13、展出来的子节点，即局部，即局部排序，就可实现较为简单的搜索策略：回溯策排序，就可实现较为简单的搜索策略：回溯策略和爬山法略和爬山法 爬山法适用于能逐步求精的问题爬山法适用于能逐步求精的问题 25（1）爬山法爬山法 爬山法实际上就是求函数极大值问题，不过这爬山法实际上就是求函数极大值问题，不过这里不是用数值解法，而是依赖于启发式知识，试里不是用数值解法，而是依赖于启发式知识，试探性地逐步向顶峰逼近（广义地，逐步求精），探性地逐步向顶峰逼近（广义地，逐步求精），直到登上顶峰直到登上顶峰 在爬山法中，限制只能向山顶爬去，即向目标在爬山法中，限制只能向山顶爬去，即向目标状态逼近，不准后退，从而简化了搜

14、索算法；即状态逼近，不准后退，从而简化了搜索算法；即不需设置不需设置OPEN和和CLOSE表，因为没有必要保存表，因为没有必要保存任何待扩展节点任何待扩展节点 26爬山法对于爬山法对于单一极值问题单一极值问题（登单一山峰）十分（登单一山峰）十分有效而又简便，但对于具有多极值的问题就无有效而又简便，但对于具有多极值的问题就无能为力了，因为很可能会因错登上次高峰而失能为力了，因为很可能会因错登上次高峰而失败败-不能到达最高峰不能到达最高峰 27 28（2）回溯策略）回溯策略 保存了每次扩展出的子节点，并按保存了每次扩展出的子节点，并按h(n)值从值从小到大排列小到大排列 相当于爬山的过程中记住了途

15、经的岔路口，相当于爬山的过程中记住了途经的岔路口，只要当前路径搜索失败就回溯（退回）到时序上只要当前路径搜索失败就回溯（退回）到时序上最近的岔路口，向另一路径方向搜索最近的岔路口，向另一路径方向搜索 可以确保最后到达最高峰（即目标状态）。可以确保最后到达最高峰（即目标状态）。 29令令PATH、SNL、n、n 为局部变量：为局部变量： P A T H - - 节 点 列 表 ， 指 示 解 答 路 径 ；节 点 列 表 ， 指 示 解 答 路 径 ； S N L - - 当 前 节 点 扩 展 出 的 子 节 点 列 表 ；当 前 节 点 扩 展 出 的 子 节 点 列 表 ； MOVE-FI

16、RST(SNL)-把把SNL表首的节点移出，作为下一次表首的节点移出，作为下一次要加以扩展的节点；要加以扩展的节点； n、 n -分别指示当前考察和下一次考察的节点。分别指示当前考察和下一次考察的节点。该递归过程的算法就取名为该递归过程的算法就取名为BACKTRACK(n),参数参数n为当前被为当前被扩展的节点，算法的初次调用式是扩展的节点，算法的初次调用式是BACKTRACK(s),s即为初即为初始状态节点。始状态节点。 30算法的步骤如下：算法的步骤如下：（1） 若若n是目标状态节点，则算法的本次调用成功结束，是目标状态节点，则算法的本次调用成功结束，返回空表；返回空表；（2） 若若n是失

17、败状态，则算法的本次调用失败结束，返回是失败状态，则算法的本次调用失败结束，返回FAIL；（3） 扩展节点扩展节点n，将生成的子节点置于列表，将生成的子节点置于列表SNL，并按评，并按评价函数价函数f(k) = h(k)的值从小到大排序（的值从小到大排序（k指示子节点）；指示子节点）；(4） 若若SNL为空，则算法的本次调用失败结束，返回为空，则算法的本次调用失败结束，返回FAIL；（5） n= MOVE-FIRST(SNL)；（6） PATH = BACKTRACK(n)；（7）若）若PATH =FAIL, 返回到语句（返回到语句（4）；）；（8） 将将n加到加到PATH表首，算法的本次调用

18、成功结束，返表首，算法的本次调用成功结束，返回回PATH。 31失败状态通常意指三种情况：失败状态通常意指三种情况：（1）不合法状态（如传教士和野人问题中所述的那）不合法状态（如传教士和野人问题中所述的那样）样）（2）旧状态重现（如八数码游戏中某一棋盘布局的）旧状态重现（如八数码游戏中某一棋盘布局的重现，会导致搜索算法死循环）重现，会导致搜索算法死循环）（3）状态节点深度超过预定限度（例如八数码游戏）状态节点深度超过预定限度（例如八数码游戏中，指示解答路径不超过中，指示解答路径不超过6步）。步）。 32 皇后问题 33 34四四 状态空间抽象和生成状态空间抽象和生成-测试法测试法 状态空间抽象

19、策略适合寻找令人满意的解答状态空间抽象策略适合寻找令人满意的解答 生成生成-测试法用于最优化问题测试法用于最优化问题 35（1）状态空间抽象策略）状态空间抽象策略 状态空间抽象是减少搜索量的重要技术。常用的方式是状态空间抽象是减少搜索量的重要技术。常用的方式是将状态空间按子问题进行划分，子问题构成抽象空间。显然，将状态空间按子问题进行划分，子问题构成抽象空间。显然，抽象空间中的一个搜索与步抽象空间中的一个搜索与步(一个子问题一个子问题)对应于实际状态空对应于实际状态空间中的许多步，因而抽象空间小得多，使搜索大幅度加快间中的许多步，因而抽象空间小得多，使搜索大幅度加快 36（2）生成）生成-测试

20、法测试法 搜索过程由两个部件合作完成：可能解的生成器搜索过程由两个部件合作完成：可能解的生成器和修剪不正确解答的测试器。和修剪不正确解答的测试器。 在搜索过程中，生成器和测试器的工作往往需交在搜索过程中，生成器和测试器的工作往往需交替进行。替进行。 使用生成使用生成-测试法应考虑的关键问题是如何在生成测试法应考虑的关键问题是如何在生成器和测试器之间分配知识器和测试器之间分配知识 经验证明，知识丰富的生成器会导致较高的搜索经验证明，知识丰富的生成器会导致较高的搜索效率效率 37 38五五 启发式搜索的适用性讨论启发式搜索在人工智能研究的启发式搜索在人工智能研究的早期早期是很重要的议是很重要的议题

21、，甚至有人说人工智能就是启发式搜索。题，甚至有人说人工智能就是启发式搜索。但随着知识工程的兴起，启发式搜索已较少用于但随着知识工程的兴起，启发式搜索已较少用于作为人工智能系统的顶层控制结构，尤其是使用作为人工智能系统的顶层控制结构，尤其是使用全局评价器的启发式搜索方法，因为其不适合知全局评价器的启发式搜索方法，因为其不适合知识密集型的问题求解。识密集型的问题求解。 但启发式搜索仍不失为重要技术用于解决某些适但启发式搜索仍不失为重要技术用于解决某些适合于它的子问题，且搜索技术的不少思想方法可合于它的子问题，且搜索技术的不少思想方法可用于用于KB系统的设计。系统的设计。 39启发式搜索技术面临启发式搜索技术面临三个关键三个关键选择：选择： 确定性或非确定性搜索方式；确定性或非确定性搜索方式； 搜索目标状态本身还是达到目标状态的解搜索目标状态本身还是达到目标状态的解答路径答路径(往往表示为状态或操作算子序列往往表示为状态或操作算子序列)； 搜索一个还是全部或最优解答。搜索一个还是全部或最优解答。 所谓确定性方式，就是利用启发式信息选取所谓确定性方式，就是利用启发式信息选取最好的分枝，而舍弃所有其余分枝不再予以考虑最好的分枝，而舍弃所有