学 号
班 级
姓 名
装 订 线 内 不 要 答 题 答案必须写在答题纸上，否则无效！试题页（共．．．．．．．．．．．．．．．．．．．．．2．页．）．可以．．做演．．算．纸．。． 9、 假设全程跟踪记录了200名学生的某门课程的学习情况：20次课出席情况、20一、选择题（每空2分，共32分）。将选项按照空格中的编号写在答题纸上。 次课笔记是否完整、历次课后作业分数、编程作业完成情况、各门先修课成绩、期末1、 迄今为止，图灵测试仍然是最重要的机器智能判定标准，但也备受争议。成绩等信息。现随机抽取80%同学的数据用来训练，训练后的模型用来预测其余20%例如，它有两个缺点 (1) 、 (2) 。
同学的期末成绩（百分制）。关于上述机器学习问题的描述，可以判断这 (14) 监督A）必须模拟人类的缺点，例如算术运算慢且易错，反应缓慢等 学习问题；同时，它 (15) 回归问题。 A）是 B）不是
B）回避无法说清的“Can machine thinking?”这一问题 10、 对于前馈神经元网络的一个单元，输入向量x = [x0=1, x1, x2, ..., xn]T
，权值向量
C) 不能测试知觉等属于智能的其它属性
w= [w0, w1, w2, ..., wn]T
，激励函数为f (x)=1/e-x，则其输出的计算公式为 (16) 。 2、 若表达式G是不可满足的，当且仅当对所有的解释 (3) 。 A）必真 B）必假 C）真假不能断言
A）f(x)?wT?x B）
f(x)?1(1?e-wT?x) C）以上皆错
3、 若状态空间中的任意状态只有有限个后继状态，则下列搜索算法中，具备二、简答题（共18分）。将答案写在答题纸上。
完备性的是 (4) 。 A）A?算法 B）一致代价搜索 C）以上皆是
1、 （本题6分）列举人工智能成功应用的三个领域及其典型成就。
4、 用A*搜索算法求解某问题，已构造出3个不同的可纳启发函数h1、h2、
2、 （本题6分）启发式搜索中f(x)=g(x)+h(x)中，解释f(x)、g(x)、h(x)的含义。 h3。令h4=min{h1，h2，h3}、h5=max{h1，h2，h3}，下列说法正确的是 (5) 。A）h3、 （本题6分）朴素爬山法（最陡上升）求解八皇后问题时，将会以0.86的概率陷4可纳 B）h5可纳 C）选h入局部最优而无法找到解。请你给出一种方案改进算法，使之能够满足下列条件之一：4作为启发函数，不可能比选h5少扩展节点 D）以上皆对 （1）提高一次爬山就能成功求解的概率；或者（2）跳出局部最优，从而找到一个完5、 在一般的树搜索算法的简略描述中， 整解。给出你的改进方法，并简述求解能力提升的原因。 初始化； (6) 、 (7) 、 (8) 分别是什么？
循环，直到OPEN表为空： 三、综合应用题（共50分）。答案写在答题纸上。 A）根据估值函数，从OPEN表选择一个结点n
(6) 1、 （本题16分）回答本题时，限定使用以下谓词和函数：
B）判断结点n是不是一个目标结点 (7) 谓词N(x)表示x是自然数； 谓词I(x)表示x是整数；
C）扩展节点n
(8) 谓词E(x)表示x是偶数； 谓词GZ(x)表示x是大于等于零的数； 6、 遗传算法充分体现了以下哪些优化措施 (9) 。（2分）
谓词O(x)表示x是奇数； 函数S(x)表示将x除以2得到x/2。 A）多个搜索线程并行搜索 B）不同搜索线程之间进行有效的信息交换 （1） 将事实F1、F2、F3分别用谓词公式表示出来。（6分）
C）注意探索和利用上的均衡 D）以上皆是
事实F1：自然数是大于等于零的整数； 事实F2：所有整数不是偶数就是奇数； 7、 对于用于分类的决策树学习算法，下列说法正确的是 (10) 。（2分） 事实F3：偶数除以2是整数。
A）基于贪婪的思想 B）基于分治的思想 C）结点分裂标准以测（2） 仿照事实F试属性所减少的不纯度/不确定性/惊奇度为基本标准 D）以上皆对 1、F2、F3的自然语言陈述，将结论G用自然语言描述出来。（2分）
结论G：(?x) ( N(x) ? ( O(x) ? I(S(x)) ) )。 8、 在遗传算法的简略描述中， 初始化； （3） 将F1 、F2 、F3、?G化成子句集。（4分）
(11) 、 (12) 、 (13) 分别是什么？ 循环，直到满足停止条件： A）选择 (11) ，模拟适者生存 （4） 用归结反演的方法证明G是F1、F2、F3的逻辑结论。（4分）
B）交叉 (12) ，从而产生子代 2、 （本题10分）考虑以熵的增益为结点分裂标准的决策树。训练集如表1所示，包
C）变异
含了7个训练样例，分别属于no、yes两类，每个训练样例都由A、B、C三个属性描 (13) 述，目标属性为F。
- 1 -
学 号
班 级
姓 名
装 订 装 线 订 线 内 不 要 答 题 表1 4、 （本题15分）已有三个用于求解八数码问题的正确程序：程序P1采用深度优先实例序号L A B C F 0 N1 1 的迭代加深搜索；程序P2采用启发函数为h1的A*搜索， h1表示不在位数字的总数目1 0 0 0 no N2 （错位数之个数和）；程序P3采用启发函数为h2的A*搜索， h2表示所有数字到目标2 0 0 1 yes N3 0 1 位置的曼哈顿距离之和（错位数之曼哈顿距离和）。 3 0 1 0 no 4 0 1 1 yes N4 N5 有人拿到了分别实现上述算法的三个程序，但不知道到底哪个程序实现了哪种算5 1 0 0 yes 0 1 法。于是，他首先将三个程序分别标记成X、Y、Z；然后，又随机地生成了1000个6 1 0 1 yes 八数码问题（对应于解路径长度d = 2、4、6、…、20，各有100个八数码问题）作为7 1 1 0 no N6 N7 测试集；最后，在测试集上分别执行了三个程序，最终得到的实验数据如表2所示。（1）哪个属性做为根结点N1的测试属性？简要给出你的推理根据。（5分） 请简短回答下列问题：
（2）假设N2用属性A作为测试属性，请给出中间结点N5上的测试属性、（1）请你帮他推断出：X、Y、Z与P1、P2、P3的对应关系。说明你依据什么将Y、Z叶结点N4上的类别标签、叶结点N6上的类别标签。（3分） 区分开的。（6分） （3）用上述决策树预测新实例（1, 1, 1）所属的类别。（2分）
（2）若每个结点n的后继结点的集合都避免包括结点n的直接祖先，且每个数码在棋3、 （本题9分）贝叶斯网络。已知由5个随机变量(取图中单词的首字母)构盘上任意位置等概率出现。在采用无信息的宽度优先搜索算法时，给出八数码问题的成的贝叶斯网络，各个条件概率表如图1所示。 平均分支因子R的一个估计值，并给出估算过程。（3分）
d0 d1 i0 i1 表2
0.6 0.4 0.7 0.3 解的 求解每个问题，平均扩展的结点数 有效的平均分支因子 深度d 程序X 程序Y 程序Z 程序X 程序Y 程序Z Difficulty Intelligence 2 10 6 6 2.45 1.79 1.79 g0 g1 g2 4 112 13 12 2.87 1.48 1.45 i0,d0 0.3 0.4 0.3 6 680 20 18 2.73 1.34 1.30 i08 6384 39 25 2.80 1.33 1.24 ,d1 0.05 0.25 0.7 1Grade SAT 10 47127 93 39 2.79 1.38 1.22 i,d0 0.9 0.08 0.02 i1,d1 0.5 0.3 0.2 12 3644035 227 73 2.78 1.42 1.24 s0 s1 14 --------- 539 113 --------- 1.44 1.23 i0 0.95 0.05 16 --------- 1301 211 --------- 1.45 1.25 Letter i1 0.2 0.8 18 --------- 3056 363 --------- 1.46 1.26 l0 l1 g0 0.1 0.9 20 --------- 7276 676 --------- 1.47 1.27 g1 0.4 0.6 图1 （3）从表中观察到，Y、Z程序的平均分支因子比R的估计值还小（当d > 2时），请 g2 0.99 0.01 解释原因。 （2分）
（1）请写出联合概率P(D,I,G,S,L)分解为条件概率的分解式。（3分） （4）假设程序IZ在Z的基础上采用了迭代加深技术。对于较复杂问题，通常会采用（2）求P(i1, s1, g1) = ? （2分）
迭代加深搜索，请给出IZ相比较Z更实用的一个重要原因。（2分） （3）全联合概率分布至少要存储多少个概率值？贝叶斯网络用若干个条件概（5）若不能恰当处理重复结点，则迭代加深程序将反复展开相同结点，浪费大量的时率表表示全联合概率表以后，一共需要存储多少个概率值？（4分）
间和空间资源。假设是你正在写一个24数码问题（提示：状态空间异常大），你用何种技术避免重复结点的重复展开问题？（2分）
- 2 -
学 号
班 级
姓 名
装 订 装 线 订 线 内 不 要 答 题 东 北 大 学
秦 皇 岛 分 校
3、（本题6分）
课程名称： 人工智能 试卷： (A ) 考试形式：闭卷
答：方案或方法不唯一，依学生回答情况酌情给分。例如，
授课专业： 计算机科学技术 考试日期： 2015年7月3日试卷：共2+2页
采用多次随机重爬的方法。具体地，随机从一个八皇后状态（允许皇后互相攻击）出
题号 发，选择冲突最小的后继，直到找到一个合法解，或者因为没有比当前解更好的候选一 二 三 总分 解，爬山法失败。随机重爬就是发现爬山失败，再次随机一个初始状态，重新执行爬得分 山法。反复爬山，直到某一次得到一个解为止。 3分 阅卷人 原因。因为爬山法可能陷入局部最优。允许随机选取一个点再次执行爬山法，就有机会跳出局部最优，从而找到解。 3分 答题纸
一、 选择题（每空2分，共32分）。将选择题选项按空格编号填入下表。
三、 综合应用题（共34分）
(1) A或C (2) C或A (3) B (4) C (5) D 1、 （本题16分）
(6) A (7) B (8) C (9) D (10) D 答：
(11) A (12) B (13) C (14) A (15) A （1）F1:(?x)(N(x)→GZ(x)?I(x)) 2分
(16) B F2:(?x)(I(x)→E(x)?O(x)) 2分 二、 简答题（共26分）。 F3:(?x)(E(x)→I(S(x))) 2分
1、（本题6分）
（2）G:所有自然数，不是奇数，就是其一半为整数的数。 2分 答：任意列举三个即可。比如，
（3）子句集：
计算机博弈 深蓝超级计算机 2分 自动驾驶 谷歌自动驾驶汽车 2分 1）?N(x) ? GZ(x) 自动定理证明 逻辑理论家 2分 2）?N(u) ? I(u) 1分
3）?I(y) ? E(y) ? O(y) 1分 2、（本题6分） 4）?E(z) ? I(S(z)) 1分 答：
5）N(t)
g(x)表示从初始结点到当前结点x当中，已搜索过的最短的路径的实际代价； 2分
6）?O(v) h(x)表示从当前结点x到最近的目标状态的路径的估计代价； 2分 7）?I(S(w)) 1分 f(x)表示从初始结点，经由当前结点x，抵达距离x最近的目标状态的路径的（4）归结
估计代价。 2分
8）?I(t)?E(t) 3)和6）归结
- 3 -
学 号
班 级
姓 名
装 订 装 线 订 线 内 不 要 答 题 9）?E(z) 4）和7）归结 10）?I(t) 8）和9）归结 11）?N(u) 2）和10）归结 12）NIL 5）和11）归结
因此，G是F1、F2、F3的逻辑结论。 4分
2、（本题10分）
答：
（1）C做为N1结点上的测试属性。 1分 因为
Gain(C) = -3/7*log(7/3) - 4/7*log(7/4) - 4/7 * (-1/4*log4 - 3/4*log(4/3)) - 3/7 * 0
Gain(B) = -3/7*log(7/3) - 4/7*log(7/4) - 4/7* (-1/4*log4 - 3/4*log(4/3)) -3/7 * (-1/3*log3 - 2/3*log(3/2))
Gain(A) = -3/7*log(7/3) - 4/7*log(7/4) - 4/7* (-1/2*log2 - 1/2*log2) -3/7 * (-1/3*log3 - 2/3*log(3/2))
于是, Gain(A) < Gain(B) < Gain(C)。所以选C做根结点的测试属性。 4分 （2）
N5上用B做测试属性 1分 N4上的类别标签是no 1分 N6的类别标签是yes 1分 （3）
根节点上的测试属性是C，在（1，1，1）中，属性C的值是1，因此，（1，1，1）落入叶子结点N3中，其类别标签是yes。 2分
3、（本题9分）
答：
（1）P(D,I,G,S,L)=P(D)P(I)P(S|I)P(G|D,I)P(L|G) 3分
（2）P(i1, s1, g1) = P(i1)P(s1|i1)P(g1|i1)=P(i1)P(s1|i1) (P(g1|i1,d0)P(d0) + P(g1|i1
,
d1)P(d1)) = 0.3*0.8*(0.048+0.12)=0.04032。 2分
（3）全联合概率分布，需要用2*2*2*3*2-1=47个概率值； 2分
条件概率表需要(2-1)+(2-1)+2*2*(3-1)+3*(2-1)+2*(2-1)=15个概率值。 2分
4、（本题15分）
答：
1）P1是X、P2是Y、P3 是Z。 3分 X是盲目搜索，扩展的结点数最多，故P1是X；
Y的启发函数小于等于Z的启发函数，而且，P2扩展的结点数比P1多，因此，可以推断P2是Y、P3 是Z。 3分
2）R = (4*3 + 4*2+4)/9.0 = 2.67;
若考虑到每个结点都不返回父结点，则进一步有R=2.67-1=1.67 3分
3）Y和Z因为使用了启发函数剪枝，可能扩展比较少的结点。
4）IZ可以节省更多的空间。很多实际问题因为空间不足而导致A*失败，采用迭代加深有助于解决空间不足的问题。 2分
5）采用hash表。 2分
- 4 -
相关推荐：
loading