人工智能及应用-文档资料

1、1搜索方法搜索方法启发式搜索2启发式搜索启发式搜索l前面讨论的搜索策略中没有考虑问题本身的特前面讨论的搜索策略中没有考虑问题本身的特性信息，而只是按事先规定的路线进行搜索。性信息，而只是按事先规定的路线进行搜索。l如果在搜索过程中使用在搜索过程中获得的问如果在搜索过程中使用在搜索过程中获得的问题自身的一些特性信息来指导搜索显然会有利题自身的一些特性信息来指导搜索显然会有利于搜索。我们将利用问题自身特性信息来引导于搜索。我们将利用问题自身特性信息来引导搜索过程的搜索方法称为启发式搜索。搜索过程的搜索方法称为启发式搜索。3启发性信息的作用启发性信息的作用l启发性信息对搜索的指导作用可归纳为启发性信

2、息对搜索的指导作用可归纳为3个方个方面。面。选择下一个要被扩展的结点。选择下一个要被扩展的结点。在结点扩展时，选择有用的结点。在结点扩展时，选择有用的结点。修剪掉某些不可能导致搜索成功的结点。修剪掉某些不可能导致搜索成功的结点。4估价函数估价函数l启发信息在搜索过程中的主要作用是对结点的启发信息在搜索过程中的主要作用是对结点的重要性进行评估，通过这个评估来实现重要性进行评估，通过这个评估来实现OPEN表中结点的排序表中结点的排序l这个评估一般是通过估价函数实现的。这个评估一般是通过估价函数实现的。5估价函数估价函数l估价函数估价函数f(n)的一般形式为：的一般形式为：f(n)=g(n)+h(n

3、)其中：其中：结点结点n是搜索图中当前被扩展的结点。是搜索图中当前被扩展的结点。f(n)是从初始状态经由结点是从初始状态经由结点n到达目标结点的所有到达目标结点的所有路径中最小路径代价的估计值。路径中最小路径代价的估计值。g(n)是从初始结点到结点是从初始结点到结点n的实际代价。的实际代价。h(n)是从结点是从结点n到达目标结点的最优路径的估计代到达目标结点的最优路径的估计代价。价。6估价函数示例估价函数示例l例：八数码问题。设初始状态和目标状态如下例：八数码问题。设初始状态和目标状态如下图，且估价函数为：图，且估价函数为：f(n)=d(n)+w(n) 其中：其中：d(n)表示结点的结点深度；

4、表示结点的结点深度；w(n)表示表示结点结点n不在位的数码个数。请计算初始状态的不在位的数码个数。请计算初始状态的估价函数值。估价函数值。2 31 8 47 6 52 38 47 6 5S S0 0S Sg g7估价函数示例估价函数示例解：此例估价函数中有解：此例估价函数中有 g(n)=d(n)-路径的深度代表实际代价；路径的深度代表实际代价； h(n)=w(n)-不在位数码说明结点与目标的差不在位数码说明结点与目标的差距。距。 f(S S0 0)=d(S S0 0)+w(S S0 0)=0+4=4 8A算法算法l在一般图搜索算法中，如果每一步都利用估价在一般图搜索算法中，如果每一步都利用估价

5、函数函数f(n)=g(n)+h(n)对对OPEN表中的结点进行表中的结点进行排序，则称该搜索算法为排序，则称该搜索算法为A算法。算法。l由于估价函数带有问题自身的启发性信息，所由于估价函数带有问题自身的启发性信息，所以以A算法也是启发式搜索算法。算法也是启发式搜索算法。9A算法算法-全局择优搜索全局择优搜索l产生一个仅有初始结点产生一个仅有初始结点S S0 0的的OPENOPEN表，建立表，建立一个一个仅有初始结点仅有初始结点S S0 0的图的图G G, ,置置S S0 0的估价函数的估价函数f(Sf(S0 0)=g(S)=g(S0 0)+h(S)+h(S0 0) )；l产生一个空的产生一个空

6、的CLOSEDCLOSED表；表；l如果如果OPENOPEN表为空，则失败退出；表为空，则失败退出；l在在OPENOPEN表的首部取一个结点表的首部取一个结点n n，将其放入，将其放入CLOSEDCLOSED表，在表，在OPENOPEN表删除结点表删除结点n n；10A算法算法-全局择优搜索全局择优搜索l考察结点考察结点n n是否为目标结点，若是，则得到问是否为目标结点，若是，则得到问题的解，成功退出；题的解，成功退出；l若结点不可扩展，则转第若结点不可扩展，则转第3 3步；步；l扩展结点扩展结点n n，计算子结点的，计算子结点的f(ni), f(ni), 并为每一并为每一个子结点指定父结点个

7、子结点指定父结点, ,将子结点放入将子结点放入OPENOPEN表表中；中；l按估价函数为按估价函数为OPENOPEN表中的结点排序，转第表中的结点排序，转第3 3步。步。11A算法算法-全局择优搜索全局择优搜索l例：八数码问题。设初始状态和目标状态如下例：八数码问题。设初始状态和目标状态如下图，且估价函数为：图，且估价函数为： f(n)=d(n)+w(n) 其中：其中：d(n)表示结点的结点深度；表示结点的结点深度；w(n)表示表示结点结点n不在位的数码个数。请使用全局择优搜不在位的数码个数。请使用全局择优搜索求解问题。索求解问题。2 31 8 47 6 52 38 47 6 5S S0 0S

8、 Sg g12A算法算法-全局择优搜索全局择优搜索解：搜索图为 2 31 8 47 6 52 31 8 47 6 52 8 31 47 6 52 3 1 8 47 6 51 2 3 8 47 6 52 8 3 1 47 6 52 8 31 4 7 6 52 8 31 6 47 51 2 38 47 6 5S S0 0S Sg gS S1 1S S2 2S S3 3S S4 4S S5 5S S6 6S S7 7S S8 8444646771 2 37 8 4 6 56313A算法算法-局部择优搜索局部择优搜索l产生一个仅有初始结点产生一个仅有初始结点S S0 0的的OPENOPEN表，建立表，

9、建立一个一个仅有初始结点仅有初始结点S S0 0的图的图G G, ,置置S S0 0的估价函数的估价函数f(Sf(S0 0)=g(S)=g(S0 0)+h(S)+h(S0 0) )；l产生一个空的产生一个空的CLOSEDCLOSED表；表；l如果如果OPENOPEN表为空，则失败退出；表为空，则失败退出；l在在OPENOPEN表的首部取一个结点表的首部取一个结点n n，将其放入，将其放入CLOSEDCLOSED表，在表，在OPENOPEN表删除结点表删除结点n n；14A算法算法-局部择优搜索局部择优搜索l考察结点考察结点n n是否为目标结点，若是，则得到问是否为目标结点，若是，则得到问题的解

10、，成功退出；题的解，成功退出；l若结点不可扩展，则转第若结点不可扩展，则转第3 3步；步；l扩展结点扩展结点n n，计算子结点的，计算子结点的f(ni), f(ni), 并为每一并为每一个子结点指定父结点个子结点指定父结点, , 按估价函数将子结点按估价函数将子结点排序，并放入排序，并放入OPENOPEN表的首部，转第表的首部，转第3 3步。步。15关于关于A算法算法l全局择优搜索：当全局择优搜索：当f(n)=g(n)，算法退化为代，算法退化为代价树广度优先搜索；价树广度优先搜索；f(n)=d(n)，算法退化为，算法退化为广度优先搜索。广度优先搜索。l局部择优搜索：当局部择优搜索：当f(n)=

11、g(n)，算法退化为代，算法退化为代价树深度优先搜索；价树深度优先搜索；f(n)=d(n)，算法退化为，算法退化为深度优先搜索。深度优先搜索。16A*算法算法设设f*(n)是从初始状态经由结点是从初始状态经由结点n到达目标结点到达目标结点的所有路径中最小路径代价值，的所有路径中最小路径代价值，f(n)是它的估是它的估计值。则计值。则f*(n)应由两部分组成：应由两部分组成：g g(n)是从初始结点到结点是从初始结点到结点n的最小代价。的最小代价。h(n)是从结点是从结点n到达目标结点的最优路径的代价到达目标结点的最优路径的代价值，有多个目标结点时取其代价最小者。值，有多个目标结点时取其代价最小

12、者。 所以所以 f*(n)= g g(n)+ h(n)17A*算法算法对对A算法算法-全局择优搜索中的增加如下限制：全局择优搜索中的增加如下限制：lg(n)是对是对g*(n)的估计，并且的估计，并且g(n)0lh(n)是是h*(n)的下界，即对任意结点都有的下界，即对任意结点都有lh(n)h1(n)则被则被A2*扩展的结点一定被扩展的结点一定被A1*扩展。扩展。20A*算法的最优性算法的最优性如果启发函数满足以下两个条件：如果启发函数满足以下两个条件：lh(目标结点目标结点)=0l对任意结点对任意结点n和它的子结点和它的子结点m，都有，都有 0h(n)-h(m) C(n,m) C(n,m)是结

13、点到其子结点的边代价，则称是结点到其子结点的边代价，则称h(n)满足单调限制。满足单调限制。21A*算法的最优性算法的最优性结论：如果结论：如果h满足单调条件，则当满足单调条件，则当A*算法扩展结算法扩展结点点n时，该结点就已经找到通往它的最佳路径，时，该结点就已经找到通往它的最佳路径，即即g(n)=g*(n)22A*算法算法-示例示例l例：八数码问题。设初始状态和目标状态如下例：八数码问题。设初始状态和目标状态如下图，且估价函数为：图，且估价函数为： f(n)=d(n)+w(n) 其中：其中：d(n)表示结点的结点深度；表示结点的结点深度；w(n)表示表示结点结点n不在位的数码个数。请使用不在位的数码个数。请使用A*算法求解算法求解问题。问题。2 31 8 47 6 52 38 47 6 5S S0 0S Sg g23A*算法算法-示例示例解：在前一个例中取解：在前一个例中取 h(n)=w(n) w(n)表示结点表示结点n不在位的数码个数不在位的数码个数 显然有显然有 w(n)h*(n) 即例中的即例中的A算法也是算法也是A*算法。算法。 24A*算法算法-示例示例 还可以选择还可以选择h(n)