人工智能习题集及各章小结.doc

人工智能各章小结及习题解答第一部分 绪论习题解答：1．什么是人工智能？发展过程中经历了哪些阶段？解：人工智能是计算机科学的一个重要分支，也是一门正在发展中的综合性前沿学科，它是由计算机科学、控制论、信息论、神经生理学、哲学、语言学等多种学科相互渗透而发展起来的，目前正处于发展阶段尚未形成完整体系 发展过程中经历的阶段有： 第一阶段（40年代中～50年代末） 神经元网络时代第二阶段（50年代中～60年代中） 通用方法时代第三阶段（60年代中～80年代初） 知识工程时代第四阶段（80年代中～90年代初） 新的神经元网络时代第五阶段（90年代初～现在） 海量信息处理与网络时代2．人工智能研究的基本内容是什么？解：基本内容是：搜索技术、知识表示、规划方法、机器学习、认知科学、自然语言理解与机器翻译、专家系统与知识工程、定理证明、博弈、机器人、数据挖掘与知识发现、多Agent系统、复杂系统、足球机器人、人机交互技术等3．人工智能主要有哪几大研究学派？解：（１）符号主义学派：由心理学途径产生，符号主义认为人工智能起源于数理逻辑，人　　类认识（智能）的基本元素是符号，而智能行为则是符号运算的结果。

　（２）连接主义学派：由生理学途径产生，连接主义又称为仿生学派，认为人工智能的基本元素是神经元，智能产生于大量神经元的并行分布式联结之中，而智能行为则是联结计算的结果 （３）行为主义学派：由生物演化途径产生，行为主义认为人工智能起源于控制论，提出智能取决于感知和行为，取决于对外界复杂环境的适应，而不是表示和推理４．人工智能有哪些主要的研究领域？解：（１）问题求解　（２）逻辑推理与定理证明　（３）自然语言理解　（４）自动程序设计　（５）专家系统　（６）机器学习　（７）神经网络　（８）机器人学　（９）模式识别　（１０）机器视觉　（１１）智能控制　（１２）智能检索　（１３）智能调度与指挥　（１４）分布式人工智能与Ａｇｅｎｔ　（１５）计算智能与进化计算　（１６）数据挖掘与知识发现　（１７）人工生命　（１８）系统与语言工具第2部分 知识与知识表示本章小结：知识表示谓词表示法产生式表示法框架表示法语义网络表示法框架通常由指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值语义网络由节点和弧线或链线组成，节点用于表示物体、概念和状态，弧线用于表示节点间的关系产生式系统由3个基本部分组成：规则库、综合数据库、控制系统。

首先定义谓词，指出每个谓词的确切含义，然后再用连接词把有关的谓词连接起来，形成一个谓词公式表达一个完整的意义 习题解答：1 设有如下问题：（1）有五个相互可直达且距离已知的城市A、B、C、D、E，如图所示；（2）某人从A地出发，去其它四个城市各参观一次后回到A;（3）找一条最短的旅行路线请用产生式规则表示旅行过程解：①综合数据库（x）(x)中x可以是一个字母，也可以是一个字符串②初始状态（A）③目标状态（Ax1x2x3x4A） ④规则集： r1: IF L(S)=5 THEN GOTO(A) r2: IF L(S)<5 THEN GOTO(B) r3: IF L(S)<5 THEN GOTO(C) r4: IF L(S)<5 THEN GOTO(D) r5: IF L(S)<5 THEN GOTO(E)其中L(S)为走过的城市数，GOTO(x)为走向城市x⑤路线如下图所示:( A )( AB )( AC )( AD )( AE )( A CB)( A CD)( ACE )( A CDB)( ACDE )( ACDEB )( ACDEBA)751010769108107起始目标最短旅行路线为：A->C->D->E->B->A总距离为5+6+8+10+7=362 神州大学和东方大学两校篮球队在东方大学进行一场比赛，结局的比分是85：89，用语义网络表示。

第3部分 推理本章小结：自然演绎推理推理经典逻辑推理不确定与非单调推理归结演绎推理与/或形演绎推理习题解答：1 张某被盗，公安局派出五个侦察员去调查研究案情时，侦察员A说“赵与钱中至少有一人作案”；侦察员B说“钱与孙中至少有一人作案”；侦察员C说“孙与李中至少有一人作案”；侦察员D说“赵与孙中至少有一人与此案无关”；侦察员E说“钱与李中至少有一人与此案无关”如果这五个侦察员的话都是可信的，试用归结演绎推理求出谁是盗窃犯解：第一步：将5位侦察员的话表示成谓词公式，为此先定义谓词 设谓词P(x)表示是作案者，所以根据题意：A: P(zhao) ∨ P(qian) B: P(qian) ∨ P(sun)C: P(sun) ∨ P(li) D: ﹁P(zhao) ∨ ﹁P(sun)E: ﹁P(qian) ∨ ﹁P(li)以上每个侦察员的话都是一个子句第二步：将待求解的问题表示成谓词设y是盗窃犯，则问题的谓词公式为P(y)，将其否定并与ANSWER(y)做析取：﹁P(y) ∨ ANSWER(y)第三步：求前提条件及﹁P(y) ∨ ANSWER(y)的子句集，并将各子句列表如下：（1） P(zhao) ∨ P(qian)（2） P(qian) ∨ P(sun)（3） P(sun) ∨ P(li)（4） ﹁P(zhao) ∨ ﹁P(sun)（5） ﹁P(qian) ∨ ﹁P(li)（6） ﹁P(y) ∨ ANSWER(y)第四步：应用归结原理进行推理。

7） P(qian) ∨ ﹁P(sun) (1)与(4)归结（8） P(zhao) ∨ ﹁P(li) (1)与(5)归结（9） P(qian) ∨ ﹁P(zhao) (2)与(4)归结（10） P(sun) ∨﹁P(li) (2)与(5)归结（11） ﹁P(zhao) ∨ P(li) (3)与(4)归结（12） P(sun) ∨﹁P(qian) (3)与(5)归结（13） P(qian) (2)与(7)归结（14） P(sun) (2)与(12)归结（15） ANSWER(qian) (6)与(13)归结，σ={qian/y}（16） ANSWER(sun) (6)与(14)归结, σ={sun/y}所以，本题的盗窃犯是两个人：钱和孙。

2 任何兄弟都有同一个父亲，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的父亲是DavidFather(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=S1∪S2将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第4部分 搜索策略本章小结：状态空间搜索策略搜索策略盲目搜索启发式搜索广度优先搜索深度优先搜索有界深度优先搜索代价树的广度优先搜索代价树的深度优先搜索局部择优搜索全局择优搜索A*算法与/或树搜索策略盲目搜索广度优先搜索深度及有界深度优先搜索有序搜索特殊情况博弈问题提高搜索效率的方法α-β剪枝技术博弈问题：极大极小分析法：计算出端节点的估值，再推算出父节点的得分。

推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况这样计算出的父节点的得分称为倒推值α-β剪枝技术：对于一个“与”节点来说，它取当前子节点中的最小倒推值作为它倒推值的上界，称此值为β值对于一个“或”节点来说，它取当前子节点中的最大倒推值作为它倒推值的下界，称此值为α值其一般规律为:（1）任何“或”节点x的α值如果不能降低其父节点的β值，则对节点x以下的分枝可停止搜索，并使x的倒推值为α这种剪枝成为β剪枝2）任何“与”节点x的β值如果不能升高其父节点的α值，则对节点x以下的分枝可停止搜索，并使x的倒推值为β这种剪枝成为α剪枝习题解答:1 图4-1是五城市间的交通路线图，A城市是出发地，E城市是目的地，两城市间的交通费用（代价）如图中数字所示求从A到E的最小费用交通路线。