人工智能例题大纲.doc

1. 用谓词逻辑知识表示方法表示如下知识：
(1) 有人喜欢梅花，有人喜欢菊花，有人既喜欢梅花又喜欢菊花。
(2) 不是每个计算机系的学生都喜欢在计算机上编程序。
解：(1)
定义谓词
P(x)：x是人
L(x,y)：x喜欢y
其中，y的个体域是{梅花，菊花}。
将知识用谓词表示为：
(∃x)(P(x)→L(x, 梅花)∨L(x, 菊花)∨L(x, 梅花)∧L(x, 菊花))
解：(2)
定义谓词
S(x)：x是计算机系学生
L(x, pragramming)：x喜欢编程序
U(x,computer)：x使用计算机
将知识用谓词表示为：
¬ (∀x) (S(x)→L(x, pragramming)∧U(x,computer))

2. 请用语义网络表示如下知识：
高老师从3月到7月给计算机系的学生讲“计算机网络”课。
解：

3. 判断以下子句集是否为不可满足
{P(x)∨Q(x )∨R(x), ﹁P(y)∨R(y), ﹁ Q(a), ﹁R(b)}
解：采用归结反演，存在如下归结树，故该子句集为不可满足。

4、证明G是F的逻辑结论
F: (∃x)(∃y)P(f(x))∧(Q(f(y)))
G: P(f(a))∧P(y)∧Q(y)
证：先转化成子句集
对F，进行存在固化，有
P(f(v))∧(Q(f(w)))
得以下两个子句
P(f(v))，Q(f(w))
对﹁G，有
﹁ P(f(a))∨﹁P(y) ∨﹁Q(y)
先进行内部合一，设合一{f(a)/y}，则有因子
﹁ P(f(a)) ∨﹁Q(f(a))
再对上述子句集进行归结演绎推理。其归结树如下图所示，即存在一个到空子句的归结过程。
因此G为真。

5 设有如下结构的移动将牌游戏：

其中，B表示黑色将牌，W表是白色将牌，E表示空格。游戏的规定走法是：
(1) 任意一个将牌可移入相邻的空格，规定其代价为1；
(2) 任何一个将牌可相隔1个其它的将牌跳入空格，其代价为跳过将牌的数目加1。
游戏要达到的目标什是把所有W都移到B的左边。对这个问题，请定义一个启发函数h(n)，并给出用这个启发函数产生的搜索树。你能否判别这个启发函数是否满足下界要求？在求出的搜索树中，对所有节点是否满足单调限制？

解：设h(x)=每个W左边的B的个数，f(x)=d(x)+3*h(x)，其搜索树如下：

6 设有如下一组推理规则:
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.9)
且已知CF(E1)=0.5, CF(E3)=0.6, CF(E5)=0.7。求CF(H)=?
解：(1) 先由r1求CF(E2)
CF(E2)=0.6 × max{0,CF(E1)}
=0.6 × max{0,0.5}=0.3
(2) 再由r2求CF(E4)
CF(E4)=0.7 × max{0, min{CF(E2 ), CF(E3 )}}
=0.7 × max{0, min{0.3, 0.6}}=0.21
(3) 再由r3求CF1(H)
CF1(H)= 0.8 × max{0,CF(E4)}
=0.8 × max{0, 0.21)}=0.168
(4) 再由r4求CF2(H)
CF2(H)= 0.9 ×max{0,CF(E5)}
=0.9 ×max{0, 0.7)}=0.63
(5) 最后对CF1(H )和CF2(H)进行合成，求出CF(H)
CF(H)= CF1(H)+CF2(H)- CF1(H) × CF2(H)
=0.692

7 设训练例子集如下表所示：

请用ID3算法完成其学习过程。
解：
设根节点为S，尽管它包含了所有的训练例子，但却没有包含任何分类信息，因此具有最大的信息熵。即：
H(S)= - (P(+)log 2P(+) - P(-)log2 P(-))
式中
P(+)=3/6，P(-)=3/6
即有
H(S)= - (3/6)*log (3/6) - (3/6)*log (3/6))
= -0.5*(-1) - 0.5*(-1) = 1
按照ID3算法，需要选择一个能使S的期望熵为最小的一个属性对根节点进行扩展，因此我们需要先计算S关于每个属性的条件熵：
H(S|xi)= ( |ST| / |S|)* H(ST) + ( |SF| / |S|)* H(SF)
其中，T和F为属性xi的属性值，ST和SF分别为xi=T或xi=F时的例子集，|S|、| ST|和|SF|分别为例子集S、ST和SF 的大小。
下面先计算S关于属性x1的条件熵：
在本题中，当x1=T时，有：
ST={1，2，3}
当x1=F时，有：
SF={4，5，6}
其中，ST 和SF中的数字均为例子集S中例子的序号，且有|S|=6，| ST |=| SF |=3。
由ST可知：
　　　　P(+)=2/3， P(-)=1/3
则有：
H(ST)= - (P(+)log2 P(+) - P(-)log2 P(- ))
= - ((2/3)log2(2/3)- (1/3)log2(1/3)) ==0.9183
再由SF可知：
　　　　PSF(+)=1/3， PSF(-)=2/3
则有：
H(SF)= - (PSF(+)log2 PST(+) - PSF(-)log2 PSF(- ))
= - ((2/3)log2(2/3)- (1/3)log2(1/3)) = 0.9183
将H(ST)和H (SF)代入条件熵公式，有：
H(S|x1)=(|ST|/|S|)H(ST)+ (|SF|/|S|)H(SF)
=(3/6)﹡0.9183 + (3/6)﹡0.9183
=0.9183
下面再计算S关于属性x2的条件熵：
在本题中，当x2=T时，有：
ST={1，2，5，6}
当x2=F时，有：
SF={3，4}
其中，ST 和SF中的数字均为例子集S中的各个例子的序号，且有|S|=6，| ST |=4，| SF |=2。
由ST可知：
　　　　PST (+) = 2/4
PST (-) = 2/4
则有：
H(ST)= - (P ST (+)log2 P ST (+) - P ST (-)log2 P ST (- ))
= - ((2/4)log2(2/4) - (2/4)log2(2/4))
=1
再由SF可知：
　　　PSF (+)=1/2
PSF (-)=1/2
则有：
H(SF)= - (P(+)log2 P(+) - P(-)log2 P(- ))
= - ((1/2)log2(1/2)- (1/2)log2(1/2))
=1
将H(ST)和H (SF)代入条件熵公式，有：
H(S|x2)=(|ST|/|S|)H(ST)+ (|SF|/|S|)H(SF)
=(4/6)﹡1 + (2/6)﹡1
=1
可见，应该选择属性x1对根节点进行扩展。用x1对S扩展后所得到的部分决策树如下图所示。

8八数码难题
f(n)=d(n)+P(n)
d(n) 深度
P(n)与目标距离
显然满足
P(n)≤ h*(n)
即f*=g*+h*

9 修道士和野人问题
解：用m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数，用三元组(m, c, b)表示问题的状态。
对A*算法，首先需要确定估价函数。设g(n)=d(n)，h(n)=m+c-2b，则有
f(n)=g(n)+h(n)=d(n)+m+c2b
其中，d(n)为节点的深度。通过分析可知h(n)≤h*(n)，满足A*算法的限制条件。
M-C问题的搜索过程如下图所示。

10 设有如下一组知识：
r1：IF E1 THEN H (0.9)
r2：IF E2 THEN H (0.6)
r3：IF E3 THEN H (-0.5)
r4：IF E4 AND ( E5 OR E6) THEN E1 (0.8)
已知：CF(E2)=0.8，CF(E3)=0.6，CF(E4)=0.5，CF(E5)=0.6, CF(E6)=0.8
求：CF(H)=?
解：由r4得到：
CF(E1)=0.8×max{0, CF(E4 AND (E5 OR E6))}
= 0.8×max{0, min{CF(E4), CF(E5 OR E6)}}
=0.8×max{0, min{CF(E4), max{CF(E5), CF(E6)}}}
=0.8×max{0, min{CF(E4), max{0.6, 0.8}}}
=0.8×max{0, min{0.5, 0.8}}
=0.8×max{0, 0.5} = 0.4
由r1得到：CF1(H)=CF(H, E1)×max{0, CF(E1)}
　　　　　 =0.9×max{0, 0.4} = 0.36
由r2得到：CF2(H)=CF(H, E2)×max{0, CF(E2)}
　　　　　=0.6×max{0, 0.8} = 0.48
由r3得到：CF3(H)=CF(H, E3)×max{0, CF(E3)}
　　　　　 =-0.5×max{0, 0.6} = -0.3
根据结论不精确性的合成算法，CF1(H)和CF2(H)同号，有：

CF12(H)和CF3(H)异号，有：

即综合可信度为CF(H)=0.53

11 设有如下知识：
r1： IF E1（0.6）AND E2（0.4） THEN E5 （0.8）
r2： IF E3（0.5）AND E4（0.3）AND E5（0.2）THEN H（0.9）
已知： CF（E1）=0.9，CF（E2）=0.8，CF（E3）=0.7，CF（E4）=0.6
求： CF（H）=?
解：
CF(E1 AND E2)=0.9*0.6+0.8*0.4=0.86
CF(E5)=0.860.8=0.69
CF(E3 AND E4 AND E5)
=0.7*0.5+0.6*0.3+0.69*0.2=0.67
CF(H)=0.67*0.9=0.60

12设有如下规则：
r1: IF E1 AND E2 THEN A={a1, a2} CF={0.3, 0.5}
r2: IF E3 THEN H={h1, h2} CF={0.4, 0.2}
r3: IF A THEN H={h1, h2} CF={0.1, 0.5}
已知用户对初始证据给出的确定性为：
CER(E1)=0.8 CER(E2)=0.6
CER(E3)=0.9
并假Ω定中的元素个数∣Ω∣=10
求：CER(H)=?
解：由给定知识形成的推理网络如下图所示：

(1) 求CER(A)
由r1:
CER(E1 AND E2)
=min{CER(E1), CER(E2)}
=min{0.8, 0.6} = 0.6
m({a1}, {a2})={0.6×0.3, 0.6×0.5} = {0.18, 0.3}
Bel(A)=m({a1})+m({a2})=0.18+0.3=0.48
Pl(A)=1-Bel(﹁A)=1-0=1
f(A)=Bel(A)+|A|/|Ω|•[Pl(A)-Bel(A)]
=0.48+2/10*[1-0.48]
=0.584
故
CER(A)=MD(A/E')×f(A)=0.584
(2) 求CER(H)
由r2得
m1({h1}, {h2})={CER(E3)×0.4, CER(E3)×0.2}
={0.9×0.4, 0.9×0.2}
={0.36, 0.18}
m1(Ω)=1-[m1({h1})+m1({h2})]
=1-[0.36+0.18]=0.46
由r3得
m2({h1}, {h2})={CER(A)×0.1, CER(A)×0.5}
={0.58×0.1, 0.58×0.5}
={0.06, 0.29}
m2(Ω)=1-[m2({h1})+m2({h2})]
=1-[0.06+0.29]=0.65
求正交和m=m1⊕m2
K=m1(Ω)×m2(Ω)
+m1({h1})×m2({h1})+m1({h1})×m2(Ω)+m1(Ω)×m2({h1})
+m1({h2})×m2({h2})+m1({h2})×m2(Ω)+m1(Ω)×m2({h2})
=0.46×0.65
+0.36×0.06+0.36×0.65+0.46×0.06
+0.18×0.29+0.18×0.65+0.46×0.29
=0.30+(0.02+0.23+0.03)+(0.05+0.12+0.13)
=0.88

同理可得：

故有：m(Ω)=1-[m({h1})+m({h2})]

=1-[0.32+0.34] = 0.34
再根据m可得
Bel(H)=m({h1})+m({h2}) = 0.32+0.34 = 0.66
Pl(H)=m(Ω)+Bel(H)=0.34+0.66=1

CER(H)=MD(H/E')×f(H)=0.73

13用ID3算法完成下述学生选课的例子
假设将决策y分为以下3类：
y1：必修AI
y2：选修AI
y3：不修AI
做出这些决策的依据有以下3个属性：
x1：学历层次　x1=1 研究生，x1=2 本科
x2：专业类别　x2=1 电信类，x2=2 机电类
x3：学习基础　x3=1 修过AI，x3=2 未修AI
表6.1给出了一个关于选课决策的训练例子集S。

该训练例子集S的大小为8。ID3算法就是依据这些训练例子，以S为根节点，按照信息熵下降最大的原则来构造决策树的。
解： 首先对根节点，其信息熵为：

其中，３为可选的决策方案数，且有
　　　　P(y1)=1/8，P(y2)=2/8，P(y3)=5/8
即有：
H(S)= -(1/8)log2(1/8)- (2/8)log2(2/8)- (5/8)log2(5/8) =1.2988
按照ID3算法，需要选择一个能使S的期望熵为最小的一个属性对根节点进行扩展，因此我们需要先计算S关于每个属性的条件熵：

其中，t为属性xi的属性值，St为xi=t时的例子集，|S|和|St|分别是例子集S和St的大小。
下面先计算S关于属性x1的条件熵：
在表6-1中，x1的属性值可以为1或2。当x1=1时，t=1时，有：
S1={1，2，3，4}
当x1=2时，t=2时，有：
S2={5，6，7，8}
其中，S1和S2中的数字均为例子集S中的各个例子的序号，且有|S|=8，|S1|=|S2|=4。
由S1可知：
Ps1(y1)=1/4, Ps1(y2)=1/4, Ps1(y3)=2/4
则有：
H(S1)= - Ps1(y1)log2 Ps1(y1) - Ps1(y2)log2 Ps1(y2 )- Ps1(y3)log2 Ps1(y3 )
= -(1/4)log2(1/4)- (1/4)log2(1/4)- (2/4)log2(2/4) =1.5
再由S2可知：
Ps2(y1)=0/4, Ps2(y2)=1/4, Ps2(y3)=3/4
则有：
H(S2)=– Ps2(y2)log2 Ps2(y2 )- Ps2(y3)log2 Ps2(y3 )
=- (1/4)log2(1/4)- (3/4)log2(3/4) =0.8113
将H(S1)和H(S2)代入条件熵公式，有：
H(S/x1)=(|S1|/|S|)H(S1)+ (|S2|/|S|)H(S2)
=(4/8)﹡1.5+(4/8)﹡0.8113 =1.1557
同样道理，可以求得：
H(S/x2)=1.1557
H(S/x3)=0.75
可见，应该选择属性x3对根节点进行扩展。用x3对S扩展后所得到的得到部分决策树如图6.5所示。
S
x3=1, y3
x3=2, x1, x2
图6.5 部分决策树
x3=1
x3=2

在该树中，节点“x3=1, y3 ”为决策方案y3。由于y3已是具体的决策方案，故该节点的信息熵为0，已经为叶节点。
节点“x3=2, x1, x2？”的含义是需要进一步考虑学历和专业这两个属性，它是一个中间节点，还需要继续扩展。至于其扩展方法与上面的过程类似。
通过计算可知，该节点对属性x1和x2，其条件熵均为1。由于它对属性x1和x2的条件熵相同，因此可以先选择x1，也可以先选择x2。
依此进行下去， 若先选择x1可得到如图66所示的最终的决策树；若先选择x2可得到如图7.7所示的最终的决策树。

14 （归结反演）
已知：“张和李是同班同学，如果x和y是同班同学，则x的教室也是y的教室，现在张在302教室上课。”
问：“现在李在哪个教室上课？”
解：首先定义谓词：
C(x, y) x和y是同班同学；
At(x, u) x在u教室上课。
把已知前提用谓词公式表示如下：
C(zhang, li)
(∀x) (∀y) (∀u) (C(x, y)∧At(x, u)→At(y,u))
At(zhang, 302)
把目标的否定用谓词公式表示如下：
﹁(∃v)At(li, v)
把上述公式化为子句集：
C(zhang, li)
﹁C(x, y)∨﹁At(x, u)∨At(y, u)
At(zhang, 302)
把目标的否定化成子句式，并用重言式
﹁At(li,v) ∨At(li,v)
代替之。
把此重言式加入前提子句集中，得到一个新的子句集，对这个新的子句集，应用归结原理求出其证明树。
其求解过程如下图所示。

该证明树的根子句就是所求的答案，即“李明在302教室”。
公式：
A 估价函数
用来估计节点重要性，定义为从初始节点S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。一般形式：
f(n)=g(n)+h(n)
其中，g(n)是从初始节点S0到节点n的实际代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价。

B A*算法是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法
假设f*(n)是从初始节点S0出发，约束经过节点n到达目标节点Sg的最小代价，估价函数f(n)是对f*(n)的估计值。记
f*(n)=g*(n)+h*(n)
其中， g*(n)是从S0出发到达n的最小代价,h*(n)是n 到Sg的最小代价
如果对A算法（全局择优）中的g(n)和h(n)分别提出如下限制：
第一，g(n)是对最小代价g*(n)的估计，且g(n)>0；
第二，h(n)是最小代价h*(n)的下界，即对任意节点n均有h(n)≤h*(n)。
则称满足上述两条限制的A算法为A*算法。

C 不确定性知识的表示形式：
在C-F模型中，知识是用产生式规则表示的，其一般形式为：
IF E THEN H (CF(H, E))　
其中，E是知识的前提条件；H是知识的结论；CF(H, E)是知识的可信度。

D 组合证据
合取：E=E1 AND E2 AND … En时，若已知CF(E1)，CF(E2)，…，则
CF(E)=min{CF(E1), CF(E2), … ,CF(En)}
析取：E=E1 OR E2 OR … En时，若已知CF(E1)，CF(E2)，…，则
CF(E)=max{CF(E1), CF(E2), … ,CF(En)}

E 不确定性的更新公式
CF(H)=CF(H, E)×max{0, CF(E)}
若CF(E)<0，则
CF(H)=0
即该模型没考虑E为假对H的影响。
若CF(E)=1，则
CF(H)=CF(H,E)

F 设有知识：IF E1 THEN H (CF(H, E1))
　　　　　 IF E2 THEN H (CF(H, E2))
则结论H 的综合可信度可分以下两步计算：
(1) 分别对每条知识求出其CF(H)。即
CF1(H)=CF(H, E1) ×max{0, CF(E1)}
CF2(H)=CF(H, E2) ×max{0, CF(E2)}
(2) 用如下公式求E1与E2对H的综合可信度

G 带加权因子的可信度推理
在这种不确定性推理中，证据的不确定性仍然用可信度因子表示，组合证据的可信度可通过计算得到。对于前提条件
E=E1(ω1) AND E2(ω2) AND …… AND En(ωn)
所对应的组合证据，其可信度由下式计算：
CF(E)= CF(E1)*ω1 +CF(E2)*ω2+……+CF(En)*ωn
如果不满足归一条件，则可信度由下式计算：
CF(E)= (CF(E1)*ω1 +CF(E2)*ω2+……+CF(En)*ωn)/(ω1+ ω2+… ωn)

H 证据理论
设函数m：2Ω→[0，1]，且满足

则称m是2Ω上的概率分配函数，m(A)称为A的基本概率数。

I 概率分配函数的合成
设m1和m2是2Ω上的基本概率分配函数，它们的正交和 定义为

其中

J 信任函数（下限函数）
对任何命题AΩ,其信任函数为

K 似然函数（上限函数）
对任何命题AΩ,其似然函数为

似然函数也称为上限函数，表示对A的非假信任度。可以看出，对任何命题AΩ、 AΩ都有
Pl(A)-Bel(A) = Pl(B)-Bel(B) = m(Ω)

L 类概率函数
设Ω为有限域，对任何命题AΩ，命题A的类概率函数为

M 证据的匹配度表示
设A是规则条件部分的命题，E'是外部输入的证据和已证实的命题，在证据E'的条件下，命题A与证据E'的匹配程度为

N 证据的确定性表示
条件部分命题A的确定性为
CER(A)=MD(A/E')×f(A)
其中f(A)为类概率函数。
由于f(A) ∈[0, 1]，因此CER(A) ∈[0, 1]

O 组合证据的不确定性表示
当组合证据是多个证据的合取时
E=E1 AND E2 AND … AND En
则
　 CER(E)=min{CER(E1), CER(E2), … ,CER(En)}
当组合证据是多个证据的析取时
E=E1 OR E2 OR … OR En
则
CER(E)=max{CER(E1), CER(E2), … . CER(En)

P 结论的确定性
设有知识 IF E THEN H={h1, h2, … , hn} CF={c1, c2, … , cn}
则求结论H的确定性CER(H)的方法如下：

如果有两条或多条知识支持同一结论H，例：
IF E1 THEN H={h1, h2, … , hn} CF={c11, c12, … , c1n}
IF E2 THEN H={h1, h2, … , hn} CF={c21, c22, … , c2n}
则按正交和求CER(H)，即先求出：
m1=m1({h1},{h2},…,{hn})
m2=m2({h1},{h2},…,{hn})
然后再用公式求m1和m2的正交和，最后求得H的m。

按公式CER(H)=MD(H/E') ×f(H)计算结论H确定性。

Q 信息熵
信息熵是对信息源整体不确定性的度量。假设X为信源，xi为X所发出的单个信息，P(xi)为X发出xi的概率，则信息熵可定义为：

R 条件熵
条件熵是收信者在收到信息后对信息源不确定性的度量。若假设信源为X，收信者收到的信息为Y， P(xi/yj)为当Y为yj时X为xi的条件概率，则条件熵可定义为：