补考试卷B答案--2016人工智能考试.doc

(word完整版)补考试卷B答案-2015-2016人工智能考试北京工业大学2015-2016学年第 1 学期人工智能导论 考试试卷B考试说明: 开卷考试， 考试时间95分钟 承诺：本人已学习了北京工业大学考场规则和北京工业大学学生违纪处分条例，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。若有违反，愿接受相应的处分。承诺人： 学号： 班号： 。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。.。注：本试卷共 大题，共 页，满分100分。卷 面 成 绩 汇 总 表（阅卷教师填写）题号一二三四五六七八九十总成绩满分162415151515得分得 分一、选择题 (16分）1、产生式系统的组成部分不包括（ A ）A。）状态空间 B）综合数据库 C）规则集 D)控制策略2、反演归结法在证明定理时，若当前归结式是（ C ）时，则定理得证。A）永真式B）合取式C)空子句C）析取式3、将公式$x yp(x,y)化为子句，以下（ C ）是正确的. A） p(z，y） B） p（f（x),x） C） p(x,f(x） D） p(A，y）4、若C1=Q，C2=QR,C3=R，则归结的结果是（ D ）A） R B） Q C） RD） 都不是，正确结果为（ 空 )5、置换的乘法满足交换律,即ab=ba ( B ）。 A） 对 B） 错 6、与极小极大法相比来,剪枝法增大了找不到最佳走步的危险性,但其效率较高。(B ） A 对 B 错7、设有机器人走迷宫问题,其入口坐标为（x0, y0)，出口坐标为（xt, yt），当前机器人位置为（x， y），若定义， 当从入口到出口存在通路时，用A算法求解该问题，定能找到从入口到出口的最佳路径。（ A ） A 对 B 错 8、遗传算法评价的常用方法有( ABC ）A）当前最好法 B）在线比较法 C） 离线比较法D) 都不是 得 分二、简答题（24分）1、 遗传算法中，应用“交配运算可基于已有的两个染色体生成新的染色体.假定交配运算的规则为“基于位置的交配法”,写出以下两个父代染色体生成的两个子代染色体“子代1”和“子代2。父代1:106875941 2 3父代2: 826415310 9 7所选位置: * 解： 子代1： 10 2681539 4 7子代2： 8 62 1 5 10 49 7 32、设子句集S=P（a)，Q（b)R(f（X）)，请写出S的H域及原子集。解： U0=a,b， U1=a，b,f(a)，f(b)，U2=a,b，f（a）,f（b)，f(f(a)）,f(f(b) Us=a,b,f(a）,f（b），f(f(a)）,f(f(b）), 原子集为：BS=p（a），q(a），r（a）,p（b)，q（b）,r（b），p（f（a)），q(f(a)），r(f(a） 3、求子句集S=p（a,x，f（g(y）),p(z，h(z,u）,f(u)的最一般合一mgu.解: 1） k=0， Sk=S0=S, sk=s0=e, 明显的， S0=S不是单元素集. 2) 求得其差异集D0=a,z，其中z为变量，a为项，且z不在a中出现。 令k=k+1，有 s1= s0 a/z= e a/z= a/z S1=S0a/z=p（a，x,f（g（y)）),p（z，h（z,u),f(u)）a/z =p（a，x，f（g（y）)）, p（a,h(a，u），f(u) S1不是单元素 求得其差异集D1=x，h(a,u）,其中x为变量，h（a,u）为项，且x不在h（a，u）中出现. 令k=k+1,有 s2= s1h（a,u)/x=a/zh（a,u)/x = a/z，h(a，u)/x S2=S1h(a，u)/x=p(a，x，f(g（y）,p（a，h（a,u）,f（u）h（a，u）/x =p（a，h(a，u),f(g（y)），p（a,h（a，u）,f(u）) S2不是单元素集. 求得其差异集D2=g(y），u,其中u为变量， g(y）为项,且u不在g(y）中出现. 令k=k+1，有 s3=s2g（y)/u=a/z，h(a,u)/xg（y）/u =a/z，h(a，g(y)/x S3=S2g(y）/u =p(a,h(a，u）,f（g（y)，p（a,h(a，u）,f(u)g(y)/u =p(a，h（a，g（y)）,f（g（y),p（a，h（a,g（y)，f(g（y） 明显的， S3是单元素集.3） Mgu = s3=a/z，h（a,g(y）)/x4、把命题:果树是树，且会结果，用一个语义网络表示出来： 解： 结果实果树植物树 三、计算题（15分) 将下列公式化为子句集： 1） (x）（y)(P(x， y）Q（x， y)2） 解：1） 由于（x)（y）(P(x， y）Q(x， y）)已经是Skolem标准型，且P（x， y）Q(x, y） 已经是合取范式,所以可直接消去全称量词、合取词，得 P（x， y)， Q（x， y） 再进行变元换名得子句集： S= P(x， y）, Q(u, v） 2) 去掉 3） 内移“” 4）变量换名 5) 消去存在量词， 省略全称量词 子句集为: 得 分四、（15分）下图为一字棋博弈树的部分MAX/MIN搜索示意图，叶节点下面的数字表示该棋局目前状态的评价值,请根据这些值倒推其它节点的静态估值，并使用-剪枝规则完成剪枝，求当前棋局MAX结点A的最好走步，. 要求： 1）在图中标明各层节点的、估值范围，用标明剪枝，并具体说明是什么剪枝。2)标明MAX结点A的最好走步。 得 分五(15分）已知：1。 任何上大学（college)并中了彩票（lottery)的人是快乐的；2。 任何肯学习或幸运的人可以上大学；3. Alice不学习但很幸运；4。 任何人只要是幸运的就能中彩。求证:Alice是快乐的。 给定谓词：某人x上大学,College(x）; 某人x中彩票,Lottery（x）； 某人x快乐，Happy(x）; 某人x学习，Study(x）; 某人x幸运，lucky(x); 证明： 表示为合式公式为： R1： （x）（College（x） ）Lottery(x)Happy（x) R2: (x）(Study (x） Lucky(x) College(x） R3: （Study （Alice） Lucky（Alice) R4 （x)(Lukky(x) Lottery(x）) 求证：Happy(Alice） 求证的非为： Happy(Alice） 将上述谓词公式转化为子句集并进行归结如下：1） College(x1） Lottery(x1) Happy(x1）2） Study （x2) College（x2）3） Lucky （x2） College（x2)4） Study （Alice）5） Lucky(Alice) 6） Lucky(x3) Lottery(x3)7） Happy（Alice)College(x1)Lottery（x1） Happy(x1)Happy（Alice) College（x1）Lottery（x1)Lucky(x2) College(x2）Lottery(x1）Lucky(x1)Lucky（Alice）Lucky（x3) Lottery（x3） Lottery（x1） Lucky（Alice） Lucky(x3) nil得 分六（15分）旅行商问题：一个推销员要到5个城市办理业务,城市间的里程数已知，如图所示：AB|=7；|AC=6;AD|=10；AE=13;BC|=7；|BD|=10；BE=10；|CD=5(最短)；|CE=9;DE=6。从A城市出发,遍历所有城市后（每个城市只允许访问一次）回到城市A，设计A 算法求取一条最短的旅行路径，其中状态用已遍历城市名字组成的字符串表示。要求：1） 定义状态评价函数f（n）=g(n）+h(n)，其中g(n)表示当前状态下已走过的距离的总和;h(n)=5m其中m是表示当前状态的字符串的长度。画出搜索的状态空间图并标明评价函数值.（10分）2） 判断本题定义的启发函数h(n）是否满足A 算法的条件.（5分）解：状态S： 从城市A出发访问过的城市序列, 初始状态S0：A, 终状态：A*A f(n)=g（n）+h（n)。 g(n）为已走过的路径长度，在状态n时，还需要行走的城市数为 5n（包括最后回到城市B），每次行程的最小花费为5，因此令h(n)= （5-n）5. 明显的，h(n)小于等于h(n）( A )(AB) 2727(AC)26(AD)30(AC)33(ACB)28(ACD)26(ACE)29(ACDB)31(ACDE)27(ACDEB) 22( ACDEBA) 36751010769108107起始目标第 6 页 共 6 页