第3章(搜索推理技术2图启发搜索)课件.ppt

1、人人 工工 智智 能能Artificial Intelligence (AI)第第3章章 搜索推理技术搜索推理技术 3.1 图的搜索策略图的搜索策略3.2 盲目搜索盲目搜索3.3 启发式搜索启发式搜索3.4 与或树搜索（与或树搜索（补充补充）3.5 博弈树搜索（博弈树搜索（补充补充）3.6 消解原理消解原理3.3 启发式搜索启发式搜索宽度和深度优先搜索的宽度和深度优先搜索的 缺点缺点：扩展节点的顺序是人为规定的，要扩展节点的数扩展节点的顺序是人为规定的，要扩展节点的数目可能非常大，占用大量的计算时间和内存空间，目可能非常大，占用大量的计算时间和内存空间，使得搜索效率低使得搜索效率低等代价搜索技

2、术的等代价搜索技术的 缺点缺点选取已经搜索到的代价最小的节点来扩展，但是选取已经搜索到的代价最小的节点来扩展，但是没有考虑目标状态，不知道离目标状态还有多远，没有考虑目标状态，不知道离目标状态还有多远，还需要付出多大的代价还需要付出多大的代价提高搜索效率的提高搜索效率的 思路思路：利用更多的与问题有关的信息来选取待扩展利用更多的与问题有关的信息来选取待扩展的节点的节点 3.3.1 启发式搜索策略和估价函数启发式搜索策略和估价函数启发信息（背景知识）启发信息（背景知识）：与具体问题特性有：与具体问题特性有关的一些信息。（在具体的使用过程中，还与使用关的一些信息。（在具体的使用过程中，还与使用人、

3、算法有关）人、算法有关）启发式搜索方法启发式搜索方法：利用启发信息的搜索方法：利用启发信息的搜索方法 ，避免宽度优先或，避免宽度优先或深度优先搜索中的盲目（人为规定）地选择扩展深度优先搜索中的盲目（人为规定）地选择扩展节点节点 在扩展一个节点的过程中，用于决定要生成哪一在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，避免盲目地同时生成所有个或哪几个后继节点，避免盲目地同时生成所有可能的后继节点可能的后继节点 用于决定某些应该从搜索树中抛弃或修剪的节点用于决定某些应该从搜索树中抛弃或修剪的节点 搜索技术中启发信息的用途搜索技术中启发信息的用途：本节的关注点本节的关注点：利用启发信息

4、来决定下一个要扩展的节点利用启发信息来决定下一个要扩展的节点有序搜索有序搜索：在搜索过程总是选择在搜索过程总是选择“ “ 最有希最有希望望 ”的节点作为下一个被扩展节点的搜索技术的节点作为下一个被扩展节点的搜索技术估价函数估价函数：用来估算节点：用来估算节点“ “ 希望希望 ”程度的程度的函数函数 一般情况下，估计函数值越大，希望程度就越一般情况下，估计函数值越大，希望程度就越低低 根据搜索过程、问题的启发信息来定义的，对根据搜索过程、问题的启发信息来定义的，对搜索效率会产生较大的影响搜索效率会产生较大的影响希望希望估价估价函数函数估价函数的基本特性估价函数的基本特性： 用用 f (n) 表示

5、节点表示节点 n 的估价函数值，并且期的估价函数值，并且期望，它是从起始节点、通过节点望，它是从起始节点、通过节点 n 、到达目到达目标节点的最小代价的一个标节点的最小代价的一个估计值估计值起始节点起始节点节点节点 n目标节点目标节点计算一个节点的计算一个节点的“ 估价函数估价函数 ” ，可，可以分成两个部分：以分成两个部分：已经付出的代价（已经付出的代价（起始节点到当前起始节点到当前节点节点）将要付出的代价（将要付出的代价（当前节点到目标当前节点到目标节点节点）估价函数的计算估价函数的计算起始节点起始节点当前节点当前节点目标节点目标节点节点节点 n 的估价函数的估价函数 f ( n ) 定义

6、为从初始定义为从初始节点、经过节点、经过 n 、到达目标节点的路径的到达目标节点的路径的最小代价的估计值，即最小代价的估计值，即 f ( n ) = g ( n ) + h ( n )g ( n ) 是从初始节点到达当前节点是从初始节点到达当前节点 n 的的实际代价实际代价h ( n ) 是从节点是从节点 n 到目标节点的最佳路到目标节点的最佳路径的径的估计代价估计代价节点节点 n目标节点目标节点起始节点起始节点g(n)h(n)h ( n ) 体现出搜索过程中采用的启发式信息（背体现出搜索过程中采用的启发式信息（背景知识），称之为景知识），称之为启发函数启发函数g ( n ) 所占的比重越大，

7、越趋向于宽度优先或等所占的比重越大，越趋向于宽度优先或等代价搜索；反之，代价搜索；反之，h ( n ) 的比重越大，表示启发的比重越大，表示启发性能就越强性能就越强f ( n ) = g ( n ) + h ( n )对于具体问题来说，根据问题的本质及解的性质，对于具体问题来说，根据问题的本质及解的性质，可以定义多种估价函数。可以定义多种估价函数。用不同的估价函数指导用不同的估价函数指导搜索，其效果可能会相差很远。搜索，其效果可能会相差很远。因此，必须尽可因此，必须尽可能选择最能体现问题特性的、最佳的估价函数能选择最能体现问题特性的、最佳的估价函数例：例：八数码问题的估价函数八数码问题的估价函

8、数 f ( n )= g ( n ) + h ( n )g ( n ) 定义为搜索树中定义为搜索树中 n 的深度的深度h ( n ) 可以定义成不同形式可以定义成不同形式 节点节点 n 的状态与目标状态之间数字不在位的状态与目标状态之间数字不在位的个数（错放棋子的个数，不记空格）的个数（错放棋子的个数，不记空格）目标状态目标状态当前状态当前状态 节点节点 n 中每一个数字与目标位置最短距离（每中每一个数字与目标位置最短距离（每一个数字走到目标位置的要走的最少步数）之一个数字走到目标位置的要走的最少步数）之和和目标状态目标状态当前状态当前状态 把中心位置除掉，沿顺时针方向，如果一个数字把中心位置

9、除掉，沿顺时针方向，如果一个数字的跟随数字是目标状态中的数字，则记的跟随数字是目标状态中的数字，则记0分，否则分，否则记记2分。中心位置有数字记分。中心位置有数字记1分，无数字记分，无数字记0分。所分。所有的总和为有的总和为 h(n) 目标状目标状态态当前状当前状态态例：数字例：数字2的跟随的跟随数字是数字是1，而目标，而目标状态的数字应该状态的数字应该是是8有序搜索算法（方法、技术）有序搜索算法（方法、技术）在搜索过程中，在搜索过程中，OPEN表中节点按照其估价函数值表中节点按照其估价函数值以递增顺序排列，选择以递增顺序排列，选择OPEN表中具有最小估价函表中具有最小估价函数值的节点作为下一

10、个待扩展的节点，这种搜索数值的节点作为下一个待扩展的节点，这种搜索方法称为方法称为有序搜索有序搜索这里，介绍尼尔逊这里，介绍尼尔逊(Nilsson)提出的有序搜索的基提出的有序搜索的基本算法：本算法：有序状态空间搜索算法有序状态空间搜索算法3.3.2 有序搜索有序搜索 (1) 把起始节点把起始节点 S 放到放到 OPEN 表中，并计算节点表中，并计算节点 S 的的 f (S) (2) 如果如果 OPEN 是空表，则失败退出（无解）是空表，则失败退出（无解）有序状态空间搜索算法有序状态空间搜索算法：(3) 从从 OPEN 表中选择一个表中选择一个 f 值最小的节点值最小的节点 i 。如果有几个节

11、点值相同，当其中有一个为目如果有几个节点值相同，当其中有一个为目标节点时，则选择目标节点；否则就选择其标节点时，则选择目标节点；否则就选择其中任一个节点作为节点中任一个节点作为节点 i (4) 把节点把节点 i 从从 OPEN 表中移出，并把它放入表中移出，并把它放入 CLOSED 的已扩展节点表中的已扩展节点表中(5) 如果如果 i 是个目标节点，则成功退出（有解）是个目标节点，则成功退出（有解）(6) 扩展节点扩展节点 i ，生成其全部后继节点。对于生成其全部后继节点。对于 i 的的每一个后继节点每一个后继节点 j ：说明：说明：节点节点 j 可以分成三种情形可以分成三种情形： 新产生的节

12、点，即不属于新产生的节点，即不属于OPEN表又不属于表又不属于CLOSED表表（6-1、6-2步）步） 已经产生过的节点，且属于已经产生过的节点，且属于OPEN表，其已经有父节点表，其已经有父节点（6-1、6-3、6-3-1、6-3-2步）步） 已经产生过的节点，且属于已经产生过的节点，且属于CLOSED表，其已经有父节表，其已经有父节点和后继节点（点和后继节点（ 6-1、6-3、6-3-1、6-3-2、6-3-3步步)CLOSED表表OPEN表表有父节点有父节点既父节点又有子节点既父节点又有子节点(6-1) 计算计算 f ( j ) (6-2)如果如果 j 既不在既不在OPEN表中，又不在表

13、中，又不在CLOSED 表中，则用估价函数表中，则用估价函数 f 把它加入把它加入OPEN表相应位置。从表相应位置。从 j 加一个指向其父辈加一个指向其父辈节点节点 i 的指针，以便于反向追踪解的路径的指针，以便于反向追踪解的路径(6-3) 如果如果 j 已在已在 OPEN 表（表（处理与父节点的关系处理与父节点的关系）或或 CLOSED 表（表（处理与父节点和子节点的关处理与父节点和子节点的关系系）中，则比较新的）中，则比较新的 f ( j ) 值和前面计算出来值和前面计算出来的的 f ( j ) 值。如果新的值。如果新的 f ( j ) 值较小，则值较小，则(6-3-1) 用新的值取代旧的

14、值用新的值取代旧的值(6-3-2) 改变指针，从改变指针，从 j 指向指向 i ，删除原来的父辈删除原来的父辈节点指针节点指针(6-3-3) 如果节点如果节点 j 在在 CLOSED 表中，则把它移表中，则把它移回回 OPEN 表表(7) 转向转向(2)旧旧CLOSED表表OPEN表表新新新新新小旧大新小旧大XX移回移回 对于图的搜索，一个节点可能有多个父节点，对于图的搜索，一个节点可能有多个父节点，这一步可以保证具有最小估价函数值的节点当这一步可以保证具有最小估价函数值的节点当作父节点，同时使得搜索得到的子图总是一棵作父节点，同时使得搜索得到的子图总是一棵树树 对于树的搜索，任何节点（除起始

15、节点）只有对于树的搜索，任何节点（除起始节点）只有一个父节点，则可以省略这一步一个父节点，则可以省略这一步步骤步骤6-3的说明的说明后继节点后继节点 j新新节点节点在在Open？在在Closed？新新 f 值小值小调整父节点调整父节点新新 f 值小值小调整父节点调整父节点移回移回Open自动删除子自动删除子节点节点 如果如果 f ( i ) 取节点取节点 i 的深度，这时就是宽度优的深度，这时就是宽度优先搜索先搜索 如果如果 f( i ) 取从起始节点到当前节点取从起始节点到当前节点 i 之间路之间路径的代价，这时就是等代价搜索径的代价，这时就是等代价搜索有序搜索算法的特例有序搜索算法的特例：

16、例：例：八数码问题八数码问题估价函数为：估价函数为： f ( n ) = d ( n ) + W ( n )其中其中:d ( n ) ：节点节点 n 的深度的深度W ( n )：即即 h ( n ) , 节点节点 n 中错放的棋子个数中错放的棋子个数283164754283164752831476528316475646空空1234283147652318476528314765655832147652837146567231847652318476557231847655123847651238476512378465575目目标标节节点点带圆圈的数字表示估价函数的值带圆圈的数字表示估价函数

17、的值不带圆圈的数字表示扩展顺序不带圆圈的数字表示扩展顺序相同值时，同相同值时，同一次扩展按先一次扩展按先后顺序排放，后顺序排放，否则后扩展的否则后扩展的节点放在前面节点放在前面深深度度每一个状态的存储形式每一个状态的存储形式：状态空间法状态空间法：长度为：长度为9的一维数组的一维数组父父 符符 123804765盲目搜索中盲目搜索中：长度为：长度为11的一维数组的一维数组123804765启发搜索中启发搜索中：长度为：长度为14的一维数组的一维数组父父 符符 123804765d ( n ) + W ( n ) = f ( n )例：例：迷宫迷宫人人4321代价代价：关键位置点之间的水平与垂直

18、距离之和：关键位置点之间的水平与垂直距离之和g : 起始位置到当前位置之间的已经走过的距离起始位置到当前位置之间的已经走过的距离h : 当前位置到目标位置的水平与垂直距离之和当前位置到目标位置的水平与垂直距离之和人人4S3E2N1W(1,1) 0+6N3(2,3) 3+3(2,4) 4+2N1S1(2,2) 4+4(1,4) 5+3(3,4) 5+1W1E1(3,3) 6+2(4,4) 6+0E1S1思考题思考题对于下列迷宫，用对于下列迷宫，用有序搜索算法有序搜索算法寻找出从入口到寻找出从入口到出口的一条路径出口的一条路径代价代价：关键位置之间的路程，关键位置之间的路程，其中其中=3.0g:

19、起始位置到当前位置的起始位置到当前位置的已经走过的距离已经走过的距离假设假设：通道是放射状的直线和圆弧：通道是放射状的直线和圆弧h: 当前位置到目标位置的直线和圆弧距离之和的最小值当前位置到目标位置的直线和圆弧距离之和的最小值3.3.3 A*算法算法 特殊的估价函数（对估价函数作出某些规定）特殊的估价函数（对估价函数作出某些规定） h ( n ) h*( n ) 最佳的启发函数值最佳的启发函数值 有序算法的细化（考虑更多的细节）有序算法的细化（考虑更多的细节）例：例：八数码问题八数码问题 h(n) 定义为节点定义为节点 n 中每一个数字与目标位置最中每一个数字与目标位置最短距离（每一个数字走到

20、目标位置的最少步数）短距离（每一个数字走到目标位置的最少步数）之和之和 相邻两个节点之间的代价为相邻两个节点之间的代价为 1思考题思考题：用用C/C+语言编写八数码问题的有序算法程序，语言编写八数码问题的有序算法程序，估价函数可以选择前面介绍的任意一种。估价函数可以选择前面介绍的任意一种。（有能力的同学可以选做，并写到实验报告中有能力的同学可以选做，并写到实验报告中）要求掌握的算法要求掌握的算法：宽度优先搜索算法宽度优先搜索算法深度优先搜索算法深度优先搜索算法等代价搜索算法等代价搜索算法有序算法有序算法作业题：作业题：15243678初始状态初始状态12345678目标状态目标状态利用宽度优先、深度优先、有序搜索算法（启发函数定利用宽度优先、深度优先、有序搜索算法（启发函数定义为数码不在位的个数）找出上述八数码问题从初始状义为数码不在位的个数）找出上述八数码问题从初始状态到目标状态的操作符序列？态到目标状态的操作符序列？1234