2015-2016北工大人工智能试卷及答案-共6页.pdf

北京工业大学 20152016 学年第 1 学期 人工智能 考试试卷1 北京工业大学 20152016 学年第 1 学期 人工智能导论 考试试卷 A考考试说试说明：明：开卷考试,考试时间 95 分钟 承承诺诺：本人已学习了北京工业大学考场规则和北京工业大学学生违纪处分条例，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。若有违反，愿接受相应的处分。承诺人：学号：班号：。注：本试卷共 六 大题，共 八 页，满分 100 分。卷 面 成 绩 汇 总 表（阅卷教师填）题题号号一二三四五六总总成成绩绩满满分分362010101014得分得分 得分 一、填空题（36 分）1.产生式系统的组成部分有（数据库，规则库，推理机 ）。2.在一般图搜索中，当目标出现的时候，算法可能仍然不结束，原因是（目标不在 open 表的第一个 ）。3.在回溯算法中，有（4 ）个回溯点，分别是：（非法状态，无规则可用，达到规定深度，有环路出现 ）。4.满足（h(n)h*(n)）条件的 A 算法称为是 A*算法。5.在 A*算法中为避免出现多次扩展同一个节点的情况，有两种解决的途径，分别是：（1）对h 加以限制；2）对算法进行改进 ）。6.极小极大算法是博弈树搜索的基本方法，目前常用的-剪枝搜索方法也是从其发展而来。请从结果和效率两个方面对-剪枝法与极小极大算法进行比较。（二者结果相同，-剪枝法的效率更高 ）。7.子句是如下形式(L1 L2 Ln,每个 Li是文字(原子或原子的非)的合式公式.8.归结法在证明定理时，若当前归结式是(空 )时，则定理得证。9.任一合式公式都可以转化成子句集，这种转化不是（等价的），但在不可满足性上是等价的，即原公式是（矛盾的 ），转化后的子句（是矛盾的 ）。10.E 为 P(x,y,f(a),g(c),=b/x,f(x)/y,c/z,则 E=(P(b,f(x),f(a),g(c),)。11.S=p(x),p(y),则 mgu=（x/y 或者 y/x ）。北京工业大学 20152016 学年第 1 学期 人工智能 考试试卷212.若 C1=PQ，C2=QR，C3=P，则归结的结果是（R ）。13.yP(x,y)的 skolem 标准型是(P(x,a),xyP(x,y)的 skolem 标准型是（xP(x,f(x)）。14.语义基元是（由有向图表示的三元组（结点 1，弧，结点 2）).15.请写出贝叶斯定理（设事件 A1，A2，An两两互不相交（即 ij，AiAj=）；且 P(Ai)0，i=1，2，n，则对任何事件 B，有下式成立 niABPAPABPAPBAPnjjjiii,.2.1)|()()|()()|(1L16.遗传算法中的“染色体”指（解的编码 ）。17.遗传算法评价的常用方法有（1）当前最好法，（2）在线比较法，（3）离线比较法 ）。18.邻域的定义是（设 D 是问题的定义域，若存在一个映射N，使得：DSNDSN2)(:则称N(S)为S的邻域）。得分 二、二、简答题（简答题（2020 分）分）1）（3 3 分）遗传算法中，应用“交配运算”可基于已有的两个染色体生成新的染色体。假定交配运算的规则为“基于次序的交配法”，写出以下两个父代染色体生成的两个子代染色体“子代 1”和“子代 2”。父代 1：106875941 2 3父代 2：826415310 9 7所选位置：*解：子代 1 1：8 82 26 64 45 51 13 31010 9 9 7 7父代 2 2：6 61 18 810105 59 94 47 7 2 2 3 3 2）（4 4 分）设子句集 S=Q(x,y),P(f(x)，请写出 S 的 H 域及原子集 A。解：U0=a,，U1=a,f(a)Us=a,f(a),f(f(a),原子集 A=P(a),Q(a,a),P(f(a),Q(a,f(a),Q(f(a),a),Q(f(a),f(a),3）（4 4 分）求子句集 S=P(b,y,f(g(w),P(z,h(z,u),f(u)的最一般合一 mgu。解:1)k=0,Sk=S0=S,k=0=,明显的,S0=S 不是单元素集.2)求得其差异集 D0=b,z,其中 z 为变量,b 为项,且 z 不在 a 中出现.另 k=k+1,有 1=0 b/z=b/z=b/z 北京工业大学 20152016 学年第 1 学期 人工智能 考试试卷3 S1=S0b/z=p(b,y,f(g(w),p(z,h(z,u),f(u)b/z=p(b,y,f(g(w),p(b,h(b,u),f(u)S1不是单元素集.求得 S1的差异集 D1=y,h(b,u),其中 x 为变量,h(b,u)为项,且 y 不在 h(b,u)中出现.另 k=k+1,有 2=1h(b,u)/y=b/zh(b,u)/y=b/z,h(a,u)/y S2=S1 h(a,u)/y=p(b,y,f(g(w),p(b,h(b,u),f(u)h(b,u)/y =p(b,h(b,u),f(g(w),p(b,h(b,u),f(u)S2不是单元素集.求得 S2差异集 D2=g(w),u,其中 u 为变量,g(w)为项,且 u 不在 g(w)中出现.另 k=k+1,有 3=2g(w)/u=b/z,h(b,u)/yg(w)/u=b/z,h(b,g(w)/y S3=S2g(w)/u=p(b,h(b,u),f(g(w),p(b,h(b,u),f(u)g(w)/u =p(b,h(b,g(w),f(g(w),p(b,h(b,g(w),f(g(w)明显的,S3是单元素集.3)Mgu=3=b/z,h(b,g(w)/y4）（6 6 分）将公式(x)P(x)(x)P(x)化为子句集 ()(,)()(,)解：1）消去“”(x)P(x)(x)P(x)()(,)()(,)2）内移“”(x)P(x)P(x)()(,)()(,)3）变量换名 (u)P(u)P(x)()(,)()(,)4）消去存在量词 P(a)P(x)()(,)()(),)5）将公式化为前束范式 P(a)P(x)()(,)()(),)6）化为合取范式 P(a)P(x)()(,)(),)()(),)省略全称量词后,子句集为：P(a),P(x)()(,),(),),()(),)5）（3 3 分）图灵测试的目的是什么？假设你是图灵测试中的询问者，请想出 2 个提问，用于判断它们中哪一个是人，哪一个是机器，并说明判断的依据？图灵测试的目的是测试机器是否具有图灵测试意义上的智能问题 1）请计算 2 的 15 次方等于多少？2）多次重复问同一个问题，例如：你今天吃的是什么？机器与人相比具有快速的计算能力，但是常识知识和情绪能力较弱。北京工业大学 20152016 学年第 1 学期 人工智能 考试试卷4三、（10 分）桌上有 5 个钱币，A、B 两人可以从 5 个钱币堆中轮流拿走 1 个、2 个或 3 个钱币，拣起最后一个钱币者算输。试通过博弈证明先拿钱币的人必输。解：(5,MAX)，)(4，MIN)起始(2，MIN)(3，MIN)(3，MAX)(2，MAX)(1，MAX)(2，MIN)(1，MIN)(1，MAX)可以看到先拿钱币的人必输。四、（10 分）下图为一字棋博弈树的部分 MAX/MIN 搜索示意图，叶节点下面的数字表示该棋局目前状态的评价值，请根据这些值倒推其它节点的静态估值，并使用-剪枝规则完成-剪枝，求当前棋局 MAX 结点 A 的最好走步。要求：1）在图中标明各层节点的 、估值，用 X 标明剪枝，并具体说明是什么剪枝。2）标明MAX 结点 A 的最好走步。最佳走步35 X 剪枝 X 剪枝0=22 X 剪枝 北京工业大学 20152016 学年第 1 学期 人工智能 考试试卷5五 （10 分）假设：所有不贫穷且聪明的人都快乐。那些看书的人是聪明的。李明能看书且不贫穷。快乐的人过着激动人心的生活。求证：李明过着激动人心的生活。给定谓词：某人 x 贫穷，Poor(x);某人 x 聪明，Smart(x);某人 x 快乐，Happy(x);某人 x 读书，Read(x);某人 x 过着激动人心的生活，Exciting(x);证明：R1：所有不贫穷且聪明的人都快乐：()()()xPoor xSmart xHappy x:R2：那些看书的人是聪明的：()()x read xSmart xR3：李明能看书且不贫穷：()()read LiPoor Li:R4：快乐的人过着激动人心的生活：()()x Happy xExciting x结论李明过着激动人心的生活的否定：()Exciting Li:将上述谓词公式转化为子句集并进行归结如下：由 R1 可得子句：()()()Poor xSmart xHappy x:由 R2 可得子句：()()read ySmart y:由 R3 可得子句：()read Li()Poor Li:由 R4 可得子句：()()Happy zExciting z:有结论的否定可得子句：()Exciting Li:根据以上 6 条子句，归结如下：Li/z()Happy Li:Li/x()()Poor LiSmart Li:()Smart Li:Li/y()read Li:W由上可得原命题成立。六（14 分）旅行商问题：一个推销员要到 5 个城市办理业务，城市间的里程数已知，如图所示：|AB|=7；|AC|=6；|AD|=10；|AE|=13；|BC|=7；|BD|=10；|BE|=10；|CD|=5；|CE|=9；|DE|=6。从B 城市出发，遍历所有城市后（每个城市只允许访问一次）回到城市 B，设计 A*算法求取一条最短的旅行路径，其中状态用已遍历城市名字组成的字符串表示。要求：定义状态评价函数 f(n)=g(n)+h(n)，其中 g(n)表示当前状态下已走过的距离的总和；（1）画出搜索的状态空间图并标明评价函数值。（2）判断本题定义的启发函数 h(n)是否满足 A*算法的条件。1，MIN)1，MIN)1，MIN)1，MIN)1，MIN)1，MIN)1，MIN)1，MIN)1，MIN)1，MIN)1，MIN)1，MIN)北京工业大学 20152016 学年第 1 学期 人工智能 考试试卷6解：状态 S:从城市 B 出发访问过的城市序列,初始状态 S0:B,终状态：B*B f(n)=g(n)+h(n).g(n)为已走过的路径长度，在状态 n 时，还需要行走的城市数为 5-n（包括最后回到城市B）,每次行程的最小花费为 5，因此令 h(n)=(5-n)*5.明显的，h(n)小于等于 h(n)*(B)(BA)27(BC)27(BD)30(BE)30(BAC)28(BAD)32(BAE)35(BCDA)32(BCDE)28(BCDEA)36起始目标(BCD)27(BCE)31(BACD)28(BACE)32(BACDE)29(BACDEB)34