2016-人工智能复习题目.doc

2016 人工智能复习重点题型： 选择、填空、简答、推理、计算。 各20分主要内容：AI三大学派、AI应用领域、图灵测试、谓词逻辑表示法语义网络表示法产生式表示法与或树，解树，可解节点的含义及解释、归结子句、置换、合一状态空间产生式系统盲目搜索、启发式搜索(求解城市最短路径相关例题要着重看)演绎推理和归结推理可信度算法和bayse算法ID3算法【第一章 绪论】1、三大学派及其对人工智能发展历史的不同看法符号主义：认为人工智能源于数理逻辑。符号主义仍然是人工智能的主流派。这个学派的代表有纽厄尔、肖、西蒙和尼尔逊(Nilsson)等。联结主义：认为人工智能源于仿生学，特别是人脑模型的研究。行为主义：认为人工智能源于控制论。这一学派的代表作首推布鲁克斯(Brooks)的六足行走机器人，它被看做新一代的“控制论动物”，是一个基于感知动作模式的模拟昆虫行为的控制系统。 2.人工智能的研究及应用领域人工智能研究及应用领域很多，主要研究领域包括问题求解、机器学习、专家系统、模式识别、自动定理证明、自然语言理解等。问题求解：人工智能的第一个大成就是发展了能够求解难题的下棋(如国际象棋)程序，它包含问题的表示、分解、搜索与归约等。 机器学习：学习是人类智能的主要标志和获得知识的基本手段；机器学习(自动获取新的事实及新的推理算法)是使计算机具有智能的根本途径；机器学习还有助于发现人类学习的机理和揭示人脑的奥秘。学习是一个有特定目的的知识获取过程，其内部表现为新知识结构的不断建立和修改，而外部表现为性能的改善。 专家系统：一般地说，专家系统是一个智能计算机程序系统，其内部具有大量专家水平的某个领域知识与经验，能够利用人类专家的知识和解决问题的方法来解决该领域的问题。发展专家系统的关键是表达和运用专家知识，即来自人类专家的并已被证明对解决有关领域内的典型问题是有用的事实和过程。模式识别：人工智能所研究的模式识别是指用计算机代替人类或帮助人类感知模式，是对人类感知外界功能的模拟，研究的是计算机模式识别系统，也就是使一个计算机系统具有模拟人类通过感官接受外界信息、识别和理解周围环境的感知能力。自动定理证明：自动定理证明的研究在人工智能方法的发展中曾经产生过重要的影响。例如，采用谓词逻辑语言的演绎过程的形式化有助于更清楚地理解推理的某些子命题。许多非形式的工作，包括医疗诊断和信息检索都可以和定理证明问题一样加以形式化。因此，在人工智能方法的研究中定理证明是一个极其重要的论题。我国人工智能大师吴文俊院士提出并实现了几何定理机器证明的方法，被国际上承认为“吴氏方法”，是定理证明的又一标志性成果。自动程序设计：对自动程序设计的研究不仅可以促进半自动软件开发系统的发展，而且也使通过修正自身数码进行学习(即修正它们的性能)的人工智能系统得到发展。程序理论方面的有关研究工作对人工智能的所有研究工作都是很重要的。自动程序设计研究的重大贡献之一是作为问题求解策略的调整概念。已经发现，对程序设计或机器人控制问题，先产生一个不费事的有错误的解，然后再修改它(使它正确工作)，这种做法一般要比坚持要求第一个解就完全没有缺陷的做法有效得多。自然语言理解：语言处理也是人工智能的早期研究领域之一，并引起了进一步的重视。语言的生成和理解是一个极为复杂的编码和解码问题。一个能理解自然语言信息的计算机系统看起来就像一个人一样需要有上下文知识以及根据这些上下文知识和信息用信息发生器进行推理的过程。理解口头的和书写语言的计算机系统所取得的某些进展，其基础就是有关表示上下文知识结构的某些人工智能思想以及根据这些知识进行推理的某些技术。机器人学：人工智能研究日益受到重视的另一个分支是机器人学，其中包括对操作机器人装置程序的研究。这个领域所研究的问题，从机器人手臂的最佳移动到实现机器人目标的动作序列的规划方法，无所不包。目前已经建立了一些比较复杂的机器人系统。机器人和机器人学的研究促进了许多人工智能思想的发展。智能机器人的研究和应用体现出广泛的学科交叉，涉及众多的课题，机器人已在各领域获得越来越普遍的应用。人工神经网络：人工神经网络处理直觉和形象思维信息具有比传统处理方式好得多的效果。人工神经网络已在模式识别、图象处理、组合优化、自动控制、信息处理、机器人学和人工智能的其它领域获得日益广泛的应用。智能检索：随着科学技术的迅速发展，出现了“知识爆炸”的情况，研究智能检索系统已成为科技持续快速发展的重要保证。智能信息检索系统的设计者们将面临以下几个问题。首先，建立一个能够理解以自然语言陈述的询问系统本身就存在不少问题。其次，即使能够通过规定某些机器能够理解的形式化询问语句来回避语言理解问题，但仍然存在一个如何根据存储的事实演绎出答案的问题。第三，理解询问和演绎答案所需要的知识都可能超出该学科领域数据库所表示的知识。【第二章 知识表示方法】1. 谓词逻辑表示（通过PPT例题和试卷题目理解解题方法及步骤）。2. 产生式的三大组成模块及其作用规则库：规则库是某领域知识（规则）的存储器，规则是以产生式表示的，规则集蕴涵着将问题从初始状态转换解状态的那些变换规则，规则库是专家系统的核心。规则可表成与或树形式，基于数据库中事实对这与或树的求值过程就是推理。数据库：数据库存放输入的事实、外部数据库输入的事实以及中间结果（事实）和最后结果的工作区。推理机：推理机是一个程序，控制协调规则库与数据的运行，包含了推理方式和控制策略。3.语义网络表示法（应用题）理解语义网络的概念及结构，常用的语义联系和用语义网络表示知识的方法。Eg1：我的车是棕黄色的，John 的车是绿色的。其中结点car是附加的，这样便于将单个网络连结起来。Eg2：理解下面图示的含义。4.状态空间表示法及其三要素（PPT第五章内容） 状态空间表示法用“状态”和“算符”来表示问题及求解问题可使用的知识。 状态：是求解过程中用以描述问题在任一时刻状况的数据结构。 算符：表示对状态的操作，算符的一次使用就使问题由一种状态变换为另一种状态。 问题的解：当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题的一个解。5.与或树中树、解树、可解节点的含义（PPT第五章内容）与树：问题的分解过程可用一个“与树”表示。把问题P分解为三个子问题P1、P2、P3，只有当P1、P2、P3三个子问题都可解时，问题P才可解，称P1、P2、P3之间存在“与关系”；称节点P为“与节点”。或树：问题的等价变换过程可用一个“或树”表示。问题P被等价变换为新问题P1、P2、P3，其中，新问题P1、P2、P3中只要有一个可解，则原问题就可解，称P1、P2、P3之间存在“或关系”；节点P称为“或节点”。与或树：其中既有“与”节点，也有“或”节点。可解节点：它是一个终叶节点。 它是一个“或”节点，且其子节点至少有一个是可解节点。 它是一个“与”节点，且其子节点全部是可解节点。解树：由可解节点构成的、且由这些可解节点可推出初始节点（它对应于原始问题）为可解节点的与/或树称为解树。【第三章 确定性推理方法】1. 自然演绎推理方法理解概念P/T/拒取/假言推理等。Eg1：构造下列的推理的证明：前提：PQ, PR, SM, SR, M结论：QEg2：一公安人员审查一件案件。一致的事实如下：(1).张三或李四盗窃了录像机；(2).如果张三盗窃了录像机，则作案时间不能在午夜前；(3).如果李四证词正确，则午夜时屋内灯光未灭；(4).如果李四证词不正确，则作案时间在午夜前；(5).午夜时屋内灯灭了。求解是谁偷了录相机。解：将已知事实符号化：设 P:张三盗窃录像机； Q:李四盗窃录像机; R:作案时间发生在午夜前； S:李四证词正确； M:午夜时灯光未灭。则前提为: (1) PQ, (2)PR, (3)SM, (4)SR, (5)M。结论未定。所以，可以得出是李四盗了录像机。Eg3：前提：p (rs)q)，p，s 结论：q。证明： p p规则 p (rs)q) p规则 (rs)q s p规则 s r I (rs) E q I2.归结推理方法（应用证明题）掌握推理方法，重在理解Eg1：Eg2：Eg3：任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问Peter的父亲是谁？解 第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先定义谓词。（1） 定义谓词：设Father(x,y)表示x是y的父亲。Brother(x,y)表示x和y是兄弟。（2） 将已知事实用谓词公式表示出来。 F1 ：任何兄弟都有同一个父亲。 (x)(y)(z)(Brother(x,y)Father(z,x)Father(z,y) F2：John和Peter是兄弟。 Brother(John,Peter) F3： John的父亲是David。 Father(David, John)（3） 将它们化成子句集得： S1=Brother(x,y)Father(z,x)Father(z,y), Brother(John,Peter), Father(David,John)第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER作析取。 设Peter的父亲是u，则有：Father(u,Peter)。 将其否定与ANSWER作析取，得： G：Father(u,Peter)ANSWER(u)第三步：将上述公式G化为子句集S2,并将S1和S2合并到S。 S2 =Father(u,Peter)ANSWER(u) S= S1S2将S中各子句列出如下：（1）Brother(x,y)Father(z,x)Father(z,y)。（2）Brother(John,Peter)。（3）Father(David,John)。（4）Father(u,Peter)ANSWER(u)。第四步：应用归结原理进行归结（5）Brother(John,y)Father(David,y) （1）与（3）归结 =David/z,John/x（6）Brother(John,Peter)ANSWER(David) （4）与（5）归结=David/u,Peter/y（7）ANSWER(David) （2）与（6）归结第五步：得到了归结式ANSWER(David)，答案即在其中，所以u=David。即Peter的父亲是David。【第四章 不确定推理方法】这一章就是多看例题多看例题多看例题（可信度方法和主观Bayes）Eg1：设有一组知识已知：求CF（H）解：1. 先用R4和R5求CF(E1)和CF(E3)2. 用R1, R2和R3求CF1(H), CF2(H)和CF3(H)3. 用CF1(H), CF2(H)和CF3(H)合成CF (H) Eg2：Eg3：Eg4：【第五章 状态空间搜索策略】1. 一般搜索算法的综述和理解搜索的结果将获得一棵搜索树。搜索树是由称为 open表和 closed表的两个表共同记载的。 open表记载搜索过程中尚未考查的节点和新生成的节点； open表支持按指定要求对表中节点排序； 搜索算法每次循环时都将open表中的第一个节点移送到 closed表的表尾； closed表记载搜索过程中已被考查过的节点。（PPT 2138面）重点掌握例题！例5.3 应用状态空间的搜索策略求解最短路径问题：求从城市A经过每个城市最多一次到达城市E的最小交通费用的解。（1）给出问题求解的状态定义（2）给出问题求解的算符定义（3）应用有代价宽度优先搜索求解（4）应用有代价深度优先搜索求解图5.7 例5.3的城市交通路线图解：（1）状态定义 状态S定义为当前走过的城市名字符串，刚走过的城市名在串尾。 初态：S0 = A 终态：Sg = A $ E 其中 $ 为城市名子串，$B，C，D（2）算符定义 go(x,y) 表示从城市x走到城市y。 使用条件：当前状态Si城市名字符串串尾城市名是x且Si不含城市名y算符操作：将城市名y添加到当前状态Si的串尾。（3）应用有代价宽度优先搜索求解open = ( 1 (0) )Loop1: closed = ( 1 (0) ) open = ( 3 (3) , 2 (4) )Loop2: closed = ( 1 (0) , 3 (3) ) open = ( 2 (4) , 4 (5) )Loop3: closed = ( 1 (0) , 3 (3) , 2 (4) ) open = ( 4 (5) , 5 (8) , 6 (9) )Loop4: closed = ( 1 (0) , 3 (3) , 2 (4) , 4 (5) ) open = ( 5 (8) , 8 (8) , 6 (9) , 7(9) )Loop5: closed = ( 1 (0) , 3 (3) , 2 (4) , 4 (5) , 5 (8) ) open = ( 8 (8) , 6 (9) , 7(9) , 9(10) , 10(11) )Loop6: closed = ( 1 (0) , 3 (3) , 2 (4) , 4 (5) , 5 (8) , 8 (8) ) S8 = ACDE是目标状态，故算法成功终止。 open = ( 6 (9) , 7(9) , 9(10) , 10(11) )图5.8 例5.3的有代价宽度优先搜索生成的搜索树（4）应用有代价深度优先搜索求解 open = ( 1 (0) )Loop1: closed = ( 1 (0) ) open = ( 3 (3) , 2 (4) )Loop2: closed = ( 1 (0) , 3 (3) ) open = ( 4 (5) , 2 (4)Loop3: closed = ( 1 (0) , 3 (3) , 4 (5) ) open = ( 6 (8) , 5 (9) , 2 (4) )Loop4: closed = ( 1 (0) , 3 (3) , 4 (5) , 6 (8) ) S6 = ACDE是目标状态，故算法成功终止。 open = ( 5 (9) , 2 (4) )图5.9 例5.3的有代价深度优先搜索生成的搜索树（5）应用全局择优搜索策略求解 估计函数：fj = gj + hj 代价函数 gj = gi + c(i, j) ， 启发函数 hj = a (b - dj)其中，参数a为两个城市之间的平均费用（代价） a = （3 + 4 + 4 + 2 + 3 + 5）/ 6 = 21 / 6 = 3.5可取整数a = 3参数b为从初始节点到目标节点需要到达的城市数的估计。可以取b=2, 或取b=3, 或取b=4。 （1）取b=2 ，则hj=3（2 - dj） open = ( 1 ( 6 ) )Loop1 : closed = ( 1 ( 6 ) open = ( 3(5) , 2(7)Loop2 : closed = ( 1(6) , 3(6) open = ( 4(5) , 2(7)Loop3 : closed = ( 1(6) , 3(6) , 4(5) open = ( 6(5) , 5(6) , 2(7)Loop4 : closed = ( 1(6) , 3(6) , 4(5) , 6(5) S6 = ACDE 是目标状态，故算法成功终止。 open = ( 5(6) , 2(7) 生成的搜索树（2）取b=3 ，则hj = 3(3 - dj) open = ( 1(9) Loop1 : closed = ( 1(9) open = ( 3(9) , 2(10) Loop2 : closed = ( 1(9) , 3(9) open = ( 4(8) , 2(10) Loop3 : closed = ( 1(9) , 3(9) ,4(8) open = ( 6(8) , 5(9) , 2(10) Loop4 : closed = ( 1(9) , 3(9) , 4(8) , 6(8) S6 = ACDE是目标状态，故算法成功终止。 open = ( 5(9) , 2(10) 生成的搜索树 （3）取b = 4 , 则 hj = 3（4 dj） open = ( 1(12) Loop1 : closed = ( 1(12) open = ( 3(12) , 2(13) Loop2 : clo