资源描述：
《第三章1搜索推理技术》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第三章搜索推理技术3.6产生式系统3.7系统组织技术3.8不确定性推理3.9非单调推理3.10小结3.1图搜索策略3.2盲目搜索3.3启发式搜索3.4消解原理3.5规则演绎系统AI为什么要研究search问题没有直接的解法;需要探索地求解;什么是搜索?根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程.包括两个方面：---找到从初始事实到问题最终答案的一条推理路径---找到的这条路径在时间和空间上复杂度最小2在图中寻找路径的方法初始节点初始数据库目标节点满足终止条件的数据库求取把一个数据库变换为另一个数据库的规则序列求得图中一条路径3.1图搜索策
2、略图搜索控制策略3节点深度：根节点深度=0其它节点深度=父节点深度+101234路径设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径路径的耗散值（代价）一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。5盲目搜索图搜索策略启发式搜索宽度优先搜索深度优先搜索6搜索过程的要点:起始节点:对应于初始状态描述后继节点:把适用于某个节点状态描述的一些算符用来推算该节点而得到
3、的新节点,称为该节点的后继节点,检查各后继节点看是否为目标节点.指针:从每个后继节点返回指向其父辈节点7两个主要的数据结构：OPEN表:存放刚生成的节点,是还未扩展的节点.一般是端节点.CLOSED表:存放将要扩展或已扩展的节点.或者是已被扩展但还没有在搜索树中生成后继节点的端节点,或者是非端节点8状态节点父节点编号状态节点父节点OPEN表CLOSED表9(1)把初始节点S0放入OPEN表,并建立目前只包含S0的图,记为G(2)检查OPEN表是否为空,若为空则问题无解,退出(3)把OPEN表的第一个节点取出放入CLOSED表,记该节点为n(4)考察n是否为目标节点.如是,则问题得解,退出(
4、5)扩展节点n,生成一组子节点.把其中不是节点n先辈的那些节点记作集合M,并把这些子节点作为节点n的子节点加入G中搜索的一般过程：10(6)针对M中子节点的不同情况,分别进行处理对于那些未曾在G中出现过的M成员设置一个指向父节点(即n)的指针,并把它们放入OPEN表对于那些先前已在G中出现过的M成员,确定是否需要修改它指向父节点的指针对于那些先前已在G中出现并且已经扩展了的M成员,确定是否需要修改其后继节点指向父节点的指针(7)按某种搜索策略对OPEN表中的节点进行排序(8)转第(2)步11开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点
5、吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1图搜索过程框图是是否否3.1图搜索策略121,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算
6、是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；13SOPENCLOSE{S}{}123{}{S}{1,2,3}{S}{2,1,3}{S}45{1,3}{S,2}{1,3,4,5}{S,2}{3,1,4,5}{S,2}{1,4,5}{S,2,3}6{1,4,5,6}{S,2,3}例子：G14这是一个通用的搜索过程,后面讨论的状态空间各种搜索策略都是其特例.各种搜索策略的主要区别就是对OPEN表中节点排序准则不同。算法结束后，将生成一个图G，称为搜索图。同时由于每个节点都有一个指针指向父节点，这些指针指向的节点构成G的一个支撑树，称为搜索树。从目
7、标节点开始，将指针指向的状态回串起来，即找到一条解路径。树/不修改指针;图/修改指针。修改指针:找最优解。153.2盲目搜索特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。3.2.1宽度优先搜索定义以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到它。算法从初始节点开始,逐层对节点进行扩展并考察它是否为目标节点,在第n层的节点没有全部扩展并考察之前，不对第n+1层的
