搜索
人工智能期末考试卷（1）标准答案及评分标准一、填空题（每空1分，共10分）1智能具有五个特征，分别为①学习能力、自适应能力、②记忆与思维能力、表达能力和感知能力。2．机器的③感知能力是让机器自动获取知识的基本条件，而知识的自动获取一直是智能系统研究中最困难的问题之一。3．从研究的角度不同，对人工智能的研究可分两大阵营：④联接和⑤符号。其中⑤符号的理论基础为数理逻辑。4.⑥问题规约方法是一种将复杂问题变换为比较简单的子问题，子问题再转换为更简单的子问题，最终将问题转换为对本原问题的知识表示方法。5.鲁宾逊提出了⑦归结原理使机器定理证明成为可能。6．当某个算符被认为是问题求解的决定步骤时，此算符为⑧关键算符。7.宽度优先搜索与深度优先搜索方法的一个致命的缺点是当问题比较复杂是可能会发生⑨组合爆炸。8.语义网络⑩方法是1968年由J.R.Quilian在研究人类联想记忆时提出的心理学模型。1972年，Simon首先将⑩用于自然语言理解系统。二、简答题（共30分）1．什么是A*算法的可纳性？(4分)答：在搜索图存在从初始状态节点到目标状态节点解答路径的情况下，若一个搜索法总能找到最短（代价最小）的解答路径，则称算法具有可采纳性。2．在一般图搜索算法中，当对某一个节点n进行扩展时，n的后继节点可分为三类，请举例说明对这三类节点的不同的处理方法。(8分)答：把SNS中的子节点分为三类：（1）全新节点，（2）已出现于OPEN表的节点，（3）已出现于CLOSE表的节点；/后二类子节点实际上意味着具有新老两个父节点；(3分)加第1类子节点于OPEN表，并建立从子节点到父节点n的指；(1分)比较第2类子节点经由新、老父节点到达初始状态节点s的路径代价，若经由新父节点的代价较小，则移动子节点指向新父节点(2分)对于第3类子节点作与第2类同样的处理，并把这些子节点从CLOSE表中移出，重新加入OPEN表；(2分)3．请简述不确定性推理的含义。(4分)是一种从不确定的初始证据出发，通过运用不确定性知识，最终推出具有一定程度的不确定性但却有是合理或基本合理的结论的推理过程。4．若S={P(x)∨Q(f(x)),┐P(a),┐Q(y)}，请画出与该子句集对应的语义树，为什么可以用封闭语义树来判定子句集的不可满足性？(14分)答：H={a,f(a),f(f(a)),……}(1分)Й={P(a),Q(a),p(f(a)),Q(f(a)),……}(1分)n11导致基子句┐P(a)为假；(1分)n21：导致基子句┐Q(a)为假；(1分)n41：导致基子句P(a)∨Q(f(a))为假；(f(a)/y)(1分)n42：导致基子句P(x)∨Q(f(x))为假；(a/x)(1分)n43：导致基子句Q(f(a))为假；(1分)n44：导致基子句P(a)∨Q(f(a))为假。(1分)至此，已生成了一棵封闭的语义树。若某个子句集不可满足，则不必无限地扩展语义树，就可以确定语义树上的所有路径都分别对应一个导致子句集不可满足的解释。(4分)三、不确定性推理题（每题10分，共20分）1.设有如下知识：R1:IFE1THEN(20,1)HR2:IFE2THEN(300,1)H已知：结论H的先验概率P(H)=0.03。若证据E1，E2依次出现，按主观Bayes方法推理，求H在此条件下的概率P(H/E1E2)。解：(1)求p(B1/A)由于A是必然发生的,所以证据A肯定存在。又由于P(A/S)=1(由规则R1得：p(B1/A)=[LS1*P(B1)]/[(LS1-1)*P(B1)+1]=0.382(3分)(2)求p(B2/A)由于B1不是必然发生的,即证据B1是不确定的。所以应使用EH公式。(2分)又由于P(A/S)=1（证据A必然发生），所以使用公式的后半部。由规则R2得：P(B2/A)=P(B2)+[P(B2/B1)-P(B2)]/[1-P(B1)]*[P(B1/A)-P(B1)](3分)而P(B2/B1)=[LS2*P(B2)]/[(LS2-1)*P(B2)+1]=0.752(2分)所以P(B2/A)=0.01+（0.752-0.01）/（1-0.03）*（0.382-0.03）=0.279┐Q(fa))Q(f(a))┐Q(fa))┐P(f(a))P(f(a))Q(a)┐Q(a)n31n41n42n43n44n21n11┐P(a)P(a)n0Q(f(a))(2分)2．已知：R1:IFA1THENB1CF(B1,A1)=0.6R2:IFA2THENB1CF(B1,A2)=0.5R3:IFB1∨A3THENB2CF(B2,B1∨A3)=0.8初始证据A1,A2,A3,的可信度均为1。而对B1,B2一无所知。求CF(B1)和CF(B2)。解：（1）对知识R1和R2分别计算CF(B1)CF1(B1)=CF(B1,A1)*max{0,CF(A1)}=0.6*1=0.6(2分)CF2(B1)=CF(B1,A2)*max{0,CF(A2)}=0.5*1=0.5(2分)(2)利用合成算法计算B1的综合可信度。CF1，2(B1)=CF1(B1)+CF2(B1)-CF1(B1)*CF2(B1)=0.8(3分)(3)计算B2的可信度CF(B2).CF(B2)=CF(B2,B1∧A3)*CF(B1∨A3)(3分)=0.8*max{0,CF(B1∨A3)}=0.8*max{0,max{CF(B1),CF(A3)}}=0.64四、请用鲁宾逊归结原理证明：任何通过历史考试并中了彩票的人是快乐的。任何肯学习或幸运的人可以通过所有的考试。John不学习但很幸运。任何人只要是幸运就能中彩。求证：John是快乐的。（10分）证明：先将问题用谓词描述如下：(x)(Pass(x,computer)∧Win(x,prize))→Happy(x))(x)(y)(Study(x)∨Lucky(x)→Pass(x,y))┐Study(zhang)∧Lucky(zhang)(x)(Lucky(x)→Win(x,prize))结论“张是快乐的”的否定┐Happy(zhang)(3分)将上述公式转化为子句集如下：（1）┐Pass(x,computer)∨┐Win(x,prize)∨Happy(x)(2)┐Study(y)∨Pass(y,z)(3)┐Lucky(u)∨Pass(u,v)(4)┐Study(zhang)(5)Lucky(zhang)(6)┐Lucky(w)∨Win(w,prize)(7)┐Happy(zhang)(3分)1．用框架表示下述报道的地震事件。[虚拟新华社4月24日电]昨日，在唐山地区发生地震，造成财产损失约20万元，死亡10人。有关部门如果需要详细的损失数字，可电询900119。另据专家认为震级为6级。提示：分析、概括用下划线标出的要点，经过概念化形成槽（slot）、侧面（facet）值。特别注意，“值”（value）、“默认值”（default）、“如果需要”（if-needed）、的区别与应用，建议采用格式如下，不用的侧面值可删。Frame台风地点:唐山时间:昨日财产损失:20万元死亡：10人答：Frame台风地点:Value:唐山(2分)时间:Value:昨日(2分)财产损失:Value:20万元If-needed:电询900119(2分)死亡：Value:10人If-needed:电询900119(2分)震级：Value:6级(2分)2．请对下列命题写出它的语义网络：{zhqang/u,computer/v}{zhqang/x}{W/x}┐Pass(x,computer)∨┐Win(x,prize)∨Happy(x)┐Lucky(w)∨Win(w,prize)┐Pass(w,computer)∨Happy(w)∨┐Lucky(w)┐Happy(zhang)┐Pass(zhang,computer)∨┐Lucky(zhang)Lucky(zhang)┐Pass(zhang,computer)┐Lucky(u)∨Pass(u,v)┐Lucky(zhang)Lucky(zhang)NIL(4分)所有的学生都看过所有的四大名著。答：六．用A*算法解决八数码难题：设计八数码游戏的估价函数f(n)，其满足A*算法的要求；设初始棋盘布局为S，目标棋盘布局分别为g，如下图所示：画出使用该估价函数的搜索图，并标注每个节点的f(n)值。(10分)答：f(n)=g(n)+h(n)，g(n)=d(n)(即节点n的深度)；(1分)h(n)=∑每个棋子与目标节点相差的步数(1分)算符集合F={U,D,L,R}(2分)U：空格上移D：空格下移L：空格左移R：空格右移(2分)(2分)(2分)(2分)ISAISAISAISAsrmstudentreadmasterpieaceobjectsubjectgGS81324765S:12384765g:(2分)gRDR75DRU7UDLDLU581324765S:8132476581243765813245765778132476581326475832147651382476581324765813724657138247651238476513824765557(6分)