ai2015期末复习

名词解释：1.人工智能2.专家系统3.机器学习4.符号主义5.联结主义6.行为主义7.模式识别8.神经计算9.进化计算10.智能检索11.命题12.规划13.Skolem范式14.鲁滨逊归结原理15.自由变元16.约束变元简答题：1.人工智能三个学派是如何理解人工智能？2.自立估价函数，用A或A*算法给出下图启发信息优先搜索树。初始状态目标状态解：f(n)=d(n)+P(n),d(n)为搜索树深度，P(n)为定义为每一数码到其目标位置之间距离和，显然满足P(n)=h*(n)3.在选择知识表示方法时，应考虑哪些因素？答：（1）是否充分表示相关的领域知识（2）是否有利于对知识的利用（3）是否便于知识的组织、维护和管理（4）是否便于理解和实现4.什么是产生式系统，它的基本组成及各部份作用。答：把一组产生式放在一起，让它们相互配合，协同作用，一个产生式生成的结论可以供另一个产生式作为已知事实使用，以求得问题的解决，这样的系统称为产生式系统。产生式系统由3个部分构成：规则库、综合数据库、推理机规则库：是用于描述某领域内知识的产生式集合，是某领域知识的存储器。综合数据库：又称事实库。用于存放输入的事实、外部数据库输入的事实以及中间结果和最后结果的工作区。推理机：是一个或一组程序，用来控制和协调规则库与综合数据库的运行，包含推理方式和控制策略。5.一阶谓词表示：P29例2.1-例2.3设有如下语句，请用相应的谓词公式分别把他们表示出来：s(1)有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。解：定义谓词dP(x)：x是人L(x,y)：x喜欢y其中，y的个体域是{梅花，菊花}。将知识用谓词表示为：(x)(P(x)→L(x,梅花)∨L(x,菊花)∨L(x,梅花)∧L(x,菊花))(2)有人每天下午都去打篮球。解：定义谓词P(x)：x是人B(x)：x打篮球A(y)：y是下午将知识用谓词表示为：a(x)(y)(A(y)→B(x)∧P(x))(3)新型计算机速度又快，存储容量又大。解：定义谓词NC(x)：x是新型计算机F(x)：x速度快B(x)：x容量大将知识用谓词表示为：(x)(NC(x)→F(x)∧B(x))(4)不是每个计算机系的学生都喜欢在计算机上编程序。解：定义谓词S(x)：x是计算机系学生L(x,pragramming)：x喜欢编程序U(x,computer)：x使用计算机将知识用谓词表示为：¬(x)(S(x)→L(x,pragramming)∧U(x,computer))(5)凡是喜欢编程序的人都喜欢计算机。解：定义谓词P(x)：x是人L(x,y)：x喜欢y将知识用谓词表示为：(x)(P(x)∧L(x,pragramming)→L(x,computer))(6)并不是每一个人都喜欢吃海鲜。答：定义谓词MAN(X):X是人LIKE(X,Y):X喜欢吃Y),()()(HaixianXLIKEXMANX（7）欲穷千里目，更上一层楼。答：定义谓词MAN(X):X是人EYE(X):X想穷千里目UP(X):X要更上一层楼))()()()((XUPXEYEXMANX（8）张晓辉是一名计算机系的学生，但他不喜欢编程序COMPUTER(x):x是计算机系的学生LIKE(x,y):x喜欢yCOMPUTER(zhangxh)~LIKE(zhangxh,programming)（9）李晓鹏比他父亲长得高HIGHER(x,y):x比y高father(lixp):李晓鹏的父亲HIGHER(lixp,father(lixp))（10）综合性知识表示：（1）如果录取A而不录取B，则一定录取C；（2）如果录取B，则一定录取C；（3）三人中至少要录取一个人；ABCBCABC6.一阶谓词逻辑表示法适合于表示哪种类型知识？它有哪些特点？答:一阶谓词逻辑表示法适用于表示确定性的知识。它具有自然性、精确性、严密性及易用性等特点。7.请写出一阶谓词逻辑表示法表示知识的步骤。答：（1）定义谓词及个体，确定每个谓词及个体的确切含义。（2）根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。（3）根据所要表达的知识的语义，用适当的连接符号将各个谓词连接起来，形成谓词公式。8.请写出用状态空间表示法表示问题的一般步骤。答：（1）定义状态的描述形式（2）用所定义的状态描述形式把问题的所有可能的状态都表示出来，并确定问题的初始状态集合描述和目标状态集合描述。（3）定义一组算符。使用利用这组算符可把问题由一种状态转变为另一种状态。9.产生式系统求解问题的一般步骤。答：（1）初始化综合数据库，把问题的初始化已知事实送入综合数据库中。（2）若规则库中存在尚未使用过的规则，而且它的前提可与综合数据库中的已知事实匹配，则转第（3）步;若不存在这样的事实，则转第（5）步。（3）执行当前选中的规则，并对该规则做上标记，把该规则执行后得到的结论送入综合数据库中。如果该规则的结论部分指出的是某些操作，则执行这些操作。（4）检查综合数据库中是否已包含了问题的解，若已包含，则终止问题的求解过程；否则转第（2）步。（5）要求用户提供进一步的关于问题的已知事实，若能提供，则转第（2）步；否则终止问题的求解过程。（6）若规则库中不再有未使用过的规则，则终止问题的求解过程。10.什么是启发式搜索，什么是启发式信息？答：启发式搜索是在搜索中加入了与问题有关的启发性信息，以指导搜索朝着最有希望的方向进行，从而加速问题的求解过程并找到最优解。启发式信息是可用于指导搜索过程，且与具体问题求解有关的控制性信息。11.什么是估价函数？在估价函数中，g(x)和h(x)含义？答：估价函数是用于评估节点重要性的函数，其一般形式为：f(x)=g(x)+h(x)g(x)为从初始节点到节点x已经实际付出的代价，h(x)是从节点x到目标节点的最优路径的估计代价，它体现了问题的启发性信息。12.试比较无代价宽度优先搜索、有代价的宽度优先搜索与全局择优搜索三者之间的差异。答：（1）.三种搜索是基于宽度优先搜索的，但无代价宽度优先搜索是严格按搜索树的“层”的方向搜索，有代价宽度优先搜索与全局择优搜索的搜索方向不是按层扩展的。（2）.全局择优搜索：f(x)=g(x)+h(x)有代价宽度优先搜索：上式h(x)=0或常量时。无代价宽度优先搜索：上式h(x)=0或常量,g(x)=常量（各节点的代价相等时）。（3）.无代价宽度优先搜索和有代价宽度优先搜索都是完备的，但全局择优搜索是非完备的。（4）.如果三种算法都能找到问题的解路径而成功终止，那么，无代价优先搜索生成的代价树规模较大。全局择优搜索生成的代价树取决于启发函数设计的合理性。13.A算法的求解步骤14.A算法与A*算法的区别15.A*算法应用举例P88-8916.画出专家系统一般的组成框图。17.简述专家系统各组成的主要功能。18.建造专家系统的基本要求是什么？答：a)选择一个适合建造专家系统的应用领域或实际问题，要考虑是否有使用专家系统的需求，是否适合用专家系统来解决，领域专家的经验是否易于获得。b)建造专家系统可行性，包括经济可行性、技术可行性和操作可行性。c)要有领域专家的积极参与。d)专家知识的可表达性，它直接关系到专家系统中知识的有效性。19.写出将谓词公式转为子句集的步骤。20.把下列谓词公式化成子句集：P56-P59(1)(x)(y)(P(x,y)∧Q(x,y))(2)(x)(y)(P(x,y)→Q(x,y))(3)(x)(y)(P(x,y)∨(Q(x,y)→R(x,y)))(4)(x)(y)(z)(P(x,y)→Q(x,y)∨R(x,z))解：(1)由于(x)(y)(P(x,y)∧Q(x,y))已经是Skolem标准型，且P(x,y)∧Q(x,y)已经是合取范式，所以可直接消去全称量词、合取词，得{P(x,y),Q(x,y)}再进行变元换名得子句集：S={P(x,y),Q(u,v)}(2)对谓词公式(x)(y)(P(x,y)→Q(x,y))，先消去连接词“→”得：(x)(y)(¬P(x,y)∨Q(x,y))此公式已为Skolem标准型。再消去全称量词得子句集：S={¬P(x,y)∨Q(x,y)}(3)对谓词公式(x)(y)(P(x,y)∨(Q(x,y)→R(x,y)))，先消去连接词“→”得：(x)(y)(P(x,y)∨(¬Q(x,y)∨R(x,y)))此公式已为前束范式。再消去存在量词，即用Skolem函数f(x)替换y得：(x)(P(x,f(x))∨¬Q(x,f(x))∨R(x,f(x)))此公式已为Skolem标准型。最后消去全称量词得子句集：S={P(x,f(x))∨¬Q(x,f(x))∨R(x,f(x))}(4)对谓词(x)(y)(z)(P(x,y)→Q(x,y)∨R(x,z))，先消去连接词“→”得：(x)(y)(z)(¬P(x,y)∨Q(x,y)∨R(x,z))再消去存在量词，即用Skolem函数f(x，y)替换z得：(x)(y)(¬P(x,y)∨Q(x,y)∨R(x,f(x,y)))此公式已为Skolem标准型。最后消去全称量词得子句集：S={¬P(x,y)∨Q(x,y)∨R(x,f(x,y))}19、把下列谓词公式分别化成相应的子句集～（x）（y）（z）｛P（x）（x）[Q（x,y）R（z）]｝解：原式=(x)(y)(z)~｛P（x）（x）[Q（x,y）R（z）]｝=(x)(y)(z)~{~P（x）（x）[Q（x,y）R（z）]}=(x)(y)(z)~{~P（x）（x）[~Q（x,y）R（z）]}=(x)(y)(z){P（x）(x)[Q（x,y）~R（z）]}=(x)(y)(z){P（x）[Q（f(y,z),y）~R（z）]}={P（H）Q（f(y,z),y）~R（z）}子句集：P（H）,Q（f(y,z),y）,~R（z）已知A:（x）（（y）（P（x,y）Q（y））（y）(R（y）T（x,y）））B:~(x)R（x）（x）(y)（P（x,y）～Q（y））求证：B是A的逻辑结论证明：对A求子句集：（1）～（P（x,y）～Q（y）R（f（x））（2）～（P（x,y）～Q（y）T（x，f（x））对～B求子句集：（3）～(R（z）（4）P（a，b）（5）Q（b）下面进行归结（6）～P（x,y）～Q（y）（1）与（3）归结，=｛f（x）/z｝（7）～Q（b）（4）与（6）归结，=｛a/x，b/y｝（8）NIL（空子句）（5）与（7）归结所以B是A的逻辑结论20、任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问Peter的父亲是谁？解：第一步：将已知条件用谓词公式表示出来，并化成子句集。那么，要先定义谓词。（1）定义谓词：设Father(x,y)表示x是y的父亲。设Brother(x,y)表示x和y是兄弟。将已知事实用谓词公式表示出来：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)（2）将它们化成子句集，得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