人工智能第3章确定性推理

1、人 工 智 能 Artificial Intelligence (AI),第3章 确定性推理,3.1 图的搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 与或树搜索（补充） 3.5 博弈树搜索（补充） 3.6 消解原理,解决实际问题的两个关键之处：,问题的表达 状态空间法 问题归约法 谓词逻辑法,问题的求解 搜索技术 推理技术,盲目与启发式搜索：状态空间法、图的搜索技术 与或树搜索：问题归约法、与或图的特例的搜索技术 博弈树搜索：状态空间法问题归约法、双人博弈的特殊搜索技术 消解原理：谓词逻辑法、推理技术,3.1 图搜索策略,状态空间中： 状态 初始状态 目标状态 操作符,图中有： 节

2、点 初始节点 目标节点 有向弧,状态空间法与图的对应关系,在状态空间中，解是从初始状态到目标状态的操作符序列 在图中，解是从初始节点到目标节点的一条路径,解的含义：,状态：(城市名) 算子：常德益阳 益阳常德 益阳汨罗 益阳宁乡 益阳娄底 ,？,？,？,？,必须记住哪些点走过了,必须记住下一步还可以走哪些点,必须记住从目标返回的路径,必须记住哪些点走过了,必须记住下一步还可以走哪些点,必须记住从目标返回的路径,OPEN表(记录还没有扩展的点),CLOSED表(记录已经扩展的点),每个表示状态的节点结构中必须有指向父节点的指针,图的搜索策略：图搜索过程的一般步骤（基本思路、框架），经过细化后得到

3、具体算法： 盲目搜索技术（深度、宽度、代价优先算法） 启发式搜索技术（有序算法、A*算法）,图搜索中的两个重要记号（符号）： OPEN 表： 存放待扩展的节点 CLOSED 表：存放已扩展的节点 注意：在与或树搜索中也要用到这两张表,数据结构中图的遍及：从图某一个节点出发，访问遍图中其余节点，且每一个节点仅仅被访问一次。,当前图的搜索技术中，有两个特殊之处： 搜索前，图并没有生成好，需要边生成图边搜索 搜索从起始节点（初始状态）开始，到目标节点（目标状态）结束，不需要搜索所有可能的节点,盲目搜索是指无问题先验信息的搜索技术 特点： OPEN表中节点的排列是人为规定的 一般只适合于求解比较简单的

4、一些问题,3.2 盲目搜索,图的盲目搜索技术分成： 宽度优先搜索技术 深度优先搜索技术 等代价（代价优先）搜索技术,3.2.1 宽度优先搜索,宽度优先搜索：以接近起始节点的程度依次扩展节点的搜索技术（即：离起始节点近的节点先被扩展） 扩展节点的原则：先扩展出来的节点随后优先被扩展（生成其所有的后继节点）, 把起始节点放到 OPEN 表中(如果该起始节点为一目标节点，则得到解) 如果 OPEN 是个空表，则无解，失败退出；否则继续下一步,宽度优先搜索算法：, 把第一个节点(记作节点 n )从 OPEN 表移出，并把它放入 CLOSED 的已扩展节点表中 扩展节点 n 。如果没有后继节点，则转向第

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

6、：,空,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表的存储形式：队列,插入端（队尾）,删除端（队头）,队列：一种先进先出的线性表，允许在表的一端进行插入、另一端进行删除,CLOSED表的存

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

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

9、,先生成的节点在左,目标节点,（先扩展的节点画在左边）,生成后继节点的顺序,OPEN与CLOSED表的存储形式的简化,CLOSED,OPEN,加入扩展节点,C,O,1 2 3 4 5 6 7 8 9 10 11 12 13 14,15 16 17 18 19 20 21 22 23 24 25 26 27,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,练习：,根据下列迷宫，用宽度优先搜索算法寻

10、找出从入口到出口的一条路径,状态：用极坐标表示的人的位置 操作符：人向左方、前方、右方前进 提示：不要产生已有的状态,存在的问题： 走步方向不符合人走路的习惯 没有标注走步的方向 中间改变走步方向的顺序 多画搜索树，有解后还再往下扩展,(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,

11、90),(0,0),前,右,(6,90),出口,宽度优先搜索算法,先在左,X,人,向右 3,向前2,3.2.2 深度优先搜索,深度优先搜索策略是先扩展最新产生的(即最深的)节点,节点的深度； 、起始节点(即根节点)的深度为0。 、任何其它节点的深度等于其父辈节点深度加上1。,深度优先搜索的基本思路： 先扩展最深的节点。当出现没有后继节点时，换到旁边的次深节点,后生成的节点画在左边, 把起始节点 S 放到未扩展节点的 OPEN 表中。如果此节点为一目标节点，则得到解 如果 OPEN 为一空表，则无解、失败退出,含有深度界限的深度优先搜索算法：,深度界限的设置： 为了避免出现过深的路径，搜索过程要

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

13、： 状态旁边的数字表示该节点生成后继节点的顺序，即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,后在左,练习：,根据下列迷宫，用深度优先搜索算法寻找出从入口到出口的一条路径,状态：用极坐标表示的人的位置 操作符：人向左方、前方、右方前进

14、提示：不要产生已有的状态,深度优先算法存在问题： 先后顺序有误，规定的先后顺序：左前右 改变坐标系，极坐标直角坐标 对于一个节点，按照规定的操作符顺序，使用所有可能的操作符，产生相应的后继节点,(6,0),人,向左 1,向右 3,向前2,(4,0),前,右,(6,45),(4,45),前,前,(2,45),右,(4,90),左,(2,90),右,(6,90),出口,深度优先搜索算法 （没有产生已有的节点）,后在左,思考题： 利用宽度优先与深度优先算法解决八数码问题？,3.2.3 等代价搜索,宽度优先搜索技术找到了应用算符数目最少或者深度最浅的解 如果认为每一个操作符的代价相等，则宽度优先搜索技

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

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

17、计算 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

18、,W1,E1,(3,2) 5,(3,1) 6,E1,S2,(3,3) 6,(4,4) 6,E1,S1,X,X,可以扩展 (3,1)6 (3,3)6,例：最小路程问题。下图是五个城市的交通路线图，图中的数字是公里数。问题是找到一条从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,等代价算法存在的问题： 如果当前扩展出来的节点，已经存在，需要比较新旧代价，一般先画出节点，再删除代价大的节点。也可以不画代价大的节点。但是不能有的地方画，有点的地方不画。,(6,0) 0,人,向左 1,向右 3,向前2,(4,0) 2,前2,右4.5,(6,45) 4.5,(4,45) 5,(2,0) 4,前2,右3,左2,(2,45) 7,前3,(0,0) 9,前2,右1.5,(2,90)8.5,右2,(6,90) 10,出口,等代价搜索算法,X,X,2,4.5,3,1.5,前2,(4,45) 6.5,左2,(2,90) 10,X,X,(4,90)10.5,前2,X,右2,