人工智能
第1部分绪论
1-1.什么是人工智能?试从学科和能力两方面加以说明。
答:从学科方面定义:人工智能是计算机科学中涉及研究、设计和应用智能机器的一个分支。它的近期目标在于研究用机器来模拟和执行人脑的某些智力功能,并开发相关理论和技术
从能力方面定义:人工智能是智能机器所执行的通常与人类智能有关的智能行为,如判断、推理、证明、识别、感知、理解、通信、设计、思考、规划、学习和问题求解等思维活动。
1-2.在人工智能的发展过程中,有哪些思想和思潮起了重要作用?
答:
1)数理逻辑和关于计算本质的新思想,提供了形式推理概念与即将发明的计算机之间的联系;
2)1956年第一次人工智能研讨会召开,标志着人工智能学科的诞生;
3)控制论思想把神经系统的工作原理与信息理论、控制理论、逻辑以及计算联系起来,影响了许多早期人工智能工作者,并成为他们的指导思想;
4)计算机的发明与发展;
5)专家系统与知识工程;
6)机器学习、计算智能、人工神经网络和行为主义研究,推动人工智能研究的近一步发展。
1-3.为什么能够用机器(计算机)模仿人的智能?
答:物理符号系统的假设:任何一个系统,如果它能够表现出智能,那么它就必定能执行输入符号、输出符号、存储符号、复制符号、建立符号结构、条件迁移6种功能。反之,任何系统如果具有这6种功能,那么它就能够表现出智能(人类所具有的智能)。
物理符号系统的假设伴随有3个推论。
推论一:既然人具有智能,那么他(她)就一定是各物理符号系统;
推论二:既然计算机是一个物理符号系统,它就一定能够表现出智能;
推论三:既然人是一个物理符号系统,计算机也是一个物理符号系统,那么我们就能够用计算机来模拟人的活动。
1-4.人工智能的主要研究内容和应用领域是什么?其中,哪些是新的研究热点?
答:研究和应用领域:问题求解(下棋程序),逻辑推理与定理证明(四色定理证明),自然语言理解,自动程序设计,专家系统,机器学习,神经网络,机器人学(星际探索机器人),模式识别(手写识别,汽车牌照识别,指纹识别),机器视觉(机器装配,卫星图像处理),智能控制,智能检索,智能调度与指挥(汽车运输高度,列车编组指挥),系统与语言工具。
新的研究热点:概率图模型(隐马尔可夫模型、贝叶斯网络),统计学习理论(SLT)&支持向量机(SVM),数据挖掘与知识发现(超市市场商品数据分析),人工生命。1-5.人工智能的发展对人类有哪些方面的影响?试结合自己了解的情况和理解,从经济、社会和文化等方面加以说明?
答:1、人工智能对经济的影响。人工智能系统的开发和应用,已为人类创
造出可观的经济效益,专家系统就是一个例子。随着计算机系统价格的继
续下降,人工智能技术必将得到更大的推广,产生更大的经济效益。
2、人工智能对社会的影响。劳务就业问题;社会结构变化;思维方式与观
念的变化;心理上的威胁;技术失控的危险.
3、人工智能对文化的影响。改善人类知识;改善人类语言;改善文化生活;1-6.试评述人工智能的未来发展。
答:人工智能的未来发展主要可以概括为更新的理论框架,更好的技术集成,更成熟的应用方法。
而在具体的应用方面,我认为主要有以下两个发展方向:
1、计算机能直接而人类大脑实现人机交流。借助以上技术,人类可以用思维控制自己想看到的,想听到的,使媒体技术中的感官媒体更真实化,对虚拟的事物不仅可以看见听见,更可以摸得,闻得着。同时电脑可以进一步辅助人类做出一定的判断,储存大量信息,甚至可以以身体为媒介,执行电脑程序,是人类更快的学会各种技巧,掌握更多知识。同时,提高了生物验证的渠道,比如利用DNA染色体作为密码的载体,相信是很难伪造的。
2、电脑拥有机器思维:机器学会人类的思维方式,帮助人更好的思考问题。
第2部分知识表示
2-1.什么是知识?知识的要素有哪些?知识的表示方法有哪些?
答:知识是经过消减、塑造、解释和转换的信息。简单地说,知识是经过加工的信息。
知识是由特定领域的描述、关系和过程组成的。
知识是事实、信念和启发式规则。从知识库的观点看,知识是某领域中所涉及的各
有关方面的一种符号表示。
知识的要素:事实、规则、控制和元知识。
知识的表示方法有:状态空间法、问题归纳法、谓词逻辑法、语义网路法和框架表
示法
2-2.谓词逻辑法、产生式表示法、框架表示法和语义网络表示法的要点是什么?它们有何本质上的联系及异同点?
答:谓语逻辑法是采用谓词合式公式和一阶谓词演算把要解决的问题变为一个有待证明的问题,然后采用消解定理和消解反演来证明一个新语句是从已知的正确语句导
出的,从而证明这个新语句也是正确的
状态空间法是基于解答空间的问题表示和求解方法,是以状态和操作符为基础的。
问题归约法是从目标(要解决的问题)出发逆向推理,建立子问题以及子问题的子问
题,直至最后把初始问题归约为一个平凡的本原问题集合。
谓语逻辑法是采用谓词合式公式和一阶谓词演算把要解决的问题变为一个有待证
明的问题,然后采用消解定理和消解反演来证明一个新语句是从已知的正确语句导
出的,从而证明这个新语句也是正确的
语义网络法是用“节点”代替概念,用节点间的“连接弧”代替概念之间的关系。
语义网络表示法的优点:结构性、联想性、自然性。
2-3.如何用谓词逻辑法表示知识? (见课本例题)
例题:
所有学生都穿彩色制服。
任何整数或者为正数或者为负数。
自然数都是大于零的整数。
解:首先定义谓词如下:
Student(x):x是学生
Uniform(x,y):x穿y
N(x):x是自然数
I(x):x是整数
P(x):x是正数
Q(x):x是负数
L(x):x大于零
用谓词公式分别表示如下:
(?x)(Student(x)->Uniform(x,color))
(?x)(I(x)->P(x)VQ(x))
(?x)(N(x)->L(x)ΛI(x))
2-4.什么是产生式规则?产生式系统由哪些部分组成?说明各部分的功能。
答:产生式规则:
1.确定性和不确定性规则知识的产生式表示
确定性规则知识表示方法用产生式的基本形式P→Q或IF P THEN Q
不确定性规则知识表示方法用P→Q(可信度)或者IF P THEN Q (可信度)2.确定性和不确定性事实性知识的产生式表示
确定性事实性知识表示方法一般用三元组(对象,属性,值)或(关系,对象1,
对象2)来表示
不确定性事实性知识表示方法一般用四元组(对象,属性,值,不确定度量值)或
(关系,对象1,对象2,不确定度量值)
产生式系统组成:
产生式系统通常由规则库、数据库和推理机三个基本部分组成。
规则库用于描述某领域内知识的产生式集合,其中规则是以产生式表示,库中包含着将问题从初始状态转换成解状态的变换规则。规则库是专家系统的核心。
数据库又称为事实库,用来存放输入事实、外部数据库输入的事实以及中间结果和最后结果,数据库中的内容是动态变化的。
推理机又称控制系统,由一组程序组成,用来控制协调规则库与数据库的运行,包含推理方式与控制策略。控制策略作用是确定选用什么规划或如何运用规则。从选择规则到执行操作要分三步完成:匹配、冲突解决和操作
2-5.说明产生式系统推理机的推理方式及推理过程。
答:产生式系统推理机的推理方式有正向推理、反向推理和双向推理三种
正向推理是从已知事实出发,通过规则求得结论,也称数据驱动方式或自底向上的方
式,过程如下: 1. 规则集中的规则与数据库中的事实进行匹配,得到匹配的规则集合。 2. 使用冲突解决算法,从匹配规则集合中选择一条规则作为启用规则。 3. 执行启用规则的后件,将该启用规则的后件送入数据库。 重复这个过程直至达到目标。
反向推理是从目标(作为假设)出发,反向使用规则,求得已知事实,也称目标驱动方式或称自顶向下的方式,过程如下:
1. 规则库中的规则后件与目标事实进行匹配,得到匹配的规则集合。
2. 使用解决算法,从匹配规则集合中选择一条规则作为启用规则。
3. 将启用规则的前件作为子目标。
重复这个过程直至各子目标均为已知事实成功结束。 双向推理是一种既自顶向下、又自底向上的推理方式,推理从两个方向同时进行,直至 某个中间界面上两方向结果相符便成功结束。
2-6. 如何用框架表示法表示知识?如何用语义网络法表示知识?(见课本例题)
框架表示法表示知识举例:描述“教师”的框架 框架名:<教师>
类属:<知识分子>
工作:范围(教学,科研) 默认:教学 性别:(男,女) 学历:(中专,大专) 类别:(<小学教师>,<中学教师>,<大学教师>) 语义网络法表示知识举例:
第3部分 经典逻辑推理
3-1. 什么是推理?推理的任务是什么?可分为哪几类(按推理的逻辑基础划分、所利用
的知识划分、推出的结论的单调性划分)? 答:推理:按某种策略由已知判断推出另一判断的思维过程 推理的任务:从一种判断推出另一种判断 按判断推出的途径(逻辑基础)来划分:演绎推理、归结推理、默认推理 按所利用的知识划分:确定性推理、不确定性推理 按推出的结论的单调性划分:单调推理、非单调推理 3-2. 什么是置换?什么是合一?什么是归结? 答:
置换是形如 的有限集合。其中 是项, 是变元; 表示用 替换 ,不允许 与 相同,也不允许变元 循环出现在另一个 中。 合一:设有公式集 ,若存在一个代换 , 使得 则称 为公式集 F 的一个合一, 且称 是可合一的。
},,,{2211n n x t x t x
t n t t t ,,,21 n x x x ,,,21 i i x t i x i t i t i x i x i t },,,{21n F F F F n F F F 21 n F F F ,,,21 2
C
归结:设 与 是子句集中的任意两个子句, 如果 中的文字 与 中的文字 互补, 那么从 和 中分别消去 和 , 并将二个子句中余下的部分析取,构成一个新子句 , 则称这一过程为归结,称 为 和 的归结式, 称 和 为 的亲本子句。 3-3. 什么是子句?把谓词公式化为子句集有哪些步骤? 答:任何文字的析取式称为子句。 谓词公式化为子句集共有9个步骤
1)消去蕴涵符号; 2)减少否定符号的辖域; 3)对变量标准化; 4)消去
存在量词
5)化为前束形 6)把母式化为合取范式 7)消去全称量词
8)消去连词符号^
9)更换变量名称
3-4. 掌握把谓词公式化为子句集的方法。如把下列句子变换成子句形式:
3-5.
简述用归结法证明定理的过程(消解反演求解过程)。(见课本例题)P94 17 20
1C 1C 1L 2C 2L 1C 2C 1L 2L 12C 12C 12C 1C 1C 2C 2C
答:归结法证明定理的过程:
1)否定结论G,得到?G;
2)将前提条件A?ΛA?Λ…ΛAn和?G化为子句集S;
3)应用归结原理,反复对子句集S进行归结,若能归结出空子句,则证明子句
集S的不可满足性,从而证明了公式A?ΛA?Λ…ΛAn →G为真。
P95第17题:
证明:先将问题用谓词描述如下:
( x)(Pass(x,computer)∧Win(x,prize))→Happy(x))
( x) ( y)(Study(x)∨Lucky(x)→Pass(x,y))
┐Study(zhang) ∧Lucky(zhang)
( x)( Lucky(x)→Win(x,prize))
结论“张是快乐的”的否定
┐Happy(zhang)(3分)
将上述公式转化为子句集如下:
(1)┐Pass(x,computer)∨┐Win(x,prize)∨Happy(x)
(2) ┐Study(y)∨Pass(y,z)
(3)┐Lucky(u) ∨Pass(u,v)
(4)┐Study(zhang)
(5) Lucky(zhang)
(6)┐Lucky(w) ∨Win(w,prize)
(7) ┐Happy(zhang) (3分)
P95第20题:设已知:
(1) 能阅读的人是识字的;
(2) 海豚不识字;
(3) 有些海豚是很聪明的。
证明:有些很聪明的人并不识
解:第一步,先定义谓词,
设R(x)表示x 是能阅读的;
K(y)表示y 是识字的;
W(z) 表示z 是很聪明的;
第二步,将已知事实和目标用谓词公式表示出来
能阅读的人是识字的:(?x)(R(x))→K(x))
海豚不识字:(?y)(?K (y))
有些海豚是很聪明的:( ?z)W(z)
有些很聪明的人并不识字:( ?x)(W(z)∧?K(x))
第三步,将上述已知事实和目标的否定化成子句集:
?R(x))∨K(x)
?K (y)
W(z)
?W(z)∨K(x))
第四步,用归结演绎推理进行证明
3-6.如何通过归结法求取问题的答案? P95 18 19
答:归结法求取问题的步骤如下:
1)把已知前提条件用谓词公式表示出来,并且化为子句集S;
2)把待求解的问题用谓词公式表示出来,然后将其否定,并与谓词公式ANSWER 构成析取式,ANSWER是一个为了求解问题而专设的谓词,并且其変元必须与
谓词公式中的変元一致;
3)将2)中的析取式化为子句集,并且将该子句集并入到子句集S中。得到子句集S’;
4)对子句集S’应用归结原理进行归结。
P95第18题:
定义谓词: p ( x ): x 作案。
由五个侦察员的话为真,有
P ( z )∨ p ( q )( 1 )
(4分)
P ( q )∨ p ( s )( 2 )
P ( s )∨ p ( l )( 3 )
┐p ( z )∨┐p ( s )( 4 )
┐p ( q )∨┐p ( l )( 5 )
把结论的否定加入结论的否定的否定的子句中去,得:
┐ p ( x )∨┐ P ( x )( 6 )
因为这些全都是子句,所以化为子句集的步骤可以省略了。
( 1 ),( 4 )归结得:
p ( q )∨┐p ( s )( 7 )
( 2 ),( 7 )归结得:
p ( q )( 8 )
即:钱是盗窃犯。
( 5 ),( 8 )归结得:┐p ( l )( 9 )
李不是盗窃犯。
( 3 ),( 9 )归结得: p(s) (10)
孙是盗窃犯。
( 4 ),( 10 )归结得:┐p ( z )
赵不是盗窃犯。
所以,钱和孙是盗窃犯。
P95第19题:看附件
3-7.与/或形演绎推理有哪几种推理方式? 简述推理过程(见课本例题)P95 21 22 答:与/或形演绎推理分为正向演绎、逆向演绎和双向演绎推理。
与/或正向演绎推理过程如下:
1)用与/或树将已知事实表示出来;
2)用F规则的左部和与/或树的叶结点进行匹配,并将匹配成功的F规则加入大与/或树中;
3)重复步骤2),直至产生一个含有目标结点的一致解图。
与/或逆向演绎推理过程如下:
1)用与/或树将求解目标表示出来;
2)用B规则的右部和与/或树的叶结点进行匹配,并将匹配成功的B规则加入大与/或树中;
重复步骤2),直至产生一个含有已知事实结点的一致解图。
P95第21题:看附件
第5部分搜索问题求解
5-1 说明用状态空间法求解问题的过程,基本的求解方法有哪些?
答:求解问题过程:
1)将所要求的问题表示成状态空间,问题的解就在状态空间中
2)根据给定的条件,在状态空间中搜索出目标状态,从而求得问题的解
基本的求解方法有:
1)状态空间的穷搜索法
a,广度优先搜索算法 b,深度优先搜索算法。
2)启发式搜索法
a,图启发式搜索算法A、b,图启发式搜索算法A*
5-2什么是盲目搜索?启发式搜索法的基本思想是什么?评估函数如何定义?评估函数的作用是什么?
答:盲目搜索:指从当前状态到目标状态需要走多少步,或者每条路径的花费并不知道,所能做的只是可以区分出哪个是目标状态。因此它一般是按预定的搜索策略进行搜
索,没有考虑到问题本身的特性,所以具有很大的盲目性,效率不高,不便于复
杂问题的求解。
启发式搜索法的基本思想:是在搜索过程中加入了与被解问题有关的启发性信息
(特征),用于指导搜索朝着有希望至达目标结点的的方向前进,加速问题的求解
并找到最优解。只要知道问题的部分状态空间就可以求解,效率高。
评估函数定义:f(n)=g(n)+h(n)
这里个g(n)表示迄今为止搜索已产生的从初始结点S?到结点n的实际代价,h(n)表示从结点n到目标结点的估计代价,h(n)称为启发函数,它体现了搜索的启发信
息。
评估函数的作用:估计待扩展各结点在问题求解中的价值。
5-3 什么是问题归约法?与或图的作用是什么?为什么应用问题规约得到的状态空间可表示为与或图?
答:问题归约法把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解:只有当这些子问题全部解决时,问题才算解决,问题的解答由子问题的解
答联合构成。
与或图的作用是可以方便地把问题归约为子问题替换集合。
5-4 说明博弈树搜索的极大极小过程、 - 过程?P150 6
答:参照以下例题:
设有如图所示的博弈树,其中最下面的数字是假设的估值,请对该博弈树作如下工作:
(1) 计算各节点的倒推值;
(2)利用α-β剪枝技术剪去不必要的分枝。
解:各节点的倒推值和剪枝情况如下图所示:
倒推值和剪枝情况