人工智能例题大纲

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

2、mputer)2请用语义网络表示如下知识：高老师从 3 月到 7 月给计算机系的学生讲“计算机网络”课。解:3.判断以下子句集是否为不可满足P(x) VQ(x ) VR(x),P(y) VR(y),Q(a),R(b)解：采用归结反演，存在如下归结树，故该子句集为不可满足。4、证明 G 是 F 的逻辑结论F： (? x)(? y)(P(f(x)A(Q(f(y)G： P(f(a) AP(y) AQ(y)证：先转化成子句集对 F,进行存在固化，有P(f(v) A(Q(f(w)得以下两个子句)VR(K)-.P(yVR(y)P(f(v) , Q(f(w)对G,有P(f(a) VP(y) VQ(y)先进行

3、内部合一，设合一 f(a)/y,则有因子P(f(a) VQ(f(a)再对上述子句集进行归结演绎推理。其归结树如下图所示，即存在一个到空子句的归结过程。因此 G 为真。-p(f(nn v町)巩恥”5 设有如下结构的移动将牌游戏:BBWWE其中，B 表示黑色将牌， W 表是白色将牌，E 表示空格。游戏的规定走法是：(1)任意一个将牌可移入相邻的空格，规定其代价为1 ；(2)任何一个将牌可相隔 1 个其它的将牌跳入空格，其代价为跳过将牌的数目加1。游戏要达到的目标什是把所有W 都移到 B 的左边。对这个问题，请定义一个启发函 数 h(n)，并给出用这个启发函数产生的搜索树。你能否判别这个启发函数是否

4、满足下界要的八求？在求出的搜索树中，对所有节点是否满足单调限制?解：设 h(x)=每个 W 左边的 B 的个数，f(x)=d(x)+3*h(x)，其搜索树如下:BBV1)=1+12=130B VvBBvBBi rrR 2zB十AH二I十看ioF(i)=5+3-8fW=6+3=9WD|Bfx)=7+0=76 设有如下一组推理规则r1：IFE1THENE2(0.6)r2：IFE2ANDE3THENE4(0.7)r3：IFE4THENH (0.8)r4：IFE5THENH (0.9)且已知 CF(Ei)=0.5, CF(E3)=0.6, CF(E5)=0.7。求 CF(H)=? 解：(1)先由门求C

5、F(E2)CF(E2)=0.6 x max0,CF(E1)=0.6 x max0,0.5=0.3再由 r2求 CF(E4)f(x)-0+12-121(1)=1+12=13f(x)=2412=14CF(E4)=0.7xmax0, minCF(E2), CF(E3)=0.7 x max0, min0.3, 0.6=0.21 再由 r3求 CFi(H)CFi(H)= 0.8 x max0,CF(E4)=0.8 x max0, 0.21)=0.168再由4求 CF2(H)CF2(H)= 0.9Xmax0,CF(E5)=0.9 xmax0, 0.7)=0.63(5)最后对 CFi(H )和 CF2(H)

6、进行合成，求出 CF(H)CF(H)= CFi(H)+CF2(H)- CFi(H) x CF2(H)=0.6927 设训练例子集如下表所示:序号属性分类X】1TT+2TT+3TF4FF+5FT6FT请用 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

7、算法，需要选择一个能使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的条件熵：在本题中，当 xi=T 时，有：ST=1, 2, 3当 xi=F 时，有：SF=4, 5, 6其中，ST和SF中的数字均为例子集S 中例子的序号，且有|S|=6 , |ST|=| SF|=3。由

8、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|XI)=(|ST|/|S|)H(ST)+ (|SF|/|S|)H(SF)=(3/6) * 0.9183

9、+ (3/6)* 0.9183=0.9183下面再计算 S 关于属性 X2的条件熵：在本题中，当 X2=T 时，有:=1ST=1, 2, 5, 6当 X2=F 时，有：SF=3, 4其中，ST和SF中的数字均为例子集 S 中的各个例子的序号，且有|S|=6 , |ST|=4 , |SF|=2。由ST可知：PST(+) = 2/4PST(-) = 2/4则有：H(ST)=- (PST什)log2 PST(+) - PST(-)log2 PST(-)=-(2/4)log2(2/4) - (2/4)log2(2/4)=1再由SF可知：PSF(+)=1/2PSF(-)=1/2则有：H(SF)= - (

10、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可见，应该选择属性 X1对根节点进行扩展。用 X1对 S 扩展后所得到的部分决策树如下图所示。扩展勺后的部分决策树8 八数码难题f(n )=d( n)+P( n)八数码11(QP(11)的搜藝树d(n)深度P(n)与目标距离显然满足P(n) h*(n)231 S 475231 E 4LUf=4g*_3 h

11、*Tf=4L4f-616 49 修道士和野人问题解：用 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+c-2b其中，d(n)为节点的深度。通过分析可知h(n) 36212於722138222该训练例子集 S 的大小为 8 o ID3 算法就是依据这些训练例子， 以 S 为根节点，按照信 息熵下降最大的原则来构造决策树的。X1:学历层次X2:专业类别X2=1x1=1 研究生，X1=2 本科电信类，

12、X2=2 机电类修过 AI，x3=2 未修 AI解：首先对根节点，其信息熵为：3H(S)P(y)og2P(yi1其中，3 为可选的决策方案数，且有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 关于每个属性的条件熵：H(S/Xi)回H(SJt|S|t其中，t 为属性 Xi的属性值，St为 Xi=t 时的例子集，|S|和|St|分别是例子集 S 和 St的

13、 大小。下面先计算 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)log2Ps1(y1) - Ps1(y2)log2Ps1(y2)- Ps1(y3)log2Ps1(y3)=-(1/4)log2(1/4)- (1/4)log2(1/4)

14、- (2/4)log2(2/4) =1.5再由 S2可知:Ps2(yi)=0/4,Ps2(y2)=1/4,Ps2(y3)=3/4贝 U 有：H(S2)= Ps2(y2)log2Ps2(y2)- Ps2(y3)log2Ps2(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.1557H(S/x3)=0.75可见，应该选择属性 X3

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

16、.7 所示的最终的决策树。1)=1. y(可E6-7屋汽的决幫時14 （归结反演）已知：“张和李是同班同学，如果x 和 y 是同班同学，贝 y x 的教室也是 y 的教室，现在张在 302 教室上课。”问：“现在李在哪个教室上课？”解：首先定义谓词：C(x, y)x 和 y 是同班同学；At(x, u)x 在 u 教室上课。把已知前提用谓词公式表示如下：C(zha ng, li)(? x) (? y) (? u) (C(x, y) AAt(x, u) At(y,u)At(zhang, 302)把目标的否定用谓词公式表示如下：(? v)At(li, v)把上述公式化为子句集：C(zha ng,

17、li)C(x, y) VAt(x, u) VAt(y, u)At(zhang, 302)把目标的否定化成子句式，并用重言式At(li,v)VAt(li,v)代替之。把此重言式加入前提子句集中，得到一个新的子句集，对这个新的子句集，应用归结原理求出其证明树。其求解过程如下图所示。第二，h(n)是最小代价 h*(n)的下界，即对任意节点n 均有 h(n) 0 ;则称满足上述两条限制的 A 算法为 A*算法。302 教室”。该证明树的根子句就是所求的答案，即“李明在C 不确定性知识的表示形式：在 C-F 模型中，知识是用产生式规则表示的，其一般形式为：IF E THEN H (CF(H, E)其中，

18、E 是知识的前提条件；H 是知识的结论；CF(H, E)是知识的可信度。D 组合证据合取：E=E1 AND E2 AND En 时，若已知 CF(E1) , CF(E2)，则CF(E)=minCF(E1), CF(E2),，CF(En)析取：E=E1 OR E2 OR En 时，若已知 CF(E1) , CF(E2)，贝 UCF(E)=maxCF(E1), CF(E2),，CF(E n)E 不确定性的更新公式CF(H)=CF(H, E) xmax0, CF(E)若 CF(E)0，贝 UCF(H)=0即该模型没考虑 E 为假对 H 的影响。若 CF(E)=1 ,贝 UCF(H)=CF(H,E)F

19、 设有知识：IF E1THEN H (CF(H, E1)IF E2THEN H (CF(H, E2)则结论 H 的综合可信度可分以下两步计算：(1)分别对每条知识求出其CF(H)。即CFi(H)=CF(H, E1) Xmax0, CF(E1)CF2(H)=CF(H, E2) Xmax0, CF(E2)(2)用如下公式求E1与巳对 H 的综合可信度CF(H)CF(H)CF(H)CFfH)若 CF(H)0且 CF2(H)0CF(H)CF(H)CF(H)CF(H)CF(H)若 CF(H)0且 CF(H)0CRH)CF2H)若 CF(H)与1 min CFKH)|,|CF2H)CH)异号G 带加权因子

20、的可信度推理在这种不确定性推理中， 证据的不确定性仍然用可信度因子表示，组合证据的可信度可通过计算得到。对于前提条件E=E1(1) AND E2(2) ANDAND En(n)所对应的组合证据，其可信度由下式计算：CF(E)= CF(E1)*w1 +CF(E2)*2+CF(En)*n如果不满足归一条件，则可信度由下式计算：CF(E)= (CF(E1)*w1 +CF(E2)*2+CF(En)*n)/(1+2+n)H 证据理论设函数 m : 20 , 1，且满足m) omA)iA则称 m 是 2 上的概率分配函数， m(A)称为 A 的基本概率数。I 概率分配函数的合成设 mi和 m2是 2 上的

21、基本概率分配函数，它们的正交和 定义为m2mSi)1Km(Si)mSi)mg)m()m()m(Si)其中Km(n)m( )m(Si)i1mg)mg)m()m()m(Si)J信任函数(下限函数)对任何命题AQ,其信任函数为Bel(A)mSi)SiAnBel()mB)msj)Bi 1m)1K 似然函数(上限函数)对任何命题AQ,其似然函数为Pl(A)iBel(A)1msj)n1 mSi)mSi)SiAi1SiA1 1m)Bel(A)m)Bel(A)Pl()1Bel()1Bel()1似然函数也称为上限函数，表示对 A 的非假信任度。可以看出，对任何命题 A Q、API(A)-Bel(A) = PI(

22、B)-Bel(B) = m(L 类概率函数设 Q 为有限域，对任何命题 A Q,命题 A 的类概率函数为Af(A)Bel(A) 卄PI(A)Bel(A)M 证据的匹配度表示设 A 是规则条件部分的命题，E是外部输入的证据和已证实的命题，在证据E的条件下，命题 A 与证据 E的匹配程度为仃如果 A 的所有元素都出现在疋中MDC4|F) =0否则N 证据的确定性表示条件部分命题 A 的确定性为CER(A)=MD(A/E) Xf(A)其中 f(A)为类概率函数。由于 f(A) 0, 1，因此 CER(A) 0,1Q)O 组合证据的不确定性表示 当组合证据是多个证据的合取时CER(E)=minCER(E1), CER(E2),，CER(En)当组合证