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

1、人工智能各章小结及习题解答第一部分 绪论习题解答：1什么是人工智能？发展过程中经历了哪些阶段？解：人工智能是计算机科学的一个重要分支，也是一门正在发展中的综合性前沿学科，它是由计算机科学、控制论、信息论、神经生理学、哲学、语言学等多种学科相互渗透而发展起来的，目前正处于发展阶段尚未形成完整体系。发展过程中经历的阶段有： 第一阶段（40 年代中50 年代末） 神经元网络时代第二阶段（50 年代中60 年代中） 通用方法时代第三阶段（60 年代中80 年代初） 知识工程时代第四阶段（80 年代中90 年代初） 新的神经元网络时代第五阶段（90 年代初现在） 海量信息处理与网络时代2人工智能研究的基

2、本内容是什么？解：基本内容是：搜索技术、知识表示、规划方法、机器学习、认知科学、自然语言理解与机器翻译、专家系统与知识工程、定理证明、博弈、机器人、数据挖掘与知识发现、多Agent 系统、复杂系统、足球机器人、人机交互技术等。3人工智能主要有哪几大研究学派？解：（）符号主义学派：由心理学途径产生，符号主义认为人工智能起源于数理逻辑，人 类认识（智能）的基本元素是符号，而智能行为则是符号运算的结果。（）连接主义学派：由生理学途径产生，连接主义又称为仿生学派，认为人工智能的基本元素是神经元，智能产生于大量神经元的并行分布式联结之中，而智能行为则是联结计算的结果。（）行为主义学派：由生物演化途径产生

3、，行为主义认为人工智能起源于控制论，提出智能取决于感知和行为，取决于对外界复杂环境的适应，而不是表示和推理。人工智能有哪些主要的研究领域？解：（）问题求解（）逻辑推理与定理证明（）自然语言理解（）自动程序设计（）专家系统（）机器学习（）神经网络（）机器人学（）模式识别（）机器视觉（）智能控制（）智能检索（）智能调度与指挥（）分布式人工智能与（）计算智能与进化计算（）数据挖掘与知识发现（）人工生命（）系统与语言工具第 2 部分 知识与知识表示本章小结：知识表示谓词表示法产生式表示法框架表示法语义网络表示法框架通常由指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值。语义网

4、络由节点和弧线或链线组成，节点用于表示物体、概念和状态，弧线用于表示节点间的关系。产生式系统由 3 个基本部分组成：规则库、综合数据库、控制系统。首先定义谓词，指出每个谓词的确切含义，然后再用连接词把有关的谓词连接起来，形成一个谓词公式表达一个完整的意义。习题解答：1 设有如下问题：（1）有五个相互可直达且距离已知的城市 A、B、C、D、E，如图所示；（2）某人从 A 地出发，去其它四个城市各参观一次后回到 A;（3）找一条最短的旅行路线请用产生式规则表示旅行过程。解：综合数据库（x）(x)中 x 可以是一个字母，也可以是一个字符串。初始状态（A）目标状态（Ax1x2x3x4A） 规则集：r1

5、: IF L(S)=5 THEN GOTO(A)r2: IF L(S)C-D-E-B-A总距离为 5+6+8+10+7=362 神州大学和东方大学两校篮球队在东方大学进行一场比赛，结局的比分是 85：89，用语义网络表示。第 3 部分 推理本章小结：推理经典逻辑推理不确定与非单调推理归结演绎推理与/或形演绎推理习题解答：1 张某被盗，公安局派出五个侦察员去调查。研究案情时，侦察员 A 说“赵与钱中至少有一人作案” ；侦察员 B 说“钱与孙中至少有一人作案 ”；侦察员 C 说“孙与李中至少有一人作案” ；侦察员 D 说“赵与孙中至少有一人与此案无关 ”；侦察员 E 说“钱与李中至少有一人与此案无

6、关” 。如果这五个侦察员的话都是可信的，试用归结演绎推理求出谁是盗窃犯。解：第一步：将 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)的子句集，并将各子句

7、列表如下：（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)归结

8、（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） 将

9、已知事实用谓词公式表示出来：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)（3） 将它们化成子句集，得S1=Brother(x,y)Father(z,x)Father(z,y), Brother(John, Peter), Father(David, John)第二步：把问题用谓词公式表示出来，并将其否定与谓词 ANSWER 做析取。设 Peter 的父亲

10、是 u，则有：Father(u, Peter)将其否定与 ANSWER 做析取，得G: Father(u, Peter) ANSWER(u)第三步：将上述公式 G 化为子句集 S2，并将 S1 和 S2 合并到 S。S2=Father(u, Peter) ANSWER(u)S=S1S2将 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)

11、 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*算法与/或树搜索策略盲目搜

12、索广度优先搜索深度及有界深度优先搜索有序搜索特殊情况博弈问题提高搜索效率的方法 - 剪枝技术极大极小分析法：计算出端节点的估值，再推算出父节点的得分。推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。- 剪枝技术：博弈问题：对于一个“与”节点来说，它取当前子节点中的最小倒推值作为它倒推值的上界，称此值为 值。对于一个“或”节点来说，它取当前子节点中的最大倒推值作为它倒推值的下界，称此值为 值。其一

13、般规律为:（1）任何“或 ”节点 x 的 值如果不能降低其父节点的 值，则对节点x 以下的分枝可停止搜索，并使 x 的倒推值为 。这种剪枝成为 剪枝。（2）任何“与”节点 x 的 值如果不能升高其父节点的 值，则对节点 x 以下的分枝可停止搜索，并使 x 的倒推值为 。这种剪枝成为 剪枝。习题解答:1 图 4-1 是五城市间的交通路线图， A 城市是出发地，E 城市是目的地，两城市间的交通费用（代价）如图中数字所示。求从 A 到 E 的最小费用交通路线。解：先将交通图转换为代价树，如图 4-2 所示。若用 g(x)表示从初始节点 s0 到节点 x 的代价，用 c(x1,x2)表示从父节点 x1

14、 到子节点x2 的代价，则有：g(x2)=g(x1)+c(x1,x2)AC1 B1D11 D2 E1E2 B2E4C2 E33 423 454 52 3图 4-2图 4-1方法一：代价树的广度优先搜索（扩展节点，将其子节点放入 open 表中，计算各子节点的代价，并按各节点的代价对open 表中全部节点按从小到大的顺序进行排序（队列） ）步骤如下：图 4-3-1图 4-3-2图 4-3-3所以，最优路径为 A-C-D-E图 4-3-4图 4-3-5方法二：代价树的深度优先搜索（不一定是最优解）（扩展节点，将其子节点按代价从小到大的顺序放到 open 表的首部（栈） ）步骤如下：435AC1 B1D12图 4-4-2435AC1 B1D18图 4-4-393 4E2 B2E 为目标节点，E2-D1-C1-A所以路径为 A-AC1 B143图 4-4-1虽然 D1 的代价大于 B1 的代价，但按照代价树的深度优先搜索策略，要对 D1 进行扩展，放入 closed 表中（若按代价树的广度优先搜索，要对 B1、D1 排序，先扩展 B1）