启发式搜索策略.ppt

欢迎使用本课件
教材简介:
名称:人工智能原理与应用
作者:张仰森
出版社:高等教育出版社
章节:共十章
主讲教师: 宗春梅
定义
搜索:根据问题的实际情况,按照一定的策略或规则,从知识库中寻找可利用的知识,从而构造出一条使问题获得解决的推理路线
搜索的概念及种类
搜索的概念
搜索的种类
搜索的概念及种类
1、状态空间图搜索:
包括三种状态空间图搜索方法,即宽度优先搜索、深度优先搜索和状态空间图搜索。
2、启发式搜索:
启发式搜索弥补状态空间图搜索的不足,提高搜索效率。
1、定义
宽度优先搜索可被推广用来解决寻找从起始状态至目标状态的具有最小代价的路径问题,这种推广了的宽度优先搜索算法叫做状态空间图搜索算法。
2、状态空间图搜索中的几个记号
起始节点记为S;
从节点i到它的后继节点j的连接弧线代价记为c(i,j);
从起始节点S到任一节点i的路径代价记为g(i)。
3、状态空间图搜索算法
(请同学们课后认真阅读本算法,指出与宽度优先、深度优先算法有何特别之处。)
4、状态空间图搜索方法分析
如果所有的连接弧线具有相等的代价,那么状态空间图算法就简化为宽度优先搜索算法。
状态空间图搜索策略
状态空间图搜索策略
1、定义
如果搜索是以接近起始节点的程度依次扩展节点的,那么这种搜索就叫做宽度优先搜索(breadth-first search)。
2、特点
这种搜索是逐层进行的;在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。
3、宽度优先搜索算法
(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点,则求得一个解答)。
(2) 如果OPEN是个空表,则没有解,失败退出;否则继续。
(3) 把第一个节点(节点n)从OPEN表移出,并把它放入CLOSED的扩展节点表中。
状态空间图搜索策略
宽度优先搜索策略
(4) 扩展节点n。如果没有后继节点,则转向上述第(2)步。
(5) 把n的所有后继节点放到OPEN表末端,并提供从这些后继节点回到n的指针。
(6) 如果n的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向第(2)步。
4、宽度优先搜索方法分析:
宽度优先搜索是图搜索一般过程的特殊情况,将图搜索一般过程中的第8步具体化为本算法中的第6步,这实际是将OPEN表作为“先进先出”的队列进行操作。
宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径;这棵搜索树提供了所有存在的路径(如果没有路径存在,那么对有限图来说,我们就说该法失败退出;对于无限图来说,则永远不会终止)。
状态空间图搜索策略
宽度优先搜索策略
5、例:把宽度优先搜索应用于八数码难题时所生成的搜索树,这个问题就是要把初始棋局变为如下目标棋局的问题:
1 2 3
8 4
7 6 5
提问:宽度优先搜索方法中OPEN表需要按什么方式进行操作?

状态空间图搜索策略
宽度优先搜索策略
1、定义
在此搜索中,首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。
这种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。
2、特点
首先,扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去;只有当搜索到达一个没有后裔的状态时,它才考虑另一条替代的路径。
3、深度界限
为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去),往往给出一个节点扩展的最大深度棗深度界限。任何节点如果达到了深度界限,那么都将把它们作为没有后继节点处理。
状态空间图搜索策略
深度优先搜索策略
4、含有深度界限的深度优先搜索算法
请同学们课后自学,并回答课后思考题。
思考题:有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径吗?
状态空间图搜索策略
深度优先搜索策略
1、为什么需要启发式搜索
盲目搜索效率低,耗费过多的计算空间与时间,这是组合爆炸的一种表现形式。
2、定义
进行搜索技术一般需要某些有关具体问题领域的特性的信息,把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。
3、启发式搜索策略
有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后,搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程,需要某些估算节点“希望”的量度,这种量度叫做估价函数