补考试卷B答案--2016人工智能考试.doc

(word完整版)补考试卷B答案-2015-2016人工智能考试
北京工业大学2015—-2016学年第 1 学期
《人工智能导论》 考试试卷B
考试说明: 开卷考试， 考试时间95分钟
承诺：
本人已学习了《北京工业大学考场规则》和《北京工业大学学生违纪处分条例》，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。若有违反，愿接受相应的处分。

承诺人： 学号： 班号：
。。..。。。..。。。。。。.。。.。..。..。。。。。。。.。。.。。.。。。。。。。。。。。.。。。。.。。..。。。。.。。。。.。。。。。。.。.。。。。。。。。。。。。。
注：本试卷共 大题，共 页，满分100分。

卷 面 成 绩 汇 总 表（阅卷教师填写）
题号
一
二
三
四
五
六
七
八
九
十
总成绩
满分
16
24
15
15
15
15

得分

得 分

一、选择题 (16分）

1、产生式系统的组成部分不包括（ A ）
A。）状态空间 B）综合数据库 C）规则集 D)控制策略

2、反演归结法在证明定理时，若当前归结式是（ C ）时，则定理得证。
A）永真式 B）合取式 C)空子句 C）析取式

3、将公式Ø$x "yp(x,y))化为子句，以下（ C ）是正确的.
A） p(z，y） B） p（f（x),x） C） Ø p(x,f(x）） D） p(A，y）

4、若C1=Q，C2=～QÚR,C3=～R，则归结的结果是（ D ）
A） R B） Q C） ~R D） 都不是，正确结果为（ 空 )

5、置换的乘法满足交换律,即ab=ba ( B ）。
A） 对 B） 错

6、与极小极大法相比来,α—β剪枝法增大了找不到最佳走步的危险性,但其效率较高。(B ）
A 对 B 错
7、设有机器人走迷宫问题,其入口坐标为（x0, y0)，出口坐标为（xt, yt），当前机器人位置为
（x， y），若定义， 当从入口到出口存在通路时，用A算法求解该问题，定能找到从入口到出口的最佳路径。（ A ）
A 对 B 错
8、遗传算法评价的常用方法有( ABC ）
A）当前最好法 B）在线比较法 C） 离线比较法 D) 都不是

得 分

二、简答题（24分）
1、 遗传算法中，应用“交配运算"可基于已有的两个染色体生成新的染色体.假定交配运算的规则为“基于位置的交配法”,写出以下两个父代染色体生成的两个子代染色体“子代1”和“子代2"。
父代1:10 6 8 7 5 9 4 1 2 3
父代2: 8 2 6 4 1 5 3 10 9 7
所选位置: * * ＊ ＊
解： 子代1： 10 2 6 8 1 5 3 9 4 7
子代2： 8 6 2 1 5 10 4 9 7 3

2、设子句集S={P（a)，Q（b)ÚR(f（X）)}，请写出S的H域及原子集。
解： U0=｛a,b}， U1=｛a，b,f(a)，f(b)｝，U2=｛a,b，f（a）,f（b)，f(f(a)）,f(f(b))｝
¼¼
Us={a,b,f(a）,f（b），f(f(a)）,f(f(b）),¼｝
原子集为：BS=｛p（a），q(a），r（a）,p（b)，q（b）,r（b），p（f（a)），q(f(a)），r(f(a）） ¼｝
3、求子句集S={p（a,x，f（g(y）)),p(z，h(z,u）,f(u))}的最一般合一mgu.
解: 1） k=0， Sk=S0=S, sk=s0=e, 明显的， S0=S不是单元素集.
2) 求得其差异集D0=｛a,z｝，其中z为变量，a为项，且z不在a中出现。
令k=k+1，有 s1= s0 ｛a/z｝= e ｛a/z}= ｛a/z｝
S1=S0｛a/z}=｛p（a，x,f（g（y)）),p（z，h（z,u),f(u)）｝{a/z｝ ={p（a，x，f（g（y）)）, p（a,h(a，u），f(u))｝
S1不是单元素
求得其差异集D1=｛x，h(a,u）},其中x为变量，h（a,u）为项，且x不在h（a，u）中出现.
令k=k+1,有 s2= s1｛h（a,u)/x}={a/z}｛h（a,u)/x} = ｛a/z，h(a，u)/x}
S2=S1｛h(a，u)/x｝={p(a，x，f(g（y）））,p（a，h（a,u）,f（u））}{h（a，u）/x}
={p（a，h(a，u),f(g（y)）），p（a,h（a，u）,f(u）)}
S2不是单元素集.
求得其差异集D2={g(y），u},其中u为变量， g(y）为项,且u不在g(y）中出现.
令k=k+1，有 s3=s2｛g（y)/u}=｛a/z，h(a,u)/x｝｛g（y）/u} ={a/z，h(a，g(y))/x}
S3=S2｛g(y）/u} =｛p(a,h(a，u）,f（g（y)))，p（a,h(a，u）,f(u))｝｛g(y)/u}
=｛p(a，h（a，g（y)）,f（g（y))),p（a，h（a,g（y))，f(g（y）））｝
明显的， S3是单元素集.
3） Mgu = s3={a/z，h（a,g(y）)/x}
4、把命题:果树是树，且会结果，用一个语义网络表示出来：
解：

结果实
果树
植物
树

三、计算题（15分)
将下列公式化为子句集：
1） (x）（y)(P(x， y）∧Q（x， y))
2） ］}
解：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) 去掉
]｝}
3） 内移“”
］}}
］｝｝
4）变量换名
］}｝
5) 消去存在量词， 省略全称量词
］｝}
］}｝
子句集为:

得 分

四、（15分）下图为一字棋博弈树的部分MAX/MIN搜索示意图，叶节点下面的数字表示该棋局目前状态的评价值,请根据这些值倒推其它节点的静态估值，并使用-剪枝规则完成—剪枝，求当前棋局MAX结点A的最好走步，.
要求： 1）在图中标明各层节点的、估值范围，用标明剪枝，并具体说明
是什么剪枝。2)标明MAX结点A的最好走步。

得 分

五(15分）已知：
1。 任何上大学（college)并中了彩票（lottery)的人是快乐的；
2。 任何肯学习或幸运的人可以上大学；
3. Alice不学习但很幸运；
4。 任何人只要是幸运的就能中彩。
求证:Alice是快乐的。
给定谓词：某人x上大学,College(x）; 某人x中彩票,Lottery（x）； 某人x快乐，Happy(x）; 某人x学习，Study(x）; 某人x幸运，lucky(x);

证明： 表示为合式公式为：
R1： （x）（College（x） ）ÙLottery(x)→Happy（x))
R2: (x）(Study (x） ÚLucky(x) →College(x））
R3: （¬Study （Alice） ÙLucky（Alice)
R4 （x)(Lukky(x) →Lottery(x）)
求证：Happy(Alice）
求证的非为：¬ Happy(Alice）
将上述谓词公式转化为子句集并进行归结如下：
1） ¬College(x1） Ú¬Lottery(x1) ÚHappy(x1）
2） ¬Study （x2) Ú College（x2）
3） ¬Lucky （x2） Ú College（x2)
4） ¬Study （Alice）
5） Lucky(Alice)
6） ¬Lucky(x3) ÚLottery(x3)
7） ¬ Happy（Alice)

¬College(x1)Ú¬Lottery（x1） ÚHappy(x1)

¬Happy（Alice)

¬College（x1）Ú¬Lottery（x1)
¬Lucky(x2)Ú College(x2）

¬Lottery(x1）Ú¬Lucky(x1)
Lucky（Alice）

¬Lucky（x3) ÚLottery（x3）

¬ Lottery（x1）

Lucky（Alice）
¬ Lucky(x3)

nil

得 分

六（15分）旅行商问题：一个推销员要到5个城市办理业务,城市间的里程数已知，如图所示：｜AB|=7；|AC｜=6;｜AD|=10；｜AE｜=13;｜BC|=7；|BD|=10；｜BE｜=10；|CD｜=5(最短)；|CE｜=9;｜DE｜=6。从A城市出发,遍历所有城市后（每个城市只允许访问一次）回到城市A，设计A＊ 算法求取一条最短的旅行路径，其中状态用已遍历城市名字组成的字符串表示。
要求：
1） 定义状态评价函数f（n）=g(n）+h(n)，其中g(n)表示当前状态下已走过的距离的总和;h(n)=5—m其中m是表示当前状态的字符串的长度。画出搜索的状态空间图并标明评价函数值.（10分）
2） 判断本题定义的启发函数h(n）是否满足A＊ 算法的条件.（5分）

解：状态S： 从城市A出发访问过的城市序列, 初始状态S0：A, 终状态：A**＊*A
f(n)=g（n）+h（n)。 g(n）为已走过的路径长度，在状态n时，还需要行走的城市数为 5—n（包括最后回到城市B），每次行程的最小花费为5，因此令h(n)= （5-n）＊5.
明显的，h(n)小于等于h(n）＊
( A )
(AB) 27

27

(AC)26
(AD)30

(AC)33

(ACB)28

(ACD)26

(ACE)29

(ACDB)31

(ACDE)27

(ACDEB) 22

( ACDEBA) 36
7
5
10
10
7
6
9
10
8
10
7
起始
目标

第 6 页 共 6 页