《人工智能讲义AI02N.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《人工智能讲义AI02N.优秀PPT.ppt（69页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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）基本概念状态与操作状态：表示问题求解过程中每一步问题状况的数据结构初始状态：由问题已知的前提、初始条件的原始描述所构成的状态目标状态：问题解决时应当到达的状态操作(算符)
2、：把一种状态变成另一种状态的运算y状态空间法y状态空间：问题求解过程中由初始状态可能到达的全部状态的集合y状态空间法：建立初始状态，在状态空间中进行搜寻，以找到一条从初始状态到达目标状态的（最佳）路径。这条路径（即达到目标状态的操作步骤）就是问题的解。基本系统结构产生式系统的组成综合数据库：初始数据库，目标数据库，中间数据库产生式规则：IF A THEN BA:条件B:操作/结果限制策略：选择可运用的规则和搜寻算法等 限制策略产生式规则 综合数据库 产生式系统的组成八数码难题y综合数据库x可用3X3的二维数组表示一个状态（棋局）初始数据库：2 8 3 1 6 4 7 0 5目标数据库：1 2
3、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 没有去过E THEN 下一
4、步去ER5：IF 都去过了 THEN 下一步去A2.2 状态空间的搜寻策略搜寻过程概述用图来描述状态空间节点：对应于状态描述扩展节点：把适用于某个节点状态的产生式规则运用到该节点而产生其后继节点指针：从每个后继节点指向其父节点y状态空间的搜寻图搜寻y搜寻过程：从起始节点起先扩展节点，设置指针并检查各后继节点是否为目标节点。假如没有找到目标节点，则接着进行扩展节点和设置指针的过程。当找到目标节点时，沿着有关指针可以从目标节点回朔到起始节点，产生一条解答路径。y由于扩展节点的依次不同，及搜寻的依次不同，形成了各种不同的搜寻方法。y爬山法(PP20-23)y回溯法 习题1 P42 第2题2 P42
5、第3题3 P43 第6题(更正:“图2-8”应为“图2-9”。从（2M，2C）节点起先接着原图的搜寻。)y贪心法y贪心法与爬山法类似，也是一种不行撤回搜寻法。y算法思想:从起始节点动身,每一步都选从当前来看对达到目标最有利的操作.y举例: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的成员作为n的后继节点加入G,并
7、设置一个通向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 7 52 8 3 2 8
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 0 47 5 0 1 7 5
9、 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 6 4 1 0 4 1 6
10、 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 428316470528316407528310476528316475028306417528301476520318476528314076528316075408326417528360417528371405502
11、318476523018476528014376528314576028310675408321476528016375480326417520368417528364017580321476520814376528314570628301675420318675428315670428367410520816375483026417586320417523068417583021476581320476528370461528371465012380476502368417512378406528371460528064317528364517028367415028367401512308
12、4765234180765CLOSED:26OPEN:21探讨OPEN表中节点的排序对算法的影响先进先出：宽度优先后进先出：深度优先启发函数：启发式搜寻第七步搜寻图的扩充与指针的调整S126453CLOSED表中的节点OPEN表中的节点每条弧的费用为1，要搜寻到达目标节点的最少费用路径搜寻图的弧搜寻树的指针，指向父节点x留意：因为节点1的后继已在CLOSED表中（已扩展），所以调整指针时，不仅要调整自己的指针，还要调整其后裔的指针（节点4、5）。若其自身的指针未调整，则不必考虑其后裔节点。对其在CLOSED表中的后裔，也要同样处理。x此算法不仅生成一个搜寻图G，而且也生成了一棵由指针联接起来的
13、搜寻树，搜寻树能给出从起始节点到目标节点的唯一路径问题的解2.3 启发式图搜寻法引言盲目搜寻的缺点启发信息用于确定要扩展的下一个节点在扩展一个节点时，用于确定要生成哪一个或哪几个后继节点用于确定某些应当从搜寻树中抛弃或修剪的节点估价函数估价函数：用来估算节点处于最佳求解路径上的希望程度的函数有序搜寻法：按估价函数值来排OPEN表依次的图搜寻算法单值有序搜寻法 只有一个估价函数x多值有序搜寻法有n个估价函数x第一类多值有序搜寻：先按f1排序，f1相同时，再按f2排序，(P31八数码难题之例）。x其次类多值有序搜寻：每个估价函数fi有确定的前提条件pi，pn=true，对条件满足的估价函数按第一类
14、多值有序搜寻方法处理。x第一类多值有序搜寻的探讨x当n=1时，就是一般的单值有序搜寻。x令n=2，f1为搜寻的深度，f2为另一和问题有关的估价函数，则多值有序搜寻变成优化的广度优先搜寻，即在广度优先的前提下，在同一层深度中优先选择希望较大的节点。x令n=2，f1为接近目标状态的程度估计，f2为接近最佳路径的程度估计，则可以在尽快到达目标的前提下求最佳可能的路径。令n=2，f1=depth/m（/为整除运算），f2为另一个估价函数，则为广义的优化广度优先算法。即按深度计算，以每m层为一个阶梯，搜寻优先在低阶的阶梯内进行，在每一层阶梯内部，优先绽开那些希望大的节点，每一层阶梯试验完毕后，再向高一层
15、阶梯过渡。令n=3，f1为多空格的N数码难题中被移动棋子所在的行数，f2为被移动棋子所在列数的负数，f3为被移动棋子将要去的行数的负数。则搜寻的规则为：1.优先移动行数小的棋子，2.对同一行棋子，优先移动列数大的，3.对相同行列的棋子，优先移动向行数大的方向走的棋子。x其次类多值有序搜寻的探讨x当p1=p2=true时，退化为第一类多值有序搜寻。x令n=2，p1=freecellm，f1=depth，f2=-depth，算法的意思是：当还有相当数量的存储空间（m）时，用广度优先搜寻，一旦存储空间数量削减到某种限度以内，即接受深度优先搜寻。x令n=2，p1=pendingm，f1=depth，f
16、2=-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之前。可见,只有当最佳路径上的全部中间节点均被扩展后,处于最佳路径上的目标节点才可能排在OPEN表的第一位(3)由上可
17、知，当目标节点进入CLOSED表时，它确定处在最佳路径上,且该路径上的全部节点 均已在CLOSED表中,只要追踪指针,就可以得到 问题的最优解。h函数的启发实力设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少证明:我们对搜寻树中扩展节点的深度接受数学归纳法进行证明(1)深度为0时,当前节点n=S:若S为目标节点,两个算法都不必扩展任何节点;否则,两个算法都要扩展S.故深度为0时
18、,结论 成立.(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)为不在位的牌与其 目标位置的距离之和,而f(
19、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)=h*(n)此时f(n)=g(n)+h*(
20、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分，非中心方格中的棋子如其后面跟的棋子和目标依次不同则计2分，若相
21、同则计0分。试比较运用这样的h函数的A算法和用h(n)=W(n)的A*算法解此题的效率。g函数的作用y如我们只考虑找到目标节点所需的剩余工作量,是否可以不要把g函数包括在f中?如八数码难题取f(n)=w(n)y当h函数不是一个志向的估计时,搜寻过程可能会误入歧途,不断向纵深发展,而总不能达到目标.yg函数使搜寻增加了一个宽度优先重量,因而确保了隐含图中没有那一部分会恒久搜寻不到.h的单调限制调整指针的代价h的单调限制假如对全部节点ni及其后继节点nj,有0 h(ni)-h(nj)K(ni,nj)且h(t)=0其中K(ni,nj)表示ni到nj弧线上标记的实际耗散值,t为目标节点.则称h函数满足
22、单调限制.满足单调限制的h函数必取h*的下界习题P44 第13题在P34图2-19的旅行商问题中,设 h(n)=(目标状态表的元素总数现行状态表的元素数)X 7,f1(n)=g(n)+h(n),f2(n)=-d(n),请画出第一类多值有序算法的搜寻图.思索题在h函数启发实力的探讨中,能否证明若h2(n)大于等于h1(n),A1扩展的节点数不会比A2少?试用数学归纳法证明满足单调限制的h函数必取h*的下界.yH满足单调限制,则在任一搜寻路径上,h函数单调下降,f函数单调上升.(P38)yh满足单调限制,全部已扩展的节点必处在从S到该节点的最佳路径上.证明:设n是当前要扩展的任一节点,对从S到n的
23、 最佳路径的长度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算法举例:设所搜寻的状态空间如图所示n0n5n1n2n4n311 9 6 13231141600481636其中n5
24、为起始节点,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 n3 n2 n1 n0 36 17 10 9 7 40
25、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算法设置一个动态的全局变量F,其值为至目前为止所搜寻到的节点的最大f值.在GRAPHSEARCH第8步排OPEN表时,对节点n:若f(n)F,则按f值排序;若f(n)F,则令f(n)=g(n),再按新的f值排序.总共扩展节点次数(红变白):20+20+21+22+23+20 24上例按B算法的搜寻过程:F n5 n4 n3 n2 n1 n0
26、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值而得到单调非降序列SFS。由于h=h*，可知f(nr)必在SFS中，
27、因此 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。综合以上两点，可知B算法的困难性=O(N2)。2.7 搜寻性能的
28、度量衡量搜寻算法性能的标准渗透率P定义：P=L/T其中：L是所求得的到达目标节点的路径长度；T是搜寻期间所生成的节点总数（包括目标节点，但不包括起始节点）。例：八数码难题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.419探讨：P何时达到最大值？若八数码难题1的目标节点为26#（宽度优先）P=?有效分枝系数B定义：一棵高度为求解路径长度L，节点数为搜寻过程中生成的节点总数T的完全丰满树，其每个中间节点的理论上的分枝数即为有效分枝系数B由定义：B+B2+BL=T 即 (BL-1)B/(B-1)=T 由此，可给出在不同L值时B与T的关系曲线，可依据此曲线查出B，也可在知道B的状况下估计在不同的搜寻深度会生成多少节点。另外由 P=L/T=L(B-1)/B(BL-1)可得到不同B值时的P与L的关系曲线。习题P44 第16题n0n5n1n2n4n311 9 6 11631341300481616*试用数学归纳法证明满足单调限制的h函 数必取h*的下界.第三章