第3章 搜索推理技术课件.ppt

《第3章 搜索推理技术课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.1图搜索策略3.2盲目搜索3.3启发式搜索3.4消解原理3.5规则演绎系统3.6产生式系统3.7系统组织技术3.8不确定性推理3.9非单调推理3.10小结第3章搜索推理技术3.1图搜索策略图搜索控制策略一种在图中寻找路的方法。图中每个节点对应一个状态，每条连线对应一个操作符。节点和连线（即状态与操作）又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。图搜索过程1.建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表（简称OPEN表）

2、。2.建立一个叫做CLOSED的已扩展节点表（简称CLOSED表），其初始为空表。3.LOOP：若OPEN表是空表，则失败退出。4.选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n，它是CLOSED表中节点的编号。5.若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到（指针将在第7步中设置）。图搜索过程6.扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。7.对那些未曾在G中出现过的（既未曾在OPEN表上

3、或CLOSED表上出现过的）M成员设置一个通向n的指针，把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。8.按某一任意方式或按某个探试值，重排OPEN表。9.GOLOOP。图搜索过程框图3.2盲目搜索概念没有启发信息的一种搜索形式一般只适用于求解比较简单的问题特点不需重排OPEN表种类宽度优先深度优先等代价搜索3.2.1宽度优先搜索1)定义以接近起始节点的程度为依据，进行

4、逐层扩展的节点搜索方法。2)特点搜索是逐层进行的，即在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。一种高代价搜索，但若有解存在，则必能找到它。宽度优先搜索示意图宽度优先算法框图宽度优先搜索算法描述1.把起始节点放到OPEN表中（如果该起始节点为一目标节点，则求得一个解答）。2.如果OPEN是个空表，则没有解，失败退出；否则继续。3.把第一个节点（节点n）从OPEN表移出，并把它放入CLOSED的扩展节点表中。4.扩展节点n。如果没有后继节点，则转向上述第2步。宽度优先搜索算法描述5.把n的所有后继节点放到OPE

5、N表的末端，并提供从这些后继节点回到n的指针。6.如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第2步。7.扩展当前节点后生成的子节点总是置于OPEN表的后端，即OPEN表作为排队表使用，先进先出，使搜索优先向横方向发展。宽度优先搜索是图搜索一般过程的特殊情况，这实际是将OPEN表作为“先进先出”的队列进行操作。搜索树:搜索过程产生的节点和指针构成一棵隐式定义的状态空间图的子树,称为搜索树。如果问题有解,宽度优先算法能够保证找到一条通向目标节点的最短路径(即找到最优解).如要问题无解,对于有限图,该算

6、法会失败退出，对于无限图,则永远不会终止。宽度优先搜索算法说明八数码难题将牌移入空格的顺序：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，才求得解（目标节点）。八数码难题的宽度优先搜索树3.2.2深度优先搜索1定义首先扩展最新产生（即最深的）节点。深度相等的节点可以任意排列。2)特点首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；仅当搜索到达一个没有后裔的状态时，才考虑另一条替代的路径。3)节点深度定义:起始节点(即根节点)的深度为0.任何其他节点的

7、深度等于其父辈节点的深度加1.4)深度界限:–为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去),往往给出一个节点扩展的最大深度,称为深度界限.–任何节点如果达到了深度界限,那么都将把它们作为没有后继节点来处理.–即使应用了深度界限,深度优先搜索所求得的解答路径也不一定就是最短路径.3.2.2深度优先搜索深度优先搜索示意图深度优先搜索算法描述1.把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。2.如果OPEN为一空表，则失败退出。3.把第一个节点（节点n）从OPEN表移到CLOSED表

8、。4.如果节点n的深度等于最大深度，则转向(2)。5.扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。6.如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。深度优先搜索算法描述起始把S放入OPEN表OPEN表是否为空?把OPE