人工智能期末试题.doc

如有侵权，请联系网站删除，仅供学习与交流人工智能期末试题【精品文档】第 11 页2.证明G是否为,，的逻辑结论。G：2.先把G否定，并放入F中，得到的F1,F2, ¬G为再把F1,F2, ¬G化为子句集，得到其中是由F1化为的两个子句，是由F2化为的两个子句，是由G化为的子句。由子句集可以看出只有唯一的一个Q因此可以得出G不是F的逻辑结构。3.假设张被盗，公安局派出5人去调查。案情分析时，侦查员A说：“赵与钱中至少有一人作案”；侦查员B说：“钱与孙中至少有一人作案”；侦查员C说：“孙与李中至少有一人作案”；侦查员D说：“赵与孙中至少有一人与此案无关”；侦查员E说：“钱与李中至少有一人与此案无关”。如果这5个侦查员的话都是可信的，试用归结演绎推理求出谁是盗窃犯。3.解：(1) 先定义谓词和常量设C(x)表示x 作案，Z 表示赵，Q 表示钱，S 表示孙，L 表示李(2) 将已知事实用谓词公式表示出来赵与钱中至少有一个人作案：C(Z)C(Q)钱与孙中至少有一个人作案：C(Q)C(S)孙与李中至少有一个人作案：C(S)C(L)赵与孙中至少有一个人与此案无关：¬ (C (Z)C(S)，即¬C (Z) ¬C(S)钱与李中至少有一个人与此案无关：¬ (C (Q)C(L)，即¬C (Q) ¬C(L)(3) 将所要求的问题用谓词公式表示出来，并与其否定取析取。设作案者为u，则要求的结论是C(u)。将其与其否取析取，得：¬ C(u) C(u)(4) 对上述扩充的子句集，按归结原理进行归结，其修改的证明树如下：C(Q)C(S)¬C (Z)¬C(S)C(Z)C(Q)C(Q)¬C(S)C(Q)¬C(u)C(u)C(Q)Q/u因此，钱是盗窃犯。实际上，本案的盗窃犯不止一人。根据归结原理还可以得出：C(S)C(L)¬C (Q) ¬C(L)C(S)¬C(Q)C(Q)C(S)C(S)¬C(u)C(u)C(S)S/u因此，孙也是盗窃犯。4.设有如图所示的与/或树，请分别用和代价法、最大代价法求解树的代价。Dt4t3t2t132226157ECBA4. 解：若按和代价法，则该解树的代价为：h(A)=2+3+2+5+2+1+6=21若按最大代价法，则该解树的代价为：h(A)=maxh(B)+5, h(C)+6 = max(h(E)+2)+5, h(C)+6= max(max(2, 3)+2)+5, max(2, 1)+6=max(5+5), (2+6)=105.设有如下一组推理规则：IF THEN （0.6）：IF AND THEN (0.7)：IF THEN H （0.8）：IF THEN H (0.9)且已知CF()=0.5，CF()=0.6,CF()=0.7,求CF(H)。5. 解：(1) 先由r1 求CF(E2)CF(E2)=0.6 × max0,CF(E1)=0.6 × max0,0.5=0.3(2) 再由r2 求CF(E4)CF(E4)=0.7 × max0, minCF(E2 ), CF(E3 )=0.7 × max0, min0.3, 0.6=0.21(3) 再由r3 求CF1(H)CF1(H)= 0.8 × max0,CF(E4)=0.8 × max0, 0.21)=0.168(4) 再由r4 求CF2(H)CF2(H)= 0.9 ×max0,CF(E5)=0.9 ×max0, 0.7)=0.63(5) 最后对CF1(H )和CF2(H)进行合成，求出CF(H)CF(H)= CF1(H)+CF2(H)+ CF1(H) × CF2(H)=0.6926.设 U=V=W=1，2，3，4且有如下规则：IF x is F THEN y is G：IF y is G THEN z is H：IF x is F THEN z is H其中，F,G,H的模糊集分别为F=1/1+0.8/2+0.5/3+0.4/4G=0.1/2+0.2/3+0.4/4H=0.2/2+0.5/3+0.8/4请用模糊关系验证满足模糊三段论。6.先求FG上的关系，=再求GH上的关系,=最后求FGH的关系R，R=2.(龙云献） 简述用A*算法求解问题时为什么会出现重复扩展节点问题，解决的方法有哪些？答：当问题有解时，A*算法总是找到问题的最优解结束。如果h函数定义的不合理，则当扩展一个节点时，不一定就找到了从初始节点到该节点的最优路径，对于这样的节点，就有可能被多次扩展。特别是如果这样的节点处于问题的最优解路径上时，则一定会被多次扩展。解决的方法一是对h函数的定义给出限制，使得h满足单调性。对于满足单调性条件的h，则一定不会出现重复扩展节点问题。二是对A*算法加以改进，使用修正的A*算法进行搜索，则可以减少重复扩展节点问题。3. （刘林洋）简述回溯策略与深度优先策略的不同点。答：回溯搜索策略与深度有限搜索策略最大的不同是深度有限搜索策略属于图搜索，而回溯搜索则不是图搜索。在回溯搜索中，只保留了从初始节点到当前节点的搜索路径。而深度优先搜索，则保留了所有的已经搜索过的路径。4. (张松)设有如下两个模糊关系：请写出R1与R2的合成R1R2。解：R(1,1)=(0.30.2)(0.70.6)(0.20.9)= 0.20.60.2=0.6R(1,2)=(0.30.8)(0.70.4)(0.20.1)= 0.30.40.1=0.4R(2,1)=(10.2)(00.6)(0.40.9)= 0.200.4=0.4R(2,2)=(10.8)(00.4)(0.40.1)= 0.800.1=0.8R(3,1)=(00.2)(0.50.6)(10.9)= 0.20.60.9=0.9R(3,2)=(00.8)(0.50.4)(10.1)= 00.40.1=0.4因此有5.（张松）设U=V=1，2，3，4且有如下推理规则： IF x is 少 THEN y is 多其中，“少”与“多”分别是U与V上的模糊集，设 少=0.9/1+0.7/2+0.4/3 多=0.3/2+0.7/3+0.9/4已知事实为 x is 较少“较少”的模糊集为 较少=0.8/1+0.5/2+0.2/3请用模糊关系Rm求出模糊结论。 解：先用模糊关系Rm求出规则 IF x is 少 THEN y is 多所包含的模糊关系Rm Rm (1,1)=(0.90)(1-0.9)=0.1 Rm (1,2)=(0.90.3)(1-0.9)=0.3 Rm (1,3)=(0.90.7)(1-0.9)=0.7 Rm (1,4)=(0.90.9)(1-0.9)=0.7 Rm (2,1)=(0.70)(1-0.7)=0.3 Rm (2,2)=(0.70.3)(1-0.7)=0.3 Rm (2,3)=(0.70.7)(1-0.7)=0.7 Rm (2,4)=(0.70.9)(1-0.7)=0.7 Rm (3,1)=(0.40)(1-0.4)=0.6 Rm (3,2)=(0.40.3)(1-0.4)=0.6 Rm (3,3)=(0.40.7)(1-0.4)=0.6 Rm (3,4)=(0.40.9)(1-0.4)=0.6 Rm (4,1)=(00)(1-0)=1 Rm (4,2)=(00.3)(1-0)=1 Rm (4,3)=(00.7)(1-0)=1 Rm (3,4)=(00.9)(1-0)=1即：因此有即，模糊结论为 Y=0.3, 0.3, 0.7, 0.86.(张松)设已知：(1) 如果x是y的父亲，y是z的父亲，则x是z的祖父；(2) 每个人都有一个父亲。使用归结演绎推理证明：对于某人u，一定存在一个人v，v是u的祖父。 解：先定义谓词 F(x,y)：x是y的父亲 GF(x,z)：x是z的祖父 P(x)：x是一个人 再用谓词把问题描述出来： 已知F1：(x) (y) (z)( F(x,y)F(y,z)GF(x,z) F2：(y)(P(x)F(x,y) 求证结论G：(u) (v)( P(u)GF(v,u) 然后再将F1，F2和¬G化成子句集： ¬F(x,y)¬F(y,z)GF(x,z) ¬P(r)F(s,r) P(u) ¬GF(v,u) 对上述扩充的子句集，其归结推理过程如下：¬F(x,y)¬F(y,z)GF(x,z)¬GF(v,u)¬F(x,y)¬F(y,z)¬P(r)F(s,r)¬F(y,z)¬P(y)¬P(r)F(s,r)¬P(y)¬P(z)¬P(y)P(u)NIL x/v,z/ux/s,y/ry/s,z/r y/z y/u 由于导出了空子句，故结论得证。1.假设有以下一段天气预报：“贵阳地区今天白天晴，东北风1级，最高气温25º，最低气温16º，降水概率10%，湿度64%。”请用框架表示这一知识。（陈丽丽）解：Frame<天气预报> 地域：贵阳 时段：今天白天 天气：晴 风向：东北 风力：1级 气温：最高：25度 最低：16度 降水概率：10% 湿度：64%2.把下列谓词公式化成子句集：（陈丽丽）(1) (x)(y)(P(x, y)Q(x, y)(2) (x)(y)(P(x, y)(Q(x, y)R(x, y) 解：(1) 由于(x)(y)(P(x, y)Q(x, y)已经是Skolem标准型，且P(x, y)Q(x, y)已经是合取范式，所以可直接消去全称量词、合取词，得 P(x, y), Q(x, y) 再进行变元换名得子句集： S= P(x, y), Q(u, v) (2) 对谓词公式(x)(y)(P(x, y)(Q(x, y)R(x, y)，先消去连接词“”得：(x)(y)(P(x, y)(¬Q(x, y)R(x, y)此公式已为前束范式。再消去存在量词，即用Skolem函数f(x)替换y得：(x)(P(x, f(x)¬Q(x, f(x)R(x, f(x)此公式已为Skolem标准型。 最后消去全称量词得子句集： S=P(x, f(x)¬Q(x, f(x)R(x, f(x) (1) 有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花 。解：定义谓词P(x)：x是人L(x,y)：x喜欢y其中，y的个体域是梅花，菊花。将知识用谓词表示为：(x )(P(x)L(x, 梅花)L(x, 菊花)L(x, 梅花)L(x, 菊花) (2) 新型计算机速度又快，存储容量又大。解：定义谓词NC(x)：x是新型计算机F(x)：x速度快B(x)：x容量大将知识用谓词表示为：(x) (NC(x)F(x)B(x)(3) 凡是喜欢编程序的人都喜欢计算机。解：定义谓词P(x)：x是人L(x, y)：x喜欢y将知识用谓词表示为：(x) (P(x)L(x,pragramming)L(x, computer)、设有如下一组推理规则:r1: IF E1 THEN E2 (0.6)r2: IF E2 AND E3 THEN E4 (0.7)r3: IF E4 THEN H (0.8)r4: IF E5 THEN H (0.9)且已知CF(E1)=0.5, CF(E3)=0.6, CF(E5)=0.7。求CF(H)=?解：(1) 先由r1 求CF(E2)CF(E2)=0.6 × max0,CF(E1)=0.6 × max0,0.5=0.3(2) 再由r2 求CF(E4)CF(E4)=0.7 × max0, minCF(E2 ), CF(E3 )=0.7 × max0, min0.3, 0.6=0.21(3) 再由r3 求CF1(H)CF1(H)= 0.8 × max0,CF(E4)=0.8 × max0, 0.21)=0.168(4) 再由r4 求CF2(H)CF2(H)= 0.9 ×max0,CF(E5)=0.9 ×max0, 0.7)=0.63(5) 最后对CF1(H )和CF2(H)进行合成，求出CF(H)CF(H)= CF1(H)+CF2(H)+ CF1(H) × CF2(H)=0.692一、（夏道丽）请把下面命题用一个语义网络表示出来：（1） 所有动物都具有喜吃食、能运动的属性；（2） 鸟（bird）、鱼（fish）分别都是动物的一种，因此，它们也各自继承了动物的这些属性；（3） 此外，金鱼是鱼的一种，故金鱼就又继承了fish类动物所具有的会游泳、繁殖、可喂养等属性，并又有可观赏等特点；同理，孔雀继承了鸟具有的能下蛋、有翅膀的属性，还具有展翼喜欢表现的习性等。吃食运动解：CANCAN下蛋翅膀繁殖喂养游泳动物CANAKOCANMAYCANHAVE展翼观赏鱼鸟CANAKOAKOCAN 金鱼孔雀二、（夏道丽）假设有以下一段新闻：“今天，一次强度为里氏8.5级的强烈地震袭击下斯洛文尼亚地氏，造成25人死亡和5亿美元的财产损失。下斯洛文尼亚地区主席说：多年来，靠近萨迪壕金斯断层的重灾区一直是一个危险地区。这是本地区发生的第3号地震。”请用框架表示这一知识。解：Frame<地震3>时间：今天地点：下斯洛文尼亚地区伤亡人数：25人财产损失：500，000，000美元震级：8.5断层：萨迪壕金斯五、（赵娉婷）4.5 有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制：(1) 船太小，农夫每次只能带一样东西过河；(2) 如果没有农夫看管，则狼要吃羊，羊要吃菜。请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。题示：(1) 用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。(2) 把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。解：第一步，定义问题的描述形式用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态：S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0) S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)其中，状态S3，S6，S7，S8，S9，S12是不合法状态，S0和S15分别是初始状态和目标状态。第三步，定义操作，即用于状态变换的算符组F由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下：L(i)表示农夫从左岸将第i样东西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。由于农夫必须在船上，故对农夫的表示省略。R (i)表示农夫从右岸将第i样东西带到左岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。同样，对农夫的表示省略。这样，所定义的算符组F可以有以下8种算符：L (0)，L (1)，L (2)，L (3) R(0)，R(1)，R (2)，R (3)第四步，根据上述定义的状态和操作进行求解。该问题求解过程的状态空间图如下：(1,1,l,1)L(2)(0,1,0,1)R(0)(1,1,0,1)L(3)L(1)(0,1,0,0)(0,0,0,1)R(2)R(2)(1,1,1,0)(1,0,1,1)L(2)L(3)(0,0,1,0)R(0)(1,0,1,0)L(2)(0,0,0,0)六、（赵娉婷）1 我们有n(n64)根小木棍，每根长度均不大于50。现在需要将它们拼接成长度相同的若干长木棍，并使得这些长木棍最短。问如何拼接？剪枝一（改变搜索顺序）对木棍长从大到小排个序。直观上，先拼上长木棍接下来用短木棍补充似乎更容易成功拼完。剪枝二(对d的约束)d应该不小于最长的小木棍长度d不大于木棍总长td必须是t的约数剪枝三bool solve(int rest, int start, int step)我们从start到n枚举小木棍编号i，如果此时rest=len(i),那么显然把这根木棍拼上是最好的选择了，也不需要枚举i+1，n号木棍了。 剪枝四 如果len(i)len(j)都具有相同的长度，那么试探完i后应该跳过这些相同长度的小木棍，直接枚举第(j+1)号小木棍。剪枝五 如果当前挑选的小木棍是目前正在拼的木棍的首根木棍，即rest = d, 那么试完i后我们没有必要再去试i+1，而是直接跳回递归上一层。七、（何文娜）设有论域U=u1,u2,u3,u4,u5并设F，G是U上的两个模糊集，且有F=0.9/u1+0.7/u2+0.5/u3+0.3/u4 G=0.6/u3+0.8/u4+1/u5请分别计算FG,FG,F解：FG=（0.90）/u1+(0.70)/u2+(0.50.6)/u3+(0.30.8)/u4+(10)/u5=0.9u1+0.7u2+0.6u3+0.8u4+1/u5FG=0.5u3+0.3u4F=（1-0.9）/u1+(1-0.7)/u2+(1-0.5)/u3+(1-0.3)/u4+(1-0)/u5=0.1u1+0.3u2+0.5u3+0.7u4+1u54、 将下列谓词公式化成子句集（出题人：马智旭）解：5、用语义网络表示：（出题人：邓先玉） 动物能运动、会吃。 鸟是一种动物，鸟有翅膀、会飞。 鱼是一种动物，鱼生活在水中、会游泳。解： 其语义网络如图所示：运动吃动物鸟鱼翅膀飞游泳水中cancanAKOAKOhavelivecancan