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

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

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

3、基本元素是是神经元，智智能产生于大大量神经元的的并行分布式式联结之中，而而智能行为则则是联结计算算的结果。 （）行为为主义学派：由生物演化化途径产生，行为主义认为人工智能起源于控制论，提出智能取决于感知和行为，取决于对外界复杂环境的适应，而不是表示和推理。人工智能有有哪些主要的的研究领域？解：（）问题题求解（）逻辑推推理与定理证证明（）自然语语言理解（）自动程程序设计（）专家系系统（）机器学学习（）神经网网络（）机器人人学（）模式识识别（）机器器视觉（）智能能控制（）智能能检索（）智能能调度与指挥挥（）分布布式人工智能能与（）计算算智能与进化化计算（）数据据挖掘与知识识发现（）人工工生命（）系

4、统统与语言工具具第2部分 知知识与知识表表示本章小结：知识表示谓词表示法产生式表示法框架表示法语义网络表示法框架通常由指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值。语义网络由节点和弧线或链线组成，节点用于表示物体、概念和状态，弧线用于表示节点间的关系。产生式系统由3个基本部分组成：规则库、综合数据库、控制系统。知识表示谓词表示法产生式表示法框架表示法语义网络表示法框架通常由指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值。语义网络由节点和弧线或链线组成，节点用于表示物体、概念和状态，弧线用于表示节点间的关系。产生式系统由3个基本部分组成：

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

6、： r11: IF L(SS)=5 THEEN GOOTO(A) r22: IF L(SS)5 THEEN GOOTO(B) r33: IF L(SS)5 THEEN GOOTO(C) r44: IF L(SS)5 THEEN GOOTO(D) r55: IF L(SS)CC-D-E-B-A总距离为5+66+8+100+7=3662 神州大学和和东方大学两两校篮球队在在东方大学进进行一场比赛赛，结局的比比分是85：89，用语语义网络表示示。第3部分 推推理本章小结：自然演绎推理推理自然演绎推理推理经典逻辑推理不确定与非单调推理归结演绎推理与/或形演绎推理习题解答：1 张某被盗，公公安局派出五五

7、个侦察员去去调查。研究究案情时，侦侦察员A说“赵与钱中至至少有一人作作案”；侦察员BB说“钱与孙中至至少有一人作作案”；侦察员CC说“孙与李中至至少有一人作作案”；侦察员DD说“赵与孙中至至少有一人与与此案无关”；侦察员EE说“钱与李中至至少有一人与与此案无关”。如果这五五个侦察员的的话都是可信信的，试用归归结演绎推理理求出谁是盗盗窃犯。解：第一步：将将5位侦察员员的话表示成成谓词公式，为为此先定义谓谓词。设谓词P(xx)表示是作作案者，所以以根据题意：A: P(zhhao) P(qiaan) B: P(qiian) P(suun)C: P(suun) P(lii) D: PP(zhaoo)

8、P(ssun)E: P(qqian) P(lli)以上每个侦察员员的话都是一一个子句。第二步：将待求求解的问题表表示成谓词。设设y是盗窃犯犯，则问题的的谓词公式为为P(y)，将将其否定并与与ANSWEER(y)做做析取：P(y) ANSWWER(y)第三步：求前提提条件及PP(y) ANSWWER(y)的子句集，并并将各子句列列表如下：P(zhao) P(qiian)P(qian) P(suun)P(sun) P(lii)P(zhaoo) P(ssun)P(qiann) P(lli)P(y) ANSWWER(y)第四步：应用归归结原理进行行推理。P(qian) P(ssun) (1)与(4)归

9、结P(zhao) P(lli) (1)与(5)归结P(qian) P(zzhao) (2)与(44)归结P(sun) P(lii) (2)与(5)归结P(zhaoo) P(lii) (3)与(44)归结P(sun) P(qiian) (3)与(5)归结P(qian) (2)与(7)归结P(sun) (2)与(12)归结ANSWER(qian) (6)与(13)归结，=qiaan/yANSWER(sun) (6)与(14)归结, =sunn/y所以，本题的盗盗窃犯是两个个人：钱和孙孙。 2 任何兄弟都都有同一个父父亲，Johhn和Petter是兄弟弟，且Johhn的父亲是是Davidd，问Pet

10、ter的父亲亲是谁？解：第一步：将将已知条件用用谓词公式表表示出来，并并化成子句集集。那么，要要先定义谓词词。定义谓词：设Fatherr(x,y)表示x是yy的父亲。设Brotheer(x,yy)表示x和和y是兄弟。将已知事实用谓谓词公式表示示出来：F1: 任何兄兄弟都有同一一个父亲。( x)( y)( z)( Brothher(x,y)Fatheer(z,xx)Fatheer(z,yy)F2: Johhn和Petter是兄弟弟。Brotherr(Johnn, Peterr)F3: Johhn的父亲是是Davidd。Father(Davidd, John)将它们化成子句句集，得S1=Brrot

11、herr(x,y)Fathher(z,x)Fatheer(z,yy), Brothher(Joohn, Peterr), Fatheer(Davvid, John)第二步：把问题题用谓词公式式表示出来，并将其否定与谓词ANSWER做析取。设Peter的的父亲是u，则则有：Fatther(uu, Peterr)将其否定与ANNSWER做做析取，得G: Faather(u, Peterr) ANSWWER(u)第三步：将上述述公式G化为为子句集S22，并将S11和S2合并并到S。S2=Faather(u, Peterr) ANSWWER(u)S=S1S22将S中各子句列列出如下：（1）Brooth

12、er(x,y)Fathher(z,x)Fatheer(z,yy)（2）Brotther(JJohn, Peterr)（3）Fathher(Daavid, John)（4）Fatther(uu, Peterr) ANSWWER(u)第四步：应用归归结原理进行行归结。（5）Broother(John,y) Fathher(Daavid,yy) （1）与（3）归归结，= Davidd/z, John/x（6）Broother(John, Peterr) ANSWWER(Daavid) （4）与与（5）归结结，= Davidd/u, Peterr/y（7）ANSWWER(Daavid) （2）与与（6

13、）归结结第五步：得到了了归结式ANNSWER(Davidd)，答案即即在其中，所所以u=Daavid,即即Peterr的父亲是DDavid。第4部分 搜搜索策略本章小结：状态空间搜索策略状态空间搜索策略搜索策略盲目搜索启发式搜索广度优先搜索深度优先搜索有界深度优先搜索代价树的广度优先搜索代价树的深度优先搜索局部择优搜索全局择优搜索A*算法与/或树搜索策略盲目搜索广度优先搜索深度及有界深度优先搜索有序搜索特殊情况博弈问题提高搜索效率的方法-剪枝技术博弈问题博弈问题：极大极小分析法法：计算出端端节点的估值值，再推算出出父节点的得得分。推算的方法是：对“或”节点，选其其子节点中一一个最大的得得分作为

14、父节节点的得分，这这是为了使自自己在可供选选择的方案中中选一个对自自己最有利的的方案；对“与”节点，选其其子节点中一一个最小的得得分作为父节节点的得分，这这是为了立足足于最坏的情情况。这样计计算出的父节节点的得分称称为倒推值。-剪枝技术术：对于一个“与”节点来说，它它取当前子节节点中的最小小倒推值作为为它倒推值的的上界，称此此值为值。对于一个个“或”节点来说，它它取当前子节节点中的最大大倒推值作为为它倒推值的的下界，称此此值为值。其一般规律为:（1）任何何“或”节点x的值如果不能能降低其父节节点的值，则对节节点x以下的的分枝可停止止搜索，并使使x的倒推值值为。这种剪枝枝成为剪枝。（2）任何“与

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

16、4-2方法一：代价树树的广度优先先搜索（扩展节点，将将其子节点放放入openn表中，计算算各子节点的的代价，并按按各节点的代代价对opeen表中全部部节点按从小小到大的顺序序进行排序（队队列）步骤如下：图4-3-1 图4-3-1图4-3-2图4-3-2图图4-3-3图4-3-4图4-3-4图4-3-5图4-3-5所以，最优路径径为A-CC-D-E方法二：代价树树的深度优先先搜索（不一一定是最优解解）（扩展节点，将将其子节点按按代价从小到到大的顺序放放到openn表的首部（栈栈）步骤如下：AAC1B143图4-4-1虽然D1的代价大于B1的代价，但按照代价树的深度优先搜索策略，要对D1进行扩展，

17、放入closed表中（若按代价树的广度优先搜索，要对B1、D1排序，先扩展B1）4虽然D1的代价大于B1的代价，但按照代价树的深度优先搜索策略，要对D1进行扩展，放入closed表中（若按代价树的广度优先搜索，要对B1、D1排序，先扩展B1）435AC1B1D12图4-4-24435AC1B1D18图4-4-3934E2B2E为目标节点，EE2-D11-C1-A所以路径为A-注：该题代价树树的深度优先先搜索与代价价树的广度优优先搜索的结结果相同，但但这只是巧合合。一般情况况下，这两种种方法得到的的结果不一定定相同。另外外，由于代价价树的深度优优先搜索有可可能进入无穷穷分支的路径径，因此它是是不

18、完备的。如下图-5所示，分分别用代价树树的广度优先先搜索策略和和代价树的深深度优先搜索索策略，求A到E的最短短费用路径。图图解：先将其化成成代价树,如如图4-6：D1D1651C1D2E1C2E2B2E3E466577788图4-6(1)代价树的的广度优先搜搜索,步骤如如下：AAB1C167图图4-7-1B1B1C167D1A511图图4-7-25B15B1C16D1A11D2E17781415图图4-7-3E为目标节点，路路径为A-C-E，代代价为15。（2）代价树的的深度优先搜搜索,步骤如如下：B1C1B1C167D1A511C2E2761817B1C167D1A511图4-8-2图4-8

19、-2图4-8-1虽然C1代价低低于D1，但但按照代价树树的深度优先先搜索策略，对对D1进行扩扩展，放入cclosedd表中，因为为B1扩展的的节点为D11，而C1是是A节点扩展展得到的。EE出栈，为目目标节点，结结束。故解路路径为A-B-D-E,代价价为17，不不是最优解。注：深度优先搜搜索是不完备备的，即使问问题有解，也也不一定能求求得解。得到到的解也不一一定是最优解解（因为是局局部优先搜索索）。3 下图是五城城市间的交通通费用图，若若从西安出发发，要求把每每个城市都访访问一遍，最最后到达广州州，请找一条条最优路线。边边上的数字是是两城市间的的交通费用。北京B北京B上海DA西安S0昆明C广州

20、ESg7570809590120150170160130图4-9解：先画出代价价树： AAB1C1D1E1C2D2E2B2D3E3B3C3E4D4E5C4E6D5E7B4E8C5E9B5E10E11E12E13E14E15E16809512015017075160130709017013090751307013090751607570图4-10按代价树的广度度优先搜索即即可得出最优优路线，步骤骤如下：C1C1图4-11-1AB1D11C1图4-11-2AB1D12D2E2250155240C1C1图4-11-3AB1D12D2E2250155240B2D3E3265225185C1图C1图4-11-4AB1D12D2E2250155240B2