设为首页 - 加入收藏
广告 1000x90
您的当前位置:E乐彩票app下载 > 博弈树搜索 > 正文

人工智能与或图搜索

来源:未知 编辑:admin 时间:2019-04-20

  2、文档下载后都不会有金锄头文库的水印,预览文档经过压缩,下载后原文更清晰;

  3、所有的PPT和DOC文档都被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;下载前须认真查看,确认无误后再购买;

  4、所有文档都是可以预览的,金锄头文库作为内容存储提供商,无法对各卖家所售文档的真实性、完整性、准确性以及专业性等问题提供审核和保证,请慎重购买;

  5、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据;

  第四章 与或图搜索,4.1 问题归约法 4.2 与或图 4.3 与或图搜索 4.4 AO*算法 4.5 博弈树的搜索,4.1 问题归约法,当问题复杂时,可把初始问题分解成若干简单的子问题,若子问题仍复杂,可再进一步分解,直到这些子问题的解可直接得到。这种问题的描述和求解方法,称为问题归约法。 可直接解答的问题称为本原问题,它是不必证明的、自然成立的。 归约法的问题表示可由下列三部分组成 1)一个初始问题的描述; 2)一组把问题变成子问题的算子; 3)一组本原问题的描述 问题归约由问题出发,运用操作算子产生一些子问题,对子问题再运用操作算子产生子问题的一些子问题,,一直进行到产生的子问题都为本原问题,则问题得解。由于一问题所产生的若干子问题内的关系是并列的、同时的,所以,用与或图便能表示问题归约的状态空间。即对问题归约的描述可以很方便地用一个与或图的结构来表示它。,4.2 与或图,与节点一个归约算子能够把单个问题变为几个子问题组成的集合,这时只有当所有子问题都有解,该父辈节点才有解。这种关系称为“与”关系,对应的节点称为与节点。 或节点几个算子适用于同一个问题,从而产生不同的后继问题集合。这时只要有一个后继集合有解,则意味该父辈问题有解,此时关系是“或”关系,对应节点称为或节点。,,与节点由与运算连接,如图(a)中Q和R,并用一条弧线将相关的边连接起来,这种弧线及所相关的边被称为超弧。 或节点由或运算连接,如图4-1(b)中Q和R 。,与或图是一种普遍图,这种图被称为超图。也就是说,超图是存在超弧的图。一超弧所相关的边数(K)被称为该超弧的度,实现的连接为K-连接。 K连接符 假设节点N被某个算子归约为一个包含K个子问题的替换集合,K  1,我们用一个叫做K连接符的超弧线把它们和节点N连接起来。每个K连接符从一个父节点指向一个含有K个后继节点的集合,并说N有一个外向连接符K。 问题归约描述对应的结构就是一个与或图,原始问题描述对应于起始节点(或根节点),本原问题所对应的节点叫做叶节点。在某些特殊情况下,不出现任何与节点(所有超弧的度都为1),此时的图成了普通图,问题归约描述也就成为状态空间描述。,从图4-2所示的与或图中,节点n0有两个连接符1-连接符指向节点n1;2-连接符指向节点集合{n4、n5};对于节点n0来讲,n1可称为或节点,n4、n5可称为与节点。,,图4-2、与或图,4.3 与或图搜索,在与或图上执行搜索的过程,其目的在于表明起始节点是有解的,也就是说,搜索不是去寻找目标节点,而是寻找一个解图。 一个节点被称为是能解节点SOLVED,其递归定义为 1.终节点是能解节点(直接与本原问题相关联); 2.若非终节点 有“或”子节点时,当且仅当其子节点至少有一个能解 ,该非终节点才能解; 3.若非终节点有“与”子节点时,当且仅当其子节点均能解,该非终节点才能解。 一个节点被称为是不能解节点UNSOLVED,其递归定义为 1.没有后裔的非终节点是不能解的节点; 2.若非终节点有“或”子节点时,当且仅当所有子节点均不能解时,该非终节点才不能解; 3.若非终节点有“与”子节点时,当至少有一子节点不能解时,该非终节点才不能解。,一个解图就是那些能解节点的子图,是包含一节点(n)到目的节点集合(N)的、连通的能解节点的子图。其定义如下 一个与或图G中,从节点 n 到节点集 N 的解图记为 G, G是 G的子图。 1.若 n 是 N 的一个元素,则 G由单个节点n组成; 2.若 n 有一个指向节点集 {n1,nk}的外向连接符 K,使得从每一个节点ni到 N有一个解图 i1,,k,则 G由节点 n,连接符K,以及 {n1 ,,nk}中的每一个节点到 N的解图所组成; 3.否则 n 到 N 不存在解图。,如果 ns 为初始节点,则此解图即为所求解问题的解图。在对普通图的解路求解或搜索中,一般须计算或估计其路径代价,同样地,在搜索与或图解图的过程中,也需要进行耗散值的计算。设连接符的耗散值规定为k-连接符的耗散值k,若解图的耗散值记为kn, N,则可递归计算如下 1.若n是N的一个元素,则kn, N0; 2.若n有一个外向连接符指向后继节点集合{n1,ni},并设该连接符的耗散值为Cn,则 kn, NCnkn1, Nkni, N。 具有最小耗散值的解图称为最佳解图,其值也用h*n标记。求解问题的解图的值为h*s。,解图的求法是从节点n开始,正确选择一个外向连接符,如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止。图4-3给出了上图所示与或图中n0 {n7,n8}的三个解图(解图的耗散值分别为8,7,5)。,图4-3、三个解图,,与或图搜索与状态空间图搜索的不同,搜索目的是证明起始节点是否可解,而可解节点是递归定义的,取决于后继节点是否可解,即搜索是否找到可解的叶节点。因此,搜索有可解标示过程和不可解标示过程。 初始节点被标示为可解,则搜索成功结束,初始节点被标示为不可解,则搜索失败。 一旦发现不可解节点,应把该节点从图中删去。,4.4 AO*算法,假设估价函数q nhn ;G为当前扩展生成的与或图;G为一后选局部解图,是G的一个子图;hn是节点n的启发函数;而qn是节点n的估价函数;是从节点n到一组终叶节点的一个最优解图的一个代价估计; 过程AO* 1.建立一个搜索图G,Gs,计算qshs,IF GOALs THEN Ms, SOLVED;开始时图G只包括s,耗散值估计为hs,若s是终节点,则标记上能解。 2. Until s已标记为SOLVED, do 3. Begin 4. G FINDG;根据连接符标记(指针)找出一个待扩展的局部解图G(G的连接符将在第11步中标记)。 5. nG中的任一非终节点;选一个非终节点作为当前节点。 6. EXPANDn,生成子节点集{ni}, GADD{ni}, G,计算 qnihni,如果ni  G, IF GOALni THEN Mni, SOLVED; 对G中原未出现的n的子节点添加到G中, 并计算其耗散值,若n的子节点为终节点则加能解标记。,7、Sn; 建立含n的单一节点集合S.(待修正的节点集合) 8、 Until S为空, do 9、 begin 10、 REMOVEm, S,当mc  S;从集合S中移出一节点m,要求这个m在图G中的子节点mc,不出现在S中。(从底层开始修正) 11、  根据下面方法修改m的耗散值qm 对m指向节点集n1i,n2i,nki的每一个连接符i分别计算qi, qi mCiqn1iqnki, qm min qi m; 对m的i个k-连接符,取计算结果最小的那个连接符的耗散值为节点m 的qm。  加指针到min qi m的连接符上,或把指针修改到min qi m的连接符上,即原来指针与新确定的不一致时应删去. IF Mnji, SOLVED THEN Mm, SOLVED;(j1,2,,k)若该连接符的所有子节点都是能解的,则m也标上能解. 12、 IF Mm, SOLVED  qm  q0m THEN ADDma, S; m 能解或修正的耗散值与原先估算q0不同,则把m的所有先辈节点ma,添加到S中. (修正向上传递) 13、 end 14、end,AO*搜索算法可以理解为两个主要过程的重复。首先,是一个自上而下的图生长过程(4-6步),先通过有标记的连接符,找到目前为止最好的一个局部解图,然后对其中一个非终节点进行扩展,并对其后继节点赋估计耗散值和加能解标记。 第2过程是一个自下而上的估价函数值的修正、连接符的标记和SOLVED的标注过程。 耗散值的修正从刚被扩展的节点n开始,其修正耗散值qn取对h*n的所有估计值中最小的一个,然后根据耗散值递归计算公式逐级向上修正其先辈节点的耗散值,只有下层节点耗散值修正后,才可能影响到上一层节点的耗散值,因此必须自底向上一直修正到初始节点。,假设各节点的启发函数值分别为 hn0 3,hn1 2,hn2 4,hn3 4,hn4 1,hn5 1,hn6 2,hn7 hn8 0(目标节点),k-连接符的耗散值k。 应用AO*算法,经过四个循环,可找到解图。 在第一次循环中,扩展节点n0;下一次循环扩展节点n1;接着扩展节点n5;最后扩展节点n4。在节点n4被扩展之后,节点n0便被标注SOLVED,此时,通过向下跟踪有标记的连接符,便获得了此状态空间的解图。,,图4.4、AO* 搜索过程 每个节点旁边标记的是启发函数hn值(不带括号)或估价函数q(n)的修正值(带括号);短箭头用来标记连接符,标明侯选局部解图;已经标注SOLVED的节点用实心圆来表示。,4.5 博弈树的搜索,博弈一直是启发式搜索的一个重要应用领域,早在20世纪60年代就已经出现若干个博弈系统,美国IBM公司的“深蓝”系统已达到了国际特级大师级的水平(97年胜了卡斯帕罗夫)。2001年,德国的“更弗里茨”软件击败了世界排名10位中的9位。本节所指博弈问题是指二人完备博弈 1.由二人对垒,二人严格地轮流走步,自己的走步自己选择, 2.任何一方都完全知道对方过去的走步情况和今后可能的走步,不包括碰运气的情况。 由于在决定自己走步时只需考虑对自己有利的一步或,而考察对方时,则应考虑对方所有可能的走步与,因此,能够利用与或图搜索算法来解决博弈问题。另外,由于两人严格地轮流走步,使博弈状态图呈现出严格的与或图的交替层次,所以,可设计特殊的与或图搜索算法博弈树搜索算法,使搜索更有效。,4.5.1 Grundy 博弈,例假设桌上放有一堆(7个)钱币,由两人轮流进行分堆,要求每人每次只把其中某堆钱币分成数目不相等的两小堆,最后不能分下去的人为负。 该问题的描述 综合数据库用无序数字序列x1,x2,,xn表示n堆钱币不同的个数,再用两个说明符号MIN方和MAX方代表选手,无序数列和符号M组合(x1,x2,,xn,M)就代表该由某个选手走步的状态。MAX方代表努力赢的一方,或尽力将其赢的几率最大化的一方;而MIN方代表力图使MAX方偏离取胜目标的另一方。博弈双方总是偏向最有利于自己的状态前进,反过来说,也就是MIN方和MAX方总是移向最不利于对方的状态。 规则,,,图4-5、Grundy博弈问题状态空间图,,设初始状态为(7,MIN),则该问题的状态空间图如图4-5所示,图中所有终节点均表示要走步的选手必输的情况,取胜方的目标是设法使棋局发展为结束在对方走步时的终节点上,因此节点A是MAX的搜索目标,而节点B,C则为MIN的搜索目标。,搜索策略要考虑的问题是(以MAX方的角度) 对MIN走步后的每一个MAX节点(该状态由MIN控制),必须证明MAX对MIN所有可能走的每一个棋局对弈后都能够获胜,即MAX必须考虑应付MIN的所有招法,这是一个与的含义,因此含有MAX符号的节点可看成与节点。 对MAX走步后的每一个MIN节点(该状态由MAX控制),只需要证明MAX有一步能走赢就可以,即MAX只要考虑能走出一步棋使MIN无法招架就成,因此含有MIN符号的节点可看成或节点。 于是对弈过程的搜索图就呈现出与或图表示的形式,从搜索图可以看出,MAX方存在完全取胜的策略,图中所示部分就代表了这种策略,这时不论MIN怎么走,MAX方均可取胜。因而寻找MAX的取胜的策略便和求与或图的解图能解→能胜一致起来,即MAX要获胜,必须对所有与节点取胜,但只需对一个或节点取胜,这就是一个解图。因此实现一种取胜的策略就是搜索一个解图的问题,解图就代表一种完整的博弈策略。,

  本文(人工智能与或图搜索)为本站会员(wanguosheng)主动上传,金锄头文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即阅读金锄头文库的“版权提示”【网址:】,按提示上传提交保证函及证明材料,经审查核实后我们立即给予删除!

本文链接:http://mzi-ads.com/boyishusousuo/260.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top