人工智能简答题.docx

1、20世纪40位图灵奖获得者中有6位人工智能学者：
Marvin Minsky（1969年）
John McCarthy（1971年）
Herbert Simon和Allen Newell（1975年）
Edward Feigenbaum和Raj Reddy （1994年）

1969年第一届国际人工智能联合会议（International Joint Conference on AI）召开, 此后每两年开一次，成为人工智能界最高级别的学术盛会。
2、简述人工智能的概念，目标
人工智能又称为智能模拟，用计算机模拟人脑的智能行为。包括感知、学习、推理、对策、决策、预测、直觉、联想。
根本目标 要求计算机不仅能模拟而且可以延伸、扩展人的智能,达到甚至超过人类智能的水平
3、人工智能的研究学派
符号主义/逻辑主义学派 --符号智能
连接主义 --计算智能
行为主义 --低级智能
4、人工智能的主要研究领域有哪些？
自动推理、专家系统、机器学习、自然语言理解、机器人学和 智能控制、模式识别、基于模型的诊断、智能规划、智能agent、神经网络、智能信息检索、自动程序设计、博弈
5、机器学习一般分为哪几种类型？
监督学习、无监督学习、半监督学习、增强学习
6、常用的知识表示方法有哪几种？简要回答各自的特点。
（1）非结构化方法
逻辑表示法 QA3,STRIPS,DART,MOMO
产生式系统 DENDRAL，MYCIN
（2）结构化方法
框架、语义网络
（3）过程式知识表示法
7、产生式系统
产生式系统是人工智能系统中常用的一种程序结构，是一种知识表示系统。 通常由以下三部分组成： 综合数据库、产生式规则集、控制系统。
综合数据库：存放问题的状态描述的数据结构。
产生式规则形式： 当规则的前提条件被某一状态描述满足时，就对该状态施行规则所指出的操作。
控制系统：
（1）选择规则：对同一个状态的多个可用规则排序。
（2）检验状态描述是否满足终止条件。
如果满足终止条件，则终止产生式系统的运行，并用使用过的规则序列构造出问题的解。

8、产生式系统的基本过程
Procedure PRODUCTION
1. DATA←初始状态描述
2. until DATA 满足终止条件，do：
3. begin
4. 在规则集合中，选出一条可用于DATA的规则R
5. DATA←把R应用于DATA所得的结果
6. End
9、产生式系统的特点
一、模块性强。综合数据库、规则集和控制系统相对独立，程序的修改更加容易。
二、各产生式规则相互独立，不能互相调用，增加一些或删去一些产生式规则都十分方便。
三、产生式规则的形式与人们推理所用的逻辑形式十分接近，人们具有的知识转换成产生式规则很容易，产生式规则也容易被人们读懂。DENDRAL和MYCIN都采用了产生式系统的结构。
10、回答产生式系统控制策略的分类，并说明各自的优缺点。
（1）不可撤回的控制策略
优点：空间复杂度很低，速度快。
缺点：爬山函数有多个局部极大值时，会失败，有很大局限性。
（2）回溯控制策略
优点：占空间较少，应用最广。
缺点：时间复杂性一般；如果系统不包括有关解的知识 ，则规则选取是盲目的，要多次回溯；如果深度限制得很低，可能找不到解。
（3）图搜索控制策略
优点：一定能找到解。
缺点：占空间大，速度较慢。
11、什么叫正向产生式系统？什么叫反向产生式系统？它们各自适合于怎样的实际问题？
正向产生式系统：从初始状态出发，不断地应用F规则，直到产生目标状态为止。
适用条件：初始节点数≤目标节点数
反向产生式系统（目标驱动控制） ：从目标状态出发，利用反向的产生式规则（ B规则 ）不断地产生子目标，直到产生出与初始状态相同的子目标为止。
适用条件：初始节点数≥目标节点数
12、叙述什么样的产生式系统是可交换产生式系统。（什么是可交换产生式系统？）
在某些产生式系统中。规则应用的次序对产生的状态无影响，即从初始状态到目标状态不依赖规则次序，因此可应用不可撤回式控制策略，从而提高了产生式系统的效率，这类产生式系统就是可交换的产生式系统。
13、叙述可交换产生式系统的主要特征，说明哪种搜索策略用可交换产生式系统比较合适。
a）每一条对D可应用的规则对于对D应用一条可应用规则后所产生的状态描述仍是可应用。
b)如果D满足目标条件，则对D应用任何一条可应用的规则所产生的状态描述也满足目标条件。
c）对D应用一个由可应用于D的规则所构成的规则序列所产生的状态描述不因序列的次序不同而改变。
不可撤回的控制方式比较合适。
14、什么是可分解的产生式系统？试述可分解的产生式系统求解问题的一般步骤。
能够把产生式系统综合数据库的状态描述分解为若干组成部分，产生式规则可以分别用在各组成部分上，并且整个系统的终止条件可以用在各组成部分的终止条件表示出来的产生式系统，称为可分解的产生式系统
Procedure SPLIT
1. DATA ← 初始状态描述
2. {Di} ← DATA的分解结果；每个Di看成是独立的状态描述
3. until 对所有的Di Î{Di}， Di都满足终止条件，do:
4. begin
5. 在{Di}中选择一个不满足终止条件的D*
6. 从{Di}中删除D*
7. 从规则集合中选出一个可应用于D*的规则R
8. D ← 把R应用于D*的结果
9. {di} ← D的分解结果
10. 把{di}加入{Di}中
11. end
15、一般的图搜索过程
ProcedureGRAPHSEARCH
1．G←{s}， OPEN ←（s）．
2．CLOSED ←NIL．
3．LOOP：IF OPEN=NIL,THEN FAIL．
4． n ← FIRST(OPEN)，OPEN ←TAIL(OPEN),CONS(n, CLOSED) ．
5． IF TERM(n)，THEN 成功结束
（解路径可通过追溯G中从n到s的指针获得）。
6． 扩展节点n，
令M={m︱ m是n的子节点，且m不是n的祖先} ，
G ←G ∪M
7． （设置指针，调整指针）对于mÎM,
(1)若mÏCLOSED, mÏOPEN, 建立m到n的指针，并CONS(m, OPEN).
(2)(a)mÎOPEN, 考虑是否修改m的指针.
(b)mÎCLOSED,考虑是否修改m及在G中后裔的指针。
8． 重排OPEN表中的节点（按某一任意确定的方式或者根据探索信息）。
9． GO LOOP
16、无信息的图搜索方法主要有哪两种？
深度优先搜索：排列OPEN表中的节点时按它们在搜索树中的深度递减排序 。深度最大的节点放在表的前面，深度相等的节点以任意方式排序。
宽度优先搜索：在排列OPEN表中节点时按它们在搜索图中的深度递增顺序，深度最小的节点放在表的前面。
深度相等的节点以任意方式排序。
17、什么叫启发信息？它是如何使用的？
启发式信息：用于帮助减少搜索量的与问题有关的信息或知识。
使用启发信息的一种重要方法是采用估价函数。 估价函数值低的节点排在OPEN表的前面。
18、请写出图搜索过程的A算法。分别指出A*和AO*算法是否可采纳，如果不是，给出可采纳的条件。
A算法: 使用估价函数f(n)=g(n)+h(n) 排列OPEN表中节点顺序的GRAPHSEARCH算法。
A*算法:对任何节点n都有h(n)≤h*(n)的A算法。
如果一个搜索算法对于任何具有解路径的图都能找到一条最佳路径，则称此算法为可采纳的。
A*算法是可采纳的（如果解路径存在，A*一定由于找到最佳解路径而结束）。
AO*算法是不可采纳的。采纳的条件：
如果一个AND/OR 图存在解图，如果对于图中所有的节点n都有好h（n）≤h*（n）,并且启发函数满足单调限制，则AO*算法必然终止于找到最佳解图。
19、什么叫A*算法？A*算法的主要性质是什么？
定理1 GRAPHSEARCH对有限图必然终止。
定理2 若存在s到目标的解路径，则算法A*终止前的任何时刻，OPEN表中总存在一个节点n’， n’在从s到目标的最佳解路径上，且满足f(n’) ≤f*(s) 。
定理3 若存在解路径，则A*算法必终止。
定理4 算法A*是可采纳的。（若解路径存在,A*一定找到最佳解路径而终止）。
定理5 算法A*选择的任意扩展点n都有f(n)≤f*(s)。
20、两个A*算法如何比较好坏？
设A1和A2是两个 A*算法，分别使用如下两个估价函数：
f1(n)=g1(n)+h1(n) f2(n)=g2(n)+h2(n)
其中，h1(n)和h2(n)是h*(n)的两个下界。若对于所有的非目标节点n，都有h2(n)＞h1(n)，则称算法A2比算法A1有较多的信息。
21、影响算法A启发能力的三个重要因素：
（1）算法A所找到的解路径的费用。
（2）算法A在寻找这条解路径的过程中所需要扩展的节点数。
（3）计算启发函数所需要的计算量
22、估价函数一般定义为f(n) = g(n) + h(n)，指明定义中各部分的含义，并说明为什么使用这种定义方式？
f(n)：表示从起点到目标，经由节点n最小费用路径上费用的估计。
g(n)：已经求得的当前搜索图中从初始节点到当前节点n的最优路径费用。
h(n)：从n到目标节点的最优路径费用的估计值。
便于找到最佳解路径。
23、搜索方法的启发能力有哪几种基本的度量方法？
渗透度是对一个搜索算法的搜索性能的度量，表示搜索集中指向某个目标的程度，而不是在无关的方向上徘徊。
定义为： P = L / T
其中，L是算法发现的解路径的长度，T是算法在寻找这条解路径期间所产生的节点（不包括初始节点，包括目标节点）
有效分枝系数就是一棵搜索树的平均分枝数．
设搜索树的深度是L，算法所产生的总节点数为T，有效分枝系数是B，则有
B＋B2十…＋BL=T
或
B（BL-1）/（B-1）=T
24、试述博弈树极大极小过程。
1）.按宽度优先生成0至L层所有节点。
2）.使用静态估值函数计算第L层节点的函数值。
3）.按极小极大原则计算各层节点的倒推值，直到求出初始节点的倒推值为止。实现该倒推值的走步就是相对好的走步
25、叙述α、β剪枝规则。什么情况下效率最高？
（A）（1）α剪枝：如果一个MIN节点的β值小于或等于它的某一个MAX祖先节点的α值，则剪枝发生在该MIN节点之下。
（2）β剪枝：如果一个MAX节点的α值大于或者等于它的某一个MIN祖先节点的β值，则剪枝发生在该MAX节点之下。
（B）α-β以各节点最终的返回值的顺序产生后继节点，即对MIN节点来说先产生具有最小值的后继，对MAX节点来说先产生具有最大值的后继（人为安排）。这种情况下，α-β搜索所产生的剪枝数最多，需要产生的尖端节点数最小，效率最高。使用相同存储空间，搜索深度可扩大一倍。
26、逻辑符号Þ 、®的含义和差别。
Þ：蕴含符号，G、H是公式，对任一解释I，若I满足G，则I也满足H ，称G蕴含H，记作GÞH。
®：逻辑连接词，G®H表示“若G，则H”。
G®H 是公式，GÞH不是公式，GÞH当且仅当G®H恒真。
27、一阶逻辑中，公式是怎样定义的？
一阶逻辑中的公式，被递归定义如下：
1）原子是公式。
2）若H,G是公式，则（~H）,,(HÚG),(HÙG),(H®G),(H G)是公式。
3） 若G是公式，x是G中的自由变量，则（"x）G，（$x）G 是公式。
4）所有公式都是有限次使用1）-3）生成的符号串。
28、叙述一阶逻辑解释的定义。
一阶逻辑解释中公式G的一个解释I，是由非空区域D和下列对G中常量符号、函数符号、谓词符号的一组指定组成：
1） 对每一个常量符号，指定D中一个元素。
2） 对每个n元函数符号，指定一个函数，即指定Dn到D 的一个映射
3） 对每个n元谓词符号，指定一个谓词，即指定Dn到D到{T,F}的一个映射。
21、命题逻辑中，常用哪两种公式范式？一阶逻辑中，常用哪两种范式？
析取范式和合取范式
有限个短语的析取式成为析取范式
有限个子句的合取式成为合取范式
前束范式，Skolem范式
29、什么叫子句集的Herbrand域？
设S为子句集，令H0是出现于子句集S的常量符号集。如果S中无常量符号出现，则H0由一个常量符号a组成。对于i＝1，2，…，令
Hi = Hi-1È｛所有形如f(t1，…，tn)的项｝
其中f(t1，…，tn)是出现在S中的所有n元函数符号， tjÎ Hi-1，j＝1，…，n．
称Hi为S的i级常量集，H¥ 称为S的Herbrand域，简称S的H域。
30、在语义上证明子句集恒假时，仅考虑该子句集的Herbrand解释是否够用？为什么？
够用，因为子句集S恒假，当且仅当S被其所有的H 解释弄假。
31、简要说明子句集S的Herbrand解释与普通解释的关系。
子句集S的H解释是S的普通解释。
S的普通解释不一定是S的H解释：普通解释不是必须定义在H域上，即使定义在H域上，也不一定是一个H解释。
任取普通解释I，依照I，可以按如下方法构造S的一个H解释I*，使得若 S在 I下为真则 S在I*下也为真
32、在合一算法中，设W是非空表达式集合，D是W的差异集合，则当D具有怎样的形式时，W是不可合一的？
（1）若D中无变量符号为元素，则W是不可合一的。
例. W={P(f(x)), P(g(x))}， D={f(x), g(x)}
（2）若D中有奇异元素和非奇异元素，则W是不可合一的。
W={P(x), P(x, y)} ， D={⊙, y}
（3）若D中元素有变量符号x和项t，且x出现在t中，则W是不可合一的。
33、什么是从子句集S推出子句C的归结演绎？
设S是子句集。从S推出子句C的一个归结演绎是如下一个有限子句序列：
C1，C2，…，Ck
其中Ci或者是S中子句，或者是Cj和Cr的归结式 (j<i, r< i)；并且Ck＝C。
称从子句集S演绎出子句C，是指存在一个从S推出C的演绎
34、在基于规则正向演绎系统中，规则和目标各要求怎样的形式？
初始状态描述：事实表达式的AND/OR形转换，与化Skolem范式过程类似
F规则的形式：L→W是正常Skolem化后恢复成蕴涵式，且要求：
L是单文字；W是AND/OR形公式；
目标：是文字的析取形式
35、基于规则的正向演绎系统是否完备？反向演绎是否完备？双向演绎是否完备？
均不完备
36、在基于规则的演绎系统中，什么是合一复合替换？为什么要考虑替换的相容性？
（1）设有替换集合{σ1 ，σ2 ，……，σn}，每一σi 具有如下形式：
σi = {ti1/vi1 ，……，tim(i)/vim(i)}
其中ti1，……，tim(i) 是项，vi1，……，vim(i)是变量；
我们用这些替换构造两个表达式U1和U2如下：
U1 ={v11，……，v1m(1)，……，vn1，……，vnm(n) }
U2 ={t11，……，t1m(1)，……，tn1，……，tnm(n)）}
如果U1 和U2是可合一的，则替换集合{σ1 ，σ2 ，……，σn}称作是相容
的，否则称作是不相容的，
U1 和U2的最一般合一替换也叫做{σ1 ，σ2 ，……，σn}的合一复合替换
（2）如果使用不相容的替换，可演绎出从事实规则归结不出的子句。
37、正向演绎系统不完备的原因
（1）目标形式单一
（2）改名不彻底，导致AND/OR图的一般性比子句差，有些推理问题通过使用子句的归结演绎能推出来，但用正向演绎系统推不出来。
38、归结原理有哪几种重要的改进？
支架集归结、语义归结、线性归结、锁归结、锁语义归结、广义归结

39、请指出提高基于规则演绎系统推理能力的几种方法。
（1）在AND/OR图中使用归结
（2）正向系统与反向系统的结合
40、给出归结反正系统的产生式系统表示。