人工智能例题大纲

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

2、生讲“计算机网络”课。解：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)再对上述子句集进行归结演绎推理。其归结树如下图所示，即存在一个到空子句的归结过程。因此G为

3、真。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设有如下一组推理规则且已知1: IF2: IF3: IF4: IFCF(E

4、1)=,THEN E 2AND E 3 THEN E 4THEN HTHEN HCF(E 3)=, CF(E 5)= 。求 CF(H)=?解：(1)先由ri求CF(E)CF(E2)=xmax0,CF(E1)=xmax0,二(2)再由r2求CF(E4)CF(E4)=xmax0,minCF(E2),CF(E3)=xmax0,min,二(3)再由r 3 求 CF1(H)CFi(H尸x max0,CF(E 4)=xmax0,=(4)再由r 4 求 CF2(H)CF2(H尸 x max0,CF(E 5)=xmax0,=(5)最后对CF1(H)和CF2(H)进行合成，求出CF(H)CF(H尸CFi(H)+

5、CF2(H)-CFi(H)XCF2(H)7设训练例子集如下表所示：请用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)=*(-1)-*(-1)=1按照ID3算法，需要选择一个能使S的期望熵为最小的一个属性对根节点进行扩展，因此我们需要先计算S关于每个属性的条件嫡：H(S|xi)=(|ST|/|S|)*H(ST)+(|SF|/|S|)*H(SF)其

6、中，T和F为属性Xi的属性值，St和8分别为*，=丁或*，=5时的例子集，|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(+)log2P(+)-P(-)log2P(-)=-(2/3)log2(2/3)-(1/3)log2(1/3)=再由Sf可知：PSF(+)=1/3，PSF(-)=2/3则有：H(SF)=-(PS

7、F(+)log2PST(+)-PSF(-)log2PSF(-)=-(2/3)log2(2/3)-(1/3)log2(1/3)=将H(St)和H(Sf)代入条件嫡公式，有：H(S|x1)=(|ST|/|S|)H(ST)+(|SF|/|S|)H(SF)=(3/6)*+(3/6)*下面再计算S关于属性x2的条件熵：在本题中，当x2=T时，有：ST=1，2，5，6当x2=F时，有：SF=3，4其中，St和我中的数字均为例子集S中的各个例子的序号，且有|S|=6,|St|=4,|Sf|二2。由ST可知：Pst(+)=2/4Pst(-)=2/4则有：H(ST)=-(PST(+)log2PST(+)-PST

8、(-)log2PST(-)=-(2/4)log2(2/4)-(2/4)log2(2/4)=1再由Sf可知：Psf(+)=1/2PSF(-)=1/2则有：H(SF)=-(P(+)log2P(+)-P(-)log2P(-)=-(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)d(n)深度P(n)与目标距离显

9、然满足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+c-2b其中，d(n)为节点的深度。通过分析可知h(n)wh*(n),满足A*算法的限制条件。M-C问题的搜索过程如下图所示。10 设有如下一组知识：r1：IFE1THENHr2：IFE2THENHr3：IFE3THENHr4：IFE4AND(E5ORE6)THENE1已知：CF(E2)=，C

10、F(E3)=，CF(E4)=，CF(E5)=,CF(E6)=求：CF(H)=?解：由4得到：CF(E1)=Xmax0,CF(E4AND(E5ORE6)=xmax0,minCF(E4),CF(E5ORE6)=xmax0,minCF(E4),maxCF(E5),CF(E6)=xmax0,minCF(E4),max,=xmax0,min,=xmax0,=由ri得到：CFi(H尸CF(H,Ei)Xmax0,CF(E1)=xmax0,=由2得到：CE(H尸CF(H,E2)Xmax0,CF(E2)=xmax0,=由3得到：CE(H尸CF(H,E3)Xmax0,CF(E3)=xmax0,=根据结论不精确性的

11、合成算法，CF1(H)和CF2(H)同号，有：CF1,2(H)CF1(H)CF2(H)CF1(H)CF2(H)0.360.480.360.480.840.170.67CF12(H)和CF3(H)异号，有：CF,2,3(H)CF,2(H)CF(H)1minpK(H)|，CWH)|0.670.30.371min0.67,0.3-0?70.53即综合可信度为CF(H)=11设有如下知识:ri:IFE1()ANDE2()THENE5()r2:IFE3()ANDE4()ANDE5()THENH()已知：CF(E1)=,CF(E2)=,CF(E3)=,CF(E4)=求：CF(H)=?解：CF(E1ANDE

12、2)=*+*=CF(E5)=*=CF(E3ANDE4ANDE5)=*+*+*=CF(H)=*=12设有如下规则：r1：IFE1ANDE2THENA=a1,a2CF=,r2：IFE3THENH=h1,h2CF=,r3：IFATHENH=h1,h2CF=,已知用户对初始证据给出的确定性为：CER(E1)=CER(E2)=CER(E3)=并假Q定中的元素个数IQI=10求：CER(H)=?解：由给定知识形成的推理网络如下图所示:(1)求CER(A)由ri：CER(EiANDE2)=minCER(E1),CER(E2)=min,=m(a1,a»)=乂,x=,Bel(A)=m(ai)+m(a2

13、)=+=Pl(A)=1-Bel(A)=1-0=1f(A)=Bel(A)+|A|/|Q|?Pl(A)-Bel(A)=+2/10*口故CER(A)=MD(A/E')Xf(A)=(2)求CER(H)由r2得m1(h1,h2)=CER(E3)X,CER(E3)X=X,X=,m1(Q)=1-m1(h1)+m1(h2)=1-+=由r3得m2(h1,h2)=CER(A)x,CER(A)x=X,X=,m2(Q)=1-m2(h1)+m2(h2)=1-+=求正交和m=m®m2K=mi()Xm2()+mi(hi)Xm2(hi)+mi(hi)xm2()+mi()Xm2(h1)+mi(h2)Xm2(h

14、2)+mi(h2)Xm2(Q)+mi(Q)Xm2(h2)二x+X+X+X+X+X+X=+nmhi)i? m( hi) ? n2( h) Km( hi) ? ni()m( ) ? m( hi)i 0.36 0. 880.320. 060. 36 0. 650.460. 06同理可得:n(h2) m( h2)m( h2)m( h2)m2()m()m( h2)0. 880. i80. 290. I8 0. 650.460. 290. 34故有：m(Q )=i -m(h i)+m(h 2)=i-+=再根据m可得Bel(H)=m(hi)+m(h 2) = + =Pl(H)=m( Q)+Bel(H)=+=

15、iHf(H)Bel(H)?Pl(H)Bel(H)0.66i0(i0. 66)0. 73CER(H尸MD(H/E')Xf(H)=i3用ID3算法完成下述学生选课的例子假设将决策y分为以下3类:y1：必修AIy2：选修AIy3：不修AI做出这些决策的依据有以下3个属性：x1：学历层次x1=1研究生，x1=2本科x2：专业类别x2=1电信类，x2=2机电类x3：学习基础x3=1修过AI，x3=2未修AI表给出了一个关于选课决策的训练例子集S。该训练仞子集S的大小为8。ID3算法就是依据这些训练例子，以S为根节点，按照信息熵下降最大的原则来构造决策树的。解：首先对根节点，其信息熵为：3H(S)

16、P(yi)log2P(yi)i1其中，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)=按照ID3算法，需要选择一个能使S的期望熵为最小的一个属性对根节点进行扩展，因此我们需要先计算S关于每个属性的条件熵：其中，t为属性Xi的属性值，S为xi=t时的例子集，|S|和|St|分别是例子集S和S的大小。下面先计算S关于属性x1的条件熵：在表6-1中，x1的属性值可以为1或2。当x1=1时，t=1时，有：S1=1，2，3，4当x1=2时，t=2时，有：2=5，

17、6，7，8其中，S和S2中的数字均为例子集S中的各个例子的序号，且有|S|=8,|Si|=|S2|=4。由S可知：Psi(yi)=1/4,Psi(y2)=1/4,Psi(y3)=2/4则有：H(S1)=-Psi(yi)log2Psi(yi)-Psi(y2)log2Psi(y2)-Psi(y3)log2Psi(y3)=-(1/4)log2(1/4)-(1/4)log2(1/4)-(2/4)log2(2/4)=再由S2可知：Ps2(y1)=0/4,Ps2(y2)=1/4,Ps2(y3)=3/4则有：H(S2)=Ps2(y2)log2Ps2(y2)-Ps2(y3)log2Ps2(y3)=-(1/4)

18、log2(1/4)-(3/4)log2(3/4)=将H(S1)和H(S2)代入条件嫡公式，有：H(S/x1)=(|S1|/|S|)H(S1)+(|S2|/|S|)H(S2)=(4/8)*+(4/8)*=同样道理，可以求得：H(S/x2)=H(S/x3)=可见，应该选择属性X3对根节点进行扩展。用X3对S扩展后所得到的得到部分决策树如图所示。图部分决策树在该树中，节点“X3=1,y3”为决策方案V3。由于y3已是具体的决策方案，故该节点的信息熵为0，已经为叶节点。节点“X3=2,x1,x2?”的含义是需要进一步考虑学历和专业这两个属性，它是一个中间节点，还需要继续扩展。至于其扩展方法与上面的过程

19、类似。通过计算可知，该节点对属性x1和x2，其条件熵均为1。由于它对属性x1和x2的条件嫡相同，因此可以先选择X1,也可以先选择X2O依此进行下去，若先选择x1可得到如图所示的最终的决策树；若先选择x2可得到如图所示的最终的决策树。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)AAt(x,u)-At(y,u)At(zhang,302

20、)把目标的否定用谓词公式表示如下：(？v)At(li,v)把上述公式化为子句集：C(zhang,li)C(x,y)VAt(x,u)VAt(y,u)At(zhang,302)把目标的否定化成子句式，并用重言式At(li,v)VAt(li,v)代替之。把此重言式加入前提子句集中，得到一个新的子句集，对这个新的子句集，应用归结原理求出其证明树。其求解过程如下图所示。该证明树的根子句就是所求的答案，即“李明在302教室”。公式：A估价函数用来估计节点重要性，定义为从初始节点S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。一般形式：f(n)=g(n)+h(n)其中，g(n)是从

21、初始节点So到节点n的实际代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价。BA*算法是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法假设f*(n)是从初始节点S0出发，约束经过节点n到达目标节点S的最小代价，估价函数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均有

22、h(n)wh*(n)。则称满足上述两条限制的A算法为A*算法。C不确定性知识的表示形式：在C-F模型中，知识是用产生式规则表示的，其一般形式为：IFETHENH(CF(H,E)其中，E是知识的前提条件；H是知识的结论；CF(H,E)是知识的可信度。D组合证据合取：E=E1ANDE2ANDEn时，若已知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

23、)<0，则CF(H)=0即该模型没考虑E为假对H的影响。若CF(E)=1，则CF(H)=CF(H,E)F设有知识：IFE1THENH(CF(H,E1)IFE2THENH(CF(H,E2)则结论H的综合可信度可分以下两步计算：(1)分别对每条知识求出其CF(H)。即CF1(H尸CF(H,E1)Xmax0,CF(E1)CF2(H尸CF(H,E2)Xmax0,CF(Ez)(2)用如下公式求E1与E2对H的综合可信度CF(H) CF2(H) CF(H) CF(H)C")的H) CF2(H)函H) C")C早H)CFH)1minCF=(H)|,|CF(H)|若 CF(H)0且

24、CF(H)0若 CF(H)0且 CF(H)0若CF(H)与C反H)异号G带加权因子的可信度推理在这种不确定性推理中，证据的不确定性仍然用可信度因子表示，组合证据的可信度可通过计算得到。对于前提条件E=E1(w1)ANDE2(w2)ANDANDEn(wn)所对应的组合证据，其可信度由下式计算：CF(E户CF(E1)*co1+CF(E2)*co2+CF(En)*3n如果不满足归一条件，则可信度由下式计算：CF(E尸(CF(E1)*co1+CF(E2)*co2+CF(En)*3n)/(co1+32+con)H证据理论设函数m：2°一0,1,且满足m)0mA)1A则称m是2s上的概率分配函数

25、，m(A)称为A的基本概率数。I概率分配函数的合成设m和m2是2。上的基本概率分配函数，它们的正交和mm1m1定义为mSi)K1m1(Si)m(Si)m(Si)m2()m1()m(Si)其中nkm1()m()m(Si)m(Si)m1(Si)m()m()mg)j信任函数(下限函数)对任何命题AQ,其信任函数为Bel(A)msj)SiAnBel()n(B)m(si)m)1Bi1K似然函数(上限函数)对任何命题A，其似然函数为npi(A)iBei(a)ime)ime)mSi)SiAi1SiA11m)Bel(A)m)Bel(A)Pl()1Bel()1Bel()1似然函数也称为上限函数，表示对A的非假信任度。可以看出，对任何命题A、AQ都有Pl(A)-Bel(A) = Pl(B)-