华南师范大学人工智能复习

人工智能复习（2011/5/30更新）（该部分习题答案请参考书《人工智能原理辅导与练习》王文杰，清华大学出版社）一、问答第0章概论什么是智能？智能是脑特别是人脑的属性或者说产物智能的基础是知识（没有知识的智能不可想象）人工智能的定义？人工智能（学科）是计算机科学中涉及研究、设计和应用智能机器的一个分支。它的近期主要目标在于研究用机器来模仿和执行人脑的某些智力功能，并开发相关理论和技术。人工智能（能力）是智能机器所执行的通常与人类智能有关的智能行为，如判断、推理、证明、识别、感知、理解、通信、设计、思考、规划、学习和问题求解等思维活动。图灵实验内容Turing提出的智能实验，参加者是计算机、被实验的人以及主持实验的人。由主持人提出问题，计算机和被实验的人来回答，被实验者在回答问题时尽可能地向主持人表示他是”真正的”人，计算机也尽可能逼真地模仿人的思维。如果主持人通过听取对问题的回答分辨不出哪个是人的回答时，便可认为被试验的计算机是有智能的了。有人对这样设计的实验提出了疑义：认为这种实验只反映了结果的比较而没有涉及思维的过程，而且也没明确此人是个孩子还是有良好素质的成年人参加了实验。人工智能三大学派符号主义，连接主义，行为主义（1） 符号主义主要特征立足于逻辑运算和符号操作，适合于模拟人的逻辑思维过程，解决需要逻辑推理的复杂问题知识可用显式的符号表示，在已知基本规则的情况下，无需输入大量的细节知识便于模块化，当个别事实发生变化时，宜于修改•能于传统的符号数据库进行连接•可对推理结论进行解释，便于对各种可能性进行选择缺点：•可以解决逻辑思维，但对于形象思维难于模拟•信息表示成符号后，在处理和转换时有丢失的情况（2） 连接主义主要特征通过神经元直接的并行协作实现信息处理，处理过程具有并行性，动态性和全局性•可以实现联想的功能，便于对有噪声的信息进行处理•可以通过对神经元之间连接强度的调整实现学习和分类等适合模拟人的形象思维过程求解问题时，可以较快的得到一个近似解缺点不适合解决逻辑思维人工智能三大学派对人工智能发展历史的不同看法符号主义认为人工智能源于数理逻辑。符号主义仍然是人工智能的主流派。这个学派的代表有纽厄尔、肖、西蒙和尼尔逊(Nilsson)等。联结主义认为人工智能源于仿生学，特别是人脑模型的研究。行为主义认为人工智能源于控制论。这一学派的代表作首推布鲁克斯(Brooks)的六足行走机器人，它被看做新一代的“控制论动物”，是一个基于感知一动作模式的模拟昆虫行为的控制系统。人工智能的研究与应用领域问题求解逻辑推理与定理证明自然语言理解•自动程序设计•专家系统机器学习神经网络机器人学•模式识别机器视觉智能控制•智能检索(搜索)•智能调度与指挥分布式人工智能与Agent•计算智能与进化计算数据挖掘与知识发现人工生命专家系统:是一个含有大量的某个领域专家水平的知识与经验智能计算机程序系统，能够利用人类专家的知识和解决问题的方法来处理该领域问题。简而言之，专家系统是一种模拟人类专家解决领域问题的计算机程序系统。专家系统特点？启发性：专家系统能运用专家的知识与经验进行推理、判断和决策。透明性：专家系统能够解释本身的推理过程和回答用户提出的问题，以便让用户能够了解推理过程，提高对专家系统的信赖感。灵活性：专家系统能不断地增长知识，修改原有知识，不断更新。专家系统的优点？专家系统能够高效率、准确、周到、迅速和不知疲倦地进行工作。专家系统解决实际问题时不受周围环境的影响，也不可能遗漏忘记。可以使专家的专长不受时间和空间的限制，以便推广珍贵和稀缺的专家知识与经验。专家系统能促进各领域的发展。专家系统能汇集多领域专家的知识和经验以及他们协作解决重大问题的能力。军事专家系统的水平是一个国家国防现代化的重要标志之一。专家系统的研制和应用，具有巨大的经济效益和社会效益。研究专家系统能够促进整个科学技术的发展。第一章搜索、第二章与或树基本的盲目搜索算法有两种？宽度优先搜索深度优先搜索什么是状态空间法，什么是评价函数比较宽度优先搜索与深度优先搜索？什么是启发式搜索的启发信息？可分哪几种？启发信息：进行搜索技术一般需要某些有关具体问题领域的特性的，与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息，把此种信息叫做启发信息。启发信息按其用途可分为下列3种：（1）用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。（2）在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。（3）用于决定某些应该从搜索树中抛弃或修剪的节点。什么是入*算法？采用h*（x）的下界h（x）为启发函数的A算法，称为A*算法。比较入算法与A*算法的特点。答：A算法为一种启发式搜索算法，当A算法的启发函数满足h（x）Wh*（x）时，该A算法即为A*算法。A*算法可以保证搜索取得最优解。什么是与或图的终止节点？什么是能解节点？什么是解树？答：本原问题对应的节点为终止节点；当一个节点满足以下三个条件时，该节点为能解节点：1）该节点为终止节点；2）当该节点为与节点时，当且仅当其所有子节点能解；3）当该节点为或节点时，只要其任一子节点能解皆可。解树是在一个与或图中从初始节点到目标节点的图或树形路径。什么是解树的代价？答：解树的代价即树根的代价，是从树叶开始自下而上逐层计算而求得的。什么是希望树？答：希望树是当前与或图中具有最小代价的解树。判断下图各节点的能解性，并确定解树。

指出下图的解树，并计算每个解树的代价，以及希望树。七5答：解树1：{Q0,A,ti，t2}g(t1)=g(t2)=0,g(A)=11,g(Qo)=13解树2：{Qo,B，D，G，t4,t5}g(t4)=g(t5)=0,g(G)=3,g(D)=4,g(B)=6,g(Q0)=8所以，解树2为最优解树，即希望树什么是博弈树？有什么特点第三章谓词逻辑子句(子句集)逻辑公式，是一些文字的析取(子句的集合)。不确定性推理知识的不精确性、模糊性、随机性统称为不确定性，在不确定意义下的推理为不确定推理。反演采用证明A〜B的不可满足性来证明AB，是一种反演（反驳）证明法。4..可满足性指一个逻辑公式，若在某个解释下取值为真，便说这个公式是可满足的。归纳是一种由实例得出一般性结论的推理。归结是定理证明的一种方法。产生式系统是一种以产生式表示知识的专家系统，是最常用的一种专家系统。合一对两个原子谓词，通过变量置换而合一化的过程。合取范式对一个谓词公式，通过等值演算化成如（・・・）（••••）（••）形式，称原公式的合取范式。过程性知识是一种表示和求解为一体的知识表示类型。启发式搜索是一种试探性的、不精确的、模糊的依于经验知识的搜索方法，常能明显化简问题求解的复杂性。规则一种形式为"如果A那么B"的语句为规则，专家系统中通过使用规则进行推理，即若条件入成立，使用这条规则便可推得出B。非单调推理一种非标准逻辑下的推理方法，随知识的增加原有结论不一定随之增加，甚至会减少，就是非单调推理要研究的内容。知识获取从书本、专家等信息源寻求有用的知识便是知识获取，是知识工程的三大任务（知识获取、知识表示和知识利用）之一。控制策略问题求解过程中，为提高效率而采取的技术手段。说明归结法完备性的含义，并简述其证明的思路。第四章知识表示方式知识的定义知识是人们在长期的生活及社会实践中积累起来的对客观世界的认识与经验，人们把实践中获得的信息关联在一起，就获得了知识。知识的特性相对正确性不确定性可表示性与可利用性什么是知识表示？所谓知识的表示实际上是对知识的一种描述，或者说一种约定，一种计算机可以接受的用于描述知识的数据结构。对知识表示有哪些要求？充分性：能够将问题求解所需的知识正确有效的表达出来；可理解性：所表达知识简单、明了、易于理解；可利用性：能够有效地利用所表达的知识；可扩充性：能够方便、灵活的对所表达的知识进行维护和扩充；常用的知识表示方法有哪些？一阶谓词逻辑表示法状态空间法问题归约法框架表示法语义网络表示法面向对象表示剧本(script)表示过程(procedure)表示状态空间法三要点状态怎忸饨)：表示问题解法中每一步问题状况的数据结构；算符(operator):把问题从一种状态变换为另一种状态的手段；状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。谓词：用于刻画个体词的性质或个体词之间的关系的词产生式规则的基本形式基本形式：PfQ,或者IfPthenQ其中，P是产生式的前提，用于指出该产生式是否可用的条件；Q是一组结论或操作，用于指出当前题》所指示的条件被满足时，应该得出的结论和应该执行的操作。整个产生式的含义是：如果前提P所指示的条件被满足时，则可得出结论Q或者执行Q所规定的操作。什么是产生式系统？把一组产生式放在一起，让他们互相配合，协同作用，一个产生式生成的结论可以供另一个产生式作为已知事实使用，以求得问题的解决，这样的系统称为产生式系统。产生式系统的构成？综合数据库：描述问题的状态；产生式规则：对综合数据库进行操作，使之发生变化；控制系统：查找一〉选择一〉执行规则产生式表示法的优缺点优点：1・自然性2.模块性有效性清晰性不足：效率不高不能表达具有结构性的知识什么是语义网络？语义网络由节点和节点间的弧组成；节点表示各种事物，概念，情况，属性，动作，状况等；弧表示各种语义联系，指明他所连接的节点间的各种语义联系。语义网络的特点-结构性。与框架法一样，语义网络也是一种结构化的知识表示方法。-联想性。•自然性。-非严格性。•处理上的复杂性。过程表示法的特点优点：效率较高；控制系统设计容易。缺点：不易修改及添加新知识，且当对某一过程进行修改时，有可能影响到其它程序，对系统的维护带来诸多不利。框架理论的基本观点？框架理论认为，人们对现实世界中各种事物的认识都是以一种类似于框架的结构存储在记忆中的，当面临一种新事物时，就从记忆中找出一个合适的框架并根据实际情况对其细节加以修改、补充，从而形成对当前事物的认识。框架表示法的优缺点？优点：结构性深层性继承性自然性缺点：缺乏框架的形式理论缺乏过程性知识表示清晰性难以保证第五章机器学习说明不确定推理的基本方法。什么是贝叶斯网络？答：贝叶斯网络是一种以随机变量为节点，以条件概率为节点间关系强度的有向无环图(DirectedAcyclicGraph,DAG)。它描述事物之间的因果关系或依赖关系，是一种直观的图形表示。说明机器学习概念及学习的方法。机器学习就是让计算机模拟人的学习行为，或者说计算机也具有学习的能力。人工智能中的机器学习主要是指机器对自身的行为的修正或性能的改善和机器对客观规律的发现。说明产生式和框架知识表示方法，并对两者做一比较。试问单层人工神经网络能解决"异或”问题吗？三层以上人工神经网络可以解决吗？产生式系统主要分哪几种类型什么是归纳学习机器学习的几个发展阶段是什么以ID3算法为例，说明决策树学习方法的基本思想是什么？J.R.Quinlan的ID3(interativedicremiserversion3)的工作过程是，首选找出最有判别力(信息增益，informationgain)的属性，把数据分成多个子集，每个子集又选择最有判别力的属性进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树，可以用它来对新的实例进行分类。10.试述遗传算法的基本原理，并说明遗传算法的求解步骤。答:遗传算法的基本原理如下:通过适当的编码方式把问题结构变为位串形式(染色体)，在解空间中取一群点作为遗传开始的第一代，染色体的优劣程度用一个适应度函数来衡量，每一代在上一代的基础上随机地通过复制、遗传、变异来产生新的个体，不断迭代直至产生符合条件的个体为止。迭代结束时，一般将适应度最高的个体作为问题的解。一般遗传算法的主要步骤如下：随机产生一个由确定长度的特征字符串组成的初始群体。对该字符串群体迭代的执行下面的步(a)和(b)，直到满足停止标准：计算群体中每个个体字符串的适应值；应用复制、交叉和变异等遗传算子产生下一代群体。把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这个结果可以表示问题的一个解。二、应用问题:搜索问题有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制：船太小，农夫每次只能带一样东西过河；如果没有农夫看管，则狼要吃羊，羊要吃菜。请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。题示：(1)用四元组(农夫，狼，羊，菜)表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。解：第一步，定义问题的描述形式用四元组S=(f,w,s,v)表示问题状态，其中，f,w,s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态：S0=(1,1,1,1),S]=(1,1,1,0),S2=(1,1,0,1),S3=(1,1,0,0)S4=(1,0,1,1),S5=(1,0,1,0),S6=(1,0,0,1),S7=(1,0,0,0)S8=(0,1,1,1),S9=(0,1,1,0),S10=(0,1,0,1)，S11=(0,1,0,0)S12=(0,0,1,1)，S13=(0,0,1,0),S14=(0,0,0,1),S15=(0,0,0,0)其中，状态s3,s6,s7,s8,s9,S12是不合法状态，S0和S15分别是初始状态和目标状态。第三步，定义操作，即用于状态变换的算符组F由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下：L(i)表示农夫从左岸将第i样东西送到右岸(i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西)。由于农夫必须在船上，故对农夫的表示省略。R(i)表示农夫从右岸将第i样东西带到左岸(i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西)。同样，对农夫的表示省略。这样，所定义的算符组F可以有以下8种算符：L(0),L(1),L(2),L(3)R(0)，R(1)，R(2)，R(3)第四步，根据上述定义的状态和操作进行求解。该问题求解过程的状态空间图如下：(1,1,l,1)L(2)J(0,1,0,1)R(0)I(1,1,0,1)项1/\^(3)(0,0,0,1) (0,1,0,0)R(2)IIR(2)(1,0,1,0)L(2)J(0,0,0,0)

与或图搜索用一字棋说明极大极小搜索过程的原理，并画出第一阶段的搜索树。设有如下图所示的博弈树，其中最下面的数字是假设的估值，请对该博弈树作如下工作:计算各节点的倒推值；利用a-0剪枝技术剪去不必要的分枝。谓词逻辑

要求：复习数理逻辑，明白命题逻辑、一阶谓词逻辑的基本概念，熟练谓词演算，会求谓词公式的前束范式和Skolem标准形等。【知识点】1.子句集建立归结式归结推理过程1.子句集建立归结式归结推理过程子句形Skolem标准形子句与子句集G与S在不可满足意义下是一致的2.3.4.5.归结原理置换与合一归结式归结推理过程归结法完备性不是每个计算机系的学生都喜欢在计算机上编程序。解：定义谓词S(x)：x是计算机系学生L(x,pragramming)：x喜欢编程序U(x,computer)：x使用计算机将知识用谓词表示为：-(vx)(S(x)-L(x,pragramming)AU(x,computer))新型计算机速度又快，存储容量又大。解：定义谓词NC(x)：x是新型计算机F(x)：x速度快B(x)：x容量大将知识用谓词表示为：(vx)(NC(x)fF(x)AB(x))判断下列子句集中哪些是不可满足的:{-PVQ,{-PVQ,-Q,P,}{PVQ,-PVQ,PV-Q,-PV-Q}不可满足，其归结过程为：(2)解：(1)⑵不可满足，其归结过程为:⑵不可满足，其归结过程为:判断下列公式是否为可合一，若可合一，则求出其最一般合一。P(a,b),P(x,y)P(f(x),b),P(y,z)解：(1)可合一，其最一般和一为：a={a/x,b/y}。⑵可合一，其最一般和一为：a={y/f(x),b/z}。把下列谓词公式化成子句集：(1)(vx)(vy)(P(x,y)AQ(x,y))⑵(vx)(vy)(P(x,y)fQ(x,y))解：(1)由于(vx)(vy)(P(x,y)AQ(x,y))已经是Skolem标准型，且P(x,y)AQ(x,y)已经是合取范式，所以可直接消去全称量词、合取词，得{P(x,y),Q(x,y)}再进行变元换名得子句集：S={P(x,y),Q(u,v)}⑵对谓词公式(vx)(vy)(P(x,y)fQ(x,y)),先消去连接词"f”得：(vx)(vy)(-P(x,y)VQ(x,y))此公式已为Skolem标准型。再消去全称量词得子句集：S={-P(x,y)VQ(x,y)}设已知：如果x是y的父亲，y是z的父亲，则x是z的祖父；每个人都有一个父亲。使用归结演绎推理证明：对于某人u，一定存在一个人v，v是u的祖父。解：先定义谓词F(x,y)：x是y的父亲GF(x,z)：x是z的祖父P(x)：x是一个人再用谓词把问题描述出来：已知F1：(vx)(vy)(vz)(F(x,y)AF(y,z))fGF(x,z))F2：(vx)(3y)(P(x)fF(y,x))求证结论G：(3u)(3v)(P(u)fGF(v,u))然后再将F1，F2和-G化成子句集：-F(x,y)V-F(y,z)VGF(x,z)-P(r)VF(s,r)P(u)-GF(v,u))对上述扩充的子句集，其归结推理过程如下：由于导出了空子句，故结论得证。知识表示1.高老师从1.高老师从7月到8月给计算机系学生讲《计算机网络》课。解：请把下列命题用一个语义网络表示出来:(1)树和草都是植物；解：(2)树和草都有叶和根;解：种种水草是草，且生长在水中;解：假设有以下一段天气预报：“北京地区今天白天晴，偏北风3级，最高气温12°，最低气温-2°，降水概率15%。”请用框架表示这一知识。解：Frame<天气预报〉地域：北京时段：今天白天天气：晴风向：偏北风力：3级气温：最高：12度最低：-2度降水概率：15%不确定推理方法的确定推理CF模型中的不确定性推理实际上是从不确定的初始证据出发，不断运用相关的不确性知识，逐步推出最终结论和该结论可信度的过程。而每一次运用不确定性知识，都需要由证据的不确定性和知识的不确定性去计算结论的不确定性。不确定性的更新公式CF(H)=CF(H,E)Xmax{0,CF(E)}若CF(E)<0，则CF(H)=0即该模型没考虑E为假对H的影响。若CF(E)=1，贝UCF(H)=CF(H,E)即规则强度CF(H,E)实际上是在E为真时，H的可信度当有多条知识支持同一个结论，且这些知识的前提相互独立，结论的可信度又不相同时，可利用不确定性的合成算法求出结论的综合可信度。否定证据不确定性的计算CF(-E)=-CF(E)组合证据不确定性的计算对证据的组合形式可分为“合取”与“析取”两种基本情况。

合取当组合证据是多个单一证据的组合时，即E=E1ANDE2AND…ANDEn时，若已知CF(E1),CF(E2),…，CF(En)，贝UCF(E)=min{CF(E1),CF(E2),…,CF(En)}析取当组合证据是多个单一证据的析取时，即E=E1ORE2OR…OREn时，若已知CF(E1)，CF(E2)，…，CF(En)，则CF(E)=max{CF(E1),CF(E2),…,CF(En)}设有知识：IF E1 THEN H (CF(H,E1))IF E2 THEN H (CF(H,E2))则结论H的综合可信度可分以下两步计算：分别对每条知识求出其CF(H)。即CF1(H)=CF(H,E1)Xmax{0,CF(E1)}CF2(H)=CF(H,E2)Xmax{0,CF(E2)}若CF(H)>0且CF2若CF(H)>0且CF2(H)>0若CF(H)<0且CF2(H)<0若CF1(H)与CF2(H)异号CF(H)+CF(H)-CF(H)xCF(H)CF(H)=ICF1(H)+CF2(H)+CH1(H)xCF2(H)CF](H)+CF2(H)1.设有如下一组推理规则：r1：IFE1THENE2(0.6)r2：IFE2ANDE3THENE4(0.7)r3:IFE4THENH(0.8)r4:IFE5THENH(0.9)且已知CF(E1)=0.5,CF(E3)=0.6,CF(E5)=0.7。求CF(H)=?解：(1)先由r1求CF(E2)CF(E)=0.6Xmax{0,CF(E)}21=0.6Xmax{0,0.5}=0.3⑵再由r2求CF(E4)CF(E4)=0.7Xmax{0,min{CF(E2),CF(E3)}}=0.7Xmax{0,min{0.3,0.6}}=0.21⑶再由r3求CF1(H)CF1(H)=0.8Xmax{0,CF(E4)}=0.8Xmax{0,0.21)}=0.168再由r4求CF2(H)CF2(H)=0.9Xmax{0,CF(E5)}=0.9Xmax{0,0.7)}=0.63最后对CF1(H)和CF2(H)进行合成，求出CF(H)CF(H)=CF1(H)+CF2(H)---CF1(H)XCF2(H)=0.692(六)机器学习设训练例子集如下表所示:序号属性分类x1x21TT+2TT+3TF-4FF+5FT6FT请用ID3算法完成其学习过程。解：设根节点为S,尽管它包含了所有的训练例子，但却没有包含任何分类信息，因此具有最大的信息熵。即：H(S)=-(P(+)log2P(+)+P(-)log2P(-))式中P(+)=3/6，P(-)=3/6分别是决策方案为“+”或“-”时的概率。因此有H(S)=-((3/6)log2(3/6)+(3/6)log2(3/6))=1按照ID3算法，需要选择一个能使S的期望熵为最小的一个属性对根节点进行扩展，因此我们需要先计算S关于每个属性的条件熵：H(Slx.)=(ISTI/ISI)*H(St)+(ISFI/ISI)*H(Sf)其中，T和F为属性x.的属性值，ST和SF分别为x.=T或x.=F时的例子集，ISI、ISTI和ISFI分别为例子集S、ST和SF的大小。 * *下面先计算S关于属性x1的条件熵：在本题中，当x1=T时，有：ST={1，2,3}当x1=F时，有：Sf={4,5,6}其中，ST和SF中的数字均为例子集S中的各个例子的序号，且有ISI=6,ISTI=ISFI=3。由ST可知，其决策方案为“+”或“-”的概率分别是：Pst(+)=2/3PST(-)=1/3因此有：H(St)=-(PST(+)log2PST(+)+PST(-)log2PST(-))=-((2/3)log2(2/3)+(1/3)log2(1/3))=0.9183再由SF可知，其决策方案为“+”或“-”的概率分别是：PSF(+)=1/3PSF(-)=2/3则有:H伉)=-(PSF(玖唱PSF(+)+PSF。叫PSF(-))=-((1/3)1082(1/3)+(2/3)lo喙2/3))=0.9183将H(ST)»h(SF)代入条件