人工智能期末试题

1、2.证明 G 是否为 Fi, F2,Fn的逻辑结论。FiyP(xR (Q(X)AR(X)Fi : 5p(X)AS(X)G：(玉)(S(X)AR(X)2.先把 G 否定，并放入 F 中，得到的F1,F2, ? 6 为 _ (WgP(X片(Q(x)八R(x),(玉!CP(x)八S(x), ?( Gx e(x)AR(x)再把 F1,F2, ? G化为子句集，得到1-P(x) vQ(x)2P(y) vR(y)3P(a)4S(a)5S(b) vR(b)其中是由 F1 化为的两个子句，是由 F2 化为的两个子句，是由 由子句集可以看出只有唯一的一个 Q 因此可以得出 G 不是 F 的逻辑结构。3.假设张被

2、盗，公安局派出5 人去调查。案情分析时，侦查员A 说：“赵与钱中至少有一人作案”；侦查员 B 说：“钱与孙中至少有一人作案”；侦查员 C 说：“孙与李中至少有一人作案” 侦查员D 说：“赵与孙中至少有一人与此案无关”；侦查员 E 说：“钱与李中至少有一人与此 案无关”。如果这 5个侦查员的话都是可信的，试用归结演绎推理求出谁是盗窃犯。3.解：(1)先定义谓词和常量 设 C(x)表示 x 作案，Z 表示赵，Q 表示钱，S 表示孙，(2)将已知事实用谓词公式表示出来 赵与钱中至少有一个人作案： 钱与孙中至少有一个人作案： 孙与李中至少有一个人作案：赵与孙中至少有一个人与此案无关：钱与李中至少有一个

3、人与此案无关：(3)将所要求的问题用谓词公式表示出来，并与其否定取析取。 设作案者为 U，则要求的结论是 C(u)。将其与其否取析取，得：? C(u) V C(u)表示李C(Z) V C(Q)C(Q) V C(S)C(S) V C(L)? (C (Z) A C(S)? (C (Q) A C(L)即？ C (Z) V ? C(S) 即？C (Q) V ? C(L)G 化为的子句。按归结原理进行归结，其修改的证明树如下:因此，钱是盗窃犯。实际上，本案的盗窃犯不止一人。根据归结原理还可以得出:(4)对上述扩充的子句集，因此，孙也是盗窃犯。4.设有如图所示的与/或树，请分别用和代价法、最大代价法求解树

4、的代价。1 a1* E I2若按和代价法，则该解树的代价为:t3t44.解： h(A)=2+3+2+5+2+1+6=t21若按最大代价法，则该解树的代价为：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)=10r1:IFE1THENE2(0.6 )r2:IF E2ANDE3THEN E4(0.7)r3:IF E4THENH(0.8 )r4:IF E5THENH (0.9)5.设有如下一组推理规则:且已知5.解：CF(E2)=0.6 X max0,CF(E1

5、)=0.6 X max0,0.5=0.3(2)再由 r2 求 CF(E4)CF(E4)=0.7 X max0, mi nCF(E2 ), CF(E3 )=0.7 X max0, min0.3, 0.6=0.21(3)再由 r3 求 CF1(H)CF(Ei)=0.5，CF(E3)=O.6,CF( E5)=O.7,求 CF(H)。(1)先由 r1 求 CF(E2)CF1(H)= 0.8 X max0,CF(E4)=0.8 X max0, 0.21)=0.168(4)再由 r4 求 CF2(H)CF2(H)= 0.9 X max0,CF(E5)=0.9 X max0, 0.7)=0.63(5)最后对

6、 CF1(H )和 CF2(H)进行合成，求出CF(H)CF(H)= CF1(H)+CF2(H)+ CF1(H)X CF2(H)=0.6926.设 U=V=W= 1，2，3，4且有如下规则:1：IF x is F THEN y is GIF y is G THEN z is HIF x is F THEN z is H3:其中，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请用模糊关系 RC验证满足模糊三段论。000.10.26.先求 FxG 上的关系 Rc1,Rci=L00.10.10.10

7、.20.20.2再求 GXH 上的关系 RC2, RC2 =0.40.40.40.40000 -00.10.10.100.20.20.2L00.20.40.4最后求 FXGXH 的关系 R R= RcRc1=00.20.40.4100.20.40.400.20.40.4L00.20.40.42.（龙云献）简述用A*算法求解问题时为什么会岀现重复扩展节点问题，解决的方法有哪些?答：当问题有解时，A*算法总是找到问题的最优解结束。如果 展一个节点时，不一定就找到了从初始节点到该节点的最优路径， 多次扩展。特别是如果这样的节点处于问题的最优解路径上时， 法一是对h函数的定义给岀限制，使得 现重复扩展

8、节点问题。二是对 扩展节点问题。h满足单调性。对于满足单调性条件的h函数定义的不合理， 则当扩 对于这样的节点，就有可能被 则一定会被多次扩展。解决的方h，则一定不会岀A*算法加以改进，使用修正的A*算法进行搜索，则可以减少重复3.（刘林洋）简述回溯策略与深度优先策略的不同点。答：回溯搜索策略与深度有限搜索策略最大的不同是深度有限搜索策略属于图搜索， 搜索则不是图搜索。 在回溯搜索中，只保留了从初始节点到当前节点的搜索路径。 索，则保留了所有的已经搜索过的路径。而回溯而深度优先搜4.（张松）设有如下两个模糊关系:100.4R2 =0.60.4L00.510.90.10.3 0.70.20.8R

9、i =请写岀R1与R2的合成R1O Rao解：R(1,1)=(0.3 A 0.2) V (0.7 A 0.6) V (0.2 R(1,2)=(0.3A 0.8) V (0.7 A 0.4) V R(2,1)=(1R(2,2)=(1R(3,1)=(0R(3,2)=(0因此有A 0.2)A 0.8)A 0.2)A 0.8)V (0 A 0.6) V (0.4V (0 A 0.4) V (0.4V (0.5V (0.5A 0.6)A 0.4)V (1V (1A 0.9)= 0.2 V 0.6 V 0.2=0.6(0.2 A 0.1)= 0.3 V 0.4 V 0.1=0.4A 0.9)= 0.2A

10、0.1)= 0.8A 0.9)= 0.2A 0.1)= 0 VV 0V 0.4=0.4V 0V 0.1=0.8V 0.6 V 0.9=0.90.4 V 0.1=0.4RiQR20.60.40.410.80.90.45.(张松)设U=V=1,且有如下推理规则：IF x is2,3,4少THEN yis其中，“少”与“多”分别是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求岀模糊结论。解：先用模糊关系IF x is所包含的模糊关系Rmm(1,1) =

11、(0.9m(1,2) = (0.9m(1,3) = (0.9m(1,4) = (0.9m(2,1) = (0.7m(2,2) = (0.7m(2,3) = (0.7m(2,4) = (0.7m(3,1) = (0.4m(3,2) = (0.4m(3,3) = (0.4m(3,4) = (0.4m(4,1) = (0m(4,2) = (0m(4,3) = (0m(3,4) = (0Rm求岀规则少THEN y isRRRRRRRRRRRRRRRR即：AAAAAAAAAAAA0) V (1-0.9)=0.10.3)0.7)0.9)V (1-0.9)=0.3V (1-0.9)=0.7V (1-0.9)

12、=0.70) V (1-0.7)=0.30.3)0.7)0.9)V (1-0.7)=0.3V (1-0.7)=0.7V (1-0.7)=0.70) V (1-0.4)=0.60.3)0.7)0.9)V (1-0.4)=0.6V (1-0.4)=0.6V (1-0.4)=0.6A 0) V (1-0)=1A 0.3)A 0.7)A 0.9)V (1-0)=1V (1-0)=1V (1-0)=1= 0.3,030.7,0.8 即，模糊结论为Y=0.3, 0.3, 0.7, 0.86.(张松)设已知：(1)如果x是y的父亲，y是z的父亲，则x是z的祖父；(2)每个人都有一个父亲。使用归结演绎推理证明

13、：对于某人U, 定存在一个人V，v是U的祖父。解：先定义谓词F(x,y):x是y的父亲GF(x,z):x是z的祖父P(X):x是一个人再用谓词把问题描述岀来：已知F1:(VX)( Vy) ( Vz)( F(x,y) A F(y,z) f GF(x,z) F2:(V y少(X)求证结论G: ( 3 u)(然后再将F1,F2和？1？ F(x,y) V ?2？ P(r) V F(s,r)3P(u)4? GF(v,u)对上述扩充的子句集，其归结推理过程如下：因此有110.10.30.30.30.60.70.70.60.90.70.6Y =0.8,0.5,020 00.10.30.70.90.30.30

14、.70.70.60.6 0.60.6L1111二F(x,y)3v)( P(u)fGF(v,u)G化成子句集：F(y,z) V GF(x,z)1级，最高气温25o，最低气温16o，降水概率10%湿度64%”请用框架表示这一知识。(陈丽丽)解：Framev天气预报地域：贵阳时段：今天白天天气：晴风向：东北风力：1级气温：最高：25度最低：16度降水概率：10%湿度：64%(陈丽丽)A Q(x, y)V (Q(x, y) f R(x, y)y) A Q(x, y)已经是Skolem标准型，且P(x, y) A Q(x, y)已经是合取范式，所以可直接消去全称量词、合取词，得 P(x, y), Q(x

15、, y)再进行变元换名得子句集：S= P(x, y), Q(u, v)_(2)对谓词公式(Vx)( 3y)(P(x, y) V (Q(x, y) f R(x, y)，先消去连接词“f”得:(P x)(引)(P(x, y) V (? Q(x, y) V R(x, y)此公式已为前束范式。再消去存在量词，即用Skolem函数f(x)替换y得：(P x)(P(x, f(x) V ? Q(x, f(x) V R(x, f(x)此公式已为Skolem标准型。最后消去全称量词得子句集：S=P(x, f(x)V ? Q(x, f(x) V R(x, f(x)(1)有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢

16、梅花又喜欢菊花解：定义谓词P(x):x是人L(x,y):x喜欢y其中，y的个体域是梅花，菊花。将知识用谓词表示为：(3 x )(P(X)fL(x,梅花)V L(x,菊花)V L(x,梅花)A L(x,菊花)(2)新型计算机速度又快，存储容量又大。解：定义谓词NC(x):x是新型计算机F(x):x速度快B(x):x容量大将知识用谓词表示为：(Px) (NC(x) f F(x) A B(x)(3)凡是喜欢编程序的人都喜欢计算机。解：定义谓词P(x):x是人L(x, y):x喜欢y将知识用谓词表示为：(V x) (P(x)A L(x,pragramming)f L(x, puter)2.把下列谓词公

17、式化成子句集：(1)(2)解：由于(/x)( Vy)(P(x,(/(乜)(P(x, y) (Vx)( WyXP(x, y)、设有如下一组推理规则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解：(1)先由r1求CF(E2)CF(E2)=0.6 X max0,CF(E1)=0.6 X max0,0.5=0.3(2)再由r2求CF(E4)CF(E4)=0.7 X max0, mi

18、 nCF(E2 ), CF(E3 ) =0.7 X max0, mi n0.3,0.6=0.21(3)再由r3求CF1(H)CF1(H)= 0.8 X max0,CF(E4)=0.8 X max0, 0.21)=0.168(4)再由r4求CF2(H)CF2(H)= 0.9 X max0,CF(E5)=0.9 X max0, 0.7)=0.63(5)最后对CF1(H )和CF2(H)进行合成，求岀CF(H)CF(H)= CF1(H)+CF2(H)+ CF1(H) X CF2(H)=0.692一、(夏道丽)请把下面命题用一个语义网络表示岀来：(1)(2)。求CF(H)=?(3)所有动物都具有喜吃食

19、、鸟（bird）、鱼（fish性；此外，金鱼是鱼的一种，能运动的属性；）分别都是动物的一种，因此，它们也各自继承了动物的这些属故金鱼就又继承了fish类动物所具有的会游泳、繁殖、可喂养等属性，并又有可观赏等特点；同理，孑L雀继承了鸟具有的能下蛋、有翅膀的属性,二、（夏道丽）假设有以下一段新闻：亚地氏，造成25人死亡和5亿美元的财产损失。下斯洛文尼亚地区主席说: 壕金斯断层的重灾区一直是一个危险地区。知识。解：Framev地震3时间：今天地点：下斯洛文尼亚地区伤亡人数：25人财产损失：500，000，000美元震级：8.5“今天，一次强度为里氏8.5级的强烈地震袭击下斯洛文尼多年来，靠近萨迪 这

20、是本地区发生的第3号地震。 ”请用框架表示这一断层：萨迪壕金斯五、(赵娉婷)4.5有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受 到下列条件的限制：(1)船太小，农夫每次只能带一样东西过河；(2)如果没有农夫看管，则狼要吃羊，羊要吃菜。请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画岀相应的状态空间图。题示：(1)用四元组(农夫，狼，羊，菜)表示状态，其中每个元素都为0或1,用0表示在左岸，用1表示在右岸。(2)把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。 解：第一步，定义问题的描述形式用四元组S=(f，w，s，v)表示问题状态，其中，

21、f，w, s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0,取1表示在左岸，取0表示在右岸。第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示岀来，包括问题的初 始状态和目标状态。由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态：，S3=(1,1,0,0)，S7=(1,0,0,0) ，S1=(0,1,0,0)，S15=(0,0,0,0)Sc和S15分别是初始状态和目标状态。FS0=(1,1,1,1)S4=(1,0,1,1)S8=(0,1,1,1)S12=(0,0,1,1),Si=(1,1,1,0),S5=(1,0,1,0),S9=(0,1,1,0

22、),S13=(0,0,1,0)，S2=(1,1,0,1)，S6=(1,0,0,1)，S10=(0,1,0,1)，S4=(0,0,0,1)其中，状态S3，S，S，S8，S9，S2是不合法状态， 第三步，定义操作，即用于状态变换的算符组 由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定 义如下：L(i)表示农夫从左岸将第表示船上除农夫外不载任何东西)R (i)表示农夫从右岸将第表示船上除农夫外不载任何东西)这样，所定义的算符组L (0)，L (1)，L (2)R(0)，R(1)，R，样东西送到右岸(i=1表示狼，i=2表示羊，i=3表示菜，i=0。由于农夫必须在船上，

23、故对农夫的表示省略。样东西带到左岸(i=1表示狼，i=2表示羊，i=3表示菜，i=0。同样，对农夫的表示省略。F可以有以下8种算符：，L (3)R (3)第四步，根据上述定义的状态和操作进行求解。 该问题求解过程的状态空间图如下：旳,1,1)L(2) i(0,1|,0,1)R(0)IL(1)(0,1f0,0)1 R(2)(1,0,1,1)(1,1,1,0)L(3)/L(2)(0,0f1,0)R(0) I(1,0,1,0)L(2) I六、(赵娉婷)1我们有n(n64)根0小木棍,每根长度均不大于50。现在需要将它们拼接(0A0R(2) 1成长度相同的若干长木棍，并使得这些长木棍最短。问如何拼接？ 剪枝一(改变搜索顺序)对木棍长从大到小排个序。直观上，先拼上长木棍接下来用短木棍补充似乎更容易成功拼完。剪枝二(对d的约束)d应该不小于最长的小木棍长度d不大于木棍总长td必须是t的约数剪枝三bool solve(i nt rest, int start, int ste p)我们从start到n枚举小木棍编号i，如果此时rest=len(i),那么显然把这根木棍拼上是最好的选择了，