人工智能期末试题

1、2.证明G是否为F2 , ,Fn的逻辑结论。 i Fi :-x Px Qx Rx Fi : x Px S x G x Sx Rx 2. 先把G否定，并放入F中，得到的 F1,F2, ?G为 -x Px Qx Rx ， x Px Sx ，?( x Sx Rx ” 再把 F1,F2, ?G化为子句集，得到 一 P(x) Q(x) P(y) R(y) P(a) S(a) S(b) -R(b) 其中是由Fi化为的两个子句，是由F2化为的两个子句，是由G化为的子句。 由子句集可以看出只有唯一的一个Q因此可以得出G不是F的逻辑结构。 3. 假设张被盗，公安局派出5人去调查。案情分析时，侦查员A说：“赵与钱

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

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

4、价法, 2 D t3 t则该解树的代价为: t1 解: 2 t4 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)=10 5. 设有如下一组推理规则： ri : IF Ei THEN E2( 0.6) r2: IF E2 AND E3 THEN E4 (0.7) r3 : IF E4 THEN H ( 0.8) 5 : IF E5 THEN H (0.9) 且已知 CF(

5、E1)=0.5，CF(E3)=0.6,CF( E5)=0.7,求 CF(H)。 5.解：(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 nCF(E2 ), CF(E3 ) =0.7 x max0, min0.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 m

6、ax0,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 6. 设U=V=W= 1, 2, 3, 4且有如下规则: r1:IFxisF THEN y is G r2 :IFyisG THEN z is H r3 :IFxisF THEN z is H 其中，F,G,H的模糊集分别为 F=1/1+0.8/2+0.5/3+0.4/4 G=0.1/2+0.2/3+0.4/4 H=0.2/2+0.5/3+0.8/4 18 请用模糊关系R

7、C验证满足模糊三段论。 6.先求F G上的关系Rc1 0 0 0 0.1 0.1 0.1 0.2 0.2 0.2 0.4 0.4 0.4 再求G H上的关系RC2, 最后求F G H的关系R 0.1 0.2 0.4 0 0 0 0 1 0 0.1 0.1 0.1 0 0.2 0.2 0.2 卫 0.2 0.4 0.4一 RC2 = 0 0.2 0.4 0.4 0 0.2 0.4 0.4 0 0.2 0.4 0.4 0 0.2 0.4 0.4 R= RciRci = 2. （龙云献）简述用A*算法求解问题时为什么会岀现重复扩展节点问题，解决的方法有哪些？ 答：当问题有解时，A*算法总是找到问题的

8、最优解结束。如果h函数定义的不合理，则当扩 展一个节点时，不一定就找到了从初始节点到该节点的最优路径，对于这样的节点，就有可能被 多次扩展。特别是如果这样的节点处于问题的最优解路径上时，则一定会被多次扩展。解决的方 法一是对h函数的定义给岀限制，使得h满足单调性。对于满足单调性条件的h,则一定不会岀 现重复扩展节点问题。二是对A*算法加以改进，使用修正的A*算法进行搜索，则可以减少重复 扩展节点问题。 3. （刘林洋）简述回溯策略与深度优先策略的不同点。 答：回溯搜索策略与深度有限搜索策略最大的不同是深度有限搜索策略属于图搜索，而回溯 搜索则不是图搜索。 在回溯搜索中，只保留了从初始节点到当前

9、节点的搜索路径。而深度优先搜 索，则保留了所有的已经搜索过的路径。 4. （张松）设有如下两个模糊关系: 0.3 0.70.20.2 0.8 R1 = 1 0 0.4 R2 = 0.6 0.4 - 0 0.5 1 _ 0.9 0.1 一 请写岀R1与R2的合成R10 Rao 解：R(1,1)=(0.3 人 0.2) V (0.7 人 0.6) V (0.2 人 0.9)= 0.2 V 0.6 V 0.2=0.6 R(1,2)=(0.3 人 0.8) V (0.7 人 0.4) V (0.2 人 0.1)= 0.3 V 0.4 V 0.1=0.4 R(2,1)=(1 人 0.2) V (0 人

10、0.6) V (0.4 人 0.9)= 0.2 V 0V 0.4=0.4 R(2,2)=(1 人 0.8) V (0 人 0.4) V (0.4 人 0.1)= 0.8 V 0V 0.1=0.8 R(3,1)=(0 人 0.2) V (0.5 人 0.6) V (1 人 0.9)= 0.2 V 0.6 V 0.9=0.9 R(3,2)=(0 人 0.8) V (0.5 人 0.4) V (1 人 0.1)= 0 V 0.4 V 0.1=0.4 因此有 0.6 0.4 R1 R2 0.4 0.8 0.9 0.4 5. （张松）设 U=V=1, 2, 3, 4 且有如下推理规则： IF x is少

11、 THEN y is 多 其中，“少”与“多”分别是U与V上的模糊集，设 少=091+0.7/2+0.4/3 多=0.3/2+0.7/3+094 已知事实为 x is较少 “较少”的模糊集为 较少=0.8/1+0.5/2+0.2/3 请用模糊关系Rm求岀模糊结论。 解：先用模糊关系 Rm求岀规则 IF x is 所包含的模糊关系Rm Rm (1,1)=(0.9 Rm (1,2)=(0.9 Rm (1,3)=(0.9 Rm (1,4)=(0.9 Rm (2,1)=(0.7 Rm (2,2)=(0.7 Rm (2,3)=(0.7 Rm (2,4)=(0.7 Rm (3,1)=(0.4 Rm (3,

12、2)=(0.4 Rm (3,3)=(0.4 Rm (3,4)=(0.4 Rm (4,1) = (0 Rm (4,2)=(0 Rm (4,3)=(0 Rm (3,4)=(0 即： 少 THEN y is 多 A 0) V (1-0.9)=0.1 A 0.3) V (1-0.9)=0.3 A 0.7) V (1-0.9)=0.7 A 0.9) V (1-0.9)=0.7 A 0) V (1-0.7)=0.3 A 0.3) V (1-0.7)=0.3 A 0.7) V (1-0.7)=0.7 A 0.9) V (1-0.7)=0.7 A 0) V (1-0.4)=0.6 A 0.3) V (1-0.

13、4)=0.6 A 0.7) V (1-0.4)=0.6 A 0.9) V (1-0.4)=0.6 A 0) V (1-0)=1 A 0.3) V (1-0)=1 A 0.7) V (1-0)=1 A 0.9) V (1-0)=1 0.1 0.3 0.7 0.9 0.3 0.3 0.7 0.7 Rm = 0.6 0.6 0.6 0.6 1 1 1 1 _ 因此有 0.1 0.3 Y=0.8,0.5,020 川 0.3 0.6 0.3 0.6 0.7 0.9 0.7 0.7 0.6 0.6 1 1 J.0.3,0.3.0.7,0.8 / 即，模糊结论为 Y0.3, 0.3, 0.7, 0.8 6.

14、 (张松)设已知： (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) A F(y,z) f GF(x,z) F2 : ( -y)(P(x) f F(x,y) 求证结论 G: ( u) (v)( P(u) f GF(v,u) 然后再将F1, F2和?G化成子句集： ?F(x,y) V?F(y,z

15、) V GF(x,z) ？P(r) V F(s,r) P(u) ？GF(v,u) 对上述扩充的子句集，其归结推理过程如下: 由于导出了空子句，故结论得证。 1.假设有以下一段天气预报：“贵阳地区今天白天晴，东北风1级，最高气温 250,最低气 温160，降水概率10%,湿度64%”请用框架表示这一知识。(陈丽丽) 解： Framev天气预报 地域: 贵阳 时段: 今天白天 天气: 晴 风向: 东北 风力: 1级 气温: 最高：25 度 最低：16 度 降水概率：10% 湿度：64% 2.把下列谓词公式化成子句集： (陈丽丽) (1) (- x)( - y)(P(x, y) A Q(x, y)

16、(2) (-x)(y)(P(x, y) V (Q(x, y) f R(x, y) 解： 由于(一 x)( - y)(P(x, y) A Q(x, y)已经是 Skolem 标准型，且 P(x, y) A Q(x, y) 已经是合取范式，所以可直接消去全称量词、合取词，得 P(x, y), Q(x, y) 再进行变元换名得子句集： S= P(x, y), Q(u, v) (2)对谓词公式(-x)(y)(P(x, y) V (Q(x, y) R(x, y)，先消去连接词“乍”得: (x)(y)(P(x, y) V (?Q(x, y) V R(x, y) 此公式已为前束范式。 再消去存在量词，即用S

17、kolem函数f(x)替换y得： (一 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) 有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。 解：定义谓词 P(x) : x是人 L(x,y) : x 喜欢 y 其中，y的个体域是梅花，菊花。 将知识用谓词表示为： (x )(P(x) f L(x,梅花)V L(x,菊花)V L(x,梅花)A L(x,菊花) (2) 新型计算机速度又快，存储容量又大。 解：定义谓词 NC(x

18、) : x是新型计算机 F(x) : x速度快 B(x) : x容量大 将知识用谓词表示为： (- x) (NC(x) T F(x) A B(x) (3) 凡是喜欢编程序的人都喜欢计算机。 解：定义谓词 P(x) : x是人 L(x, y) : x 喜欢 y 将知识用谓词表示为： (一 x) (P(x) A L(x,pragramming) t 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.

19、9) 且已知 CF(E1)=0.5, CF(E3)=0.6, CF(E5)=0.7 。求 CF(H)=? 解：(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, minCF(E2 ), CF(E3 ) =0.7 X max0, min 0.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)=

20、 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) 鸟(bird )、鱼(fish )分别都是动物的一种，因此，它们也各自继承了动物的这些属 性； (3) 此外，金鱼是鱼的一种，故金鱼就又继承了fish 类动物所具有的会游泳、繁殖、可喂 养等属性，并又有可观赏等特点；同理，孔雀继承了鸟具有的能下蛋、有翅

21、膀的属性, 还具有展翼喜欢表现的习性等。 CAN HAVE AKO CAN MAY CAN 鱼观赏 金鱼 二、（夏道丽）假设有以下一段新闻：“今天，一次强度为里氏8.5级的强烈地震袭击下斯洛文尼 亚地氏，造成25人死亡和5亿美元的财产损失。下斯洛文尼亚地区主席说：多年来，靠近萨迪 壕金斯断层的重灾区一直是一个危险地区。这是本地区发生的第 3号地震。”请用框架表示这一 知识。 解：Framev地震3 时间：今天 地点：下斯洛文尼亚地区 伤亡人数：25人 财产损失：500，000，000美元 震级：8.5 断层：萨迪壕金斯 五、（赵娉婷）4.5有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右

22、岸，但受 到下列条件的限制： （1）船太小，农夫每次只能带一样东西过河； （2）如果没有农夫看管，则狼要吃羊，羊要吃菜。 请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画岀相应的状态空间图。 题示：（1）用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1,用0表示 在左岸，用1表示在右岸。 （2）把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。 解：第一步，定义问题的描述形式 用四元组S= （f，w，s，v）表示问题状态，其中，f，w, s和v分别表示农夫，狼，羊和 青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取 0表示在右岸。 第二步，

23、用所定义的问题状态表示方式，把所有可能的问题状态表示岀来，包括问题的初 始状态和目标状态。 由于状态变量有 4个，每个状态变量都有2种取值，因此有以下 16种可能的状态： S0=(1,1,1,1) S4=(1,0,1,1) S8=(0,1,1,1) S12 = (0,0,1,1) ，S1=(1,1,1,0)，S2 = (1,1,0,1)，S3=(1,1,0,0) ，S5 = (1,0,1,0)，S6 = (1,0,0,1)，S7=(1,0,0,0) ，S9 = (0,1,1,0)，S10 = (0,1,0,1)，S1=(0,1,0,0) ，S13=(0,0,1,0)，S14 = (0,0,0,

24、1)，S15=(0,0,0,0) 其中，状态S3，S，S，S8，S9，S2是不合法状态，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 表示船上除农夫外不载任何东西)。同样，对农夫的表示省略。 这样，所定义的算

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