第二章2启发式搜索

问题求解的基本方法

启发式搜索№2盲目搜索№3盲目搜索算法的缺点：

盲目应对之道：

引入与应用领域相关的启发式知识来指导OPEN表中节点的排序№4

局部排序--这是对深度优先法的改进，仅对新扩展出来的子节点排序，使这些节点中最有希望者能优先取出考察和扩展

全局排序--对OPEN表中的所有节点排序，使最有希望的节点排在表首

№5启发式搜索概念：在搜索过程中，引入启发式知识减少搜索的盲目性，提高搜索的效率，称之为启发式搜索启发式知识对搜索的作用：选择下一个要被扩展的节点，对OPEN表进行排序在扩展一个节点时，仅仅有选择性的生成部分有用的节点修剪掉某些估计不可能导致成功的子节点№6启发式搜索-算法A

应用评价函数来实现启发式搜索的典型是算法A，评价函数f(n)：

f(n)=g(n)+h(n)n--搜索图中的某个当前被扩展的节点；f(n)--从初始状态节点s,经由节点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）n:=MOVE-FIRST(OPEN)；

5）若n是目标状态节点，则搜索成功结束，并给出解答路径；

6）扩展节点n,将非节点n祖先的子节点置于子节点集合SNS中，并插入搜索图G中，对于SNS中每个子节点ni,计算f(n,ni)=g(n,ni)+h(ni);

№97）标记和修改指针把SNS中的子节点分为三类（同一般图搜索算法）加第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表中的节点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与目标状态节点ng相比较，错位的棋牌个数

№12初始节点：f(n)=0+4=4

№13№14二实现启发式搜索的关键因素（1）搜索算法的可采纳性(Admissibility)

在搜索图存在从初始状态节点到目标状态节点解答路径的情况下，若一个搜索法总能找到最短（代价最小）的解答路径，则称算法具有可采纳性

宽度优先的搜索算法就是可采纳的

№15引入评价函数f*:f*(n)=g*(n)+h*(n)f*(n)、g*(n)、h*(n)分别指示当经由节点n的最短（代价最小）解答路径找到时实际的路经代价（长度）、该路径前段（自初始状态节点到节点n）代价和后段（自节点n到目标状态节点）代价。

将评价函数f与f*相比较，实际上，f(n)、g(n)和h(n)分别是f*(n)、g*(n)和h*(n)的近似值。

在理想的情况下，设计评价函数f时可以让g(n)=g*(n),h(n)=h*(n)

№16如何挖掘贴切的启发式知识(h(n))是设计评价函数乃至算法A的关键

在前述的八数码游戏中，h(n)采用了w(n)现在采用p(n)----节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和

№17№18可以证明，若确保对于搜索图中的节点n，总是有h(n)≤h*(n),则算法A具有可采纳性即总能搜索到最短（代价最小）的解答路径我们称满足h(n)≤h*(n)的算法A为A*宽度优先算法，是一种特殊的A*算法h(n)≡0№19实例传教士和野人问题N=5,K<=3左岸传教士人数M，野人C，船是否在左岸BH(n)=M+C-2B№20（5,5,1）（5,4,0）（5,3,0）（5,2,0）（4,4,0）（5,4,1）（5,3,1）（3,3,0）（5,1,0）（5,0,0）（4,4,1）（5,2,1）（5,1,1）（2,2,0）（3,3,1）（0,3,0）（0,4,1）（0,5,1）（0,1,0）（0,2,0）（0,4,0）（1,1,1）（0,2,1）（0,3,1）（2,2,1）（0,0,0）（1,1,0）№21№22(2)启发式函数的强弱及其影响用h(n)接近h*(n)的程度去衡量启发式函数的强弱h(n)＜h*(n)且两者差距较大时，h(n)过弱当h(n)>h*(n),则h(n)过强，使算法A失去可采纳性，从而不能确保找到最短解答路径设计接近、又总是≤h*(n)的h(n)成为应用A*算法搜索问题解答的关键，以压缩搜索图，提高搜索效率№23(3)设计h(n)的实用考虑f(n)=g(n)+h(n)使用评价函数f(n)=g(n)+wh(n)w用作加权在搜索图的浅层（上部），可让w取较大值，以使g(n)所占比例很小，从而突出启发式函数的作用，加速向纵深方向搜索；一旦搜索到较深的层次，又让w取较小值，以使g(n)所占比例很大，并确保wh(n)≤h*(n),从而引导搜索向横广方向发展，寻找到较短的解答路径。№24三回溯策略和爬山法在g(n)≡0的情况下，若限制只用评价函数f(n)=h(n)去排序新扩展出来的子节点，即局部排序，就可实现较为简单的搜索策略：回溯策略和爬山法爬山法适用于能逐步求精的问题

№25（1）爬山法

爬山法实际上就是求函数极大值问题，不过这里不是用数值解法，而是依赖于启发式知识，试探性地逐步向顶峰逼近（广义地，逐步求精），直到登上顶峰

在爬山法中，限制只能向山顶爬去，即向目标状态逼近，不准后退，从而简化了搜索算法；即不需设置OPEN和CLOSE表，因为没有必要保存任何待扩展节点

№26爬山法对于单一极值问题（登单一山峰）十分有效而又简便，但对于具有多极值的问题就无能为力了，因为很可能会因错登上次高峰而失败--不能到达最高峰

№27№28（2）回溯策略

保存了每次扩展出的子节点，并按h(n)值从小到大排列相当于爬山的过程中记住了途经的岔路口，只要当前路径搜索失败就回溯（退回）到时序上最近的岔路口，向另一路径方向搜索

可以确保最后到达最高峰（即目标状态）。№29令PATH、SNL、n、n'为局部变量：

PATH--节点列表，指示解答路径；

SNL--当前节点扩展出的子节点列表；

MOVE-FIRST(SNL)--把SNL表首的节点移出，作为下一次要加以扩展的节点；

n、n'--分别指示当前考察和下一次考察的节点。该递归过程的算法就取名为BACKTRACK(n),参数n为当前被扩展的节点，算法的初次调用式是BACKTRACK(s),s即为初始状态节点。№30算法的步骤如下：（1）若n是目标状态节点，则算法的本次调用成功结束，返回空表；（2）若n是失败状态，则算法的本次调用失败结束，返回'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表首，算法的本次调用成功结束，返回PATH。№31失败状态通常意指三种情况：（1）不合法状态（如传教士和野人问题中所述的那样）（2）旧状态重现（如八数码游戏中某一棋盘布局的重现，会导致搜索算法死循环）（3）状态节点深度超过预定限度（例如八数码游戏中，指示解答路径不超过6步）。№32

皇后问题№33№34四状态空间抽象和生成-测试法

状态空间抽象策略适合寻找令人满意的解答

生成-测试法用于最优化问题

№35（1）状态空间抽象策略状态空间抽象是减少搜索量的重要技术。常用的方式是将状态空间按子问题进行划分，子问题构成抽象空间。显然，抽象空间中的一个搜索与步(一个子问题)对应于实际状态空间中的许多步，因而抽象空间小得多，使搜索大幅度加快№36（2）生成-测试法搜索过程由两个部件合作完成：可能解的生成器和修剪不正确解答的测试器。在搜索过程中，生成器和测试器的工作往往需交替进行。

使用生成-测试法应考虑的关键问题是如何在生成器和测试器之间分配知识

经验证明，知识丰富的生成器会导致较高的搜索效率

№37№38五启发式搜索的适用性讨论启发式搜索在人工智能研究的早期是很重要的议题，甚至有人说人工智能就是启发式搜索。但随着知识工程的兴起，启发式搜索已较少用于作为人工智能系统的顶层控制结构，尤其是使用全局评价器的启发式搜索方法，因为其不适合知识密集型的问题求解。

但启发式搜索仍不失为重要技术用于解决某些适合于它的子问题，且搜索技术的不少思想方法可用于KB系统的设计。

№39启发式搜索技术面临三个关键选择：

确定性或非确定性搜索方式；

搜索目标状态本身还是达到目标状态的解答路径(往往表示为状态或操作算子序列)；

搜索一个还是全部或最优解答。

所谓确定性方式，就是利用启发式信息选取最好的分枝，而舍弃所有其余分枝不再予以考虑

常用的非确定性搜索方式又可分为两类：最佳优先和深度优先加回溯№40然而无论是最佳优先或深度优先加回溯，都是十分低效率的，尤其是后者更招致了严厉的批评。

避免回溯成为人工智能研究的一个重要课题，研究明显地向确定性方式倾斜，概括如下：

(1)有些应用领域只能使用确定性搜索方式。如下棋程序，一旦落子，即使是