人工智能试卷
姓名：学号：得分：
注：答案只作为参考，有错误请原谅，本人能力有限。
一、填空题
1．一般公认人工智能学科诞生于1956年。
2．人工智能的研究途径有符号主义、连接主义和进化主义。
//应是研究学派3．知识表示方法中的问题归约思想事实就是从目标出发逆向推理，其三要素是初始问题描述、把问题变换位子问题的操作符和本原问题描述。
4．产生式系统主要有、产生式规则知识库和控制策略三部分构成。
5．启发式搜索在搜索中使用估价函数//状态空间搜索算法帮助搜索。
6．B规则逆向推理中，要求规则的L（事实表达式）是单文字；给出的已知事实必须是文字合取形；匹配的次序是先事实节点再目标节点；推理的终止条件是事实节点的一致解图。
7．人工智能中处理不确定知识使用的数学方法有概率论、模糊集理论和粗糙集理论等。
8．公式集F={ s[ A, g(y), f( z ) ], s[ x, g(B), f(g(x))] }的最一般合一者（mgu）是s[ A, g(B), f(B ) ] 。
// 仅供参考
二、综合题
1．简述问题归约的基本思想，并指出其三要素。
答：(1)基本思想：问题规约是另一种问题描述与求解的方法。
已知问题的描述，通过一系列变换把此问题最终变成一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。
从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题规约为一个平凡的本原问题集合，这就是问题规约的实质。
(2) 三要素：一个初始问题描述；一套把问题变换位子问题的操作符；一套
本原问题描述。
2．深度优先搜索中为何常采用有界深度优先搜索？
答：在深度优先搜索中，对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。
为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度——深度界限。
任何节点如果达到了深度界限，那么都将把它们作为没有后续节点处理。
值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一定就是最短的路径。
3．设有三个瓶子a、b和c，其容积分别为8升、5升和1升，a瓶装满了8升液体。
请用状态空间法给出将a瓶8升液体平分成两个4升液体的方案。
解：(1) 用一个三元表列（X,Y,Z）表示这个问题的状态。
其中：
X：表示a瓶子里有多少升液体；
Y：表示b瓶子里有多少升液体；
Z：表示c瓶子里有多少升液体；
(2) 问题的操作符如下：
Dump(a,b,i) ：把a瓶里的液体倒入b瓶里i升；
Dump(a,c,i) ：把a瓶里的液体倒入c瓶里i升；
Dump(b,c,i) ：把b瓶里的液体倒入c瓶里i升；
Dump(c,a,i) ：把c瓶里的液体倒入a瓶里i升；
Dump(c,b,i) ：把c瓶里的液体倒入b瓶里i升；
(3) 初始状态：(8,0,0) 目标状态：(4,4,0)
(4) 第一种方案：
初始状态变换为目标状态的操作序列为：
{ Dump(a,b,5), Dump(b,c,1), Dump(c,a,1)}
状态转换序列为：
(8,0,0)→(3,5,0) →(3,4,1)→(4,4,0)
第二种方案：
初始状态变换为目标状态的操作序列为：
{ Dump(a,c,1), Dump(c,b,1), Dump(a,c,1)，Dump(c,b,1),
Dump(a,c,1), Dump(c,b,1), Dump(a,c,1), Dump(c,b,1) }
状态转换序列为：
(8,0,0)→(7,0,1) →(7,1,0)→(6,1,1) →(6,2,0)→(5,2,1)→(5,3,0)
→(4,3,1)→(4,4,0)
(5) 状态空间图略；
4．将下面的公式化为子句集表示。
(∀x){ ⌝ (∀y)[ R(x) → Q(x,y)] ∧ (∃y)[ Q(x,y) → P(y) ] }
解：求解过程如下：
(1)：(∀x){ ⌝ (∀y)[ ⌝ R(x)∨Q(x,y)]∧(∃y)[ ⌝Q(x,y)∨P(y)] }
(2)：(∀x){ (∃y)[ R(x)∧⌝Q(x,y)]∧(∃y)[ ⌝Q(x,y)∨P(y)] }
(3)：(∀x){ (∃y)[ R(x)∧⌝Q(x,y)]∧(∃w)[ ⌝Q(x,w)∨P(w)] }
(4)：(∀x){[ R(x)∧⌝Q(x,f(x))]∧[ ⌝Q(x,g(x))∨P(g(x))] }
式中，y=f(x)和w=g(x)为一个Skolem函数。
(5) ：(∀x){[ R(x)∧⌝Q(x,f(x))]∧[ ⌝Q(x,g(x))∨P(g(x))] }
前缀母式
(6) ：(∀x){ R(x)∧⌝Q(x,f(x))∧[ ⌝Q(x,g(x))∨P(g(x))] }
(7) ：R(x)∧⌝Q(x,f(x))∧[ ⌝Q(x,g(x))∨P(g(x))]
(8) ：R(x)
⌝Q(x,f(x))
⌝Q(x,g(x))∨P(g(x))
(9) ：R(x1)
⌝Q(x2,f(x2))
⌝Q(x3,g(x3))∨P(g(x3))
三、已知a + 2b + 3c + 4d + 5e = 40，a，b，c，d，e 为正整数。
用遗传算法求
解。
请你：
1．设计染色体（个体）的表示方式；
2．设计适应度函数；
3．用实例说明怎样进行交叉和变异操作。
// 仅供参考
解：(1)、(2)略；
(3) ：两个个体P1 和P2 作为父母个体，如下图所示：
交叉操作示意图：
交叉点
交叉后得到的两个后代：
变异操作如下：
两个个体P1 和P2 作为父母个体，如下图所示：
四、用谓词公式表示下面的文子描述。
1. 所有的老虎都是有腿的。
解：令S(x) ：x是老虎；M(x) ：x是有腿的；
∀x {S(x)→M(x)}
2. 有的花是不香的。
解：令P(x) ：x是花；W(x) ：x是香的；
∃x{ P(x)∧⌝W(x)}
五、用语义网络表示下列文字描述
(1) Li 7月28日游览了黄山。
// 仅供参考
解：
(2) 设计一个框架，要求：不少于4各槽；要用到侧面。
解：框架名：<大学教师>
类属：<教师>
学历：<学士，硕士，博士>
专业：<学科专业>
职称：<助教，讲师，副教授，教授>
外语：语种：范围：(英，法，日，俄，德，……)
水平：(优，良，中，差)
缺省：良
六、用归结方法证明目标公式G是条件公式F1、F2、F3的逻辑结论。
F1: ( A ∧⌝B ) →( D ∧ C )
F2: A ∧ E ∧ ( D→E )
F3: E →⌝B
G: E ∧ C
解：(1)：A ∧ E ∧ ( D→E ) [前提]
(2)：A [(1)，I2]
(3)：E [(1)，I2]
(4)：E →⌝B [前提]
(5)：(E →⌝B) ∧E [(3)，(4), I10]
(6)：⌝B [(5)，I3]
(7)：A∧⌝B [(2)，(6)，I10]
(8)：( A ∧⌝B ) →( D ∧ C ) [前提]
(9)：[( A ∧⌝B ) →( D ∧ C )] ∧( A ∧⌝B ) [(7)，(8), I10]
(10)：D ∧ C [(9)，I3]
(11)：C [(10)，I2]
(12)：E ∧ C [(3)，(11), I10]
七、已知事实：⌝P(a) ∨ [ Q(b) ∧ R(b) ]，规则：
r1: ⌝P(x) →W(x) ∧ R(x)，
r2: Q(y) →⌝S(y)，
用F规则正向演绎方法证明目标公式：⌝S(x) ∨ W(x)。
解：把规则化为子句形，得到子句集如下：
P(x) ∨ W(x) P(x) ∨ R(x)
⌝ Q(y) ∨⌝S(y)
目标的否定：⌝(⌝S(x) ∨ W(x))
其子句形为：S(x) ，⌝W(x)
满足L→W规则得到的与或图：
八、已知s、a、b、c、g五个城市相互距离如图。
构造的启发函数中h(n)值
如下表。
g(n)采用走过城市的实际路程。
用下述指定搜索方法，找到从s 到达g的路径，并用OPEN表和CLOSED表给出搜索过程。
(1) 不考虑g(n)，即：f(n) = h(n)。
(2) 不考虑h(n)，即：f(n) = g(n)，(等代价搜索)。
(3) f(n) = g(n)+ h(n)。
// 仅供参考
解：由题意知对应的代价树如下图所示：
(1) 不考虑g(n)，即：f(n) = h(n),则：
f(s) = h(s)=32 ; f(c) = h(c)=7 ; f(g) = h(g)=0
得到的最优路径是：s，c，g
此时对应的OPEN表和CLOSED表如下：
OPEN表：
f(a)= g(a)=1 ; f(g)=g(g)=8 ;
得到的最优路径是：s，a，g
此时对应的OPEN表和CLOSED表如下：
OPEN表：
(3) 若f(n) = g(n)+ h(n)，则：
得到的最优路径是：s，b，g
OPEN表：。