2017-2018人工智能试卷与答案

北京工业大学2017—2018学年第1学期《人工智能》考试试卷1北京工业大学2017——2018学年第1学期《人工智能导论》考试试卷A答案考试说明：开卷考试,考试时间95分钟承诺：本人已学习了《北京工业大学考场规则》和《北京工业大学学生违纪处分条例》，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。若有违反，愿接受相应的处分。承诺人：学号：班号：。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。注：本试卷共六大题，共六页，满分100分。卷面成绩汇总表（阅卷教师填）题号一二三四五六总成绩满分16201081010得分一、多项选择题1、产生式系统的组成部分包括（BCD）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=~QR，C3=~R，则归结的结果是（D）A）RB）QC）~RD)都不是，正确结果为（空）5、设有机器人走迷宫问题，其入口坐标为(x0,y0)，出口坐标为(xt,yt)，当前机器人位置为(x,y)，若定义，当从入口到出口存在通路时，用A算法求解该问题，定能找到从入口到出口的最佳路径。（A）A对B错6、置换的乘法满足交换律，即=（B）。A）对B）错7、遗传算法评价的常用方法有（ABC）A）当前最好法B）在线比较法C）离线比较法D)都不是8、遗传算法中的“染色体”是指（A）A）解的编码B）编码的元素C）问题的一个解D)都不是得分北京工业大学2017—2018学年第1学期《人工智能》考试试卷2二、填空题（20分）1.在一般图搜索中，当目标出现的时候，算法可能仍然不结束，原因是（目标没有排在open表的第一个）。2.在回溯算法中，有（4）个回溯点，分别是：（非法状态，无规则可用，达到规定深度，有环路出现）。3.满足（h(n)≤h*(n)）条件的A算法称为是A*算法。4.在A*算法中为避免出现多次扩展同一个节点的情况，有两种解决的途径，分别是：（1）对h加以限制；2）对算法进行改进）。5.极小极大算法是博弈树搜索的基本方法，目前常用的α-β剪枝搜索方法也是从其发展而来。请从结果和效率两个方面对α-β剪枝法与极小极大算法进行比较。（二者结果相同，α-β剪枝法的效率更高）。6.子句是如下形式(L1∨L2⋯∨Ln,每个Li是文字(原子或原子的非))的合式公式.7.任一合式公式都可以转化成子句集，这种转化不是（等价的），但在不可满足性上是等价的，即原公式是（矛盾的），转化后的子句（是矛盾的）。8.E为P(x,y,f(a),g(c)),θ={b/x,f(x)/y,c/z},则Eθ=(P(b,f(x),f(a),g(c)))。9.S={p(x),p(y)},则mgu=（{x/y}或者{y/x}）。10.∃yP(x,y)的skolem标准型是(P(x,a)),∀x∃yP(x,y)的skolem标准型是（∀xP(x,f(x))）。三、简答题（20分）1）（5分）图灵测试的目的是什么？假设你是图灵测试中的询问者，请想出2个提问，用于判断它们中哪一个是人，哪一个是机器，并说明判断的依据？图灵测试的目的是测试机器是否具有图灵测试意义上的智能问题1）请计算2的15次方等于多少？2）多次重复问同一个问题，例如：你今天吃的是什么？机器与人相比具有快速的计算能力，但是常识知识和情绪能力较弱。2）（6分）将公式∀∃)(∃x)(∀))))化为子句集。答案为：子句集为：{))，)))}3）（5分）解释P（f(x,A),A）和P（f(y.f(y,A)),A）为什么不能合一。答案为：因为会出现变量出现在t中的情况。得分得分北京工业大学2017—2018学年第1学期《人工智能》考试试卷34）（5分）遗传算法中，应用“交配运算”可基于已有的两个染色体生成新的染色体。假定交配运算的规则为“基于位置的交配法”，写出以下两个父代染色体生成的两个子代染色体“子代1”和“子代2”。父代1：10687594123父代2：82641531097所选位置：****解：子代1：85691421037父代2：26845109173四、（10分）用回溯策略求解下图的二阶梵塔问题,画出搜索过程的状态变化示意图.规则：先搬1柱的盘，放的顺序是先2柱后3柱；再搬2柱盘，放的顺序是先3柱后1柱；最后搬3柱的盘，放的顺序是先1柱后2柱。规则顺序定义如下：1—2，1—3，2—3，2—1，3—1,3—2解：AB123AB123得分北京工业大学2017—2018学年第1学期《人工智能》考试试卷4五、（10分）下图为一字棋博弈树的部分MAX/MIN搜索示意图，叶节点下面的数字表示该棋局目前状态的评价值，请根据这些值倒推其它节点的静态估值，并使用α-β剪枝规则完成α-β剪枝，求当前棋局MAX结点A的最好走步。要求：1）在图中标明各层节点的α、β估值，用X标明剪枝，并具体说明是什么剪枝。2）标明MAX结点A的最好走步。六、（12分）假设：所有不贫穷且聪明的人都快乐。那些看书的人是聪明的。李明能看书且不贫穷。快乐的人过着激动人心的生活。求证：李明过着激动人心的生活。给定谓词：某人x贫穷，Poor(x);某人x聪明，Smart(x);某人x快乐，Happy(x);某人x读书，Read(x);某人x过着激动人心的生活，Exciting(x);证明：R1：所有不贫穷且聪明的人都快乐：(()()())xPoorxSmartxHappyxR2：那些看书的人是聪明的：(()())xreadxSmartxR3：李明能看书且不贫穷：()()readLiPoorLiR4：快乐的人过着激动人心的生活：(()())xHappyxExcitingx结论李明过着激动人心的生活的否定：()ExcitingLi将上述谓词公式转化为子句集并进行归结如下：由R1可得子句：①()()()PoorxSmartxHappyx由R2可得子句：②()()readySmarty由R3可得子句：③()readLi④()PoorLi得分得分最佳走步Xα剪枝Xα剪枝Xβ剪枝北京工业大学2017—2018学年第1学期《人工智能》考试试卷5由R4可得子句：⑤()()HappyzExcitingz有结论的否定可得子句：⑥()ExcitingLi根据以上6条子句，归结如下：⑦()HappyLi⑤⑥Li/z⑧()()PoorLiSmartLi⑦①Li/x⑨()SmartLi⑧④⑩()readLi⑨②Li/y⑪⑩③由上可得原命题成立。七、（12分）旅行商问题：一个推销员要到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*算法的条件。解：状态S:从城市B出发访问过的城市序列,初始状态S0:B,终状态：B****Bf(n)=g(n)+h(n).g(n)为已走过的路径长度，在状态n时，还需要行走的城市数为5-n（包括最后回到城市B）,每次行程的最小花费为5，因此令h(n)=(5-n)*5.明显的，h(n)小于等于h(n)*得分北京工业大学2017—2018学年第1学期《人工智能》考试试卷6(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