人工智能例题大纲(共16页)

1、精选优质文档-倾情为你奉上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, pra

2、gramming)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，

3、则有因子 P(f(a) Q(f(a) 再对上述子句集进行归结演绎推理。其归结树如下图所示，即存在一个到空子句的归结过程。 因此G为真。5 设有如下结构的移动将牌游戏：其中，B表示黑色将牌，W表是白色将牌，E表示空格。游戏的规定走法是： (1) 任意一个将牌可移入相邻的空格，规定其代价为1； (2) 任何一个将牌可相隔1个其它的将牌跳入空格，其代价为跳过将牌的数目加1。 游戏要达到的目标什是把所有W都移到B的左边。对这个问题，请定义一个启发函数h(n)，并给出用这个启发函数产生的搜索树。你能否判别这个启发函数是否满足下界要求？在求出的搜索树中，对所有节点是否满足单调限制？解：设h(x)=每个W左

4、边的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 × max0,CF(E1) =0.6 × max0,0.5=0.3(2) 再由r2求CF(E4) CF(E4)=0.7 × ma

5、x0, minCF(E2 ), CF(E3 ) =0.7 × max0, min0.3, 0.6=0.21 (3) 再由r3求CF1(H) CF1(H)= 0.8 × max0,CF(E4) =0.8 × max0, 0.21)=0.168 (4) 再由r4求CF2(H) CF2(H)= 0.9 ×max0,CF(E5) =0.9 ×max0, 0.7)=0.63 (5) 最后对CF1(H )和CF2(H)进行合成，求出CF(H) CF(H)= CF1(H)+CF2(H)- CF1(H) × CF2(H) =0.6927 设训练例子集

6、如下表所示： 请用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

7、| / |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)

8、=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

9、中的数字均为例子集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

10、(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(

11、n)=d(n)+m+c-2b其中，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×max0, CF(E4 A

12、ND (E5 OR E6) = 0.8×max0, minCF(E4), CF(E5 OR E6) =0.8×max0, minCF(E4), maxCF(E5), CF(E6) =0.8×max0, minCF(E4), max0.6, 0.8 =0.8×max0, min0.5, 0.8 =0.8×max0, 0.5 = 0.4 由r1得到：CF1(H)=CF(H, E1)×max0, CF(E1) =0.9×max0, 0.4 = 0.36 由r2得到：CF2(H)=CF(H, E2)×max0, CF(E2

13、) =0.6×max0, 0.8 = 0.48 由r3得到：CF3(H)=CF(H, E3)×max0, CF(E3) =-0.5×max0, 0.6 = -0.3 根据结论不精确性的合成算法，CF1(H)和CF2(H)同号，有： CF12(H)和CF3(H)异号，有：即综合可信度为CF(H)=0.5311 设有如下知识： 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.

14、7，CF（E4）=0.6 求： CF（H）=?解：CF(E1 AND E2)=0.9*0.6+0.8*0.4=0.86CF(E5)=0.86*0.8=0.69CF(E3 AND E4 AND E5)=0.7*0.5+0.6*0.3+0.69*0.2=0.67CF(H)=0.67*0.9=0.6012设有如下规则： 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

15、 CER(E2)=0.6 CER(E3)=0.9并假定中的元素个数=10 求：CER(H)=? 解：由给定知识形成的推理网络如下图所示：(1) 求CER(A) 由r1: CER(E1 AND E2) =minCER(E1), CER(E2) =min0.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故 C

16、ER(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=

17、0.65求正交和m=m1m2 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同理可得：故有

18、：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=1CER(H)=MD(H/E')×f(H)=0.7313用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

19、给出了一个关于选课决策的训练例子集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|分别是例

20、子集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

21、/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 可见，应

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

23、如图6.6所示的最终的决策树；若先选择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,

24、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

25、*算法是对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 不确定性知

26、识的表示形式： 在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)=minCF(E1), CF(E2), ,CF(En) 析取：E=E1 OR E2 OR En时，若已知CF(E1)，CF(E2)，则 CF(E)=maxCF(E1), CF(E2), ,CF(En) E 不确定性的更新公式 CF(H)=CF(H, E)×max0, CF(E) 若CF(E

27、)<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) ×max0, CF(E1) CF2(H)=CF(H, E2) ×max0, 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：20，1，且满足则称m是2上的概率分配函数，m(A)称为A的基本概率数。I 概率分配函数的合成设m1和m2是2上的基本概率分配函数，它们的正交和 定义为其中J 信任函数（下限函数）对任何命题A,其