山东大学人工智能复习参考(2017春)(带答案)

复习参考题2016秋一、填空1．构成产生式系统的基本元素有综合数据库、规则库、控制系统,控制策略按执行规则的方式分类,分为正向、逆向、双向三类。2．归结过程中控制策略的作用是给出控制策略，以使仅对选择合适的子句间方可做归结，避免多余的、不必要的归结式出现或者说，少做些归结仍能导出空子句。常见的控制策略有线性归结策略、支持集策略、单元归结、输入归结。3．公式G和公式的子句集并不等值，但它们在不可满足的意义下是一致的。4．与或图的启发式搜索算法（AO*算法）的两个过程分别是图生成过程即扩展节点和计算耗散值的过程。5．人工智能的研究途径主要有两种不同的观点，一种观点称为符号主义,认为人类智能基本单元是符号。另一种观点称为连接主义（仿生主义），认为职能的基本单元是神经元。6．集合{P(a,x,f(g(y)),P(z,f（z）,f(u)))的mgu（最一般合一置换）为{z/a,f(x)/x,u/g(y)}。7．语义网络是对知识的有向图表示方法，一个最简单的语义网络是一个形如节点1、弧、节点2的三元组，语义网络可以描述事物间多种复杂的语义关系、常用ISA、AKO弧表示节点间具有类属的分类关系。语义网络下的推理是通过继承和匹配实现的。8．当前人工智能研究的热点之一就是机器学习。常见的机器学习方法可分为连接学习、归纳学习、分析学习和遗传算法与分类器系统等。一个机器学习系统应有环境、知识库、学习环节和执行环节四个基本部分组成。9．常用的知识表示法有逻辑表示法、产生式规则表示法、语义网络表示法、框架理论表示法、过程表示法等。10．有两个A*算法A1和A2，若A1比A2有较多的启发信息，则h1(n)h2(n)。11．关于A算法与A*算法，若规定h(n)≥0，并且定义启发函数：f*(n)=g*(n)+h*(n)表示初始状态S0经点n到目标状态Sg最优路径的费用。其中g*(n)为S0到n的最小费用,h*(n)为到Sg的实际最小费用。若令h(n）≡0，则A算法相当于宽度优先搜索，因为上一层节点的搜索费用一般比下一层的小。若g(n)≡h(n)≡0则相当于随机算法。若g(n)≡0，则相当于最佳优先算法。特别是当要求h(n)≤h*(n）就称这种A算法为A*算法。12．群智能是指无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。群智能潜在的两大特点是可行性和分布式。其典型算法有蚁群算法（蚂蚁觅食）和粒子群算法（蜂群或鸟群觅食）。已有的群智能理论的研究和应用证明群智能方法是一种能够有效解决大多数优化问题的新方法。13、蚁群算法是模拟自然界中蚂蚁寻找从巢穴到食物的最佳路径的行为而设计的，蚂蚁在遇到食物返回的路上会分泌信息素，信息素会随着时间慢慢挥发，且关键路径上的信息素相对浓度高，蚁群算法已被广泛应用于许多优化问题中，其中有聚类问题、路由算法设计、图着色、车辆调度、机器人路径规划。14、粒子群优化算法是模拟鸟群或蜂群的觅食行为而设计的，其基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。粒子群优化算法的应用领域有广泛应用于各类优化问题上、在军事领域中的应用、对巡航导弹的飞行高度进行优化、车辆路径问题的应用、邮政投递、火车及汽车的调度、港口装卸集装箱。15、遗传算法是以达尔文的自然选择学说为基础发展起来的。遗传算法的三种基本操作是复制、交叉、变异；在遗传算法中，衡量个体优劣的尺度是适应度，它决定某些个体是繁殖或是消亡，同时也是驱动遗传算法的动力。16、蚁群算法是模拟自然界中蚂蚁寻找从巢穴到食物的最佳路径的行为而设计的，依据蚁群算法的基本原理，蚁群算法中的行为因子有觅食规则、移动规则、避障规则、信息素规则、范围、环境等。17、近年有学着提出的人工鱼群算法（ArtificialFishSwarmAlgorithm-AFSA）是模仿自然界中鱼群的行为而提出来的解决问题的算法，从模拟鱼群的聚集行为、觅食行为、跟随行为和移动行为等方面来模拟自然界中的鱼群行为。18、遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。19、决策树是一种知识概念表示方法，能表示与或规则；是一种归纳/实例/有师/监督/图形。而人工神经网络（ANNs）是非图形符号表示法/函数表示法/一种普遍且实用的表示法，又是一种函数表示法；即从大量的数据中学习值为实数、离散值或向量的函数。人工神经网络对于训练数据中的“错误”数据的健壮性。人工神经网络的训练学习过程中有一个称为“学习速率η”的常数，η取值过大会引起漂移，η取值过小会收敛速度太慢，学习效率不高。20、多层神经网络的学习过程中有一种是反向传播算法（BackPropagation-BP），其基本思想是利用输出单元的误差再计算上一层单元的误差，以次向上传播，以次向上传播，俗称反向传播。又称逆推学习算法算法。利用输出单元的误差再计算上一层单元的误差，又称逆推学习算法(简称BP算法)。21、归纳学习需要的预先假定，称为归纳偏置，归纳学习算法隐含了归纳偏置，候选消除算法的归纳偏置是目标概念可以在假设空间找到-所以又称限定偏置。ID3是一种典型的决策树学习方法，ID3的归纳偏置有两点，分别是贪婪算法/从根向下推断决策树/搜索完整的假设空间，优先选择较小的树。Find-S算法（寻找极大特殊假设）使用一般到特殊序，在偏序结构的一个分支上执行一般到特殊搜索，寻找一个与样例一致的最特殊假设。22、自然语言处理是研究用机器处理人类语言的理论和技术,又叫自然语言理解,它研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法,自然语言处理研究面临的两大困难是歧义和病构,其中歧义分为音歧义、分词歧义、短语歧义、词义歧义、语用歧义四个方面。23.在证据理论(EvidentTheory)中引入了信任函数(BeL)，它满足了概率论弱公理。在概率论中，当先验概率很难获得，但又要被迫给出时，用证据理论能区分不确定性和不知道的差别。因而它比概率论更适合于专家系统推理方法。概率论是证据理论的一个特例，有时也称证据理论为广义概率论。24、贝叶斯网就是一个在弧的连接关系上加入连接强度的因果关系网络。有两个部分组成，其一是DAG，即：有向无环图；其二是CPT，即：条件概率表。贝叶斯网络通常使用三种推理是因果推理，诊断推理，辩解推理。25、在确定性推理模型中可信度因子CF(h,e)知识静态强度取值范围为[-1,+1]；主观Bayes方法中规定规则的静态强度LS,LN的值应[0,∞）。二、证明1、设公理集：(x)(R(x)L(x)),(x)(D(x)~L(x)),(x)(D(x)I(x))求证:(x)(I(x)~R(x))(给出归结步骤并画出归结树)2、将下式化为Skolem标准形：～(x)(y)P(a,x,y)→(x)(～(y)Q(y,b)→R(x))第一步，消去→号，得：～～((x)(y)P(a,x,y))∨(x)(～～(y)Q(y,b)∨R(x))第二步，～深入到量词内部，得：(x)(y)P(a,x,y)∨(x)((y)Q(y,b)∨R(x))第三步，变元易名，得(x)(y)P(a,x,y)∨(u)(v)(Q(v,b)∨R(u))第四步，存在量词左移，直至所有的量词移到前面，得：(x)(y)(u)(v)(P(a,x,y)∨Q(v,b)∨R(u))由此得到前述范式(x)(y)(u)(v)(P(a,x,y)∨Q(v,b)∨R(u))第五步，消去“”（存在量词），略去“”全称量词消去(y)，因为它左边只有(x)，所以使用x的函数f(x)代替之，这样得到：(x)(u)(v)(P(a,x,f(x))∨Q(v,b)∨R(u))消去(u)，同理使用g(x)代替之，这样得到：(x)(v)(P(a,x,f(x))∨Q(v,b)∨R(g(x))则，略去全称变量，原式的Skolem标准形为：P(a,x,f(x))∨Q(v,b)∨R(g(x))3、用归结法证明：BAAA321即B是A1、A2、A3的有效结论。))()()(())()()(()))(),()(()()()(()))(),()(())()()(((321xUxVxBxUxQxAyUyxWyxUxPxAyVyxWyxQxPxAA1的子句：S1=﹁P(x)∨Q(x)∨W(x,f(x))S2=﹁P(x)∨Q(x)∨V(f(x))A2的子句：S3=P(a),s4=U(a),s5=﹁W(a,y)∨U(y)A3的子句：s6=﹁Q(x)∨﹁U(x)﹁B的子句：S7=﹁V(x)∨﹁U(x)归结过程：S1和S3归结Q(a)∨W(a,f(a))定义为子句s8S2和S3归结Q(a)∨V(f(a))定义为子句s9S4和S6归结﹁Q(a)定义为子句s10S9和S10归结V(f(a))定义为子句s11S8和S10归结W(a,f(a))定义为子句s12S5和S12归结U(f(a))定义为子句s13S7和S13归结﹁V(f(a))定义为子句s14S11和S14归结空4、依据基于规则的正向演绎系统,有下列谓词公式(事实)(x)(y)(Q(y,x)~((R(y)P(y))S(x,y))),请给出事实的与或树表示。(x)(y)(Q(y,x)~((R(y)P(y))S(x,y)))=(x)(y)(Q(y,x)((~R(y)~P(y))~S(x,y)))=Q(y,a)((~R(y)~P(y))~S(a,y))Skolem化=Q(w,a)((~R(y)~P(y))~S(a,y))主合取元变量换名例：Q(w,a)((~R(y)~P(y))~S(a,y))三、简答题1．人工智能方法与传统程序的不同有哪些？传统方法解决问题。利用已有知识,问题可以结构化-数据结构,数学形式表达-数学公式、算法。利用知识，特别是依赖人类经验的启发知识是根本不同之处。人工智能可以解决众多的难以数学表达的非结构化的实际问题。人工智能首先研究的是以符号表示的知识,而不是数值为研究对象。其次采用的是启发式推理的方法而不是常规的算法,控制结构和领域知识是分离的。同时还允许出现相对正确的答案。2．在与或图的问题求解过程中，哪几类节点称为能解节点？终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。3．宽度优先搜索和深度优先搜索有何不同？在何种情况下宽度优先搜索优于深度优先搜索？在何种情况下深度优先搜索优于宽度优先搜索？两种搜索策略是否都是完备的？宽度优先搜索就是逐层穷举搜索。深度优先搜索就是分支优先搜索。待搜索问题的解存在且关键路径较短时宽度优先搜索优于深度优先搜索；待搜索问题的解存在且关键路径较长，而深度优先搜索过程中优先发展的正好是解所在的路径时深度优先搜索优于宽度优先搜索。宽度优先搜索是完备的。4.举例解释语义网络(SemanticNetwork)与知识图谱(Knowledgegraph)的区别与联系。5.举例说明大型应用软件系统开发过程中采用的软件技术(体系)架构是如何体现框架理论知识表示思想的。6．简要说明粒子群优化算法与遗传算法的共性和差异。共性（1）都属于仿生算法；（2）都属于全局优化方法；（3）都属于随机搜索算法；（4）都隐含并行性；（5）根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等；（6）对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。差异（1）PSO有记忆，所有粒子都保存较优解的知识，而GA，以前的知识随着种群的改变被改变；（2）PSO中的粒子是一种单向共享信息机制。而GA中的染色体之间相互共享信息，使得整个种群都向最优区域移动；（3）GA需要编