人工智能经典习题集和各章总结.pdf

人工智能各章小结及习题解答第 一 部 分 绪 论习题解答:1.什么是人工智能？发展过程中经历了哪些阶段？解：人工智能是计算机科学的一个重要分支，也是一门正在发展中的综合性前沿学科，它是由计算机科学、控制论、信息论、神经生理学、哲学、语言学等多种学科相互渗透而发展起来的，目前正处于发展阶段尚未形成完整体系。发展过程中经历的阶段有：第一阶段第二阶段第三阶段第四阶段第五阶段(4 0年代中5 0年代末)(5 0年代中6 0年代中)(6 0年代中8 0年代初)(8 0年代中9 0年代初)(9 0年代初现在)神经元网络时代通用方法时代知识工程时代新的神经元网络时代海量信息处理与网络时代2 .人工智能研究的基本内容是什么？解：基本内容是：搜索技术、知识表示、规划方法、机器学习、认知科学、自然语言理解与机器翻译、专家系统与知识工程、定理证明、博弈、机器人、数据挖掘与知识发现、多A g ent系统、复杂系统、足球机器人、人机交互技术等。3 .人工智能主要有哪几大研究学派？解：(1)符号主义学派：由心理学途径产生，符号主义认为人工智能起源于数理逻辑，人 类认识(智能)的基本元素是符号，而智能行为则是符号运算的结果。(2)连接主义学派：由生理学途径产生，连接主义又称为仿生学派，认为人工智能的基本元素是神经元，智能产生于大量神经元的并行分布式联结之中，而智能行为则是联结计算的结果。(3)行为主义学派：由生物演化途径产生，行为主义认为人工智能起源于控制论，提出智能取决于感知和行为，取决于对外界复杂环境的适应，而不是表示和推理。4 .人工智能有哪些主要的研究领域？解：(1 )问题求解(2)逻辑推理与定理证明(3)自然语言理解(4)自动程序设计(5)专家系统(6)机器学习(7)神经网络(8)机器人学(9)模式识别(10)机器视觉(11)智能控制(12)智能检索(13)智能调度与指挥(14)分布式人工智能与A g e n t(15)计算智能与进化计算(16)数据挖掘与知识发现(17)人工生命(18)系统与语言工具第2部分 知识与知识表示本章小结:知识表示谓词表不法_ _ _ _ _ _ _ _首先定义谓词，指出每个谓词的确切含义，然后再用连接词把有关的谓词连接起来，形成一个谓词公式表达一个完整的意义。产生式表示法_ _ _ _ _ _ _产生式系统由3个基本部分组成：规则库、综合数据库、控制系统。框架表不法_ _ _ _ _ _ _ _框架通常由指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值。_ _ _ _ _ _ _ _语义网络表示法_ _ _ _ _ _语义网络由节点和弧线或链线组成，节点用于表小物体、概念和状态，弧线用于表示节点间的关系。习题解答：1设有如下问题：(1)有五个相互可直达且距离已知的城市A、B、C,D、E,如图所示;(2)某人从A地出发，去其它四个城市各参观一次后回到A;(3)找一条最短的旅行路线请用产生式规则表示旅行过程。解：综合数据库(x)(X)中X可以是一个字母，也可以是一个字符串。初始状态(A)目标状态(Ax1x2x3x4A)规则集：r1:IFL(S)=5THENGOTO(A)r2:IFL(S)5THENGOTO(B)r3:IFL(S)5THENGOTO(C)r4:IFL(S)5THENGOTO(D)r5:IFL(S)C-D-E-B-A总距离为 5+6+8+10+7=362 神州大学和东方大学两校篮球队在东方大学进行一场比赛，结局的比分是85：8 9,用语义网络表示。客队 结局主 队 一第3 部 分 推 理本章小结:自然演绎推理经典逻辑推理归结演绎推理推理_ _ _ _ _ _ _ _ _ _ _ _ _ _ 与/或形演绎推理_ _ _ _ _ 不确定与非单调推理习题解答：1 张某被盗，公安局派出五个侦察员去调查。研究案情时，侦察员A 说“赵与钱中至少有一人作案”；侦察员B 说“钱与孙中至少有一人作案”；侦察员C 说“孙与李中至少有一人作案”；侦察员D 说“赵与孙中至少有一人与此案无关”；侦察员E 说“钱与李中至少有一人与此案无关”。如果这五个侦察员的话都是可信的，试用归结演绎推理求出谁是盗窃犯。解：第一步：将 5 位侦察员的话表示成谓词公式，为此先定义谓词。设谓词P(x)表示是作案者，所以根据题意：A:P(zhao)V P(qian)B:P(qian)V P(sun)C:P(sun)V P(li)D:-P(zhao)V P(sun)E:-P(qian)V-P(li)以上每个侦察员的话都是一个子句。第二步：将待求解的问题表示成谓词。设 y 是盗窃犯，则问题的谓词公式为P(y),将其否定并与ANSWER(y)做析取：P(y)V ANSWER(y)第三步：求前提条件及P(y)V ANSWER(y)的子句集，并将各子句列表如下：(1)P(zhao)V P(qian)(2)P(qian)V P(sun)(3)P(sun)V P(li)(4)-P(zhao)V-P(sun)(5)-P(qian)V-P(li)(6)P(y)V ANSWER(y)第四步：应用归结原理进行推理。(7)P(qian)V-iP(sun)(1)与(4)归结(8)P(zhao)V-P(li)(1)与(5)归结(9)P(qian)V-P(zhao)(2)与(4)归结(10)P(sun)V-P(li)(2)与(5)归结(11)-P(zhao)V P(li)(3)与(4)归结(12)P(sun)V P(qian)(3)与(5)归结(13)P(qian)(2)与(7)归结(14)P(sun)(2)与(12)归结(15)ANSWER(qian)(6)与(13)归结，o=qian/y(16)ANSWER(sun)(6)与(14)归结,o=sun/y所以，本题的盗窃犯是两个人：钱和孙。2 任何兄弟都有同一个父亲，John和 Peter是兄弟，且 John的父亲是D avid,问 Peter的父亲是谁？解：第一步：将已知条件用谓词公式表示出来，并化成子句集。那么，要先定义谓词。(1)定义谓词：设 Father(x,y)表示x 是 y 的父亲。设 Brother(x,y)表示x 和 y 是兄弟。(2)将已知事实用谓词公式表示出来：F 1:任何兄弟都有同一个父亲。(吊(y)Vz)(rother(x,y)A Father(z,x)-Father(z,y)F2:John 和 Peter 是兄弟。Brother(John,Peter)F3:John 的父亲是 DavidoFather(David,John)(3)将它们化成子句集，得S1=-Brother(x,y)V-Father(z,x)V Father(z,y),Brother(John,Peter),Father(David,John)第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER做析取。设 Peter 的父亲是 u,则有：Father(u,Peter)将其否定与ANSWER做析取，得G:-iFather(u,Peter)V ANSWER(u)第三步：将上述公式G 化为子句集S 2,并将S 1和 S 2 合并到S。S2=-Father(u,Peter)V ANSWER(u)S=S1 US2将 S 中各子句列出如下：(1)Brother(x,y)V Father(z,x)V Father(z,y)(2)Brother(John,Peter)(3)Father(David,John)(4)Father(u,Peter)V ANSWER(u)第四步：应用归结原理进行归结。(5)Brother(John,y)V Father(David,y)(1)与(3)归结，。=David/z,John/x(6)-Brother(John,Peter)V ANSWER(David)(4)与(5)归结，a=David/u,Peter/y(7)ANSWER(David)(2)与 归结第五步：得到了归结式ANSWER(David),答案即在其中，所以gDavid,即 Peter的父亲是David。第4 部 分 搜 索 策 略本章小结:状态空间广度优先搜索_ 深度优先搜索r盲目搜索一_ 有界深度优先搜索_ 代价树的广度优先搜索一搜索策略一L启发式搜索搜索策略一_ 盲目搜索_与/或树一搜索策略一L代价树的深度优先搜索局部择优搜索_ _ 全局择优搜索_ A*算法广度优先搜索_ 深度及有界深度优先搜索L有序搜索特殊情况 提高搜索效率的方法博城问题.Q.剪枝技术博弈问题：极大极小分析法：计算出端节点的估值，再推算出父节点的得分。推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。a-p剪枝技术：对于一个“与”节点来说，它取当前子节点中的最小倒推值作为它倒推值的上界，称此值为B值。对于一个“或”节点来说，它取当前子节点中的最大倒推值作为它倒推值的下界，称此值为。值。其一般规律为：（1）任何“或”节点x的a值如果不能降低其父节点的B值，则对节点x以下的分枝可停止搜索，并使x的倒推值为a。这种剪枝成为B剪枝。（2）任何“与”节点x的p值如果不能升高其父节点的a值，则对节点x以下的分校可停止搜索，并使x的倒推值为p0这种剪枝成为a剪枝。习题解答：1图4-1是五城市间的交通路线图，A城市是出发地，E城市是目的地，两城市间的交通费用（代价）如图中数字所示。求从A到E的最小费用交通路线。解：先将交通图转换为代价树，如图4-2所示。若用g(x)表示从初始节点SO到节点X的代价，用 C(x1,x2)表示从父节点X1到子节点X2的代价，则有:g(x2)=g(x1)+c(x1,x2)图4-2方法一：代价树的广度优先搜索(扩展节点n,将其子节点放入open表中，计算各子节点的代价，并按各节点的代价对open表中全部节点按从小到大的顺序进行排序(队列)步骤如下：图 4-3-3图 4-3-488 9 io图 4-3-5所以，最优路径为A-C-D-E方法二：代价树的深度优先搜索（不一定是最优解）（扩展节点n,将其子节点按代价从小到大的顺序放到。pen表的首部（栈）步骤如下：5虽 然D 1的 代 价 大 于B 1的代价，但按照代价树的深度优先搜索策略，要 对D 1进行扩展,放 入closed表 中（若按代价树的广度优先搜索,要 对B l、D 1排 序，先 扩 展B1）图 4-4-2图 4-4-3E为目标节点，E2-D1-C1-A所以路径为A-C-D-E注：该题代价树的深度优先搜索与代价树的广度优先搜索的结果相同，但这只是巧合。一般情况下，这两种方法得到的结果不一定相同。另外，由于代价树的深度优先搜索有可能进入无穷分支的路径，因此它是不完备的。2如下图4-5所示，分别用代价树的广度优先搜索策略和代价树的深度优先搜索策略,求A到E的最短费用路径。图4-5解：先将其化成代价树，如图4-6：(1)代价树的广度优先搜索，步骤如下:图 4-7-1图 4-7-2图 4-7-3E为目标节点，路径为A-C-E,代价为15。（2）代价树的深度优先搜索，步骤如下:A图 4-8-2虽然C 1代价低于D 1,但按照代价树的深度优先搜索策略，对D1进行扩展，放入closed表中，因为B1扩展的节点为D1,而C1是A节点扩展得到的。E出栈，为目标节点，结束。故解路径为A-B-D-E,代价为1 7,不是最优解。注：深度优先搜索是不完备的，即使问题有解，也不一定能求得解。得到的解也不一定是最优解（因为是局部优先搜索）。3下图是五城市间的交通费用图，若从西安出发，要求把每个城市都访问一遍，最后到达广州，请找一条最优路线。边上的数字是两城市间的交通费用。A西安SO图4-9上海D解：先画出代价树:图 4-10按代价树的广度优先搜索即可得出最优路线，步骤如下:图4-11-1图4-11-2图 4-11-4375图4-11-5故由此得出最优路线为A-B1-D2-C4-E12即A-B-D-C-E,交通费用为375。4设有如图所示的一棵与/或树，请分别用与/或树的广度优先搜索及与/或树的深度优先搜索求出解树。解：(1)与/或树的广度优先搜索先扩展节点A,得到节点B和C,再扩展节点B,得节点t1、t 2,因为t1、t2为可解节点，故节点B可解，从而可节点A可解。所以求得解树为：O A(2)与/或树的深度优先搜索先扩展节点A,得到节点B和C,再扩展节点C,得节点D和t5,t5为可解节点，再扩展节D,得节点t3、t 4,因为t3、t4为可解节点，故节点D可解，因为节点D和t5可解，故节点C可解，从而可节点A可解。所以求得解树为：t4t35设有如图所示的与/或树，请分别按和代价法及最大代价法求解树代价。(1)按和代价法：h(B)=7,h(C)=3,h(A)=7+3+5+6=21(2)按最大代价法：h(B)=5,h(C)=2,h(A)=5+5=101、谈谈你对于人工智能的认识。人工智能就是人造智能，目前指用计算机模拟或实现的智能，因此人工智能乂称机器智能。人工智能在我看来，应该是像人一样思考的系统、像人一样行动的系统、理性地思考的系统、理性地行动的系统，是像人一样具有感知的系统，是可以独立思考、独立判断的系统2、人工智能有哪些研究途径和方法？它们的关系如何？心理模拟，符号推演;生理模拟，神经计算;行为模拟，控制进化;群体模拟，仿生计算;博采广鉴，自然计算;原理分析，数学建模；它们各有所长，也都有一定的局限性，因此这些研究途径和方法并不能互相取代，而是并存和互补的关系。3、人工智能有哪些研究内容？搜索与求解、学习与发现、知识与推理、发明与创造、感知与交流、记忆与联想、系统与建造、应用与工程等八个方面。4、人工智能有哪些分支领域和研究方向？从模拟的智能层次和所用的方法看，可分为符号智能和计算智能两大领域：从模拟的脑智能或脑功能看，可分为机器学习、机器感知、机器联想、机器推理、机器行为等分支领域；从应用角度看，可分为难题求解、自动规划、调度与配置、机器定理证明、自动程序设计、机器翻译、智能控制、智能管理、智能决策、智能通信、智能仿真、智 能CAD、智能制造、智 能CAI、智能人机接口、模式识别、数据挖掘与数据库中的知识发现、计算机辅助创新、计算机文艺创作、机罂博弈、智能机器人；从系统角度看，可分为智能计算机系统和智能应用系统：从基础理论看，可分为数理逻辑和多种非标准逻辑、图论、人工神经网络、模糊集、粗糙集、概率统计和贝叶斯网络、统计学习理论与支持向量机、形式语言与自动机等领域；5、人工智能有哪些应用领域或课题？试举例说明难题求解、自动规划、调度与配置、机器定理证明、自动程序设计、机器翻译、智能控制、智能管理、智能决策、智能通信、智能仿真、智 能CAD、智能制造、智 能CAI、智能人机接口、模式识别、数据挖掘与数据库中的知识发现、计算机辅助创新、计算机文艺创作、机器博弈、智能机器人。就机器博弈方面，在1997年 旧M的“深蓝”计算机以2胜3平1负的战绩击败了蝉联12年之久的直接国际象棋冠军加里卡斯帕罗夫,比如先如今中的五子棋对弈，能实现人与电脑之间的下棋，电脑自动搜索棋步，还可根据人们所选的电脑难度来决定电脑的难易程度。6、简述人工智能的发展状况人工智能的现状和发展呈现如下特点：多种途径齐头并进，多种方法写作互补；新思想、新技术不断涌现，新领域、新方向不断开括;理论研究更加深入，应用研究更加广泛;研究队伍日益壮大，社会影响越来越大;以上特点展现了人工智能学科的繁荣景象和光明前景。它表明，虽然在通向其最终目标的道路上，还有不少困难、问题和挑战，但前进和发展毕竟是大势所趋。7、试编写一个描述亲属关系的PROLOG程序，然后再给出一些事实数据，建立一个小型演绎数据库。domainsname=symbol.sex=symbol.age=integer.predicatesperson(name,sex,age)mother(name,name)father(name,name)brother(name,name)sister(name,name)grandfather(name,name)grandmother(name.name)goalbrother(Name1,Name2),write(Name1is M,Name2,s brother!n M),sister(Name3,Name4),write(Name3,n is,Name4,s sister!n),grandfather(Name5,Name6),write(Name5,is,Name6,s grandfather!n),grandmother(Name7,Name8),write(Name7,is M,Name8/s grandmother!n).clausesperson(alan,m,21).person(john,m,22).person(marry,w,23).person(ann,w,24).mother(alice,alan).mother(alicejohn).mother(alice,marry).mother(alice,ann).mother(marryjane).father(alan,tom).father(tom,ben).brother(Name1,Name2):-person(Name1,m,Age1),person(Name2,m,Age2),mother(Z,Name1),motheZ,Name2),Age1 Age2.sister(Name3,Name4):-person(Name3,w,Age3),person(Name4,w,Age4),mother(Z,Name3),mother(Z,Name4),Age3Age4.grandfather(Name1,Name2):-father(Name1,Y),father(Y,Name2).grandmother(Name7,Name8):-mother(Name7,X),mother(X,Name8).8 .何为状态图和与或图？图搜索与问题求解有什么关系？状态图是描述寻找目标或路径问题的有向图，即描述一个实体基于事件反应的动态行为，显示了该实体如何根据当前所处的状态对不同的时间做出反应的。与或图是种系统地将问题分解为互相独立的小问题，然后分而解决的方法。与或图中有两种代表性的节点：“与节点”和“或节点”，“与节点”指所有的后续节点都有解时它才有解；“或节点”指各个后续节点均完全独立，只要其中有一个有解它就有解。关系：问题求解就是在一个图中寻找个从初始节点到目标节点的路径问题，图搜索模拟的实际是人脑分析问题，解决问题的过程，它基于领域知识的问题求解过程。9.综述图搜索的方式和策略。答：图搜索方式可分为树式搜索和线式搜索。图搜索策略可分为盲目搜索和启发式搜索。10.什么是问题的解？什么是最优解？答：能够解决问题的方法或具体做法。其中最好的解决方法即代价最小的解称为最优解。11.什么是与或树？什么是可解节点？什么是解树？答：一棵树中的弧线表示所连树枝为“与”关系，不带弧线的树枝为或关系。这棵树中既有与关系又有或关系，因此被称为与或树。满足下列条件的节点为可解节点。终止节点是可解节点；一个与节点可解，当且仅当其子节点全都可解；一个或节点可解，只要其子节点至少有一个可解。解树实际上是由可解节点形成的一棵子树，这棵子树的根为初始节点，叶为终止节点，且这棵子树一定是与树。12.设有三只琴键开关一字排开，初始状态为“关、开、关”，问连按三次后是否会出现“开、开、开”或“关、关、关”的状态？要求每次必须按下一个开关，而且只能按一个开关。请画出状态空间图。解：用(K1,K2,K3)表示三个开关的状态，取值为0时表示闭合，为1时表示打开。则初始状态为(0,1,0)o根据题设要求，一个状 态I的下一个状态和I只能有一位取值不同(此即状态转换规则)，据此可以画出状态空间图。从此状态图不难看出：经过连续三步有状态(0,1,0)只能到达状态(0,0,0)而不能到达状态(1,1,1),即会出现状态“关，关，关”,但不会出现“开,开，开”。13.有一农夫带一只狼、一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件限制：(1)船太小，农夫每次只能带一样东西过河。(2)如果没有农夫看管，则狼要吃羊，羊要吃菜。请设计一个过河方案，使得农夫、狼、羊、菜都能不受损失地过河。画出相应的状态空间图。提示：（1）用四元组（农夫、狼、羊、菜）表示状态,其中每个元素都可为0或1,用0表示在左岸，用1表示在右岸。（2）把每次过河的一种安排作为个算符，每次过河都必须有农夫，因为只有他可以划船。解：初始 S=(0,0,0,0),目标 G=(1,1,1,1)定义操作符L（i）表示农夫带东西到右岸:i=0农夫自己到右岸；i=1农夫带狼到右岸；i=2农夫带羊到右岸；i=3农夫带菜到右岸；约束状态如下：定义操作符R（i）表示农夫带东西到左岸:i=0农夫自己到左岸；i=1农夫带狼到左岸；i=2农夫带羊到左岸；i=3农夫带菜到左岸；(1,0,0,X）狼、羊在左岸;(1,X,0,0）羊、菜在左岸;(0,1,1,X）狼、羊在右岸;(0,X,1,1）羊、菜在右岸;解二：1.带羊过河(1,0,1,0）2.农夫配(0,0,1,0）3建狼过河(b1,b 0）4 一带羊回来(0,1,0,0）5.带菜过河(1,1,0,1)6 一农夫叫(0,1,0,1)7.带羊过河(1,1,1,1)1解二:1.带羊过河(1,0,1,0)。2.农夫回来(0,0,1,0)23.带菜过河(1,0,1,4.带羊回来(0,0,0,5 过河(1,1,0,6.农夫回来(0,1,0,7.带羊过河(1，1,1,(0,0,0,0”/式2)。(1,0,1,0)，(0,0,1,0)。/U i)R(3(I,b 1,0)(1,0,1,1)。&2)R(2(0,b o,0)(0,0,0,l)pU3)/L(l(I,1,0,1*贰(0,I,o,1”(1,1,1,1W14.请阐述状态空间的一般搜索过程。OPEN表与CLOSED表的作用是什么？答：先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。所谓对一个节点进行“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。OPEN表用于存放刚生成的节点，对于不同的搜索策略，节点在OPEN表中的排序是不同的。CLOSED表用于存放将要扩展或者已扩展的节点。15.广度优先搜索与深度优先搜索各有什么特点？答：广度优先搜索就是始终先在同一级节点中考查，只有当同级节点考查完之后，才考查下一级节点。或者说，是以初始节点为根节点，向下逐级扩展搜索树。所以，广度优先策略的搜索树是自顶向下一层一层逐渐生成的。深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进，直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。深度优先搜索亦称为纵向搜索。由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解(最短路径)。广度优先搜索与深度优先搜16.是五大城市间的交通示意图，边上的数字是两城市间的序，求解以下问题：解：domains p=stringd=integer pp=p*predicates road(p,p,d)path(p,p,pp,d)member(p,pp)clausespath(X,Y,L,D):-road(X,Y,D),L=X|Y.索都属于盲目搜索。path(X,Y,L,D):-road(X,Z,D1),%从当前点向前走到下一点Znot(member(Z,L),path(Z,Y,ZL,D2),D=D1+D2.%再找 Z 到出口 丫 的路径member(X,X|_).member(X,_|T)if member(X,T).road(A,B,D):-road(B,A,D).因为没向图/*交通图*/road(“西安”,”北京”,1165).road(“西安”，“广州”,2129).road(“昆明”,”北京”,3179).road(“昆明”，“广州”,2216).road(“上 海 北 京,1462).road(“西安，”上海”,1511).road(“西安”,”昆明”,1942).road(“昆明”,”上海”,2677).road(“北京”,”广州”,2510).road(“广 州 上 海”,1511).(1)path(“西安”；北京”,L,D),wDe(L,D).(2)path(“西安”,”北京”,L,D),member(上海”,L),write(L,D).(3)path(“西 安 北 京”,L,D),member(“上海”,L),not(member(“昆明”,L),write(L.D).17 .何谓估价函数？在估价函数中,g(x)和/)(x)各起什么作用？答：估价函数用来估计节点重要性的函数。估价函数f(x)被定义为从初始节点S 0 出发，约束经过节点x 到达目标节点S g 的所有路径中最小路径代价的估计值。它的一般形式为：f(x)=g(x)+h(x)其中，g(x)是从初始节点S0到节点x 的实际代价；h(x)是从节点x 到目标节点S g的最优路径的估计代价。18.局部择优搜索与全局择优搜索的相同处与区别各是什么？答：局部择优搜索与全局择优搜索的区别是，扩展节点N 后仅对N 的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的首部。故算法从略。19.传教士和野人问题。有三个传教士和三个野人一起来到河边准备渡河，河边有一条空船，且传教士和野人都会划船，但每次最多可供两人乘渡。河的任何一岸以及船上一旦出现野人人数超过传教士人数，野人就会把传教士吃掉。为安全地渡河，传教士应如何规划渡河方案？试给出该问题的状态图表示，并用PROLOG语言编程求解之。若传教士和野人的数目均为五人，渡船至多可乘三人，请定义一个启发函数，并给出相应的搜索树。解：首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸。从而可用一个三元组来表示状态：S=(m,c,b)其中，m 表示左岸的修道士人数，c 表示左岸的野人数，b 表示左岸的船数。右岸的状态可由下式确定：右岸修道士数：m=3-m；右岸野人数：c=3-c；右岸船数：b=1-b在这种表示方式下，m 和 c 都可取0、1、2、3 中之一，b 可取。和 1 中之一。因此，共有4x4x2=32种状态。这 32种状态并非全有意义，除去不合法状态和修道士被野人吃掉的状态，有意义的状态只有16种：So=(3,3,1)S4=(1,1,1)S8=(3,2,0)Si=(3,2,1)S5=(0,3,1)S9=(3,1,0)S2=(3,1,1)S6=(0,2,1)Sio=(3,0,0)Sl2=(1,1,0)Si3=(0,2,0)Si4=(0,1,0)S3=(2,2,1)S7=(0,1,1)Sn=(2,2,0)Si5=(0,0,0)有了这些状态，还需要考虑可进行的操作。操作是指用船把修道士或野人从河的左岸运到右岸,或从河的右岸运到左岸。每个操作都应当满足如下条件:一是船至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目；二是每次操作船上人数不得超过2个；三是操作应保证不产生非法状态。因此，操作应由条件部分和动作部分：条件：只有当其条件具备时才能使用动作：刻划了应用此操作所产生的结果。操作的表示：用符号Pij表示从左岸到右岸的运人操作用符号Qu表示从右岸到左岸的操作 其中：i表示船上的修道士人数 j表示船上的野人数操作集本问题有10种操作可供选择：F=P o i,P io,P l1,P02,P2O,QO I,Q io,QU,QO2,Q20）下面以PO1和Qoi为例来说明这些操作的条件和动作。操作符号P01Q0120.设（1）凡事清洁的东西就有人喜欢（2）人们都不喜欢苍蝇用归结原理证明苍蝇是不清洁的条件b=1,m=0 或 3,c1D(X)x是不涓沽的Ux.y)x 再欢yE：Vx(-.D(y)-Ux.y)F,:Vx-Ux.a)G:D G)C(l)D(x)vUx.y)(2)-Uxui)(3)D(a)(4)Ux.a)(5)0所以览命跟成立动作b=0,c=c-1凡是清沽的东山就有人。欢人Q都不喜欢也蝇在发是不治治的(I)(3)(2)(4)b=0,m=0 或 3,cw2b=1,c=c+121.八皇后问题：答案：用八元组体0 丛2丛3丛4X5穴6/7）表示第18行的棋子，值（xO,x14243向次5K6汹）表示其在列上的位置。状态可表示为八元组的一组值。D O M A I N S-l i s t =i n t e g e r%P R E D I C A T E S-q u e e n s (i n t e a e r,l i s t)-r a n q e(i n t e g e r,i n t e g e r,l i s t)s a f e j l i s t)a t t a c k(i n t e g e r,i n t e g e r,l i s t)*p e r m u t a t i o n (l i s t,l i s t)d e l e t e (i n t e a e r,l i s t,l i s t)*G O 小q u e e n s (8,X),w r i t e (X).i d,f a i l 利C L A U S E S q u e e n s(N,Q s)r a n g e(l,NrN s)rp e r m u t a t i o n(g sr/N s)rs a f e(Q s).*-(range(MrNrM|Ns|：-M蛔1)3S G.N/Y I)：-X=Y+N/attack(X,N,Y|)X=Y-N“attacklXJ-lYs)：-Nl=N+lrattack(X；NlrYs).-permutation(r).permutationj A|X,Y):-delete(A,Y,Y1),pemutation(X,Yl).照感乳A,【A|X,X)/deleteXA,B|X,B|Y|delete(A,X,Y).专家系统：所谓专家系统，就是基于人类专家知识的程序系统。专家系统的特点是拥有大量的专家知识（包括领域知识和经验知识），能模拟专家的思维方式，面对领域中复杂的实际问题，能作出专家水平级的决策，像专家一样解决实际问题。专家系统的特征：1）处理问题的性质：善于解决不确定、非结构化、没有算法解或虽有算法解但在现有机器上无法实施的困难问题。2）处理问题方法：靠知识和推理来解决问题3系统结构：强调知识与推理的分离，系统具有很好的灵活性和可扩充性。4具有解释功能：在运行中能回答用户提出的问题，同时还能对输出（结论）或处理问题的过程作出解释。5具有“自学牙，能力：即不断对已有知识进行扩充、完善和提炼。6专家系统它始终如一地以专家级水平求解问题。各部分功能：1知识库：以某种表示形式存储于计算机中的知识集合。知识库中的知识一般包括专家知识、领域知识和元知识。2推理机:推理机就是实现机器推理的程序，包括通常的逻辑推理和基于产生式的操作。3动态数据库：是存放初始证据事实、推理结果和控制信息的场所。4 0人机界面：最终用户与专家系统的交互界面5解释模块：专门负责向用户解释专家系统的行为和结果。6知识库管理系统:是知识库的支撑软件。其功能包括知识库的建立、删除、重组；知识的获取、知识的检查等。专家系统的应用和发展情况：医学诊断/地质勘探/物质结构分析/生物遗传研究/市场决策/生产管理。2 0世纪9 0年代模糊技术、神经网络和面向对象等新技术迅速崛起，为专家系统注入了新的活力。知识获取：知识获取是建造专家系统的关键一步，也是较为困难的一步，被称为建造专家系统的“瓶颈”。知识获取大体有三种途径。1人工获取：即计算机人员与领域专家合作，对有关领域知识和专家知识，进行挖掘、搜集、分析、综合、整理、归纳，然后以某种表示形式存入知识库。2半自动获取，即利用某种专门的知识获取系统，采取提示、指导或问答的方式，帮助专家提取、归纳有关知识，并自动记入知识库。3自动获取又可分为两种形式：一种是系统本身具有一种机制，使得系统在运行过程中能不断地总结经验，并修改和扩充自己的知识库；另一种是开发专门的机器学习系统，让机器自动从实际问题中获取知识，并填充知识库。22.有两个最优解树左解树：为最优解按和代价法，代价为：g(S0)=12,g(A)=7,g(D)=4.按最大代价法，代价为：g(S0)=10,g(A)=5,g(D)=2.g(S 0)=1 8/g(B)=ll,g(E)=2.+J按最大代价法，代价为：。g(S 0)=1 4,g(B)=7,g(E)=2 i第2章 知识表示方法部分参考答案2.8设有如下语句，请用相应的谓词公式分别把他们表示出来：s(1)有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。解：定义谓词dP(x)：x是人L(x,y)：x 喜欢 y其中，y的个体域是 梅花，菊花。将知识用谓词表示为：(3X)(P(X)-L(X,梅花)VL(X,菊花)VL(X,梅花)AL(X,菊花)(2)有人每天下午都去打篮球。解：定义谓词P(x)：X是人B(x)：x打篮球A(y)：y是下午将知识用谓词表示为：a(3 x)(V y)(A(yHB(x)AP(x)(3)新型计算机速度又快，存储容量又大。解：定义谓词NC(x)：x是新型计算机F(x)：x速度快B(x)：x容量大将知识用谓词表示为：(V x)(NC(xHF(x)AB(x)(4)不是每个计算机系的学生都喜欢在计算机上编程序。解：定义谓词S(x)：x是计算机系学生L(x,pragramming)：x 喜欢编程序U(x,computer)：x使用计算机将知识用谓词表示为：-(V x)(S(x)L(x,pragramming)A U(x,computer)(5)凡是喜欢编程序的人都喜欢计算机。解：定义谓词P(x)：x是人L(x,y)：x 喜欢 y将知识用谓词表示为：(V x)(P(x)A L(x,pragramming)L(x,computer)2.9用谓词表示法求解机器人摞积木问题。设机器人有一只机械手，要处理的世界有一张桌子，桌上可堆放若干相同的方积木块。机械手有4个操作积木的典型动作：从桌上拣起一块积木；将手中的积木放到桌之上；在积木上再摞上一块积木：从积木上面拣起一块积木。积木世界的布局如下图所示。图机器人摞积木问题解：(1)先定义描述状态的谓词CLEAR(x)：积木x上面是空的。ON(x,y)：积木x在积木y的上面。ONTABLE(x)：积木X在桌子上。HOLDING(x)：机械手抓住X。HANDEMPTY：机械手是空的。其中,x和y的个体域都是 A,B,C。问题的初始状态是：ONTABLE(A)ONTABLE(B)ON(C,A)CLEAR(B)CLEAR(C)HANDEMPTY问题的目标状态是：ONTABLE(C)ON(B,C)ON(A,B)CLEAR(A)HANDEMPTY(2)再定义描述操作的谓词在本问题中，机械手的操作需要定义以下4个谓词：Pickup(x)：从桌面上拣起一块积木x。Putdown(x)：将手中的积木放到桌面上。Stack(x,y)：在积木x上面再摞上一块积木y。Upstack(x,y)：从积木x上面拣起块积木y。其中，每一个操作都可分为条件和动作两部分，具体描述如下：Picku