资源描述：
《第3章 搜索推理技术ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3章搜索推理技术3.1 图搜索策略1.何谓图搜索图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。2.图搜索算法中的几个重要名词术语(1) OPEN表与CLOSE表 (2) 搜索图与搜索树3.图搜索(GRAPHSEARCH)的一般过程(1) 建立一个只含有起始节点S的搜索图G,把S放到一个叫做OPEN的未扩展节点表中。 (2) 建立一个叫做CLOSED的已扩展节点表,其初始为空表。
2、 (3) LOOP:若OPEN表是空表,则失败退出。 (4) 选择OPEN表上的第一个节点,把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。 (5) 若n为一目标节点,则有解并成功退出,此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。(6) 扩展节点n,同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。 (7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些
3、成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员,确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员,确定是否需要更改图G中通向它的每个后裔节点的指针方向。 (8) 按某一任意方式或按某个探试值,重排OPEN表。 (9) GOLOOP。4.图搜索方法分析图搜索过程的第8步对OPEN表上的节点进行排序,以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的(盲目搜索),也可以启发思想或其它准则为依据(启发式搜索)。搜索过程在找到目标节点时成功结束,这时,通过第
4、7步设置的指针从目标节点向S回溯。当图中不再有未被扩展的非端节点时,搜索过程就以失败告终,在此情况下,问题无解。3.2 盲目搜索3.2.1 宽度优先搜索(breadth-firstsearch)1.定义如果搜索是以接近起始节点的程度依次扩展节点的,那么这种搜索就叫做宽度优先搜索。2.特点这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。3.宽度优先搜索算法(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点,则求得一个解答)。 (2) OPEN是个空表,则没有解,失败退出;否
5、则继续。 (3) 把第一个节点(节点n)从OPEN表移出,并把它放入CLOSED的扩展节点表中。 (4) 扩展节点n。如果没有后继节点,则转向上述第(2)步。 (5) 把n的所有后继节点放到OPEN表的末端,并提供从这些后继节点回到n的指针。 (6) 如果n的任一后继节点是目标节点,则找到一个解答,成功退出;否则转向(2)。4.宽度优先搜索方法分析宽度优先搜索是图搜索一般过程的特殊情况,将图搜索一般过程中的第(8)步具体化为本算法中的第(5)步,这实际是将OPEN表作为“先进先出”的队列进行操作。
6、 宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径;这棵搜索树提供了所有存在的路径(如果没有路径存在,那么对有限图来说,我们就说该法失败退出;对于无限图来说,则永远不会终止)。3.2.2 深度优先搜索(depth-firstsearch)1.定义如果搜索时首先扩展最新产生的(即最深的)节点,这种搜索就叫做深度优先搜索。2.特点扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行,只有当搜索到达一个没有后裔的状态时,它才考虑另一条替代的路径。3.深度界限为了避免考虑太长的路径,往往给出
7、一个节点扩展的最大深度——深度界限。任何节点如果达到了深度界限,那么都将把它们作为没有后继节点处理。4.含有深度界限的深度优先搜索算法 请同学们课后自学,并回答课后思考题。3.2.3 等代价搜索(depth-firstsearch)1.定义宽度优先搜索可被推广用来解决寻找从起始状态至目标状态的具有最小代价的路径问题,这种推广了的宽度优先搜索算法叫做等代价搜索算法。2.等代价搜索中的几个记号起始节点记为S; 从节点i到它的后继节点j的连接弧线代价记为c(i,j); 从起始节点S到任一节点i的路径代价记为g
8、(i)。3.等代价搜索算法请同学们课后认真阅读本算法,指出与宽度优先、深度优先算法有何特别之处。4.等代价搜索方法分析如果所有的连接弧线具有相等的代价,那么等代价算法就简化为宽度优先搜索算法。3.3 启发式搜索3.3.1 启发式搜索策略和估价函数1.为什么需
