人工智能基础之搜索技术.ppt

《人工智能基础之搜索技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、目录第一章绪论第二章知识表示第三章　搜索技术第四章　推理技术第五章　机器学习第六章　专家系统第七章　自动规划系统第八章自然语言理解第九章智能控制第十章人工智能程序设计3.1盲目搜索盲目搜索：即无信息搜索宽度优先与深度优先3.1.1图搜索策略图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。研究图搜索的一般策略，能够给出图搜索过程的一般步骤。3.1盲目搜索3.1.1图搜索策略例3.1从王某家族的四代中找王A的后代且其寿命为X的

2、人A,47B1,77A3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,513.1盲目搜索3.1.1图搜索策略1.图搜索(GRAPHSEARCH)的一般过程(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从

3、n到S这条路径而得到的(指针将在第7步中设置)。3.1盲目搜索3.1.1图搜索策略1.图搜索(GRAPHSEARCH)的一般过程(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。(7)对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8)按某一任

4、意方式或按某个探试值，重排OPEN表。(9)GOLOOP。3.1盲目搜索节点父辈节点3.1.1图搜索策略2.图搜索算法的几个重要名词（1）OPEN表与CLOSE表OPEN表CLOSED表编号节点父辈节点3.1盲目搜索3.1.1图搜索策略3.搜索图与搜索树搜索过程框图开始初始化：S放入OPEN表，CLOES表置空,n=1OPEN表中的第一个结点n移至CLOSE表若n的后继未曾在搜索图G中出现，则将其放入OPEN表的末端，并提供返回结点n的指针,置n=n+1根据后继结点在搜索图G中的出现情况修改指针方向依某种准则重新排序OPEN表失败成功NYNOPEN为空

5、表NULL？n=目标结点D吗?Y3.1盲目搜索3.1.1图搜索策略4.图搜索方法分析：图搜索过程的第8步对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某些节点最终可能没有后继节点，所以OPEN表可能最后变成空

6、表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点。3.1盲目搜索3.1.2宽度优先搜索定义3.1如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索（breadth-firstsearch)3.1盲目搜索3.1.2宽度优先搜索宽度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。

7、(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。3.1盲目搜索3.1.2宽度优先搜索例3.2八数码问题操作规定:允许空格四周上、下、左、右的数码块移入空格中，不许斜方向移动，不许返回先辈结点。初始布局S和目标状态D如下图所示：3.1盲目搜索3.1.2宽度优先搜索例3.2八数码问题3.1盲目搜索3.1.3深度优先搜索深度优先算法步骤：(1)初始结点S放到未扩展节点OPEN中；(2)若OPEN为空，则搜索失败，问题无解；(3)弹出OPEN

8、表中最顶端结点放到CLOSE表中，并给出顺序编号n；(4)若n为目标结点D，则搜索成功，问题有