人工智能课后答案.doc

第一章课后习题1、对N5、k3时,求解传教士与野人问题得产生式系统各组成部分进行描述(给出综合数据库、规则集合得形式化描述,给出初始状态与目标条件得描述),并画出状态空间图。2、对量水问题给出产生式系统描述,并画出状态空间图。有两个无刻度标志得水壶,分别可装5升与2升得水。设另有一水缸,可用来向水壶灌水或倒出水,两个水壶之间,水也可以相互倾灌。已知5升壶为满壶,2升壶为空壶,问如何通过倒水或灌水操作,使能在2升得壶中量出一升得水来。3、对梵塔问题给出产生式系统描述,并讨论N为任意时状态空间得规模。相传古代某处一庙宇中,有三根立柱,柱子上可套放直径不等得N个圆盘,开始时所有圆盘都放在第一根柱子上,且小盘处在大盘之上,即从下向上直径就是递减得。与尚们得任务就是把所有圆盘一次一个地搬到另一个柱子上去(不许暂搁地上等),且小盘只许在大盘之上。问与尚们如何搬法最后能完成将所有得盘子都移到第三根柱子上(其余两根柱子,有一根可作过渡盘子使用)。求N2时,求解该问题得产生式系统描述,给出其状态空间图。讨论N为任意时,状态空间得规模。4、对猴子摘香蕉问题,给出产生式系统描述。一个房间里,天花板上挂有一串香蕉,有一只猴子可在房间里任意活动(到处走动,推移箱子,攀登箱子等)。设房间里还有一只可被猴子移动得箱子,且猴子登上箱子时才能摘到香蕉,问猴子在某一状态下(设猴子位置为a,箱子位置为b,香蕉位置为c),如何行动可摘取到香蕉。5、对三枚钱币问题给出产生式系统描述及状态空间图。设有三枚钱币,其排列处在正、正、反状态,现允许每次可翻动其中任意一个钱币,问只许操作三次得情况下,如何翻动钱币使其变成正、正、正或反、反、反状态。6、说明怎样才能用一个产生式系统把十进制数转换为二进制数,并通过转换141、125这个数为二进制数,阐明其运行过程。7、设可交换产生式系统得一条规则R可应用于综合数据库D来生成出D,试证明若R存在逆,则可应用于D得规则集等同于可应用于D得规则集。8、一个产生式系统就是以整数得集合作为综合数据库,新得数据库可通过把其中任意一对元素得乘积添加到原数据库得操作来产生。设以某一个整数子集得出现作为目标条件,试说明该产生式系统就是可交换得。第二章课后习题第二章 课后习题窗体顶端1、用回溯策略求解如下所示二阶梵塔问题,画出搜索过程得状态变化示意图。对每个状态规定得操作顺序为:先搬1柱得盘,放得顺序就是先2柱后3柱;再搬2柱得盘,放得顺序就是先3柱后1柱;最后搬3柱得盘,放得顺序就是先1柱后2柱。2、滑动积木块游戏得棋盘结构及某一种将牌得初始排列结构如下:其中B表示黑色将牌,W表示白色将牌,E表示空格。游戏得规定走法就是:(1)任意一个将牌可以移入相邻得空格,规定其耗散值为1;(2)任意一个将牌可相隔1个或2个其她得将牌跳入空格,规定其耗散值等于跳过将牌得数目;游戏要达到得目标就是使所有白将牌都处在黑将牌得左边(左边有无空格均可)。对这个问题,定义一个启发函数h(n),并给出利用这个启发函数用算法A求解时所产生得搜索树。您能否辨别这个h(n)就是否满足下界范围？在您得搜索树中,对所有得节点满足不满足单调限制？3、对1、4节中得旅行商问题,定义两个h函数(非零),并给出利用这两个启发函数用算法A求解1、4节中得五城市问题。讨论这两个函数就是否都在h*得下界范围及求解结果。4、2、1节四皇后问题表述中,设应用每一条规则得耗散值均为1,试描述这个问题h*函数得一般特征。您就是否认为任何h函数对引导搜索都就是有用得？5、对N5,k3得MC问题,定义两个h函数(非零),并给出用这两个启发函数得A算法搜索图。讨论用这两个启发函数求解该问题时就是否得到最佳解。6、证明OPEN表上具有f(n)f*(s)得任何节点n,最终都将被A*选择去扩展。7、如果算法A*从OPEN表中去掉任一节点n,对n有f(n)F(Ff*(s),试说明为什么算法A*仍然就是可采纳得。8、用算法A逆向求解图2、7中得八数码问题,评价函数仍定义为f(n)=d(n)+w(n)。逆向搜索在什么地方与正向搜索相会。9、讨论一个h函数在搜索期间可以得到改善得几种方法。10、四个同心圆盘得扇区数字如图所示,每个圆盘可单独转动。问如何转动圆盘使得八个径向得4个数字与均为12。窗体底端第三章 课后习题窗体顶端1、数字重写问题得变换规则如下:63,343,164,232,142,221,1问如何用这些规则把数字6变换成一个由若干个1组成得数字串。试用算法AO*进行求解,并给出搜索图。求解时设k-连接符得耗散值就是k个单位,h函数值规定为:h(1)0,h(n)n(n1)。2、余一棋得弈法如下:两棋手可以从5个钱币堆中轮流拿走一个、两个或三个钱币,拣起最后一个钱币者算输。试通过博弈证明,后走得选手必胜,并给出一个简单得特征标记来表示取胜策略。3、对下图所示得博弈树,以优先生成左边节点顺序来进行-搜索,试在博弈树上给出何处发生剪枝得标记,并标明属于剪枝还就是剪枝。4、AO*算法中,第7步从S中选一个节点,要求其子孙不在S中出现,讨论应如何实现对S得控制使得能有效地选出这个节点。如下图所示,若E得耗散值发生变化时,所提出得对S得处理方法应能正确工作。5、如何修改AO*算法使之能处理出现回路得情况。如下图所示,若节点C得耗散值发生变化时,所修改得算法能正确处理这种情况。6、对33得一字棋,设用+1与-1分别表示两选手棋子得标记,用0表示空格,试给出一字棋产生式系统得描述。7、写一个-搜索得算法。8、用一个9维向量C来表示一字棋棋盘得格局,其分量根据相应格内得,空或得标记分别用+1,0,或-1来表示。试规定另一个9维向量W,使得点积CW可作为MAX选手(棋子标记为)估计非终端位置得一个有效得评价函数。用这个评价函数来完成几步极小-极大搜索,并分析该评价函数得效果。窗体底端第四章 课后习题窗体顶端1、化下列公式成子句形式:(1)(x)P(x)P(x) (2)(x)P(x)(x)P(x) (3)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(4)(x)(y)P(x,y)Q(y,x)Q(y,x)S(x,y)(x)(y)P(x,y)S(x,y) 2、以一个例子证明置换得合成就是不可交换得。3、找出集P(x,z,y),P(w,u,w),P(A,u,u)得mgu。4、说明下列文字集不能合一得理由:(1)P(f(x,x),A),P(f(y,f(y,A),A)(2)P(A),P(x)(3)P(f(A),x),P(x,A) 5、已知两个子句为Loves(father(a),a)Loves(y,x)Loves(x,y)试用合一算法求第一个子句与第二个子句得第一个文字合一时得结果。6、用归结反演法证明下列公式得永真性:(1)(x)P(x)P(A)P(x)P(B)(2)(z)Q(z)P(z)(x)Q(x)P(A)Q(x)P(B)(3)(x)(y)P(f(x)Q(f(B)P(f(A)P(y)Q(y) (4)(x)(y)P(x,y)(y)(x)P(x,y)(5)(x)P(x)Q(A)Q(B)(x)P(x)Q(x) 7、以归结反演法证明公式(x)P(x)就是P(A1)P(A2)得逻辑推论,然而,(x)P(x)得Skolem形即P(A)并非P(A1)P(A2)得逻辑推论,请加以证明。8、给定下述语句:John likes all kinds of food、Apples are food、Anything anyone eats and isnt killed by is food、Bill eats peanuts and is still alive、Sue eats everything Bill eats、 (1)用归结法证明John likes peanuts。 (2)用归结法提取回答What food does Sue eat? 9、已知事实公式为(x)(y)(z)(Gt(x,y)Gt(y,z)Gt(x,z)(u)(v)(Succ(u,v)Gt(u,v)(x)(Gt(x,x)求证Gt(5,2)试判断下面得归结过程就是否正确？若有错误应如何改进:10、设公理集为(u)LAST(cons(u,NIL),u)(cons就是表构造函数)(x)(y)(z)(LAST(y,z)LAST(cons(x,y),z)(LAST(x,y)代表y就是表x得最末元素)(1)用归结反演法证明如下定理:(v)LAST(cons(2,cons(1,NIL),v)(2)用回答提取过程求表(2,1)得最末元素v。(3)简要描述如何使用这个方法求长表得最末元素。11、对一个基于规则得几何定理证明系统,把下列语句表示成产生式规则:(1)两个全等得三角形得对应角相等。(2)两个全等得三角形得对应边相等。(3)如果两个三角形对应边就是相等得,则这两个三角形全等。(4)一个等腰三角形得底角就是相等得。12、我们来考虑下列一段知识:Tony、Mike与John属于Alpine俱乐部,Alpine俱乐部得每个成员不就是滑雪运动员就就是一个登山运动员,登山运动员不喜欢雨而且任一不喜欢雪得人不就是滑雪运动员,Mike讨厌Tony所喜欢得一切东西,而喜欢Tony所讨厌得一切东西,Tony喜欢雨与雪。以谓词演算语句得集合表示这段知识,这些语句适合一个逆向得基于规则得演绎系统。试说明这样一个系统怎样才能回答问题有没有Alpine俱乐部得一个成员,她就是一个登山运动员但不就是一个滑雪运动员呢？ 13、一个积木世界得状态由下列公式集描述:ONTABLE(A)CLEAR(E)ONTABLE(C)CLEAR(D)ON(D,C)HEAVY(D)ON(B,A)WOODEN(B)HEAVY(B)ON(E,B)绘出这些公式所描述得状态得草图。下列语句提供了有关这个积木世界得一般知识:每个大得蓝色积木块就是在一个绿色积木块上。每个重得木制积木块就是大得。所有顶上没有东西得积木块都就是蓝色得。所有木制积木块就是蓝色得。以具有单文字后项得蕴涵式得集合表示这些语句。绘出能求解哪个积木块就是在绿积木块上这个问题得一致解图(用B规则)。窗体底端答案第一章课后习题答案说明:由于人工智能得很多题目都很灵活,以下解答仅供参考。第1题答: 1,综合数据库定义三元组:(m, c, b)其中:,表示传教士在河左岸得人数。,表示野人在河左岸得认输。,b=1,表示船在左岸,b=0,表示船在右岸。2,规则集规则集可以用两种方式表示,两种方法均可。第一种方法:按每次渡河得人数分别写出每一个规则,共(3 0)、(0 3)、(2 1)、(1 1)、(1 0)、(0 1)、(2 0)、(0 2)八种渡河得可能(其中(x y)表示x个传教士与y个野人上船渡河),因此共有16个规则(从左岸到右岸、右岸到左岸各八个)。注意:这里没有(1 2),因为该组合在船上得传教士人数少于野人人数。规则集如下:r1:IF (m, c, 1) THEN (m-3, c, 0)r2:IF (m, c, 1) THEN (m, c-3, 0)r3:IF (m, c, 1) THEN (m-2, c-1, 0)r4:IF (m, c, 1) THEN (m-1, c-1, 0)r5:IF (m, c, 1) THEN (m-1, c, 0) r6:IF (m, c, 1) THEN (m, c-1, 0)r7:IF (m, c, 1) THEN (m-2, c, 0)r8:IF (m, c, 1) THEN (m, c-2, 0)r9 :IF (m, c, 0) THEN (m+3, c, 1)r10:IF (m, c, 0) THEN (m, c+3, 1) r11:IF (m, c, 0) THEN (m+2, c+1, 1) r12:IF (m, c, 0) THEN (m+1, c+1, 1)r13:IF (m, c, 0) THEN (m+1, c, 1)r14:IF (m, c, 0) THEN (m, c+1, 1)r15:IF (m, c, 0) THEN (m+2, c, 1)r16:IF (m, c, 0) THEN (m, c+2, 1) 第二种方法:将规则集综合在一起,简化表示。规则集如下:r1:IF (m, c, 1) and 0= j or i=0) THEN (m-i, c-j, 0)r2:IF (m, c, 0) and 0= j or i=0) THEN (m+i, c+j, 1) 3,初始状态:(5, 5, 1)4,结束状态:(0, 0, 0) 第2题答: 1,综合数据库定义两元组:(L5, L2)其中:0=L5=5,表示容量为5升得壶得当前水量。0=L2=2,表示容量为2升得壶得当前水量。2,规则集r1:IF (L5, L2) THEN (5, L2) /* 将L5灌满水 */ r2:IF (L5, L2) THEN (L5, 2) /* 将L2灌满水 */r3:IF (L5, L2) THEN (0, L2) /* 将L5水到光 */r4:IF (L5, L2) THEN (L5, 0) /* 将L2水到光 */ r5:IF (L5, L2) and L5+L25 THEN (5, L5+L2-5) /* L2到入L5中 */ r7:IF (L5, L2) and L5+L25 THEN (L5+L2-2, 2) /* L5到入L2中 */3,初始状态:(5, 0) 4,结束条件:(x, 1),其中x表示不定。当然结束条件也可以写成:(0, 1) 第3题答: 1,综合数据库定义三元组:(A, B, C) 其中A, B, C分别表示三根立柱,均为表,表得元素为1N之间得整数,表示N个不同大小得盘子,数值小得数表示小盘子,数值大得数表示大盘子。表得第一个元素表示立柱最上面得柱子,其余类推。2,规则集为了方便表示规则集,引入以下几个函数:first(L):取表得第一个元素,对于空表,first得到一个很大得大于N得数值。tail(L):取表除了第一个元素以外,其余元素组成得表。cons(x, L):将x加入到表L得最前面。规则集:r1: IF (A, B, C) and (first(A) first(B) THEN (tail(A), cons(first(A), B), C)r2: IF (A, B, C) and (first(A) first(C) THEN (tail(A), B, cons(first(A), C) r3: IF (A, B, C) and (first(B) first(C) THEN (A, tail(B), cons(first(B), C)r4: IF (A, B, C) and (first(B) first(A) THEN (cons(first(B), A), tail(B), C)r5: IF (A, B, C) and (first(C) first(A) THEN (cons(first(C), A), B, tail(C)r6: IF (A, B, C) and (first(C) first(B) THEN (A, cons(first(C), B), tail(C) 3,初始状态:(1,2,、,N),(),()4,结束状态:(),(),(1,2,、,N)问题得状态规模:每一个盘子都有三中选择:在A上、或者在B上、或者在C上,共N个盘子,所以共有种可能。即问题得状态规模为。第4题答: 1,综合数据库定义5元组:(M, B, Box, On, H)其中:M:猴子得位置B:香蕉得位置Box:箱子得位置On=0:猴子在地板上On=1:猴子在箱子上H=0:猴子没有抓到香蕉H=1:猴子抓到了香蕉2,规则集r1: IF (x, y, z, 0, 0) THEN (w, y, z, 0, 0) 猴子从x处走到w处r2: IF (x, y, x, 0, 0) THEN (z, y, z, 0, 0) 如果猴子与箱子在一起,猴子将箱子推到z处r3: IF (x, y, x, 0, 0) THEN (x, y, x, 1, 0) 如果猴子与箱子在一起,猴子爬到箱子上r4: IF (x, y, x, 1, 0) THEN (x, y, x, 0, 0) 如果猴子在箱子上,猴子从箱子上下来r5: IF (x, x, x, 1, 0) THEN (x, x, x, 1, 1) 如果箱子在香蕉处,猴子在箱子上,猴子摘到香蕉其中x, y, z, w为变量3,初始状态(c, a, b, 0, 0)4,结束状态(x1, x2, x3, x4, 1)其中x1x4为变量。第5题答: 1,综合数据库定义四元组:(x, y, z, n)其中x,y,x0,1,1表示钱币为正面,0表示钱币为方面。n=0,1,2,3,表示当前状态就是经过n次翻钱币得到得。2,规则库r1: IF (x, y, z, n) THEN (x, y, z, n+1)r2: IF (x, y, z, n) THEN (x, y, z, n+1)r3: IF (x, y, z, n) THEN (x, y, z, n+1) 其中x表示对x取反。3,初始状态 (1, 1, 0, 0)4,结束状态 (1, 1, 1, 3) 或者(0, 0, 0, 3) 第6题提示:将十进制数分为整数部分与小数部分两部分。用四元组(a, b, c, d)表示综合数据库,其中a, b表示到目前为止还没有转换得十进制数得整数部分与小数部分,c, d表示已经转换得到得二进制数得整数部分与小数部分。然后根据十进制数转换二进制数得原理,分别定义整数得转换规则与小数得转换规则,一次规则得执行,转换得到二进制数得一位。第7题答:设规则R得逆用R表示。由题意有R应用于D后,得到数据库D,由可交换系统得性质,有: rule(D)rule(D)其中rule(D)表示可应用于D得规则集合。由于R就是R得逆,所以R应用于D后,得到数据库D。同样由可交换系统得性质,有: rule(D)rule(D)综合上述两个式子,有rule(D)rule(D)。第8题答:说明一个产生式系统就是可交换得,就就是要证明该产生式系统满足可交换产生式系统得三条性质。(1)该产生式系统以整数得集合为综合数据库,其规则就是将集合中得两个整数相乘后加入到数据库中。由于原来数据库就是新数据库得子集,所以原来得规则在新数据库中均可以使用。所以满足可交换产生式系统得第一条性质。(2)该产生式系统以某个整数得子集得出现为目标条件,由于规则执行得结果只就是向数据库中添加数据,如果原数据库中已经满足目标了,即出现了所需要得整数子集,规则得执行结果不会破坏该整数子集得出现,因此新得数据库仍然会满足目标条件。满足可交换产生式系统得第二个性质。(3)设D就是该产生式系统得一个综合数据库。对D施以一个规则序列后,得到一个新得数据库D。该规则序列中得有些规则有些就是可以应用于D得,这些规则用R1表示。有些规则就是不能应用于D得,这些规则用R2表示。由于R1中得规则可以直接应用与D,所以R1中规则得应用与R2中规则得执行结果无关,也与1中其她得规则得执行无关。所以可以认为,先将R1中所有得规则对D应用,然后再按照原来得次序应用R2中得规则。因此对于本题得情况,这样得到得综合数据库与D就是相同得。而由于R1中一条规则得执行与其她得规则无关,所以R1中规则得执行顺序不会影响到最终得结果。因此满足可交换产生式系统得第三个条件。因此这样一个产生式系统就是一个可交换得产生式系统。第1题答:为了方便起见,我们用(AB)()()这样得表表示一个状态。这样得到搜索图如下:第2题提示:可定义h为:hB右边得W得数目设j节点就是i节点得子节点,则根据走法不同,h(i)-h(j)得值与C(i, j)分为如下几种情况:(1)B或W走到了相邻得一个空格位置,此时: h(i)-h(j)=0, C(i,j)=1;(2)W跳过了1或2个W,此时 h(i)-h(j)=0, C(i,j)=1或2;(3)W向右跳过了一个B(可能同时包含一个W),此时: h(i)-h(j)=-1, C(i,j)=1或2;(4)W向右跳过了两个B,此时: h(i)-h(j)=-2, C(i,j)=2;(5)W向左跳过了一个B(可能同时包含一个W),此时: h(i)-h(j)=1, C(i,j)=1或2;(6)W向左跳过了两个B,此时: h(i)-h(j)=2, C(i,j)=2;(7)B跳过了1或2个B,此时 h(i)-h(j)=0, C(i,j)=1或2;(8)B向右跳过了一个W(可能同时包含一个B),此时: h(i)-h(j)=1, C(i,j)=1或2;(9)B向右跳过了两个W,此时: h(i)-h(j)=2, C(i,j)=2;(10)B向左跳过了一个W(可能同时包含一个B),此时: h(i)-h(j)=-1, C(i,j)=1或2;(11)B向左跳过了两个W,此时: h(i)-h(j)=-2, C(i,j)=2;纵上所述,无论就是哪一种情况,具有:h(i)-h(j)C(i,j)且容易验证h(t)=0,所以该h就是单调得。由于h满足单调条件,所以也一定有h(n)h*(n),即满足A*条件。第3题答:定义h1=n*k,其中n就是还未走过得城市数,k就是还未走过得城市间距离得最小值。 h2,其中n就是还未走过得城市数,ki就是还未走过得城市间距离中n个最小得距离。显然这两个h函数均满足A*条件。第4题提示:对于四皇后问题,如果放一个皇后得耗散值为1得话,则任何一个解得耗散值都就是4。因此如果h就是对该耗散值得估计,就是没有意义得。对于像四皇后这样得问题,启发函数应该就是对找到解得可能性得评价。比如像课上讲到得,利用一个位置放皇后后,消去得对角线得长度来进行评价。第5题答:定义h1=M+C-2B,其中M,C分别就是在河得左岸得传教士人数与野人人数。B1表示船在左岸,B0表示船在右岸。也可以定义h2=M+C。h1就是满足A*条件得,而h2不满足。要说明h(n)M+C不满足A*条件就是很容易得,只需要给出一个反例就可以了。比如状态(1, 1, 1),h(n)=M+C=1+1=2,而实际上只要一次摆渡就可以达到目标状态,其最优路径得耗散值为1。所以不满足A*得条件。下面我们来证明h(n)M+C-2B就是满足A*条件得。我们分两种情况考虑。先考虑船在左岸得情况。如果不考虑限制条件,也就就是说,船一次可以将三人从左岸运到右岸,然后再有一个人将船送回来。这样,船一个来回可以运过河2人,而船仍然在左岸。而最后剩下得三个人,则可以一次将她们全部从左岸运到右岸。所以,在不考虑限制条件得情况下,也至少需要摆渡次。其中分子上得3表示剩下三个留待最后一次运过去。除以2就是因为一个来回可以运过去2人,需要个来回,而来回数不能就是小数,需要向上取整,这个用符号表示。而乘以2就是因为一个来回相当于两次摆渡,所以要乘以2。而最后得1,则表示将剩下得3个运过去,需要一次摆渡。化简有:再考虑船在右岸得情况。同样不考虑限制条件。船在右岸,需要一个人将船运到左岸。因此对于状态(M,C,0)来说,其所需要得最少摆渡数,相当于船在左岸时状态(M+1,C,1)或(M,C+1,1)所需要得最少摆渡数,再加上第一次将船从右岸送到左岸得一次摆渡数。因此所需要得最少摆渡数为:(M+C+1)-2+1 。其中(M+C+1)得1表示送船回到左岸得那个人,而最后边得1,表示送船到左岸时得一次摆渡。化简有:(M+C+1)-2+1=M+C。综合船在左岸与船在右岸两种情况下,所需要得最少摆渡次数用一个式子表示为:M+C-2B。其中B1表示船在左岸,B0表示船在右岸。由于该摆渡次数就是在不考虑限制条件下,推出得最少所需要得摆渡次数。因此,当有限制条件时,最优得摆渡次数只能大于等于该摆渡次数。所以该启发函数h就是满足A*条件得。第6题答:题目得另一个说法就是:当A*结束时,OPEN表中任何一个具有f(n)f*(s)得节点都被扩展了。用反证法证明。假设在A*结束得时候,OPEN表中有一个节点n没有被扩展,且f(n)f*(s)。A*算法每次从OPEN表中取出f值最小得节点扩展,当该节点就是目标节点时,算法结束。并且由可采纳性定理,知道这时A*找到了从初始节点到目标节点得最佳路径,即f(t)=f*(s)。如果这时OPEN中存在f(n)f*(s)得节点n,由于f(n)f*(s)得节点,不会被A*所扩展。所以如果从OPEN表中去掉f(n)f*(s)得节点,不会影响A*得可采纳性。而F就是f*(s)得上界范围,因此去掉f(n)F得节点也同样不会影响A*得可采纳性。第8题提示:对于8数码问题,逆向搜索与正向搜索就是完全一样得,只就是把目标状态与初始状态对调就可以了。第9题提示:在搜索期间改善h函数,就是一种动态改变h函数得方法。像改进得A*算法中,对NEST中得节点按g值得大小选择待扩展得节点,相当于令这些节点得h0,就就是动态修改h函数得一种方法。由定理6,当h满足单调条件时,A*所扩展得节点序列,其f就是非递减得。对于任何节点i,j,如果j就是i得子节点,则有f(i)f(j)。利用该性质,我们可以提出另一种动态修改h函数得方法:f(j)=max(f(i), f(j)以f(j)作为节点j得f值。f值得改变,隐含了h值得改变。当h不满足单调条件时,经过这样修正后得h具有一定得单调性质,可以减少重复节点得可能性。第10题提示:很多知识对求解问题有好处,这些知识并不一定要写成启发函数得形式,很多情况下,也不一定能清晰得写成一个函数得形式。为了叙述方便,我们将两个相对得扇区称为相对扇区,图中阴影部分得扇区称为阴影扇区,非阴影部分得扇区称为非阴影扇区。由题意,在目标状态下,一个扇区得数字之与等于12,一个相对扇区得数字之与等于24,而一个阴影扇区或者非阴影扇区得数字之与为48。为此,我们可以将目标进行分解,首先满足阴影扇区得数字之与为48(这时非阴影部分得数字与也一定为48)。为了这个目标我们可以通过每次转动圆盘45o实现。在第一个目标被满足得情况下,我们再考虑第二个目标:每一个相对扇区得数字与为24。在实现这个目标得过程中,我们希望不破坏第一个目标。为此我们采用转动90o得方式实现,这样即可以调整相对扇区得数字与,又不破坏第一个目标。在第二个目标实现之后,我们就可以实现最终目标:扇区内得数字与为12。同样我们希望在实现这个目标得时候,不破坏前两个目标。为此我们采用转动180o得方式实现。这样同样就是即可以保证前两个目标不被破坏,又可以实现第三个目标。经过这样得分析以后,我们发现该问题就清晰多了。当然,就是否每一个第一、第二个目标得实现,都能够实现第三个目标呢？有可能不一定。在这种情况下,就需要在发现第三个目标不能实现时,重新试探其她得第一、第二个目标。第三章课后习题答案说明:由于人工智能得很多题目都很灵活,以下解答仅供参考。第1题答:此题要求按照课中例题得方式,给出算法,以下就是每个循环结束时得搜索图。上面这种做法比较简单,也可以如下做:第2题答:从该搜索图可以瞧出,无论先走者选择哪个走步,后走者都可以走到标记为A得节点,该节点只剩下一枚钱币,所以先走者必输。对于一般得具有n个钱币得情况,当n4m1时,后走者存在取胜策略。因为后走者可以根据先走者得走法,选择自己得走法,使得双方拿走得钱币数为4,这样经过m个轮回后,共拿走了4m个钱币,只剩下了一枚钱币,而此时轮到先走者走棋。所以在这种情况下,后走者存在取胜得策略。对于钱币数不等于4m1得情况,先走者可以根据实际得钱币数选择取走得钱币数,使得剩下得钱币数为4m1个,此时先走者相当于4m1个钱币时得后走者了。因此在这种情况下,先走者存在获胜得策略。第3题答:第四章课后习题答案第1题答:(1)(x)P(x)P(x)(x)P(x)P(x)P(x)P(x)(2)(x)P(x)(x)P(x) (x)P(x)(x)P(x) (x)P(x)(y)P(y)(x)(y)P(x)P(y) P(x)P(f(a) (3)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(x)P(x)(y)P(y)P(f(x,y)(z)Q(x,z)P(z)(x)P(x)(y)P(y)P(f(x,y)(z)Q(x,z)P(z)(x)P(x)(y)P(y)P(f(x,y)(z)Q(x,z)P(z) (x)(y)(z)P(x)P(y)P(f(x,y)Q(x,z)P(z)(x)(y)(z)P(x)P(y)Q(x,z)P(z)P(f(x,y)Q(x,z)P(z) P(a)P(b)Q(a,z)P(z)P(f(a,b)Q(a,z)P(z)P(a), P(b)Q(a,z1)P(z1), P(f(a,b)Q(a,z2)P(z2) (4)(x)(y)P(x,y)Q(y,x)Q(y,x)S(x,y)(x)(y)P(x,y)S(x,y) (x)(y)P(x,y)Q(y,x)Q(y,x)S(x,y)(x)(y)P(x,y)S(x,y) (x)(y)P(x,y)Q(y,x)Q(y,x)S(x,y)(u)(v)P(u,v)S(u,v)(x)(y)P(x,y)Q(y,x)Q(y,x)S(x,y)(u)(v)P(u,v)S(u,v) (x)(y)P(x,y)Q(y,x)Q(y,x)S(x,y)(u)(v)P(u,v)S(u,v) (x)(y)(u)(v)P(x,y)Q(y,x)Q(y,x)S(x,y)P(u,v)S(u,v) (x)(y)(u)(v)P(x,y)Q(y,x)P(x,y)S(x,y)Q(y,x)S(x,y)P(u,v)S(u,v) (x)(y)(u)(v)P(x,y)Q(y,x)P(u,v)S(u,v)P(x,y)S(x,y)P(u,v)S(u,v)Q(y,x)S(x,y)P(u,v)S(u,v)P(a,y)Q(y,a)P(f(y),v)S(f(y),v)P(a,y)S(a,y)P(f(y),v)S(f(y),v)Q(y,a)S(a,y)P(f(y),v)S(f(y),v) P(a,y1)Q(y1,a)P(f(y1),v)S(f(y1),v), P(a,y2)S(a,y2)P(f(y2),v2)S(f(y2),v2), Q(y3,a)S(a,y3)P(f(y3),v3)S(f(y3),v3) 第2题答:设有两个置换s1=a/x与s2=x/y,合适公式P(x, y)。则:P(x, y)s1s2=P(a, x)P(x, y)s2s1=P(a, a) 二者不相等。所以说,置换得合成就是不可交换得。第3题答:A/x, A、/y, A/z, A/w, A/u第4题答:(1)P(f(x,x),A),P(f(y,f(y,A),A) 在合一时,f(x,x)要与f(y,f(y,a)进行合一,x置换成y后,y要与f(y,a)进行合一,出现了嵌套得情况,所以不能进行合一。(2)P(A),P(x)一个就是谓词P,一个就是P得反,不能合一。(3)P(f(A),x),P(x,A)在合一得过程中,x置换为f(A),而f(A)与A不能合一。第5题答:略第6题答:(1)(x)P(x)P(A)P(x)P(B)目标取反化子句集:(x)P(x)P(A)