资源描述：
《人工智能-第三搜索推理技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三搜索推理技术从问题的表示到问题的解决是一个求解的过程，也就是搜索过程。在这一过程中，采用适当的搜索技术，包括各种规则、过程和算法等推理技术，力求找到问题的解答。本章首先介绍图搜索策略的一般过程，接着讨论一些早期的搜索技术或用于解决比较简单问题的搜索原理，然后研究一些比较新的能够求解比较复杂问题的推理技术。第三确定性推理§3.1图搜索策略§3.2盲目搜索§3.3启发式搜索§3.4消解原理§3.5规则演绎系统§3.6产生式系统§3.7非单调推理第三搜索推理技术一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,
2、甚至关系到求解问题有没有解。 搜索方法好的标准,一般认为有两个：(1)搜索空间小; (2)解最佳。Sg§3.1图搜索策略§3.1图搜索策略一.问题描述(图搜索问题描述)把求解问题看成一个状态图，求初始节点到目标节点的路径。§3.1.1图搜索策略回顾一下图论中几个术语的含义。节点深度：根节点的深度为0,其他节点的深度规定为父节点深度加1,即dn+1=dn+1。路径：设一节点序列为(n0、n1,…,ni,…,nk),对i=1,2,…,k,若节点ni-1都具有一个后继节点ni,则该节点序列称为节点n0到节点nK长度为k的一条路径。路
3、径耗散值：令C(ni,nj)为节点ni到nj这段路径(或弧线)的耗散值,一条路径的耗散值等于连接这条路径各节点间所有弧线耗散值的总和。路径耗散值可按如下式递归公式计算: C(ni,t)=C(ni,nj)+C(nj,t) C(nj,t)为ni→t这条路径的耗散值。§3.1.1图搜索策略回顾一下图论中几个术语的含义。扩展一个节点:后继节点操作符(相当于可应用规则)作用到节点(对应于某一状态描述)上,生成出其所有后继节点(新状态),并给出连接弧线的耗散值(相当于使用规则的代价),这个过程叫做扩展一个节点。扩展节点可使定义的隐含图生成
4、为显式表示的状态空间图。§3.1.1图搜索策略二.图搜索过程S～起始结点G～搜索图OPEN～表存放未扩展节点CLOSED～表存放已扩展节点1.图搜索过程(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3)LOOP:若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中，称此节点为节点n。§3.1.1图搜索策略(5)若n为一目标节点n，则有解并成功退出。此解是追踪图G中沿着指针从n到s这条路径
5、而得到的。(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继结点添入图G中。(7)对于那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已经在CLOSED表上的每一个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GOLOOP§3.1.1图搜索策略举例：SABCDEMFS
6、1.SOPEN(S)CLOSED()2.AOPEN(A,B)CLOSED(S)3.BOPRN(B,C,D)CLOSED(S,A)4.COPEN(C,D,E)CLOSED(S,A,B)5.DOPEN(D,E)CLOSED(S,A,B,C)6.EOPEN(E,M,F)CLOSED(S,A,B,C,D)7.N求解目标节点235647384ק3.1.1图搜索策略2.流程图开始把S放表入OPEN表中OPEN表为空表把第一个节点n从OPEN表移至CLOSED表N为目标节点把节点n的后继节点放入OPEN表，提供返回节点n的指针修正指针方向重排OPEN表失
7、败成功是是①②③§3.1.1图搜索策略§3.1.1图搜索策略§3.1.1图搜索策略§3.1.1图搜索策略§3.1.1图搜索策略§3.1.1图搜索策略3.遗留问题①n的某后继节点已在OPEN表中或CLOSED表中有了是否需要修改指针，对已存在的后继节点②按什么方式重排OPEN表宽度优先搜索深度优先搜索等代价搜索搜索控制方法§3.2盲目搜索盲目搜索是不利用问题的有关信息,而根据事先确定好的某种固定的搜索方法进行搜索，又叫做无信息搜索。一般只适用于求解比较简单的问题。典型的盲目搜索方法是深度优先搜索和宽度优先搜索(亦称广度优先搜索),这是两处基本搜
8、索方法。§3.2盲目搜索一.宽度优先搜索(一).宽度优先搜索以接近起始节点的程度依次扩展节点从根结点开始,每次都要扫遍同层的各个结点,若没有找到目标,则再往下一层扫
