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

《第3章(搜索推理技术1图盲目搜索)ppt课件.ppt》由会员分享，可在线阅读，更多相关《第3章(搜索推理技术1图盲目搜索)ppt课件.ppt（94页珍藏版）》请在三一办公上搜索。

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 是个空表，则无解，失败退出；否则继续下一步,宽度优先搜索算法：,把第一个节点(记作节点 n)从 OPEN 表移

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

5、向目标节点的最短途径（所用操作符最少）,例：八数码问题,初始状态,目标状态,操作符：,空,1,2,4,3,状态：长度为9的一维数组（q1,q2,q9）其中，qi 取 0,1,8 个数，0 表示空格，且取值互不相同,如果记空格的位置为P，这时空格的移动规则是：,P,P-3,P+1,P+3,P-1,数字表示位置,空格移动规则,P-3,为了记录后继节点与父节点之间的指针，我们将长度为 9 的数组扩大到长度为 11 的数组，其中一个元素记录该节点的父节点标志，另一个元素记录操作符的序号,操作符,父节点,状态,OPEN表的存储形式：队列,插入端（队尾）,删除端（队头）,队列：一种先进先出的线性表，允许在

6、表的一端进行插入、另一端进行删除,CLOSED表的存储形式：也可以用队列,插入端（队尾）,特殊的队列：只进不出的队列，只允许在表的一端进行插入,某一个节点的父节点标志：记录CLOSED表中的父节点的序号起始节点的父节点标志和操作符：不作记录或记录为负,搜索过程（按照程序运行方式）,起始节点放到OPEN表,OPEN不为空，继续,将第一个节点 n 从 OPEN 表中移出，并放到CLOSED表中,OPEN表,CLOSED表,节点n,1,扩展节点n,扩展,将节点 n 的所有后继节点放到 OPEN 表的末端，并提供这些后继节点回到 n 的指针,OPEN表,符,父,CLOSED,后继节点中无目标节点，转到

7、,OPEN表不为空，继续,将第一个节点 n 从 OPEN 表中移出，并放到CLOSED 表中,OPEN表,CLOSED表,节点n,12,扩展节点 n,将节点 n 的所有后继节点放到 OPEN 表的末端，并提供这些后继节点回到 n 的指针,OPEN表,.一直继续下去，而且不产生已经产生过的节点（状态），防止死循环。在程序中每一个新产生的节点必须与 OPEN 和 CLOSED 表中状态进行比较，判断是否已经产生过，只保留从未产生过的节点,最后的OPEN表：,目标节点,最后的CLOSED表：,123456789,10111213141516,目标节点,目标节点,16,8,3,1,2,1,4,3,先生

8、成的节点在左,目标节点,（先扩展的节点画在左边）,生成后继节点的顺序,OPEN与CLOSED表的存储形式的简化,CLOSED,OPEN,加入扩展节点,C,O,1234567891011121314,15161718192021222324252627,C,O,人,4S,3E,2N,1W,(1,1),N,(2,3),(2,4),N,S,(2,2),(1,4),(3,4),W,E,(3,2),(3,1),E,S,(3,3),(4,4),E,S,目标节点,X,例：迷宫问题,例：四皇后问题,X,X,X,大家听懂了“宽度优先算法”？基本听懂（85以上）大概听懂（70以上）似懂非懂（50左右）没有听懂（2

9、5以下）,课堂作业（写上学号与姓名）,根据下列迷宫，用宽度优先搜索算法寻找出从入口到出口的一条路径,状态：用极坐标表示的人的位置操作符：人向左方、前方、右方前进提示：不要产生已有的状态,(6,0),人,向左1,向右3,向前2,(4,0),前,右,(6,45),(4,45),(2,0),前,右,左,(2,45),前,(4,90),(0,0),前,右,(2,90),右,(6,90),出口,宽度优先搜索算法（没有生成已有的状态）,先在左,X,X,(6,0),向左1,(4,0),前,右,(4,45),(2,0),前,前,(2,45),右,(4,90),(0,0),前,右,(6,90),出口,宽度优先搜

10、索算法,先在左,X,人,向右3,向前2,课堂作业存在主要问题：1、搜索过程画成图的形式，将导致反向追踪路径出现歧义2、操作符使用混乱，搜索树不规范。3、画出整棵搜索树,3.2.2 深度优先搜索,深度优先搜索策略是先扩展最新产生的(即最深的)节点,节点的深度；、起始节点(即根节点)的深度为0。、任何其它节点的深度等于其父辈节点深度加上1。,深度优先搜索的基本思路：先扩展最深的节点。当出现没有后继节点时，换到旁边的次深节点,后生成的节点画在左边,把起始节点 S 放到未扩展节点的 OPEN 表中。如果此节点为一目标节点，则得到解 如果 OPEN 为一空表，则无解、失败退出,含有深度界限的深度优先搜索

11、算法：,深度界限的设置：为了避免出现过深的路径，搜索过程要设置一个深度界限对于等于深度界限的任何节点，当作没有后继节点的节点来看待缺点：可能丢失解,把第一个节点(记作节点 n)从 OPEN 表移到 CLOSED 表 如果节点 n 的深度等于最大深度，则转向,扩展节点 n，产生其全部后继节点，并把它们放入 OPEN 表的前头。如果没有后继节点，则转向 如果后继节点中有任一个节点为目标节点，则求得一个解（反向追踪从目标节点到起始节点的路径），成功退出；否则，转向,说明：现在的OPEN表是一个堆栈，后进先出,例：八数码问题,深度界限为5,后生成的节点画在左边,深度界限为4,后生成的节点画在左边,说明

12、：状态旁边的数字表示该节点生成后继节点的顺序，即CLOSED节点的存放顺序，不是本身被生成的顺序解是图中的虚线扩展过程中没有生成已有的节点,人,4S,3E,2N,1W,(1,1),N,(2,3),(2,4),N,S,(2,2),E,(3,2),(3,1),S,例：迷宫问题,(3,3),(3,4),(4,4),目标节点,E,N,E,后生成的节点在左边没有已有节点,宽度优先（先在左）,深度优先（后在左）,人,4,3,2,1,例：四皇后问题,X,X,后在左,课堂作业,根据下列迷宫，用深度优先搜索算法寻找出从入口到出口的一条路径,状态：用极坐标表示的人的位置操作符：人向左方、前方、右方前进提示：不要产

13、生已有的状态,(6,0),人,向左1,向右3,向前2,(4,0),前,右,(6,45),(4,45),前,前,(2,45),右,(4,90),左,(2,90),右,(6,90),出口,深度优先搜索算法（没有产生已有的节点）,后在左,(6,0),(4,0),前,右,(4,45),前,(2,45),右,(4,90),右,(6,90),出口,深度优先搜索算法（没有产生已有的节点）,后在左,人,向右3,向前2,思考题：（每人独立完成）利用宽度优先与深度优先算法解决八数码问题？（要求用C/C+语言编写出核心代码，考核的指标分成零、一、二、五、多步）,3.2.3 等代价搜索,宽度优先搜索技术找到了应用算符

14、数目最少或者深度最浅的解如果认为每一个操作符的代价相等，则宽度优先搜索技术就可以找到了代价最小的路径或解,所有操作符代价相等找到最短的路径宽度优先算法,操作符的代价不相等找到代价最小的路径等代价(代价优先)搜索技术,问题,推广,推广,宽度优先搜索：按照先后顺序取待扩展节点等代价搜索：将初始节点到所有端节点（OPEN中的节点）的局部路径中代价最小的端节点作为下一个要扩展的节点,推广的思路：,宽度优先搜索算法,等代价搜索算法,注：圆圈中的数字表示从起始节点到当前节点的代价,符号c(i,j)：从节点 i 到它的直接后继节点 j 的连接弧线上的代价g(i)：从起始节点 S 到某一节点 i 的路径的代价

15、,选取待扩展节点的原则：以 g(i)的递增顺序排列OPEN表以 g(i)最小的节点作为下一个要扩展的节点,将起始节点S放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解。否则令g(S)0 如果OPEN是空表，则无解，失败退出,等代价搜索算法：,从OPEN表中选择一个节点 i，使其 g(i)为最小。如果有几个节点都合格，则分两种情况，如果有目标节点，则选择一个目标节点作为节点 i；否则，从中任选一个节点作为节点 i。把节点 i 从OPEN表移至扩展节点表CLOSED中,如果节点 i 为目标节点，则求得一个解；否则，继续下一步 扩展节点 i。如果没有后继节点，则转向第步,对于节点

16、 i 的每个后继节点 j，计算 g(j)g(i)+c(i，j)并把所有后继节点 j 放进OPEN表。提供回到节点 i 的指针 转向第步,说明几点：第一、上述算法实际是树的搜索算法。如果是图的搜索，则要检查新产生的后继节点是否已经在OPEN表或CLOSED表，若是，比较新、旧代价并调整指针（保留代价小的路径）,第二、OPEN表是一张线性表，其元素按代价的递增顺序排列。表的基本操作：删除、定位与插入,例：迷宫,人,4,3,2,1,代价：关键位置点之间的水平与垂直距离之和,人,4S,3E,2N,1W,(1,1),N3,(2,3)3,(2,4)4,N1,S1,(2,2)4,(1,4)5,(3,4)5,

17、W1,E1,(3,2)5,(3,1)6,E1,S2,(3,3)6,(4,4)6,E1,S1,X,X,例：最小路程问题。下图是五个城市的交通路线图，图中的数字是公里数。问题是找到一条从A到E的最短路线。,操作符:从一个城市走向另一个城市（方向大体上从A指向E）,A(0),B(2),C(3),D(7),C(5),D(6),D(7),E(13),E(11),2,3,7,3,4,4,10,5,CLOSED,思考题,对于下列迷宫，用等代价搜索算法寻找出从入口到出口的一条路径,代价：关键位置之间的路程，其中=3.0,三种盲目搜索技术的比较主要差别：在于挑选要扩展节点的规则不同宽度优先搜索技术：先扩展出来的节点随后先扩展，OPEN表是队列深度优先搜索技术：后扩展出来的节点随后先扩展，OPEN表是堆栈等代价搜索技术：选取OPEN表中代价最小的节点先扩展，OPEN表是线性表（以局部代价的递增顺序排列）,三种算法的比较（流程图）,宽度优先,深度优先,代价优先,