人工智能讲义AI02N..ppt

《人工智能讲义AI02N..ppt》由会员分享，可在线阅读，更多相关《人工智能讲义AI02N..ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章状态空间法及搜索2.0 引言问题求解是个大课题，如求解智力测验难题、求证逻辑或数学定理、求解最短路径、求解能够取胜的博奕走步序列等。常用的求解方法是试探搜索法，即在可能的解答空间中寻找一个合理的解。例：八数码难题 2 8 3 2 8 3 2 8 3 1 6 4 1 4 1 6 4 7 5 7 6 5 7 52 8 31 6 47 51 2 38 47 6 5初始状态目标状态2.1 状态空间法的基本概念和基本系统结构（1）基本概念y状态与操作x状态：表示问题求解过程中每一步问题状况的数据结构x初始状态：由问题已知的前提、初始条件的原始描述所构成的状态x目标状态：问题解决时应该到达的状态x操

2、作(算符)：把一种状态变成另一种状态的运算y状态空间法x状态空间：问题求解过程中由初始状态可能到达的所有状态的集合x状态空间法：建立初始状态，在状态空间中进行搜索，以找到一条从初始状态到达目标状态的（最佳）路径。这条路径（即达到目标状态的操作步骤）就是问题的解。基本系统结构y产生式系统的组成x综合数据库：初始数据库，目标数据库，中间数据库x产生式规则：IF A THEN BA:条件B:操作/结果x控制策略：选择可使用的规则和搜索算法等 控制策略产生式规则 综合数据库 产生式系统的组成八数码难题y综合数据库x可用3X3的二维数组表示一个状态（棋局）初始数据库：2 8 3 1 6 4 7 0 5目

3、标数据库：1 2 3 8 0 4 7 6 5y产生式规则xR1：IF 空格上方有棋 THEN 空格上移R2：IF 空格右方有棋 THEN 空格右移R3：IF 空格下方有棋 THEN 空格下移R4：IF 空格左方有棋 THEN 空格左移旅行商问题 A 5 7 2 1E3B2434D1C综合数据库可用线性并列表（List）表示状态，表中放有旅行商经过的城市，表中最后一个元素就是旅行商当前所在的城市 初始数据库：（A）目标数据库：（A.A)产生式规则R1：IF 没有去过B THEN 下一步去BR2：IF 没有去过C THEN 下一步去CR3：IF 没有去过D THEN 下一步去DR4：IF 没有去过

4、E THEN 下一步去ER5：IF 都去过了 THEN 下一步去A2.2 状态空间的搜索策略搜索过程概述y用图来描述状态空间x节点：对应于状态描述x扩展节点：把适用于某个节点状态的产生式规则运用到该节点而产生其后继节点x指针：从每个后继节点指向其父节点y状态空间的搜索图搜索x搜索过程：从起始节点开始扩展节点，设置指针并检查各后继节点是否为目标节点。如果没有找到目标节点，则继续进行扩展节点和设置指针的过程。当找到目标节点时，沿着有关指针可以从目标节点回朔到起始节点，产生一条解答路径。x由于扩展节点的顺序不同，及搜索的顺序不同，形成了各种不同的搜索方法。爬山法(PP20-23)回溯法 习题y1 P

5、42 第2题y2 P42 第3题y3 P43 第6题(更正:“图2-8”应为“图2-9”。从（2M，2C）节点开始继续原图的搜索。)y贪心法x贪心法与爬山法类似，也是一种不可撤回搜索法。x算法思想:从起始节点出发,每一步都选从当前来看对达到目标最有利的操作.x举例:ABEDC5 7 2 1324431在旅行商的例子中，若在任何一个城市，总是选一个路程最短的未到过的城市先去，则为贪心法。这样得到的解为：ABECDA（14）不可撤回搜索法效率较高，但不能保证找到（最佳）解。如上例的最佳解为：ACDEBA （10）图搜索的一般算法GRAPHSEARCH:(1)建立一个只含有起始节点S的搜索图G,图中

6、每个 节点有一个指向其父节点的指针,S的这一指针 为一特殊值(如0),并把S放入未扩展节点表 OPEN中.(2)建立已扩展的节点表CLOSED,初始时该表为空.(3)LOOP:若OPEN表为空,则失败退出.(4)把OPEN表中的第一个节点移出,放入CLOSED表 中,称其为n节点.(5)若n为目标节点,则成功退出.问题的解是沿指针 追踪G中从n到S的路径而得到的.图搜索算法举例八数码难题初始状态：2 8 3 目标状态：1 2 3 1 6 4 8 0 4 7 0 5 7 6 5(6)扩展节点n,生成不是n的祖先的那些后继节点的集 合M.如果没有后继节点,则转LOOP.(7)把那些不在G中的M的成

7、员作为n的后继节点加入G,并设置一个通向n的指针,把它们加入OPEN表.对 已在G中的M的成员,调整有关指针.(8)按某种方式,重排OPEN表.(9)转LOOP.OPENCLOSED n 2 8 31 6 4 7 0 5 2 8 3 2 8 3 1 6 4 1 6 4 7 0 5 7 0 5 2 8 3 2 8 3 2 8 3 2 8 31 6 4 1 0 4 1 6 4 1 6 40 7 5 7 6 5 7 5 0 7 0 5 2 8 3 2 8 3 2 8 3 2 8 3 2 8 31 0 4 1 6 4 1 6 4 1 6 4 1 6 47 6 5 7 5 0 7 0 5 0 7 5 0

8、 7 52 8 3 2 8 3 2 8 3 2 8 3 2 8 31 0 4 1 6 4 0 6 4 1 6 4 1 6 47 6 5 7 5 0 1 7 5 7 0 5 0 7 5OPENCLOSED n 2 8 3 2 8 3 2 8 3 2 8 3 2 8 3 2 8 31 6 4 0 6 4 1 6 4 1 6 4 1 0 4 1 0 47 5 0 1 7 5 7 0 5 0 7 5 7 6 5 7 6 52 8 3 2 8 3 2 8 3 2 0 3 2 8 3 2 8 3 2 8 3 2 8 31 6 4 0 6 4 0 1 4 1 8 4 1 4 0 1 6 4 1 6 4 1

9、0 47 5 0 1 7 5 7 6 5 7 6 5 7 6 5 7 0 5 0 7 5 7 6 5 2 8 3 2 8 3 2 0 3 2 8 3 2 8 3 2 8 3 2 8 3 2 8 3 2 8 30 6 4 0 1 4 1 8 4 1 4 0 1 6 4 1 6 4 1 0 4 1 6 4 1 6 41 7 5 7 6 5 7 6 5 7 6 5 7 0 5 0 7 5 7 6 5 7 5 0 7 5 02 8 3 2 8 3 2 0 3 2 8 3 2 8 3 2 8 3 2 8 3 2 8 3 2 8 30 6 4 0 1 4 1 8 4 1 4 0 1 6 0 1 6 4 1

10、 6 4 1 0 4 1 6 41 7 5 7 6 5 7 6 5 7 6 5 7 5 4 7 0 5 0 7 5 7 6 5 7 5 02 8 31 6 47 0 52 8 31 6 40 7 52 8 31 0 47 6 52 8 31 6 47 5 02 8 30 6 41 7 52 8 30 1 47 6 52 0 31 8 47 6 52 8 31 4 07 6 52 8 31 6 07 5 4283164705283164075283104765283164750283064175283014765203184765283140765283160754083264175283604

11、175283714055023184765230184765280143765283145760283106754083214765280163754803264175203684175283640175803214765208143765283145706283016754203186754283156704283674105208163754830264175863204175230684175830214765813204765283704615283714650123804765023684175123784065283714605280643175283645170283674150

12、283674015123084765234180765CLOSED:26OPEN:21讨论yOPEN表中节点的排序对算法的影响x先进先出：宽度优先x后进先出：深度优先x启发函数：启发式搜索y第七步搜索图的扩充与指针的调整S126453CLOSED表中的节点OPEN表中的节点每条弧的费用为1，要搜索到达目标节点的最少费用路径搜索图的弧搜索树的指针，指向父节点x注意：因为节点1的后继已在CLOSED表中（已扩展），所以调整指针时，不仅要调整自己的指针，还要调整其后裔的指针（节点4、5）。若其自身的指针未调整，则不必考虑其后裔节点。对其在CLOSED表中的后裔，也要同样处理。y此算法不仅生成一个搜索

13、图G，而且也生成了一棵由指针联接起来的搜索树，搜索树能给出从起始节点到目标节点的唯一路径问题的解2.3 启发式图搜索法引言y盲目搜索的缺点y启发信息x用于决定要扩展的下一个节点x在扩展一个节点时，用于决定要生成哪一个或哪几个后继节点x用于决定某些应该从搜索树中抛弃或修剪的节点估价函数y估价函数：用来估算节点处于最佳求解路径上的希望程度的函数y有序搜索法：按估价函数值来排OPEN表顺序的图搜索算法x单值有序搜索法只有一个估价函数x多值有序搜索法有n个估价函数第一类多值有序搜索：先按f1排序，f1相同时，再按f2排序，(P31八数码难题之例）。第二类多值有序搜索：每个估价函数fi有一定的前提条件p

14、i，pn=true，对条件满足的估价函数按第一类多值有序搜索方法处理。x第一类多值有序搜索的讨论当n=1时，就是普通的单值有序搜索。令n=2，f1为搜索的深度，f2为另一和问题有关的估价函数，则多值有序搜索变成优化的广度优先搜索，即在广度优先的前提下，在同一层深度中优先选择希望较大的节点。令n=2，f1为接近目标状态的程度估计，f2为接近最佳路径的程度估计，则可以在尽快到达目标的前提下求最佳可能的路径。令n=2，f1=depth/m（/为整除运算），f2为另一个估价函数，则为广义的优化广度优先算法。即按深度计算，以每m层为一个阶梯，搜索优先在低阶的阶梯内进行，在每一层阶梯内部，优先展开那些希望

15、大的节点，每一层阶梯实验完毕后，再向高一层阶梯过渡。令n=3，f1为多空格的N数码难题中被移动棋子所在的行数，f2为被移动棋子所在列数的负数，f3为被移动棋子将要去的行数的负数。则搜索的规则为：1.优先移动行数小的棋子，2.对同一行棋子，优先移动列数大的，3.对相同行列的棋子，优先移动向行数大的方向走的棋子。x第二类多值有序搜索的讨论当p1=p2=true时，退化为第一类多值有序搜索。令n=2，p1=freecellm，f1=depth，f2=-depth，算法的意思是：当还有相当数量的存储空间（m）时，用广度优先搜索，一旦存储空间数量减少到某种限度以内，即采用深度优先搜索。令n=2，p1=p

16、endingm，f1=depth，f2=-depth：当已生成而未处理完的节点数小于某个限度时，采用宽度优先搜索，一旦超过这个限度，即采用深度优先搜索。（与上例的异同？）令n=3，p1=all（对方士象全），p2=pair（对方有一对士或一对象），f1=-a*H-b*K，f2=-(a+b)*(H+K)/2，f3=-b*H-a*K；其中H表示我方马的个数，K为我方炮的个数，a和b为常数，0af*(S),故f(t)f*(S)。由(1)的证明可知OPEN表中总有处在最佳路径上的节点n而f(n)f*(S),故n一定排在t之前。可见,只有当最佳路径上的所有中间节点均被扩展后,处于最佳路径上的目标节点才可

17、能排在OPEN表的第一位(3)由上可知，当目标节点进入CLOSED表时，它一定处在最佳路径上,且该路径上的所有节点 均已在CLOSED表中,只要追踪指针,就可以得到 问题的最优解。h函数的启发能力y设A1和A2是求解同一个问题的采用不同h函数的两个A*算法,其估价函数分别为 f1(n)=g1(n)+h1(n)f2(n)=g2(n)+h2(n)其中h1和h2都是h*的下界,如果对所有非目标节点n都有h2(n)h1(n),则在搜索终止时,A1扩展的节点数不会比A2少y证明:我们对搜索树中扩展节点的深度采用数学归纳法进行证明(1)深度为0时,当前节点n=S:若S为目标节点,两个算法都不必扩展任何节点

18、;否则,两个算法都要扩展S.故深度为0时,结论 成立.(2)设A1扩展了A2搜索树中所扩展的深度小于等于k 的所有节点:若A2扩展深度为k+1的任一节点n,由归纳假设,A2搜索树中n的父节点(深度为K)也会由A1 扩展,故节点n也必在A1的搜索树中,且g1(n)g2(n)若A1不能扩展n,则在A1终止时,n必在其OPEN 表中.而A1没有扩展n,说明:f1(n)f*(S)即g1(n)+h1(n)f*(S)我们已经知道g1(n)g2(n),且h1(n)g1(n)+h1(n)f*(S)但A2扩展了节点n,说明f2(n)f*(S).矛盾!故A1也一定会扩展节点n.例如,在八数码难题中,令p(n)为不

19、在位的牌与其 目标位置的距离之和,而f(n)=d(n)+p(n):2 8 3 1 6 4 7 0 5 2 8 3 2 8 3 2 8 31 6 4 1 0 4 1 6 40 7 5 7 6 5 7 5 0 2 8 3 2 0 3 2 8 30 1 4 1 8 4 1 4 07 6 5 7 6 5 7 6 5 0 2 3 2 3 0 1 8 4 1 8 4 7 6 5 7 6 5 1 2 3 0 8 4 7 6 5 1 2 3 1 2 3 8 0 47 8 4 7 6 50 6 5p(n)w(n)CLOSED:5OPEN:7以上结论说明h值越大,启发功能越强,搜索效率越高.特别地(1)h(n)=

20、h*(n)此时f(n)=g(n)+h*(n)f*(S).而只有在最佳路径上的节点才有f(n)=f*(S),故搜 索仅沿最佳路径进行,效率最高.(2)h(n)=0 无启发信息,盲目搜索,效率低.(3)h(n)h*(n)是一般的A算法,效率高,但不能保证找到最佳路 径.有时为求解难题取h(n)h*(n),以提高效率.思考题八数码难题的初始状态和目标状态分别为：2 1 60 4 87 5 31 2 38 0 47 6 5取 h(n)=P(n)+3S(n)其中P(n)是每只棋子离开其应在位置的距离的总和，S(n)是每只棋子排列顺序的计分值的总和，计分方法是中心方格上的棋子计1分，非中心方格中的棋子如其

21、后面跟的棋子和目标顺序不同则计2分，若相同则计0分。试比较使用这样的h函数的A算法和用h(n)=W(n)的A*算法解此题的效率。g函数的作用y如我们只考虑找到目标节点所需的剩余工作量,是否可以不要把g函数包括在f中?如八数码难题取f(n)=w(n)y当h函数不是一个理想的估计时,搜索过程可能会误入歧途,不断向纵深发展,而总不能达到目标.yg函数使搜索增加了一个宽度优先分量,因而确保了隐含图中没有那一部分会永远搜索不到.h的单调限制y调整指针的代价yh的单调限制x如果对所有节点ni及其后继节点nj,有0 h(ni)-h(nj)K(ni,nj)且h(t)=0其中K(ni,nj)表示ni到nj弧线上

22、标记的实际耗散值,t为目标节点.则称h函数满足单调限制.y满足单调限制的h函数必取h*的下界习题yP44 第13题y在P34图2-19的旅行商问题中,设 h(n)=(目标状态表的元素总数现行状态表的元素数)X 7,f1(n)=g(n)+h(n),f2(n)=-d(n),请画出第一类多值有序算法的搜索图.思考题y在h函数启发能力的讨论中,能否证明若h2(n)大于等于h1(n),A1扩展的节点数不会比A2少?y试用数学归纳法证明满足单调限制的h函数必取h*的下界.yH满足单调限制,则在任一搜索路径上,h函数单调下降,f函数单调上升.(P38)yh满足单调限制,所有已扩展的节点必处在从S到该节点的最

23、佳路径上.证明:设n是当前要扩展的任一节点,对从S到n的 最佳路径的长度l进行归纳.(1)l=0时:n=S,显然n已在(从S到n的)最佳路径上.(2)设l k时,结论成立.在l=k+1时,令从S到n的最佳路径为S=n0,n1,nk,nk+1=n,且该序列中已扩展的最后一个节点为 nin,由归纳假设n0ni均已扩展,即ni+1在OPEN表中,且已处在最 佳路径上.i=k,即当前要扩展的节点nk+1=n 已在最佳路径上.若ig*(n)+h(n)于是:f(ni+1)f(n)而当前要扩展的节点是n,应有f(n)f(ni+1),矛盾.2.6 B算法举例:设所搜索的状态空间如图所示n0n5n1n2n4n3

24、11 9 6 13231141600481636其中n5为起始节点,n0为目标节点.任意两节点间的实际耗散值为:2(i-2)-2(j-1)+i-j 1 ji 5 25 i=1,j=0K(ni,nj)=h函数:0 0 i 1 h(ni)=2I1 i 525+4 i=5 n5 n4 n3 n2 n1 n0 36 -36 17 14 13 11 -36 17 14 13 11 43 36 17 14 13 10 43 36 17 14 13 10 42 36 17 14 11 9 42 36 17 14 11 9 41 36 17 14 11 8 41 36 17 14 11 8 40 n5 n4

25、n3 n2 n1 n0 36 17 10 9 7 40 36 17 10 9 7 39 36 17 10 9 6 39 36 17 10 9 6 38 36 17 10 7 5 38 36 17 10 7 5 37 36 17 10 7 4 37 36 17 10 7 4 36 36 17 10 7 4 36B算法y设置一个动态的全局变量F,其值为至目前为止所搜索到的节点的最大f值.y在GRAPHSEARCH第8步排OPEN表时,对节点n:若f(n)F,则按f值排序;若f(n)F,则令f(n)=g(n),再按新的f值排序.总共扩展节点次数(红变白):20+20+21+22+23+20 24上例

26、按B算法的搜索过程:F n5 n4 n3 n2 n1 n0 36 36 -36 36 1 6 9 11 -36 36 1 2 5 7 -36 36 1 2 3 5 -36 36 1 2 3 4 -36 36 1 2 3 4 36 36 36 1 2 3 4 36可以证明:搜索m个节点的图,A*算法的复杂度为O(2(m-1),而B算法为O(m2).用B算法搜索节点数为N的图G时，其复杂性为O(N2).证明：设被B算法展开的节点序列是n1,n2,nr,其中n1为初始节点，nr为目标节点。其中可能有重复的节点，即ni=nj，i=fik fjfik,ikjik+1即删去FS中所有“下降”的f值而得到单

27、调非降序列SFS。由于h=h*，可知f(nr)必在SFS中，因此 rp=rSFS的长度是p，因为任一节点n的估计值不可能在SFS中出现两次(只有当n的第二次的f值小于它的第一次的值时，才会重新进入OPEN表)，故p=N。另外，考察节点序列 fj,fj+1,fj+m 其中 j=ik，j+m=ik+1 fj+d fj，1=dm当存在小于F的f值时，B算法是选择g值最小的节点n展开的，当前OPEN表中所有f=g(n)，ni的后继节点的g值只能比ni的g值更大，因此，除非扩展了f值=F的新节点(在SFS中)，否则n是不可能被第二次展开的。这证明了nj,nj+1,nj+m诸节点的唯一性，因此m=N。综合

28、以上两点，可知B算法的复杂性=O(N2)。2.7 搜索性能的度量衡量搜索算法性能的标准渗透率Py定义：P=L/T其中：L是所求得的到达目标节点的路径长度；T是搜索期间所生成的节点总数（包括目标节点，但不包括起始节点）。y例：八数码难题1（宽度优先）P=5/46=0.108 八数码难题1 f=d(n)+W(n)P=5/13=0.385八数码难题2 f=g+P(n)+S(n)P=18/43=0.419y讨论：xP何时达到最大值？x若八数码难题1的目标节点为26#（宽度优先）P=?有效分枝系数By定义：一棵高度为求解路径长度L，节点数为搜索过程中生成的节点总数T的完全丰满树，其每个中间节点的理论上的分枝数即为有效分枝系数By由定义：B+B2+BL=T 即 (BL-1)B/(B-1)=T 由此，可给出在不同L值时B与T的关系曲线，可根据此曲线查出B，也可在知道B的情况下估计在不同的搜索深度会生成多少节点。y另外由 P=L/T=L(B-1)/B(BL-1)可得到不同B值时的P与L的关系曲线。习题P44 第16题n0n5n1n2n4n311 9 6 11631341300481616*试用数学归纳法证明满足单调限制的h函 数必取h*的下界.第三章