厦门大学《计算智能》期末试题
（2011/7/15）
一、（20分）在3×3的九宫格棋盘上摆有8个将牌，分别标有1-8个数码，棋盘上尚有一
个空格，允许其周围的将牌向空格移动，从而实现将牌布局的不断变换。

现给定初始布局如图1（a）所示，目标布局如图1（b）所示，试设计一个启发式搜索算法，完成从初始布局到目标布局的启发式搜索，并画出搜索树。

(b)
图1：九宫格重排问题
二、（15分）下图为一棵博弈树，
(a)试用极小极大法标记各结点的倒推值；
(b)试用α−β剪枝法进行修剪，标出各端点的α值和β值，并在修剪处作标记，同时说
明是α修剪还是β
修剪？
图2：α−β剪枝
三、（20分）试设计一个人工神经网络实现异或（XOR）问题（其真值表见表1），并给出
一种尽可能详细的机器学习算法。

表1：异或（XOR）逻辑真值表
输入x0011
y0101
输出z0110
四、（20分）假设手机电池电量不足时，手机会发出提示音，而这种提示音是我们判断手机
电量的唯一途径。

假设这个简单的问题构成Markov 链，如图3所示，其中Battery 表示电池电量不足，Alarm 表示有提示音。

若观察到第一、二天没有提示音，接下来的两天都有提示音。

假设电量初始状态分布为[0.5, 0.5]。

求解下列问题：1）求第四天电池电量的状态分布。

2）采用粒子滤波算法，对第一天第二天电池电量的分布进行近似估计，写出算法步骤。

3）试证明粒子滤波算法是对状态的一致估计。

图3：描述电池电量的简单Markov 模型
五、（15分）高校研究成果的多少跟国家政策、学校政策、教师从事研究的干劲及奖励机制
有关，对这一问题进行建模，如图4所示，国家的政策会影响学校政策的制定，而学校政策又会影响奖励机制，及教师从事科研工作的热情，两者又直接影响着成果的多少。

针对图4模型采用MCMC 方法，进行算法实现，写出一轮完整的计算步骤。

图4：描述高校科研政策与科研成果的Bayes 网络
六、（10分）对线性不可分的分类问题，一个常用的方法是寻找合适的特征空间，把问题变
成特征空间中线性可分的问题。

试写出该情况下支持向量机的基本问题和对偶问题，并举例说明（要求有具体的数据、最好画图说明）。

B t-1P(A t )t
0.9f
0.2
C
P(U)t 0.95f
0.01。