人工智能例题大纲

《人工智能例题大纲》由会员分享，可在线阅读，更多相关《人工智能例题大纲（18页珍藏版）》请在装配图网上搜索。

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

2、月到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)得以下两个子句P(f(v),Q(f(w)对G,有P(f(a)VP(y)VQ(y)先进行内部合一，设合一f(a)/y,则有因子P(f(a)VQ(f(a)再对上述子句集进行归结演绎推理。其归结树如下图所示，即存在一个到空

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

4、巳(0.6)r2：IFE2ANDE3THEN曰(0.7)r3：IFE4THENH(0.8)r4：IFE5THENH(0.9)且已知CF(E)=0.5,CF(B)=0.6,CF(E)=0.7o求CF(H尸？解：(1)先由ri求CF(EJCF(E)=0.6xmax0,GF(E=0.6xmax0,0.5=0.3(2)再由r2求CF(B)CF(日)=0.7xmax0,minCF(ECF(E)=0.7xmax0,min0.3,0.6=0.21(3)再由r3求CFi(H)CF(H尸0.8xmax04CF(E=0.8xmax0,0.21)=0.168(4)再由r4求CF2(H)CF(H)=0.9xmax0,

5、5)F(E=0.9xmax0,0.7)=0.63(5)最后对CF(H)和C倒H)进行合成，求出CF(H)CF(H)=CF(H)+C凤H)-CF1(H)XC整(H)=0.6927设训练例子集如下表所示:序号属性分类巧X21TT+2TT+3TF4FF+5FT-6FT请用ID3算法完成其学习过程。解：设根节点为S,尽管它包含了所有的训练例子，但却没有包含任何分类信息，因此具有最大的信息嫡。即：H(S尸-(P(+)log2P(+)-P(-)log2P(-)式中P(+)=3/6,P(-)=3/6即有H(S)=-(3/6)*log(3/6)-(3/6)*log(3/6)=-0.5*(-1)-0.5*(-1

6、)=1按照ID3算法，需要选择一个能使S的期望嫡为最小的一个属性对根节点进行扩展，因此我们需要先计算S关于每个属性的条件嫡：H(S|xi尸(|St|/|S|)*H(St)+(|Sf|/|S|)*H(SF其中，T和F为属性Xi的属性值，St和SF分别为*1=丁或Xi=F时的例子集，|S|、|St|和|Sf|分别为例子集S、St和6的大小。下面先计算S关于属性Xi的条件嫡：在本题中，当Xi=T时，有：Sr=1,2,3当xi=F时，有：6=4,5,6其中，St和SF中的数字均为例子集S中例子的序号，且有|S|=6,|St|=|Sf|=3。由St可知：P(+)=2/3,P(-)=1/3则有：H(St)

7、=-(P(+)log2P(+)-P(-)log2P(-)=-(2/3)log2(2/3)-(1/3)log2(1/3)=0.9183再由4可知：PsR+)=1/3,Psf(-)=2/3则有：H(6)=-(PsR+)log2Pst(+)-PsF(-)log2Psf(-)=-(2/3)log2(2/3)-(1/3)log2(1/3)=0.9183将H(Sr)和H(6)代入条件嫡公式，有：H(S|xi)二(|St|/|S|)H(St)+(|Sf|/|S|)H(SF)=(3/6)*0.9183+(3/6)*0.9183=0.9183下面再计算S关于属性X2的条件嫡：在本题中，当X2=T时，有：Sr=1

8、,2,5,6当X2=F时，有：6=3,4其中，St和SF中的数字均为例子集S中的各个例子的序号，且有|S|=6,|St|=4,|Sf|二2。由St可知：Pst(+)=2/4Pst(-)=2/4则有：H(Sr)=-(Pst(+)log2Pst(+)-Pst(-)log2Pst(-)=-(2/4)log2(2/4)-(2/4)log2(2/4)=1再由我可知：Psf(+)=1/2Psf(-)=1/2则有：H(Sf)=-(P(+)log2P(+)-P(-)log2P(-)=-(1/2)log2(1/2)-(1/2)log2(1/2)=1将H(Sr)和H(6)代入条件嫡公式，有：H(S|x2)=(|S

9、t|/|S|)H(St)+(|Sf|/|S|)H(Sf)=(4/6)*1+(2/6)*1=1可见，应该选择属性X1对根节点进行扩展。用X1对S扩展后所得到的部分决策树如下图所示。8八数码难题11*=4 f=4So 2 8 3f-6f-62 8 31 47 6 51 S 4231 S 457 6 51 6 AiM户61f(n尸d(n)+P(n)d(n)深度P(n)与目标距离显然满足P(n)&h*(n)即f*=g*+h*八数码难题Mu尸F(u)的搜索树9修道士和野人问题解：用m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数，用三元组(m,c,b)表示问题的状态。对A*算法，首先需要确定

10、估价函数。设g(n)=d(n),h(n)=m+c-2b,则有f(n)=g(n)+h(n)=d(n)+m+c-2b其中，d(n)为节点的深度。通过分析可知h(n)h*(n)满足A*算法的限制条件。M-C问题的搜索过程如下图所示。修道士和野人同剧G3DLu(3,2,0)3 Ph=3 f=5 1h-3 Q6 | Us(3.0.0)-h=4 f=5h -2 J5 1rh -2电J)-0)间堰状态(nurJO怙价函数士 Mil) in )=0.6xmax0,0.8=0.48由3得到:CF3(H尸CF(H,E)xmax0,CF(E)=-0.5xmax0,0.6=-0.3根据结论不精确性的合成算法，CF1(

11、H)和CF2(H)同号，有：CF,2(H)CF(H) CF2(H) CF(H) C区 H)0.360.480.360.480.840.170.67CF2(H)和CF3(H)异号,有:CF,2,3(H)cf,2(H)CF(H)1minCFdH)|,|CE(H)|0.670.30.371min0.67,0.30.70.53即综合可信度为CF(H)=0.5311设有如下知识：CF (E1)r1:IFE1(0.6)ANDE2(0.4)THENE5(0.8)r2:IFE3(0.5)ANDE4(0.3)ANDE5(0.2)THENH(0.9)已知:=0.9,CF(E2)=0.8,CF(E3)=0.7,CF

12、(E4)=0.6求：CF(H)=?解：CF(E1ANDE2)=0.9*0.6+0.8*0.4=0.86CF(E5)=0.86*0.8=0.69CF(E3ANDE4ANDE5)=0.7*0.5+0.6*0.3+0.69*0.2=0.67CF(H)=0.67*0.9=0.6012设有如下规则：ri：IFEiANDETHENA=ai,a2CF=0.3,0.5IFE3THENH=hi,h2CF=0.4,0.2r3：IFATHENH=hi,h2CF=0.1,0.5已知用户对初始证据给出的确定性为：CER(E)=0.8CER(E)=0.6CER(E)=0.9并假定中的元素个数IQ1=10求：CER(H尸？

13、解：由给定知识形成的推理网络如下图所示：(1)求CER(A)由1：CER(EANDE2)=minCER(E1),CER(E)=min0.8,0.6=0.6m(a,a2)=0.6x0.3,0.6x0.5=0.18,0.3Bel(A)=m(a1)+m(a2)=0.18+0.3=0.48Pl(A)=1-Bel(A)=1-0=1f(A尸Bel(A)+|A|/|Q|?Pl(A)-Bel(A)=0.48+2/10*1-0.48=0.584故CER(A尸MD(A/E)Xf(A)=0.584(2)求CER(H)由2得m1(h1,h2)=CER(E)X0.4,CEF3)EX0.2=0.9X0.4,0.9X0.2

14、=0.36,0.18m1(Q)=1-m(h1)+m1(h2)=1-0.36+0.18=0.46由3得m2(hi,h2)=CER(A)X0.1,CER(A)X0.5=0.58X0.1,0.58X0.5=0.06,0.29m2(Q)=1-m(hi)+m2(h2)=1-0.06+0.29=0.65求正交和m=m1m2K=m1(Q)2(iQ)+m1(h1)X2(h1)+m1(h1)x2(Q)+ntQ)2(h1)+m1(h2)X2(h2)+m1(h2)x2(Q)+m(Q)2(h2)=0.46x0.65+0.36X0.06+0.36X0.65+0.46X0.06+0.18X0.29+0.18X0.65+0

15、.46X0.29=0.30+(0.02+0.23+0.03)+(0.05+0.12+0.13)=0.88mh1)1?m1(h1)?n2(hl)Km(h)?m()m()?n(h)同理可得:mh2)0.360.060.880.320.360.650.460.061m(h2)n(h2)m(h2)n()m()K0,180.290.180.650.460.290.88m(h2)0.34故有:m(Q)=1-m(h1)+m(h2)=1-0.32+0.34=0.34再根据m可得Bel(H)=m(h1)+m(h2)=0.32+0.34=0.66Pl(H)=m(Q)+Bel(H)=0.34+0.66=1Hf(H)

16、Bel(H)?Pl(H)Bel(H)0.66(10.66)0.7310CER(H)=MD(H/E)Xf(H)=0.7313用ID3算法完成下述学生选课的例子假设将决策y分为以下3类：y1:必修AI平:选修AIy3：不修AI做出这些决策的依据有以下3个属性:X1:学历层次x1=1研究生，x1=2本科X2：专业类别X2=1电信类，X2=2机电类X3：学习基础X3=1修过AI,X3=2未修AI表6.1给出了一个关于选课决策的训练例子集$序号属性值决策方案X,痴！心111I力211112Ji3121心412252111*36212yi7221)38222力该训练仞子集S的大小为8。ID3算法就是依据这

17、些训练例子，以S为根节点，按照信息嫡下降最大的原则来构造决策树的。解：首先对根节点，其信息嫡为：3h(s)P(yjog2P(yi)i1其中，3为可选的决策方案数，且有P(yi)=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/x)静t|S|其中，t为属性Xi的属性值，St为Xi=t时的例子集，|S|和|St|分别是例子集S和St的大小。下面先计算S关于属

18、性X1的条件嫡：在表6-1中，Xi的属性值可以为1或2。当xi=1时，t=1时，有：Si=1,2,3,4当xi=2时，t=2时，有：S2=5,6,7,8其中，Si和8中的数字均为例子集S中的各个例子的序号，且有|S|=8,|Si|=|S2|=4。由Si可知：Ps1(y1)=1/4,Ps1(y2)=1/4,Ps1(y3)=2/4则有：H(Si)=-Ps1(y1)10g2Psi(y1)-Psi(y2)log2Psi(y2)-Ps1(y3)log2Psi(y3)=-(1/4)log2(1/4)-(1/4)log2(1/4)-(2/4)log2(2/4)=1.5再由S2可知：Ps2(yi)=0/4,P

19、s2(y2)=1/4,Ps2(y3)=3/4则有：H(S2)=-Py2)log2Ps2(y2)-Ps2(y3)log2Ps2(y3)=-(1/4)log2(1/4)-(3/4)log2(3/4)=0.8113将H(&)和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对根节点进行扩展。用X3对S扩展后所得到的得到部分决策树如图6.5所示。图6.5部分决策树在该树中，节点“X3=1,y

20、3为决策方案V3。由于y3已是具体的决策方案，故该节点的信息嫡为0,已经为叶节点。节点“3=2,X1,X2?”的含义是需要进一步考虑学历和专业这两个属性，它是一个中间节点，还需要继续扩展。至于其扩展方法与上面的过程类似。通过计算可知，该节点对属性X1和X2,其条件嫡均为1。由于它对属性X1和X2的条件嫡相同，因此可以先选择Xi,也可以先选择X2。依此进行下去，若先选择X1可得到如图6.6所示的最终的决策树；若先选择X2可得到如图7.7所示的最终的决策树。WrtAhiji_I._未修AJg，,不工闺学历和专业？胡究t后I一本科生片修I专业彳专业？电信宪竺）=2电It髡炉嵬E处AI选植AJ选修A1

21、不修A1图&6最答的决策图国最终的决策树14(归结反演)已知：“张和李是同班同学，如果x和y是同班同学，则x的教室也是y的教室，现在张在302教室上课。”问：现在李在哪个教室上课？”解：首先定义谓词：C(x,y)x和y是同班同学；At(x,u)x在u教室上课。把已知前提用谓词公式表示如下：C(zhang,li)一 At(y,u)(?x)(?y)(?u)(C(x,y)AAt(x,u)At(zhang,302)把目标的否定用谓词公式表示如下：(？v)At(li,v)把上述公式化为子句集：C(zhang,li)C(x,y)VAt(x,u)VAt(y,u)At(zhang,302)把目标的否定化成子句

22、式，并用重言式At(li,v)VAt(li,v)代替之。把此重言式加入前提子句集中，得到一个新的子句集，对这个新的子句集，应用归结原理求出其证明树。该证明树的根子句就是所求的答案，即“李明在其求解过程如下图所示。302教室公式：A估价函数用来估计节点重要性，定义为从初始节点S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。一般形式：f(n)=g(n)+h(n)其中，g(n)是从初始节点S0到节点n的实际代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价。BA*算法是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法假设f*(n)

23、是从初始节点S0出发，约束经过节点n到达目标节点Sg的最小代价，估价函数f(n)是又f*(n)的估计值。记f*(n)=g*(n)+h*(n)其中，g*(n)是从出发到达n的最小代价，h*(n)是n到Sg的最小代价如果对A算法(全局择优)中的g(n)和h(n)分别提出如下限制：第一，g(n)是对最小代价g*(n)的估计，且g(n)0;第二，h(n)是最小代价h*(n)的下界，即对任意节点n均有h(n)wh*(n)则称满足上述两条限制的A算法为A*算法。C不确定性知识的表示形式：在C-F模型中，知识是用产生式规则表示的，其一般形式为：IFETHENH(CF(H,E)其中，E是知识的前提条件；H是知

24、识的结论；CF(H,E是知识的可信度。D组合证据合取：E=E1ANDE2AND-Eri寸，若已知CF(E1)CF(E2)，贝UCF(E尸minCF(E1),CF(E2),，CF(En)析取：E=E1ORE2OREn时，若已知CF(E1)CF(E2)，则CF(E尸maxCF(E1),CF(E2),，CF(En)E不确定性的更新公式CF(H尸CF(H,E)Xmax0,CF(E)若CF(E)(Si)m(Si)m()m1()m2(Si )m1(Si)m2()m()m(Si)nkm1()m()m(Si)m2(Si)i1j信任函数(下限函数)对任何命题A其信任函数为Bel(A)mSi)SiAnBel()m

25、B)mSi)m)1Bi1K似然函数(上限函数)对任何命题AQ其似然函数为npi(a)iBei(a)ime)ime)硬胡)SiAi1SiA11m)Bel(A)m)Bel(A)Pl()1Bel()1Bel()1似然函数也称为上限函数，表示对A的非假信任度。可以看出，对任何命题A、都有Pl(A)-Bel(A)=Pl(B)-Bel(B)=m(Q)L类概率函数设为有限域，对任何命题A，命题A的类概率函数为Af(A)Bel(A)Pl(A)Bel(A)M证据的匹配度表示设A是规则条件部分的命题，E是外部输入的证据和已证实的命题，在证据E的条件下,命题A与证据E的匹配程度为如果A的所有元素都出现在E中否则N证

26、据的确定性表示条件部分命题A的确定性为CER(A)=MD(A/E)Xf(A)其中f(A)为类概率函数。由于f(A)C0,1,因此CER(A)0,1O组合证据的不确定性表示当组合证据是多个证据的合取时E=BANDE2ANDANDEn则CER(E尸minCER(ECER(E),，CERE当组合证据是多个证据的析取时E=EORE2OROREn则CER(E)=maxCER(E),CER(E),.CER(EP结论的确定性设有知识IF E THENH=h1, h2,nhCF=c, c2, nc则求结论H的确定性CER(H的方法如下：m(hi，h2，,hn)(CER(E)jCER(E)C2，|,CER(E)

27、cnm()1CRE(E)ci1如果有两条或多条知识支持同一结论H,例：IFEiTHENH=hi,h2,nhCF=ci,C12,诲IFE2THENH=hi,h2,nhCF=c2i,C22,2nC则按正交和求CER(H)即先求出：mi=mi(hi,h2,hm2=m2(hi,h2,nh)然后再用公式mm明求mi和m2的正交和，最后求得H的m。nBel(H)m(hi)i1Pl(H)1Bel(H)|h|hf(H)Be(H)廿Pl(H)Be(H)Be(H)口m()按公式CER(H尸MD(H/E)xf(H算结论H确定性。Q信息嫡信息嫡是对信息源整体不确定性的度量。假设X为信源，x为X所发出的单个信息，P(x)为X发出Xi的概率，则信息嫡可定义为：H(X)P(x1)logP(x。Rx2)logP(X2)RxQlogP(x.)kP(xi)logP(xi)i1R条件嫡条件嫡是收信者在收到信息后对信息源不确定性的度量。若假设信源为X,收信者收到的信息为Y,P(x/yj)为当Y为yj时X为xi的条件概率，则条件嫡可定义为：kkH(X|Y)p(xi|yj)logP(xi|力)i1j1