《第3章(搜索推理技术2图启发搜索)课件.ppt》由会员分享，可在线阅读，更多相关《第3章(搜索推理技术2图启发搜索)课件.ppt（48页珍藏版）》请在三一办公上搜索。
1、人 工 智 能Artificial Intelligence (AI),第3章 搜索推理技术,3.1 图的搜索策略3.2 盲目搜索3.3 启发式搜索3.4 与或树搜索（补充）3.5 博弈树搜索（补充）3.6 消解原理,3.3 启发式搜索,宽度和深度优先搜索的 缺点：扩展节点的顺序是人为规定的，要扩展节点的数目可能非常大，占用大量的计算时间和内存空间，使得搜索效率低,等代价搜索技术的 缺点选取已经搜索到的代价最小的节点来扩展，但是没有考虑目标状态，不知道离目标状态还有多远，还需要付出多大的代价,提高搜索效率的 思路：利用更多的与问题有关的信息来选取待扩展的节点,3.3.1 启发式搜索策略和估价函
2、数,启发信息（背景知识）：与具体问题特性有关的一些信息。（在具体的使用过程中，还与使用人、算法有关）启发式搜索方法：利用启发信息的搜索方法, 用于决定要扩展的下一个节点，避免宽度优先或深度优先搜索中的盲目（人为规定）地选择扩展节点 在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，避免盲目地同时生成所有可能的后继节点 用于决定某些应该从搜索树中抛弃或修剪的节点,搜索技术中启发信息的用途：,本节的关注点：利用启发信息来决定下一个要扩展的节点,有序搜索：在搜索过程总是选择“ 最有希望 ”的节点作为下一个被扩展节点的搜索技术,估价函数：用来估算节点“ 希望 ”程度的函数,一般情况下，估计
3、函数值越大，希望程度就越低根据搜索过程、问题的启发信息来定义的，对搜索效率会产生较大的影响,希望,估价函数,估价函数的基本特性：,用 f (n) 表示节点 n 的估价函数值，并且期望，它是从起始节点、通过节点 n 、到达目标节点的最小代价的一个估计值,计算一个节点的“ 估价函数 ” ，可以分成两个部分：已经付出的代价（起始节点到当前节点）将要付出的代价（当前节点到目标节点）,估价函数的计算,起始节点,节点 n 的估价函数 f ( n ) 定义为从初始节点、经过 n 、到达目标节点的路径的最小代价的估计值，即 f ( n ) = g ( n ) + h ( n )g ( n ) 是从初始节点到达
4、当前节点 n 的实际代价h ( n ) 是从节点 n 到目标节点的最佳路径的估计代价,节点 n,目标节点,起始节点,g(n),h(n),h ( n ) 体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数g ( n ) 所占的比重越大，越趋向于宽度优先或等代价搜索；反之，h ( n ) 的比重越大，表示启发性能就越强,f ( n ) = g ( n ) + h ( n ),对于具体问题来说，根据问题的本质及解的性质，可以定义多种估价函数。用不同的估价函数指导搜索，其效果可能会相差很远。因此，必须尽可能选择最能体现问题特性的、最佳的估价函数,例：八数码问题的估价函数 f ( n )= g
5、 ( n ) + h ( n )g ( n ) 定义为搜索树中 n 的深度h ( n ) 可以定义成不同形式, 节点 n 的状态与目标状态之间数字不在位的个数（错放棋子的个数，不记空格）,目标状态,当前状态, 节点 n 中每一个数字与目标位置最短距离（每一个数字走到目标位置的要走的最少步数）之和,目标状态,当前状态, 把中心位置除掉，沿顺时针方向，如果一个数字的跟随数字是目标状态中的数字，则记0分，否则记2分。中心位置有数字记1分，无数字记0分。所有的总和为 h(n),目标状态,当前状态,例：数字2的跟随数字是1，而目标状态的数字应该是8,有序搜索算法（方法、技术）在搜索过程中，OPEN表中节
6、点按照其估价函数值以递增顺序排列，选择OPEN表中具有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索,这里，介绍尼尔逊(Nilsson)提出的有序搜索的基本算法：有序状态空间搜索算法,3.3.2 有序搜索,(1) 把起始节点 S 放到 OPEN 表中，并计算节点 S 的 f (S) (2) 如果 OPEN 是空表，则失败退出（无解）,有序状态空间搜索算法：,(3) 从 OPEN 表中选择一个 f 值最小的节点 i 。如果有几个节点值相同，当其中有一个为目标节点时，则选择目标节点；否则就选择其中任一个节点作为节点 i,(4) 把节点 i 从 OPEN 表中移出，并把它放入
7、CLOSED 的已扩展节点表中(5) 如果 i 是个目标节点，则成功退出（有解）(6) 扩展节点 i ，生成其全部后继节点。对于 i 的每一个后继节点 j ：,说明：节点 j 可以分成三种情形：新产生的节点，即不属于OPEN表又不属于CLOSED表（6-1、6-2步）已经产生过的节点，且属于OPEN表，其已经有父节点（6-1、6-3、6-3-1、6-3-2步）已经产生过的节点，且属于CLOSED表，其已经有父节点和后继节点（ 6-1、6-3、6-3-1、6-3-2、6-3-3步),CLOSED表,OPEN表,有父节点,既父节点又有子节点,(6-1) 计算 f ( j ) (6-2)如果 j 既
8、不在OPEN表中，又不在CLOSED 表中，则用估价函数 f 把它加入OPEN表相应位置。从 j 加一个指向其父辈节点 i 的指针，以便于反向追踪解的路径,(6-3) 如果 j 已在 OPEN 表（处理与父节点的关系）或 CLOSED 表（处理与父节点和子节点的关系）中，则比较新的 f ( j ) 值和前面计算出来的 f ( j ) 值。如果新的 f ( j ) 值较小，则,(6-3-1) 用新的值取代旧的值(6-3-2) 改变指针，从 j 指向 i ，删除原来的父辈节点指针(6-3-3) 如果节点 j 在 CLOSED 表中，则把它移回 OPEN 表(7) 转向(2),旧,CLOSED表,O
9、PEN表,新,新,新小旧大,X,X,移回,对于图的搜索，一个节点可能有多个父节点，这一步可以保证具有最小估价函数值的节点当作父节点，同时使得搜索得到的子图总是一棵树对于树的搜索，任何节点（除起始节点）只有一个父节点，则可以省略这一步,步骤6-3的说明,后继节点 j,新节点,在Open？,在Closed？,新 f 值小调整父节点,新 f 值小调整父节点移回Open自动删除子节点,如果 f ( i ) 取节点 i 的深度，这时就是宽度优先搜索如果 f( i ) 取从起始节点到当前节点 i 之间路径的代价，这时就是等代价搜索,有序搜索算法的特例：,例：八数码问题估价函数为： f ( n ) = d
10、( n ) + W ( n )其中:d ( n ) ：节点 n 的深度W ( n )：即 h ( n ) , 节点 n 中错放的棋子个数,4,6,4,6,空,1,2,3,4,6,5,5,6,7,5,7,5,5,7,5,目标节点,带圆圈的数字表示估价函数的值不带圆圈的数字表示扩展顺序,相同值时，同一次扩展按先后顺序排放，否则后扩展的节点放在前面,深度,每一个状态的存储形式：,状态空间法：长度为9的一维数组,盲目搜索中：长度为11的一维数组,启发搜索中：长度为14的一维数组,d ( n ) + W ( n ) = f ( n ),例：迷宫,人,4,3,2,1,代价：关键位置点之间的水平与垂直距离之
11、和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.0g: 起始位置到当前位置的已经走过的距离,假设：通道是放射状的直线和圆弧h: 当前位置到目标位置的直线和圆弧距离之和的最小值,3.3.3 A*算法,特殊的估价函数（对估价
12、函数作出某些规定） h ( n ) h*( n ) 最佳的启发函数值有序算法的细化（考虑更多的细节）,例：八数码问题h(n) 定义为节点 n 中每一个数字与目标位置最短距离（每一个数字走到目标位置的最少步数）之和相邻两个节点之间的代价为 1,思考题：用C/C+语言编写八数码问题的有序算法程序，估价函数可以选择前面介绍的任意一种。（有能力的同学可以选做，并写到实验报告中）,要求掌握的算法：宽度优先搜索算法深度优先搜索算法等代价搜索算法有序算法,作业题：,初始状态,目标状态,利用宽度优先、深度优先、有序搜索算法（启发函数定义为数码不在位的个数）找出上述八数码问题从初始状态到目标状态的操作符序列？,1,2,3,4,
