人工智能第2章

1、第二章与或图搜索问题22.1基本概念2.2 AO*算法2.3博弈树捜索C f (D. C (M, B f (M,(B,L)B)M)B, M)2A基本概念与节点：复合数据库分解后产生若干分量，这些分量称为对应于其父节点的与节点或节点：分量数据库经规则作用后产生一组节点这些节点称为对应于该分量的或节点伊：初始数据库= （C, B, Z ,目标Dg二（儿MM） 仅含M 规则集R, R1：R2:Rb：R4:AND节点尼AND U A9bUAUN必阳口朗晶(D . L )(U B D( L )(M , U )M )( U )伏态空冋m是(C、B、Z)叫与节点呢？还是(Ch (Bh (Z)?是指下面的J个

2、是与关系是关于父节点的与节点HHffiHnm34注h 个节点可以是某个节点的与节点，但同时又是另外一个节点的或节点.超图：由节点集和若干连接符组成的图廉一连接符：从一个父节点指向一组K个后继节点的K条连线.如1_连接符内的K条边彼此之间是与关系.注意： 小一个连接符之间的所有边:任何2个连接符之间是或的关系. 一个连接符是一条路.-SIWHUA UNW豆RSTMRESS例題:4如何在上面的超图中找出一个解图n根节点, 叶节点:不存在任何父节点的节点 不存在任何后继节点的节点筒够ch学岀版社ghuaunwBSJtyRss-6求解图的方法X （从节点n到目标节点集N的解图 从节点“开始.正确选择一

3、个外向連接符就是按照现有连接符的箭头方向去找不能逆着箭头走 从该连接符指向的毎个后继节点出发继续选择一个外向连接符 依次类推，直到由此产生的每个后继节点都是N中的一个元素为止nn解图1解图23M2HUA UNW宜y-无环解图的构成定义一个与或图(：中从节点n到节点集N的 解图记为心如果节点n是N中一个元索，则G由 单一元素组成如果节点n有一个指向节点集 nl, n2. nk 的外向连接符K,使得从每个 ni到N有一个解图(i=U.k).则(T由 节点11、連接符K及nl,n2. nk 中的 每个节点到N的解图组成2否则从I，到N不存在解图.NNN凍纣字dbHH3皿忖UA UNWERS)工y-解

4、图的耗散值计算：设K连接符的耗散值为K, G的耗散值为若n是N的一个元素 MijK(n,N)=O若n有一个到解图中后维节点集 B1.I12ni )的外向连接符，设该连接 符的耗散值为Cm则K(iiN) = Cn+ K(iibN)+ K(ii2JS)+ .-+K(ni8nWMGRPA uzyfRSn、朗Ed左图耗散值 + Kfns) - 2+ l+KliisNi + 2+K(n7，N) 2+ 1+ 2+K(n7*N) +K(ng,N| + Z+KdhN) +K(ii(,N)-2+ 1+ 2+ 0+ + 2+ 0+ 0 -7g能解节点定义： 终节点是能解节点. 如果非终节点有“或”子节点，当且仅当

5、其子节点至少有一个能解，则该 非终节点是能解节点。 如果非终节点有“与”子节点，当且仅当英子节点都能解，则该非终节点 是能解节点.不能解节点定义： 没有后裔的非终节点是不能解节点（该节点是叶节点但不在N中）. 如果非终节点有“或”子节点，当且仅当所有子节点都不能解，则该非终 节点是不能解节点. 如果菲终节点有“与”子节点，至少有一个子节点不能解，则该非终节点是22.2AO*算法1建立一个搜索图G,仅包含初始节点爲S的耗徴值为qG)=h),如果S是终 节点，则标记S为SOLVED2. t ntil s已标记SOI-VED do:3- begin4.6.7.8从S出发沿着有标记的连接持找出一个G的

6、待扩充的局部解图G 任取2中一个非终节点n作为当前节点.扩丸节点,生成n的全部子节点并将其加入到G中.对于未在G中出现 过的子节点Hj,计算其耗散值q(llj)=h(iij)；对于子节点中属于终节点者, 标记SOLVED并赋值为0建丑一个仅包含节点n的单一节点集S Until S为空do;12.12CONTIME11I_AUNyER沁必9.10.It13.begin从S中移出这样节Am.该m节点的子节点不在S中D计算修改m耗散值q(m):对扌旨尙节点集t恂刀 的每个连接 符i,分别计算 q/mkCkqUm)* q(n2i)+. + q(ii|o)令：q(m)= min qm)即：取耗散值最小妁

7、连接符的耗散值作为q(m) 标记该具有最小耗散值的连接符，如果憑来对m的茉个连接符所做的标记与新标记的连接符不同，則保留新标记，去悴原来标记. 如果该连接符的所有后继节点梆巳标记SOLVED,则此m节点标记 SOLVED如果m巳标记SOLVED或者m修正后的耗散值与原来的耗It值不同，则 将m的所有父节点加入到S中，这些父节点必须通过有标记的连按符与 节点m相连end 14. end位置2个标记：连按符标记和节点标记.特征13例题，(预先给出了各节点h值的估计值，实际的h值在搜索中计算得出)循环hh (no) =Co+h (n,) =1+2=3 h (nQ =Co+h (nJ +h (n4)

8、：取 q(no)= min 3, V节点m无标记 Ah(no)=0. h (n,) =2, h (盹) h (皿)=4 h (114)= h (njR h (ng) =2. h(n7)= h(n8)=0N= 扩充节点n, 得到n“%并加入G中，计算各节点耗散值得：h(ni)=2, h(115)=1. h(n4)=l.组成单一节点集S二% 内循环：取出节点%有2个外向连接符，分别计算：(L连接符) =2+l+l=4(2_连接符)4 = 3.标记选定的1_连接符 节点不能标记.内循环结束14詹华:二字出;K迷h S亞做边24 UZERS( TYARMS Z外循环：沿标记取当前节点n=ni扩充节点I

9、h，得到循环2：q(ni)= min 5.rb并加入G中，计算耗散值得* h(n=4, h(rh)=4 组成单一节点|feS=n,内循环：取出节点w叫有2个外向连接符，分别计算： h (n|)=Ci+h (ng) =1+4=5(左 1_連接符)h(ni)=C,+h (nj) =1+4=5(右 1_ 连按符)5 = 5.按照自然排序标记选定的左1.连接符取*节点112无标记节点叫不能标记节点叫的h值由原来的2修改为5, A将叫的父节点no加入到单一节点集S中 重新计算h(no)h (no)=q,+h (n,)=l+5=6(1_连接符)h(no)=Co+h (ns) +旗) =2+l + l=4(

10、2_连接符)取q(no)=niin 6, 4)= 4,取消廉来口。-* n】标记，莖新标记2_连接符V节点m，%无标记节点不能标记，内循环结束15循环3：内循环*内循环:沿标记取当前节点n=n5，扩充节点“5 .得到Ih，Hr并加入G中，计算耗散值得：h(n6)=2. h(n7)=0 , h(n8)=0组成单一节点集S二%* n?. rig是终节点，节点n?, tig取出节点吗，吗有2个外向连接符，分别计算： h (nJ 毛+h (聪)=1+2=3(1_谨接符)h(n5)=C5+h(n (n=2+0 +0 =2 (2_连接符) 3. 2 = 2,记选定的2_连接符标记节点吗并将加的父节点no加

11、入到S中外循环:/取 q(n5)= min*-*节点n?. m有标记 取0,计算h (no) =Co+h (ni)=1+5=6(1_3$ 接符)h(no)=Co+h(n5)+h(th)=2+2+1=5 (2_连接符)/.取q(no)=min 6, 5 = 5,原来连接不变节点Ib有标记但是m无标记 A节点n。不能标记，内循环结束16外循环*循环4:内循环塔沿标记取当前节点n二n54扩充节点比，得皿，m ,计算耗散值得：h (ng) =2, h(18)=0组成单一节点集$=114取节点山，叫有2个外向连接符，计算：hg)毛+h(n5)=1+2 =3 (左 1_连接符)h (np =C+h (ng

12、) =1+0 =2 (右 1 _连接符)取 q(n4)= min 节点n?, ng有标记内循环：取no，计算h (no)=Co+h (ni)=l+5= (1_连接符)h(no)=Co+h (ng) (%) =2+2+1=5(2_连接符):.取q(no)= min (6, 5) = 5,原来连接不变V节点加，m有标记/.标记节点no，内、外循环结束，算法结束1732=标记节点叫并将叫的父节点no加入到S中2,记选定的右1_违接符-i给出每次循环后的搜索图，并给出IK某问题状态图如图4所示。假定k连接符的耗散值为k。各节点的h值假 定为：h(A)=3,h(B)=2,h(C)=6, h(D)=3,h

13、(E)=4. h(F)=2, hG)=3, h(ll=h(l)=O (目标节点)，用算法求解该问题， 求得的解图。_y厂f-2 d .-Ir19IBM的深蓝正在与下棋的卡斯帕罗夫rCT ：5 Ai96年2月第一次比赛结杲：深蓝:胜、负、平、平、负、负97年5月第二次比赛结杲：“深蓝:负、胜、平、平、平、胜2023IBM的“深蓝”（续2）J深蓝的技术指标:32 个 C PU-每个CPU有16个协处理器-每个CPU冇256M内存1991 年，1999年，2001 年，-每个CPU的处理速度为200丿j步/秒“邦里茨”问世“弗里茨”升级为更弗里茨(Deep Fri“更弗里茨”更新了程序，击败了卡斯帕

14、罗犬和阿南徳，以及除了克拉姆尼克之外的所育排名 吐界询I位的棋于2002年10刀，“更刃:里茨”与克拉姆尼克在巴林进 行“人机大战”，思考速度为每秒600万步，双方4比 4战平2003年12月“更年少者”与卡斯帕罗夫举行人机 对抗，双方3比3战平23博弈树搜索博弈树搜索是什么呢？实际上就是一种下棋，博弈就是下棋博弈问题有很多, 在这里主要是以下棋的方式为主，比如，中国象棋，国际象棋，围棋尊尊这类下 棋程序，这类下棋程序有什么特点呢？1、博弈问题特点双人.2个人玩一人一步：双方轮流走.没有连走情况，双方信息完备双方看到的信息是一样的，比如中国瑕棋来说，甲方在棋上 看到的与乙方看到的相同零和：双方

15、是个敌对的关系，走一步棋对自己好的话，对对方就不好.没有 说步棋对双方都好的，或没有说一步棋对双方都不好的ggHUAUNgB沁朗电232.举例.分钱币的侃子问描述T有一摞钱币由2个人轮流将它分成2堆，第一个人先将这堆钱币分成2 堆，第二个人将从这2堆中选择一堆，然后再分成2堆，第一个人然后又从3堆中 选择一堆，然后再分成2堆，变成4堆如何决定胜负：一旦一选手先无法把钱币再分成不相等的两堆时，就得认输对方对方对方先走(4,3)的 UNyERS疔、朋. I、(5,2)、(44J4)(321,1)(2,2,2,1)对方(2,234,1)(2X144,1)注问题规模比较小, 枚钱币不对方怎走,（$3,

16、1）我方必胜可以把所有状态搜索出来看有没有决胜的策略-对于7 我方都可以走成（4, 2. 1）这个状态，从而取得胜利.25414 UNyERST、朋丄3、博弈问题存在的问存在问JR：是不是对于任何一个博弈问题都可以得到这样一个对象策略呢？不是因为问 题太复杂是不可能搜索出所有的状态，就拿中国象棋来说.一盘棋平均走50 步，总状态数大是10假设1毫秒走一步地话，大约需要10倔年。解决问题：通过索的办法，一个水平高的棋子，为什么高7除了各种各样的经验外， 他会算，如何算呢？并不是一下就能看出胜负，而是在当前状态下，这步 棋我方有几种走法，对方有几种走法，这样反复的看下去几步后，他选择出 他认为一个

17、比较好的，就是这样子，那么，能不能把这种思想应用到真实的 博弈中，这就是我们下面将要研究的内容.;别纣字出篮%假定：4、极小极大过程通过例子来看被称为极小极大的*过程圆罔表赤对方在此下战 方框表赤我方在此下棋532-O30AK6任何一种棋局有_种估计的办法，估计棋局格局好 坏的办法，假定能够算，而且算呢？是能够用数字来表示28端节点数字是用评估函数计算得到的.其他节点是不能用评估函数计算的.评估函数大于仇 对我方有利对方不利，越大对我方越有利评估函数小于山 对我方不利，对方有利，越大对我方越不利-” f超纣:字出版迪ggHUA uzy理SB朗氐圆圈衷示对方 方框表示X我方If6O4端节点数字是

18、用评估函数计算得到的，其他节点是不能用评估函数计算的TSlNGnUA UNST、丘題圆圈衷示对方 方框表示*我方w32极小极大的索过程问题: 搜*了儿步节点仍然足很幺.这卑毎一步只产卞2或3个状态.对中国象机 來讲，每个状态都冇十儿种走法，这样搜索几步，会产牛一个爆炸戌的状态。 把捜常树的牛成和格局佔值分开进行-亍致了低效率神态估值和倒推fff汁仲问题解决:将不必塑的分支剪切和搜索树的牛成和格局佔值紧密结介，就足卜面讲的 a -P刘枝。詹华:穴学出磁比=8恥加4姑必RSL315. G -P剪枝定义：极大节点的下界是a,（因为极大节点每次都选择函数值极大的，那它 实际上是极大节点的值是一直增加的，所以我们选择一个下界）极小节 点的上界*P剪枝的条件X后辈节点的P 和先节点的a值时.a剪枝.后辈节点的a 旳先节点的P值时.P剪枝.例子，通过例子我们学习一下a-P剪枝是如何进行的，为了使生成和估计过程R密结合.采用有界度优先策略进行捜索 生成到一定深度节点时.立即计算评价函数，非终结点有条件确定倒推值时就立即计算值SJTY极大结点极小结点5-华/川勺虫 /V氏 C3 3 3 -3A9 O030-235如何剪？a,这时达到了搜索深度限制从左到右,达到搜索深度.就可以进行剪枝了.搜索的顺序：从f开始，到d、b、遇到分支我们就扩展左边节点然后再扩展右边节点.33淸华加出