人工智能经典习题集及各章总结期末考试必备（参考）.doc
《人工智能经典习题集及各章总结期末考试必备（参考）.doc》由会员分享，可在线阅读，更多相关《人工智能经典习题集及各章总结期末考试必备（参考）.doc（57页珍藏版）》请在冰点文库上搜索。
人工智能各章小结及习题解答
第一部分绪论
习题解答：
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:
IFL（S）=5THENGOTO（A）
r2:
IFL（S）<5THENGOTO（B）
r3:
IFL（S）<5THENGOTO（C）
r4:
IFL（S）<5THENGOTO（D）
r5:
IFL（S）<5THENGOTO（E）
其中L（S）为走过的城市数，GOTO（x）为走向城市x
⑤路线如下图所示:
（A）
（AB）
（AC）
（AD）
（AE）
（ACB）
（ACD）
（ACE）
（ACDB）
（ACDE）
（ACDEB）
（ACDEBA）
7
5
10
10
7
6
9
10
8
10
7
起始
目标
最短旅行路线为：
A->C->D->E->B->A
总距离为5+6+8+10+7=36
2神州大学和东方大学两校篮球队在东方大学进行一场比赛，结局的比分是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的父亲是David。
Father（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的最小费用交通路线。
图4-1
解：
先将交通图转换为代价树，如图4-2所示。
若用g（x）表示从初始节点s0到节点x的代价，用c（x1,x2）表示从父节点x1到子节点x2的代价，则有：
g（x2）=g（x1）+c（x1,x2）
A
C1
B1
D11
D2
E1
E2
B2
E4
C2
E3
3
4
2
3
4
5
4
5
2
3
图4-2
方法一：
代价树的广度优先搜索
（扩展节点ｎ，将其子节点放入open表中，计算各子节点的代价，并按各节点的代价对open表中全部节点按从小到大的顺序进行排序（队列））
步骤如下：
图4-3-1
图4-3-2
图4-3-3
图4-3-4
图4-3-5
所以，最优路径为A->C->D->E
方法二：
代价树的深度优先搜索（不一定是最优解）
（扩展节点ｎ，将其子节点按代价从小到大的顺序放到open表的首部（栈））
步骤如下：
A
C1
B1
4
3
图4-4-1
虽然D1的代价大于B1的代价，但按照代价树的深度优先搜索策略，要对D1进行扩展，放入closed表中（若按代价树的广度优先搜索，要对B1、D1排序，先扩展B1）
4
3
5
A
C1
B1
D1
2
图4-4-2
4
3
5
A
C1
B1
D1
8
图4-4-3
9
3
4
E2
B2
E为目标节点，E2->D1->C1->A
所以路径为A->Ｃ->Ｄ->Ｅ
注：
该题代价树的深度优先搜索与代价树的广度优先搜索的结果相同，但这只是巧合。
一般情况下，这两种方法得到的结果不一定相同。
另外，由于代价树的深度优先搜索有可能进入无穷分支的路径，因此它是不完备的。
２ 如下图４-5所示，分别用代价树的广度优先搜索策略和代价树的深度优先搜索策略，
求A到E的最短费用路径。
图４－５
Ａ
Ｃ
Ｂ
Ｄ
Ｅ
６
５
６
７
８
７
解：
先将其化成代价树,如图4-6：
D1
6
5
Ａ
Ｂ1
C1
D2
E1
C2
E2
B2
E3
E4
6
6
5
7
7
7
8
8
图4-6
（1）代价树的广度优先搜索,步骤如下：
A
B1
C1
6
7
图4-7-1
B1
C1
6
7
D1
A
5
11
图4-7-2
5
B1
C1
6
D1
A
11
D2
E1
7
7
8
14
15
图4-7-3
E为目标节点，路径为A->C->E，代价为15。
（2）代价树的深度优先搜索,步骤如下：
B1
C1
6
7
D1
A
5
11
C2
E2
7
6
18
17
B1
C1
6
7
D1
A
5
11
图4-8-2
图4-8-1
虽然C1代价低于D1，但按照代价树的深度优先搜索策略，对D1进行扩展，放入closed表中，因为B1扩展的节点为D1，而C1是A节点扩展得到的。
E出栈，为目标节点，结束。
故解路径为A->B->D->E,代价为17，不是最优解。
注：
深度优先搜索是不完备的，即使问题有解，也不一定能求得解。
得到的解也不一定是最优解（因为是局部优先搜索）。
3下图是五城市间的交通费用图，若从西安出发，要求把每个城市都访问一遍，最后到达广州，请找一条最优路线。
边上的数字是两城市间的交通费用。
北京B
上海D
A西安
S0
昆明C
广州E
Sg
75
70
80
95
90
120
150
170
160
130
图4-9
解：
先画出代价树：
A
B1
C1
D1
E1
C2
D2
E2
B2
D3
E3
B3
C3
E4
D4
E5
C4
E6
D5
E7
B4
E8
C5
E9
B5
E10
E11
E12
E13
E14
E15
E16
80
95
120
150
170
75
160
130
70
90
170
130
90
75
130
70
130
90
75
160
75
70
图4-10
按代价树的广度优先搜索即可得出最优路线，步骤如下：
C1
图4-11-1
A
B1
D1
E1
80
95
120
150
C1
图4-11-2
A
B1
D1
E1
80
95
120
150
C2
D2
E2
250
155
240
C1
图4-11-3
A
B1
D1
E1
80
95
120
150
C2
D2
E2
250
155
240
B2
D3
E3
265
225
185
C1
图4-11-4
A
B1
D1
E1
80
95
120
150
C2
D2
E2
250
155
240
B2
D3
E3
265
225
185
B3
C3
E4
195
250
190
B4
E8
B3
C3
E4
195
250
190
C1
图4-11-5
A
B1
D1
E1
80
95
120
150
C2
D2
E2
250
155
240
B2
D3
E3
265
225
185
C4
E6
285
225
C5
E9
365
355
300
295
E10
B5
E5
D4
380
340
420
340
E7
D5
340
425
E12
375
故由此得出最优路线为A->B1->D2->C4->E12
即A->B->D->C->E，交通费用为375。
4设有如图所示的一棵与/或树，请分别用与/或树的广度优先搜索及与/或树的深度优先搜索求出解树。
B
C
t1
t2
t3
t4
t5
A
D
解：
（1）与/或树的广度优先搜索
先扩展节点A,得到节点B和C，再扩展节点B,得节点t1、t2，因为t1、t2为可解节点，故节点B可解，从而可节点A可解。
B
t1
t2
A
所以求得解树为：
（2）与/或树的深度优先搜索
先扩展节点A,得到节点B和C,再扩展节点C,得节点D和t5,t5为可解节点，再扩展节D，得节点t3、t4，因为t3、t4为可解节点，故节点D可解，因为节点D和t5可解，故节点C可解，从而可节点A可解。
所以求得解树为：
C
t3
t4
t5
A
D
5设有如图所示的与/或树，请分别按和代价法及最大代价法求解树代价。
B
C
D
t2
t1
t4
A
t3
5
7
2
2
3
6
2
1
（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=10
1、谈谈你对于人工智能的认识。
人工智能就是人造智能，目前指用计算机模拟或实现的智能，因此人工智能又称机器智能。
人工智能在我看来，应该是像人一样思考的系统、像人一样行动的系统、理性地思考的系统、理性地行动的系统，是像人一样具有感知的系统，是可以独立思考、独立判断的系统
2、人工智能有哪些研究途径和方法？
它们的关系如何？
心理模拟,符号推演;生理模拟,神经计算;行为模拟,控制进化;群体模拟,仿生计算;博采广鉴,自然计算;原理分析,数学建模;它们各有所长,也都有一定的局限性，因此这些研究途径和方法并不能互相取代,而是并存和互补的关系。
3、人工智能有哪些研究内容？
搜索与求解、学习与发现、知识与推理、发明与创造、感知与交流、记忆与联想、系统与建造、应用与工程等八个方面。
4、人工智能有哪些分支领域和研究方向？
从模拟的智能层次和所用的方法看，可分为符号智能和计算智能两大领域；从模拟的脑智能或脑功能看，可分为机器学习、机器感知、机器联想、机器推理、机器行为等分支领域；从应用角度看，可分为难题求解、自动规划、调度与配置、机器定理证明、自动程序设计、机器翻译、智能控制、智能管理、智能决策、智能通信、智能仿真、智能CAD、智能制造、智能CAI、智能人机接口、模式识别、数据挖掘与数据库中的知识发现、计算机辅助创新、计算机文艺创作、机器博弈、智能机器人；从系统角度看，可分为智能计算机系统和智能应用系统；从基础理论看，可分为数理逻辑和多种非标准逻辑、图论、人工神经网络、模糊集、粗糙集、概率统计和贝叶斯网络、统计学习理论与支持向量机、形式语言与自动机等领域；
5、人工智能有哪些应用领域或课题？
试举例说明
难题求解、自动规划、调度与配置、机器定理证明、自动程序设计、机器翻译、智能控制、智能管理、智能决策、智能通信、智能仿真、智能CAD、智能制造、智能CAI、智能人机接口、模式识别、数据挖掘与数据库中的知识发现、计算机辅助创新、计算机文艺创作、机器博弈、智能机器人。
就机器博弈方面，在1997年IBM的“深蓝”计算机以2胜3平1负的战绩击败了蝉联12年之久的直接国际象棋冠军加里卡斯帕罗夫，比如先如今中的五子棋对弈，能实现人与电脑之间的下棋，电脑自动搜索棋步，还可根据人们所选的电脑难度来决定电脑的难易程度。
6、简述人工智能的发展状况
人工智能的现状和发展呈现如下特点：
多种途径齐头并进，多种方法写作互补；新思想、新技术不断涌现，新领域、新方向不断开括;理论研究更加深入，应用研究更加广泛;研究队伍日益壮大，社会影响越来越大;以上特点展现了人工智能学科的繁荣景象和光明前景。
它表明，虽然在通向其最终目标的道路上，还有不少困难、问题和挑战，但前进和发展毕竟是大势所趋。
7、试编写一个描述亲属关系的PROLOG程序，然后再给出一些事实数据，建立一个小型演绎数据库。
domains
name=symbol.sex=symbol.age=integer.
predicates
person（name,sex,age）mother（name,name）father（name,name）brother（name,name）
sister（name,name）grandfather（name,name）grandmother（name,name）
goal
brother（Name1,Name2）,write（Name1,"is",Name2,"'sbrother!
\n"）,
sister（Name3,Name4）,write（Name3,"is",Name4,"'ssister!
\n"）,
grandfather（Name5,Name6）,write（Name5,"is",Name6,"'sgrandfather!
\n"）,
grandmother（Name7,Name8）,write（Name7,"is",Name8,"'sgrandmother!
\n"）.
cl
升级会员 