1.请至少列举3位20世纪图灵奖获得者中的人工智能学者。，简述图灵测试的过程。批判
地用图灵测试来判定非人机器是否能思考进行评价，至少提出一种不同观点。
答(1):Marvin Minsky, John McCarthy ,Herbert Simon, Allen Newell, Raj Reddy
(2)人工智能之父：John McCarthy
(3)国际人工智能联合会议的英文全称与简称：International Joint Conference on AI: IJCAI 是一种测试机器是不是具备人类智能的方法。被测试的有一个人，另一个是声称自己有人类智力的机器。一种测试机器是不是具备人类智能的方法。
写出图搜索过程的A算法。
分别指出一般情况下A*和AO*算法是否可采纳，若不是，给出可采纳的条件。
答：对于某些问题，我们可以使用与问题有关的信息帮助减少搜索量，这种信息叫做
启发信息。
A算法（GraphSearch图搜索算法）：
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．（设置指针，调整指针）对于mM,
(1)若mCLOSED, mOPEN, 建立m到n的指针，并CONS(m, OPEN).
(2)(a)mOPEN, 考虑是否修改m的指针.
(b)mCLOSED,考虑是否修改m及在G中后裔的指针。
8．重排OPEN表中的节点（按某一任意确定的方式或者根据探索信息）。
9．GO LOOP
一般情况下，A*算法可采纳的，即如果解路径存在，A*算法一定能找到最佳解路径而
终止；
AO*算法：如果一个与或图存在解图，如果对于图中所有的节点n都有h(n)
且启发函数h满足单调限制，则AO*算法必然终止于找出最佳解图。
3.命题逻辑中，常用哪两种公式凡是？一阶逻辑中，常用哪两种公式范式？
答：命题逻辑中是吸取范式和和取范式。一阶逻辑中中：前束范式，Skolem范式
4.叙述一阶逻辑解释的定义；什么叫子句集S的Herbrand解释？在语义上证明子句集恒
假时，仅考虑该子句集的Herbrand解释是否够用？为什么？
答：（1）谓词逻辑中公式G的一个解释I，是由非空区域D和对G中常量符号，函数符号，谓词符号以下列规则进行的一组指定组成：
1.对每个常量符号，指定D中一个元素；
2.对每个n元函数符号，指定一个函数，即指
定Dn到D的一个映射；
3.对每个n元谓词符号，指定一个谓词，即指
定Dn到{T，F}的一个映射。
（2）定义（Herbrand域）设S为子句集，令H0是出现于子句集S的常量符号集。如果S中无常量符号出现，则H0由一个常量符号a组成。
5.2.3.
4.对于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域。(3) 在语义上证明子句集恒假时，仅考虑该子句集的Herbrand解释是够用的，因为 因为子句集S恒假，当且仅当S被其所有的H解释弄假什么是可分解的产生式系统？产生是系统求解的一般步骤，控制策略可以在哪些步骤中使用。 答：能够把产生式系统综合数据库的状态描述分解为若干组成部分，产生式规则可以分别用在各组成部分上，并且整个系统的终止条件可以用各组成部分的终止条件表示出来的产生式系统，称为可分解的产生式系统。 Procedure SPLIT 1.DATA ← 初始状态描述 2.{Di} ← DATA的分解结果；每个Di看成是独立的状态描述 3.until 对所有的Di {Di}，Di都满足终止条件，do: 4.begin5.在{Di}中选择一个不满足终止条件的D* 6.从{Di}中删除D* 7.从规则集合中选出一个可应用于D*的规则R 8.D ← 把R应用于D*的结果 9.{di} ← D的分解结果 10.把{di}加入{Di}中 11.EndSPLIT的控制策略：在步骤5中如何选取D*，在步骤7如何选取R。 搜索算法的可采纳性定义，并分别指出一般情况下A*算法。AO*算法是否可采纳，若不是，给出可采纳性的条件。 (1) 如果一个搜索算法对于任何具有解路径的图都能找到一条最佳路径，则称此算法为可采纳的。 (2) A*算法是可采纳的（如果解路径存在，A*一定由于找到最佳解路径而结束） AO*算法不可采纳，采纳的条件：如果一个AND/OR图存在解图，如果对于图中所有节点n都有h(n)
答：极小极大过程：
(1)按宽度优先生成0至L层的所有节点
(2)使用静态估计值函数（e(p)）计算第L层节点的函数值
(3)按照极小极大原则计算各层节点的到推值，直到求出初始节点的倒推为止，实现该倒推的走步就是相对好的走步
α剪枝：
如果一个MIN节点的β值小于或等于他的某一个MAX祖先节点的α值，则剪枝发生在该MIN节点之下；终止这个Min节点之下的搜索过程，这个MIN节点最终的倒推值就确定为这个β值
β剪枝：如果一个MAX节点的α值大于或等于他的某一个MIN祖先节点的β值，则剪枝发生在该MAX节点之下；终止这个MAX节点之下的搜索过程，这个MAX节点最终的倒推值就确定为这个α值
5.谓词逻辑中，对字句进行归结推理时，若被归结子句C1和C2中有相同的变元（变量），
请举例说明一定要改名的原因
C1=P(x)VQ(x),
C2=~P(f(x))
C1与C2有相同的变量x，若不改名，归结时，会出现替换：{f(x)/x}，这是不允许的
1.归结反证系统的产生式系统表示
2.子句集S的Herbrand域和普通解释的关系
子句集s的H解释是s的普通解释，
S的普通解释不一定是s的H解释：普通解释不是必须定义在H域上的，即使定义在H域上，也不一定是一个H解释
3.判断集合合一
4.C1,C2归结式
定义设C1, C2是两个无公共变量的子句(称为亲本子句),
L1, L2分别是C1, C2中的两个文字。
如果L1和～L2有最一般合一，则子句
(C1- {L1}) ( C2- {L2})
称为C1和C2的二元归结式，L1和L2称为归结文字
例.设C1=P(x) Q(x),C2=～P(a) R(x)
将C2中x改名为y。取L1＝P(x), L2=～P(a),={a/x},
于是(C1- {L1}) ( C2- {L2})
＝({P(a), Q(a)}-{P(a)}) ({～P(a), R(y)}-{～P(a)})
={Q(a), R(y)}= Q(a) R(y)----C1和C2的二元归结式.
5.原子集和封闭语义树
Davis-Putnam方法证明可满足（纯文字即只有L（~L）；删除纯文字的基字句后为空则S可满足，否则不满足；分裂规则，单文字规则L：删除但文字和包含单文字的基字句，为空则可满足的，否则删除~L的文字（注意不是删除基字句））
1.人工智能的主要研究学派，以及主要研究领域：
（1） 符号主义/逻辑主义学派--符号智能
（2） 连接主义-- 计算智能
（3） 行为主义--低级智能
2.产生式系统组成部分，产生式系统求解问题的一般步骤
答：（1）综合数据库
（2）产生式规则集
（3）控制系统
Procedure PRODUCTION
1.DATA←初始状态描述
2.until DATA 满足终止条件，do：
3.begin
4.在规则集合中，选出一条可用于DATA的规则R
5.DATA←把R应用于DATA所得的结果
6.End
4.产生式系统的控制策略有哪几种方式，简述各自的优缺点
答：（1）不可撤回的控制策略
优点：空间复杂度很低，速度快。
缺点：爬山函数有多个局部最大值时，会失败有很多局限性
（2）回溯控制策略
优点：占空间较少，应用最广。
缺点：时间复杂性一般；如果系统不包括有关解的知识，则规则选取是盲目的，要多次回溯，如果深度限制定的很低，可能找不到解。
（3）图搜素控制策略
优点：如果有解，一定能找到解
缺点：占空间大，速度较慢
6.与或图启发式搜素算法AO*的可采纳性条件
1.无信息的图搜索方法主要有哪两种？
深度优先搜索和宽度优先搜索
2.影响A算法启发能力的因素有哪些？
（1） 算法A所找到的解路径的费用
（2） 算法A在寻找这条解路径的过程中所需要扩展的节点数
（3） 计算启发函数所需要的计算量
7.什么叫子句集的Herbrand域？
定义（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域。
