北语 18春《人工智能导论》

1、18春人工智能导论作业1一、单选题(每题4分，共10道小题，总分值40分)在公式(v)(Q(v，u)A (R (v)VP (v)AS (u, v)中，Q (v, u)是一个主合 取元，是另一个主合取元。(R (v)VP (v)AS (u, v)S (u, v)(R (v)VP (v)R (v)答案：A基于规则的正向演绎系统的的子集形式：_。子句的合取式(合取范式)子句的析取式(析取范式)文字的析取式文字的合取式答案：A将结论的否定所对应的子句s在归结树中的位置，用重言式ss代替s,并参予归结树中 所有的置换，所得到的树称为_。归结树证明树修改证明树置换答案：C基于规则的逆向演绎系统的初始综合数

2、据库是_。事实表达式的与或树目标公式的与或树与或树证明树答案：B八数码问题取不同启发函数，应用A*算法求得最佳解时所扩展和生成的节点数最少的是:。h(n)Wh*(n)h(n)=0h(n)=W(n)h(n)=P(n)答案：D基于规则的正向演绎系统的目标公式为_。文字析取形任意形式子句的合取式文字合取形下面哪个不是图搜索方式的特点_。图中的每一个节点代表问题的状态，节点间的弧代表应用的规则。就是从隐含图中搜索出含有解路径的子图来。对每一个状态可应用的所有规则都要去试，并把结果记录下来。沿着单独的一条路向下延伸搜索下去。如果一个产生式系统可以分解为几个子问题，当子问题得以求解时，则原始问题被求解。这

3、样的产生式系统称为_。双向产生式系统可交换的产生式系统可分解的产生式系统正向产生式系统利用评价函数f (n)=g (n)+h (n)来排列OPEN表节点顺序的图搜索算法称为_。深度优先算法宽度优先算法盲搜索算法A算法问题的规模是指。问题全状态空间搜索空间最优解解路径二、多选题(每题4分，共5道小题，总分值20分)下面关于能解节点(SOLVED)的定义正确的是。终节点是能解节点若非终节点有或子节点时，当且仅当其子节点至少有一能解，该非终节点才能解若非终节点有与子节点时，当且仅当其子节点均能解，该非终节点才能解。叶节点是能解节点答案：ABC用归结法证明定理的过程_。将已知条件化作子句集将结论的否定

4、化作子句集从所有子句集中选取两个可归结的子句进行归结重复以上过程，直到出现空子句NIL为止下列说法正确的是：_。不可撤回方式相当于沿着单独的一条路向下延伸搜索下去。回溯方式则不保留完整的搜索树结构，只记住当前工作的一条路径，回溯就是对这条路 径进行修正。图搜索方式则记下完整的搜索树。对一个要求解的具体问题，有可能用不同的方式都能求得解，至于选用哪种方式更适宜， 往往还需要根据其他一些实际的要求考虑决定。基于规则的正向演绎系统对事实、规则和目标的化简过程：_。用Skolem函数消去事实表达式中的存在量词，化简的公式受全称量词的约束。（*）对规则的处理同（*）式。用Skolem函数（对偶形）消去目

5、标公式中的全称量词，化简的公式受存在量词约束。用Skolem函数消去事实表达式中的存在量词，化简的公式受全称量词的约束。用产生式系统求解某一个问题时，如果按照规则使用的方式或者说按推理方向来划分的 话，产生式系统可分为_。单向正向逆向双向 三、判断题（每题4分，共10道小题，总分值40分）对有限图，如果从初始节点，到目标节点t有路径存在，则算法A 一定成功结束。 答案：正确任何一个合适公式，都可以等价地转化为一个前束范式。LISP程序设计，实际上就是定义函数。在基本函数和已经定义的函数的基础上，定义更多 的函数，实现所需要的功能。合一复合是可结合、可交换的。这是一个很好的性质，说明在用基于规则

6、的正向演绎方法 求解问题时，与使用规则的次序无关。PROLOG中的表与LISP中的表，在概念上是一致的，且表示形式也完全相同。同A算法类似，若s-N集存在解图，当h （n）Wh* （n）且h （n）满足单调限制条件时， 则AO*一定能找到最佳解图，即AO*具有可采纳性。图搜索策略的一个特点就是只保留了从初始状态到当前状态的一条路径，从而节省了存储 空间。归结方法的特点是简单，易于程序实现。无论是正向系统还是逆向系统，其目标都是从众多的解图中，找一个一致解图。简单的BACKTRACK过程设置四个以上回溯点，可用于求解N 一皇后这类性质的问题。18春人工智能导论作业2一、单选题(每题4分，共10道

7、小题，总分值40分)对于五城市旅行商问题，求从A出发经B、C、D、E再回到A的最短路径。如果用s表示 当前状态，L(s)表示已经走过的城市数，Goto(x)表示走向城市x，则其规则可以表示为：1， IF L(s)=5 THEN Goto(A)； 2, IF L(s)5 THEN Goto(B)； 3, IF L(s)5 THEN Goto(C)； 4, IF L(s)5 THEN Goto(D)； 5，IF L(s)5 THEN Goto(E)。若 s=(AXXXX)，则被触发规则为_。 TOC o 1-5 h z (1)(2)(3)或(5)基于规则的正向演绎系统的子句形式：_。子句的合取式(

8、合取范式)子句的析取式(析取范式)文字的析取式文字的合取式我国是从年才开始人工智能课题的研究，主要在定理证明、汉语自然语言理解、机器人 及专家系统方面设立课题，并取得一些初步成果。 TOC o 1-5 h z 1978196019501959对于子句C1VL1和C2VL2，其中L1、L2是单文字。如果L1与L2可合一，且s是其合 一者，则(C1VC2)s是其式。这一过程称作_。置换置换合一合一归结归结递归递归一般地说对任意一个图，当，到目标节点有一条路径存在时，如果搜索算法总是在找到一 条从s到目标节点的最佳路径上结束，则称该搜索算法具有_。可采纳性包容性唯一性两面性_是利用问题给出的局部知识

9、来决定如何选取规则，接着再根据新状态继续选取规则，搜 索过程一直进行下去，不必考虑撤回用过的规则。不可撤回方式试探性方式回溯方式D.图搜索方式八数码游戏的初始状态为283450716,而结束状态为123456780。问初始状态的不在位 的将牌数是_。 TOC o 1-5 h z 2345回溯策略可以有多种实现的方法，其中用实现也许是最简单的方法了。枚举法递归法反证法迭代法_是根据给定的文法重写规则，判断一个字串是否是符合该重写规则的句子。八数码问题旅行商问题句法分析问题传教士和野人问题基于规则的正向演绎系统的初始综合数据库是_。事实表达式的与或树目标公式的与或树与或树证明树二、多选题(每题4分

10、，共5道小题，总分值20分)基于归结法的问题提取回答的过程：_。先用归结法证明结论成立，并画出归结树找出结论的否定所对应的子句s在归结树中的位置，用重言式s s代替s,并参予归结树 中所有的置换，得到修改证明树在原来归结树中空子句所在位置得到一个子句，该子句即为问题的回答。重复以上过程，直到出现空子句NIL为止。对于五城市旅行商问题，求从A出发经B、C、D、E再回到A的最短路径。如果用s表示 当前状态，L(s)表示已经走过的城市数，Goto(x)表示走向城市x，则其规则可以表示为：1， IF L(s)=5 THEN Goto(A)； 2, IF L(s)5 THEN Goto(B)； 3, I

11、F L(s)5 THEN Goto(C)； 4, IF L(s)5 THEN Goto(D)； 5, IF L(s) 行动前提- 结论ifthen论点- 论据改进A*算法的理论基础是_。要保持A*算法的可采纳性。不能增加过多的计算工作量。OPEN表上任一具有f（n） f*（s）的节点n定会被扩展。A*选作扩展的任一节点，定有f（n）Wf*（s）。AO*算法可划分成哪两个操作阶段:_。第一阶段是4-6步，完成自顶向下的图生成操作，先通过有标记的连接符，找到目前为 止最好的一个局部解图，然后对其中一个非终节点进行扩展，并对其后继节点赋估计耗散值 和加能解标记。第二阶段是7-12步，完成自下向上的耗

12、散值修正计算、连接符（即指针）的标记以及节 点的能解标记。第一阶段1-3步，完成初始化。第二阶段，扩展节点控制策略中，试探性方式可划分为哪两大类：_。不可撤回方式试探性方式回溯方式图搜索方式对八数码游戏，回溯应发生在以下几种情况：_。新生成的状态在通向初始状态的路径上已出现过从初始状态开始，应用的规则数目达到所规定的数目之后还未找到目标状态对当前状态，再没有可应用的规则。沿着单独的一条路向下延伸搜索下去三、判断题（每题4分，共10道小题，总分值40分）双向产生式系统则是正向推理和逆向推理同时使用的产生式系统。归结法中，可以通过修改证明树的方法得到问题的解答。基于规则的正向演绎系统，就是不断的对

13、与或图施以规则变换，直到找到一个解图，该解 图中的所有叶节点全部都与目标公式中的文字匹配为止。在回溯策略中，可以通过引入一些与问题有关的信息来加快搜索到解的速度，如皇后问题。在过程AO*中，第一步建立一个搜索图G，开始时图G只包括s，耗散值估计为h （s）， 若s是终节点，则标记上不能解。在语言学中，决定任意一个符号序列是不是一个句子的问题，是一个句法分析问题，我们 可以用产生式系统来分析这个问题。PROLOG属于逻辑程序设计语言，其理论基础是一阶谓词逻辑。归结方法将所有的谓词公式均化简为子句，致使很多隐含在原来的谓词公式中的、对推理 有利的信息得不到充分的利用。PROLOG系统的基本求解策略

14、是：从上到下，从左到右，深度优先。正是由于PROLOG语言自己决定如何做，使得求解问题的效率比较低，严重影响了它的 使用。18春人工智能导论作业_4一、单选题（每题4分，共10道小题，总分值40分）在AO*算法中，已知h (n)函数对一个与或图中各节点的假想估值如下：h (n0)=3, h (n1)=2, h (n2)=4, h (n3)=4, h (n4)=1, h (n5)=1, h (n6)=2, h (n7)=h (n8)=0 (目标节点)。此外假设k-连接符的耗散值为k。开始时，初始节点n0, n0被 扩展，生成出节点n1、n4和n5, 一个1连接符指向n1, 一个2连接符指向n4和

15、n5。 这两个连接符之间是或的关系。问指针将指向_。n0的1 一连接符n0的2 一连接符n4n5对于五城市旅行商问题，求从A出发经B、C、D、E再回到A的最短路径。如果用s表示 当前状态，L(s)表示已经走过的城市数，Goto(x)表示走向城市x，则其规则可以表示为：1， IF L(s)=5 THEN Goto(A)； 2, IF L(s)5 THEN Goto(B)； 3, IF L(s)5 THEN Goto(C)； 4, IF L(s)5 THEN Goto(D)； 5, IF L(s)5 THEN Goto(E)。若(A)为初始状态，则目标状态为_。(AA)(AxxxxA)(AxxA)

16、(Axxxx)用产生式系统来描述一个具体问题。设字符转换问题规则如下：1. AAB-C； 2. AACD；BAC-G； 4. BAEfF； 5. D-E；已知：A, B求：F。设综合数据库用集合x表示，其中 x为字符。采用顺序排队的控制策略。初始状态A, B。为了得到F,最后执行的被触发规 则是：。5.IF D THEN E2.IF AAC THEN D3.IF BAC THEN G4.IF BAE THEN F用产生式系统来描述一个具体问题。设字符转换问题规则如下：1. AABfC； 2. AAC-。；3. BAC-G； 4. BAEfF； 5. D-E；已知：A, B求：F。设综合数据库用

17、集合x表示，其中 x为字符。采用顺序排队的控制策略。初始状态A，B。下列结束条件正确的是：_。FEx,当目标F在综合数据库中出现时，则F被求得。FEx,当目标F在综合数据库中出现时，则F 一定不被求得。F不包含于x,当目标F不在综合数据库中出现时，则F被求得。F不包含于x，当目标F不在综合数据库中出现时，则F 一定被求得。用产生式系统来描述一个具体问题。设字符转换问题规则如下：1. AAB-C； 2. AAC-D；3. BAC-G； 4. BAE-F； 5. D-E；已知：A, B求：F。设综合数据库用集合x表示，其中 x为字符。采用顺序排队的控制策略。初始状态A, B。根据已经给出的字符的转

18、换规则， 用IFTHEN的形式表示，其中错误的是：_。1.IF AAB THEN C2.IF AAC THEN D3.IF BAC THEN G4.IF BAE THEN F5.IF E THEN D在进行a -p剪枝时，比较都是在间进行的。极大节点和极大节点极小节点和极小节点极小节点和极大节点以上全选在年，人工智能作为一门学科正式诞生于美国。 TOC o 1-5 h z 1950195419561960在句法分析问题中，为了实现目标条件，最后执行的文法重写规则是_。P DNPPPDNP PPDNPV DNPVPDNP VPS如何求解一个用产生式系统描述的问题，以及如何寻找具有最小耗散的解，属

19、于问题。综合数据库规则集合目标状态搜索策略用产生式系统来描述一个具体问题。设字符转换问题规则如下：1. AABC； 2. AACD；3. BACG； 4. BAEF； 5. D E；已知：A，B求：F。设综合数据库用集合x表示，其中 x为字符。采用顺序排队的控制策略。初始状态A，B。当执行被触发规则(1 )后，综合数据 库中字符为_。ABABCABCDABCDG二、多选题(每题4分，共5道小题，总分值20分)基于规则的逆向演绎系统的使用条件：_。事实表达式是文字合取形式事实表达式是任意形式规则形式为：WL或WL1AL2其中L为单文字，W为任意形式。目标公式是任意形式基于规则的正向演绎系统的使用条件：_。A. 事实表达式是任意形式规则形式为：L-W或L1VL2-W，其中L为单文字，W为任意形式。目标公式为文字析取形。目标公式是任意形式。改进A*算法的时候，要注意哪两点：_。要保持A*算法的可采纳性去除可采纳性不能增加过多的计算工作量。以增加工作量为代价。下列关于启发式搜索的说法正确的是：_。就是利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。一般来说，启发信息强，可