第3章(搜索推理技术1-图盲目搜索)ppt课件.ppt

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

1、第3章搜索推理原理3.1图的搜索策略3.2盲目搜索3.3启发式搜索3.4与或树搜索（补充）3.5博弈树搜索（补充）3.6消解原理解决实际问题的两个关键之处：①问题的表达状态空间法问题归约法谓词逻辑法②问题的求解搜索技术推理技术盲目与启发式搜索：状态空间法、图的搜索技术与或树搜索：问题归约法、与或图的特例的搜索技术博弈树搜索：状态空间法＋问题归约法、双人博弈的特殊搜索技术消解原理：谓词逻辑法、推理技术3.1图搜索策略状态空间中：状态初始状态目标状态操作符图中有：节点初始节点目标节点有向弧状态空间法与图的对应关系在状态空间中，解是从初始状态到目标状态的操作符

2、序列在图中，解是从初始节点到目标节点的一条路径解的含义：图的搜索策略：图搜索过程的一般步骤（基本思路、框架），经过细化后得到具体算法：盲目搜索技术（深度、宽度、代价优先算法）启发式搜索技术（有序算法、A*算法）图搜索中的两个重要记号（符号）：OPEN表：存放待扩展的节点CLOSED表：存放已扩展的节点注意：在与或树搜索中也要用到这两张表数据结构中图的遍及：从图某一个节点出发，访问遍图中其余节点，且每一个节点仅仅被访问一次。当前图的搜索技术中，有两个特殊之处：搜索前，图并没有生成好，需要边生成图边搜索搜索从起始节点（初始状态）开始，到目标节点（目标状态）结

3、束，不需要搜索所有可能的节点盲目搜索是指无问题先验信息的搜索技术特点：OPEN表中节点的排列是人为规定的一般只适合于求解比较简单的一些问题3.2盲目搜索图的盲目搜索技术分成：宽度优先搜索技术深度优先搜索技术等代价（代价优先）搜索技术3.2.1宽度优先搜索宽度优先搜索：以接近起始节点的程度依次扩展节点的搜索技术（即：离起始节点近的节点先被扩展）扩展节点的原则：先扩展出来的节点随后优先被扩展（生成其所有的后继节点）①把起始节点放到OPEN表中(如果该起始节点为一目标节点，则得到解)②如果OPEN是个空表，则无解，失败退出；否则继续下一步宽度优先搜索算法：③把

4、第一个节点(记作节点n)从OPEN表移出，并把它放入CLOSED的已扩展节点表中④扩展节点n。如果没有后继节点，则转向第②步⑤把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针⑥如果n的任一个后继节点是个目标节点，则找到一个解（反向追踪得到从目标节点到起始节点的路径），成功退出，否则转向第②步OPEN表是存放待扩展的节点，从数据结构上来说，它是一个先进先出的队列CLOSED表是存放已被扩展过的节点（包括有后继节点的非端节点和无后继节点的端节点）说明：流程图①搜索过程产生的节点和指针构成一棵隐式定义的状态空间树的子树，称之为搜索树注意

5、几点：②宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径（所用操作符最少）例：八数码问题初始状态目标状态操作符：2831476512384765空1243状态：长度为9的一维数组（q1,q2,…,q9）其中，qi取0,1,…,8个数，0表示空格，且取值互不相同如果记空格的位置为P，这时空格的移动规则是：123456789123456789PP-3P+1P+3P-1数字表示位置顺序规则前提条件应用结果1左移P≠1,4,7P位置与P-1位置上的元素互换2上移P≠1,2,3P-33下移P≠7,8,9P+34右移P≠3,6,9P+1空格移动规则P

6、-3PP+3P-1P+1123456789为了记录后继节点与父节点之间的指针，我们将长度为9的数组扩大到长度为11的数组，其中一个元素记录该节点的父节点标志，另一个元素记录操作符的序号操作符父节点状态OPEN表的存储形式：队列插入端（队尾）删除端（队头）队列：一种先进先出的线性表，允许在表的一端进行插入、另一端进行删除CLOSED表的存储形式：也可以用队列父符插入端（队尾）特殊的队列：只进不出的队列，只允许在表的一端进行插入某一个节点的父节点标志：记录CLOSED表中的父节点的序号起始节点的父节点标志和操作符：不作记录或记录为负搜索过程（按照程序运行方式

7、）①起始节点放到OPEN表283104765②OPEN不为空，继续28314765③将第一个节点n从OPEN表中移出，并放到CLOSED表中00283104765OPEN表CLOSED表节点n1④扩展节点n28301476520318476528316470528314076500283104765扩展28314765⑤将节点n的所有后继节点放到OPEN表的末端，并提供这些后继节点回到n的指针11283014765122031847651328316470514283140765OPEN表符父00283104765CLOSED⑥后继节点中无目标节点，转到

8、②②OPEN表不为空，继续③将第一个节点n从OPEN表中移出，并放到CLOSED