人工智能-许建华- 南京师范大学计算机科学系-22 图的搜索技术B.ppt

定义2: 在A算法中，如果对所有的 x 存在 h ( x )≤ h*( x ) 则称 h ( x ) 为 h*( x )的下界 意义： h ( x )是h*( x )的某种偏于保守的估计 后继节点 j 新 节点 在 Open？ 在 Closed？ 新 f 值小 调整父节点 新 f 值小 调整父节点 移回Open 如果 f ( i ) 取节点 i 的深度，这时就是宽度优先搜索 如果 f( i ) 取从起始节点到当前节点 i 之间路径的代价，这时就是等代价搜索 有序搜索算法的特例： 例：八数码问题 估价函数为： f ( n ) = g ( n ) + h ( n ) 其中: g(n)： 节点 n 的深度 h ( n ) ：节点 n 中错放的棋子个数 5 7 4 6 1 3 8 2 4 5 7 4 6 1 3 8 2 5 6 7 4 1 3 8 2 5 7 4 6 1 3 8 2 6 4 6 空 1 2 3 4 5 6 7 4 1 3 8 2 5 6 7 4 8 1 3 2 5 6 7 4 1 3 8 2 6 5 5 5 6 7 4 1 2 3 8 5 6 4 1 7 3 8 2 6 7 5 6 7 4 8 1 3 2 5 6 7 4 8 1 3 2 5 7 5 6 7 4 8 1 3 2 5 5 6 7 4 8 3 2 1 5 6 7 4 8 3 2 1 5 6 4 8 7 3 2 1 5 7 5 目标节点 带圆圈的数字表示估价函数的值 不带圆圈的数字表示扩展顺序 相同值时，后扩展的节点放在前面 每一个状态的存储形式： 状态空间法：长度为9的一维数组 5 6 7 4 0 8 3 2 1 符 父 盲目搜索中：长度为11的一维数组 5 6 7 4 0 8 3 2 1 启发搜索中：长度为14的一维数组 5 6 7 4 0 8 3 2 1 符 父 g ( n ) + h ( n ) = f ( n ) 例：迷宫 人 4 3 2 1 代价：关键位置点之间的水平与垂直距离之和 g : 起始位置到当前位置之间的已经走过的距离 h : 当前位置到目标位置的水平与垂直距离之和 人 4S 3E 2N 1W (1,1) 0+6 N3 (2,3) 3+3 (2,4) 4+2 N1 S1 (2,2) 4+4 (1,4) 5+3 (3,4) 5+1 W1 E1 (3,3) 6+2 (4,4) 6+0 E1 S1 出口 思考题 对于下列迷宫，用有序搜索算法寻找出从入口到出口的一条路径 代价：关键位置之间的路程，其中π=3.0 g: 起始位置到当前位置的已经走过的距离 假设：通道是放射状的直线和圆弧 h: 当前位置到目标位置的直线和圆弧距离之和的最小值 (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) 出口 宽度优先搜索算法 先在左 X 人 向右 3 向前2 (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 (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 (4,90) 8 (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 (6,45) 7 X 说明：当扩展某一个节点生成全部后继节点时出现搜索图中已经有的节点（在Open或者Closed表的节点），在等代价搜索中有两种处理策略： 只保留新产生的节点，已有的节点都不保留 借助于有序算法中的处理策略（上述例子中的方法） (6,0)0+9 人 向左 1 向右 3 向前2 (4,0)2+8 前2 右4.5 (6,45)4.5+4.5 (4,45