考试题型：

一、选择2 ：20
二、填空5：10 主观题改成填空题
三、趣味编程题，10分

第0章 绪论

• 图灵测试

1950年图灵发表的《计算机与智能》中设计了一个测试，用以说明人工智能的概念。

• 希尔勒的中文屋子

证明：即使通过图灵测试也不能说明计算机能思维。

• 人工智能三大学派：

• 符号主义学派方面（专家系统、知识工程）
• 连接主义学派（神经网络）
• 行为主义学派（进化算法）

• 人工智能的发展简史

• 人工智能研究的经典课题
  

• 人工智能研究的新课题
  

第1章 搜索技术

• 根据是否使用启发式信息分为：

• 盲目搜索
• 启发式搜索

• 根据问题的表示方式分为：

状态空间搜索
状态空间搜索是用状态空间法来求解问题所进行的搜索
与或树搜索
与/或树搜索是指用问题规约方法来求解问题时所进行的搜索。

• 盲目搜索

• 一般图搜索算法中，提高搜索效率的关键在于优化OPEN表中节点的排序方式 。
• 一种简单的排序策略就是按预先确定的顺序或随机地排序新加入到OPEN表中的节点，常用的方式是深度优先和宽度优先。

1、深度优先搜索算法

深度优先搜索的特点：
 一般不能保证找到最优解
 当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制
 最坏情况时，搜索空间等同于穷举
 与回溯法的差别：图搜索
 是一个通用的与问题无关的方法

有限深度搜索和迭代加深搜索

2、宽度优先搜索算法

宽度优先搜索的特点：
 当问题有解时，一定能找到解
 当问题为单位耗散值，且问题有解时，一定能找到最优解
 方法与问题无关，具有通用性
 效率较低
 属于图搜索方法

3、启发式搜索：

利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。搜索过程中，要对OPEN表进行排序，需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度。

4、A算法：

 g*(n)：从s到n的最短路径的耗散值
 h*(n)：从n到g的最短路径的耗散值
 f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值
 g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值

• A算法的思想

算法A的设计与一般图搜索类似，划分为二个阶段：
1、初始化 
2、搜索循环
	MOVE-FIRST(OPEN)-取出OPEN表首的节点n 
	⑥扩展出n的子节点,插入搜索图G和OPEN表 
		对每个子节点ni,计算f(n,ni)=g(n,ni)+h(ni)
	⑦适当的标记和修改指针（子节点->父节点）
		(i)全新节点：f(ni)=f(n,ni)
		(ii)已出现在OPEN表中的节点
		(iii)已出现的CLOSE表中的节点
			IF f(ni)>f(n,ni) THEN
    			修改指针指向新父结点n
   　			f(ni)=f(n,ni)
	⑧排序OPEN表（评价函数f(n)的值排序）

5、爬山法的思想 （g(n)=0）

6、如果对于任何n，当h(n)=0时，A算法就成为了动态规划算法。

7、A*算法

8、数码问题的A*算法

定理1.4： 设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n) > h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。
因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。

第2章 与或图搜索问题

1、基本概念

与或图是一个超图，节点间通过连接符连接。

能解结点：

 终节点是能解节点
 若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。
 若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。

不能解结点：

 没有后裔的非终节点是不能解节点。
 若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。
 若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。
对与或图的搜索，是通过对局部图的评价来选择待扩展的节点。

2、AO*算法

算法划分二个阶段：
1、初始化 
	建立只包含初始状态节点n0的搜索图G:={n0}；
	待扩展局部解图集LGS:={}；
2、搜索循环
	选择和扩展LGS中的局部解图:
		④选择LGS中fi(n0)最小的待扩展解图G’；
		⑤随机选择G’中一个非终节点的叶节点作为n；
		⑥扩展n
			建立K-连接，子节点ni并加入G；
			计算子节点ni的f(ni)=h(ni)
		⑦若n存在j个K-连接
			LGS中删除G’
			将j个新的局部解图加入LGS;
	精化新局部解图代价的估计:
		用公式f(n) = K + h(n1) + h(n2) + … + h(nk)取代原先的f(n);
		递归地作用到初始节点n0；
	传递节点的能解性:
		标记作为终节点的子节点为能解节点；
		递归地传递节点的能解性到初始节点n0 

3、博弈问题特点：双人，一人一步，双方信息完备，零和

4、极小极大搜索思想：

 (1)设博弈的双方中一方为A，另一方为B。为一方(如A)寻找最优行动方案。
 (2)为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较。
 (3)为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。
 (4)当端节点的估值计算出来后，再推算出父节点的得分，方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。
 (5)如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。

• 一字棋第一阶段搜索树例子
  
  

5、α-β剪枝采用的是深度优先策略进行搜索

α-β过程就是把生成后继和倒推值估计结合起来，及时剪掉一些无用分支，以此来提高算法的效率。

α-β交替

• 在节点A处，已生成5个子节点，并且A处的倒推值等于-1(此时是另一方走，应考虑最坏的情况，选极小)
• 轮到B，生成第一个节点C静态值为-1，那么B的倒推值≤-1，B的其他后继节点可以不用管了，即B处β≤-1

• β值小于等于父节点的α值时的情况，实际上当某个MIN节点的β值不大于它的先辈的MAX节点（不一定是父节点）的α值时，则MIN节点就可以终止向下搜索。
• 同样，当某个节点的α值大于等于它的先辈MIN节点的β值时，则该MAX节点就可以终止向下搜索。

第3章 谓词逻辑与归结原理

1、基本概念

合取范式：命题、命题和的与， 如：
PΛ（ P∨Q）Λ（ ～P∨Q）

子句集S：合取范式形式下的子命题（元素）的集合
比如上面的子句集S：S = {P, P∨Q, ～P∨Q}

归结式：消除互补对，求新子句→得到归结式。
如子句：C1, C2， 归结式：R(C1, C2) = C1ΛC2

归结过程

• 将命题写成合取范式
• 求出子句集
• 对子句集使用归结推理规则
• 归结式作为新子句参加归结
• 归结式为空子句□ ，S是不可满足的（矛盾），原命题成立。
•  （证明完毕）
  谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。
  

前束范式
定义：公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。

SKOLEM标准：消去量词后的谓词公式。

置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。

• 置换的合成
  

合一:可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。

2、掌握将谓词逻辑转为子句集。

例题：
转化为谓词逻辑公式
转化为子句形式

3、掌握归结原理证明命名和求解问题。

例题：证明命名

第一步：问题用谓词表示

第二步：转化为子句形式

第三步：归结

例题：求解问题

先证明老师存在
加辅助谓词ANS（）

• 归结过程中的控制策略

• 删除策略
  
• 采用支撑集
  
• 线性归结
  

第4章 知识表示

• 逻辑表示法

一阶谓词逻辑是谓词逻辑中最直观的一种逻辑
谓词逻辑规范表达式：
P ( x1, x2, x3, …)， 这里P是谓词, xi是主体与客体。

• 产生式规则表示法

产生式系统的基本特征：

• 一组规则，即产生式本身。
  每个规则分左边右边。 如：天上下雨 → 地上湿
  （一般左边表示情况，即什么条件。发生时产生式被调用。通常用匹配方法和式情况。匹配成功时，执行右边规定的动作。）
• 数据库
  存放的数据是构成产生式的基本元素，又是产生式作用的对象。这里的数据是广义的常量、变量、多元组谓词、表、图像等。往往是事实或断言——知识元
• 一个解释程序
  从匹配成功的规则（可能不止一个）中选出一个加以执行。

产生式系统基本结构
工作存储器(数据库)： 存放当前已知的数据，包括推理过程中形成的中间结论。数据是广义的，可以是常量、多元数组、谓词、表示结构等。
产生式规则： 每条产生式规则分为左右两个部分。左部表示激活该产生式规则的条件，右部表示调用该产生式规则后所作的动作。条件是一组复杂的模式，规则之间的控制也不是语句的传递，而且满足条件的规则被激活但不一定立即执行，取决于产生式系统的冲突消解策略。
规则解释程序

• 匹配器：判断规则条件是否成立。
• 冲突消解器：选择可调用的规则。
• 解释器：执行规则的动作。并且在满足结束条件时终止产生式系统运行。

推理方法：正向、反向、双向、与或树

优点：
	模块性。
		规则与规则之间相互独立
	灵活性。
		知识库易于增加、修改、删除
	自然性。
		方便地表示专家的启发性知识与经验
	透明性。
		易于保留动作所产生的变化、轨迹

缺点：
	知识库维护难。
 	效率低。为了模块一致性。
 	理解难。由于规则一致性彼此之间不能调用。
 	
应用实例：
	用于化工工业测定分子结构的DENDRAL
	用于诊断脑膜炎和血液病毒感染的MYCIN
	估计矿藏的PROSPECTOR

• 语义网络表示法

表示形式
每一个要表达的事实用一个“结点”表示，而事实之间的关系用“弧线”表示。即，有向图表示的三元组，（结点1， 弧，结点2）连接而成。

类属关系:
A-Kind-of:表示一个事物是另一个事物的一种类型
A-Member-of:表示一个事物是另一个事物的成员
Is-a:表示一个事物是另一个事物的实例
包含关系（聚类关系）：
(它和类属关系的最主要的区别就是包含关系一般不具备属性的继承性。)
Part_of:表示一个事物是另一个事物的一部分
属性关系：
Have：表示一个结点具有另一个结点所描述的属性
Can：表示一个结点能做另一个结点的事情
位置关系:
Located-on: 一物在另一物之上
Located-at: 一物在何位置
Located-under: 一物在另一物之下
Located-inside: 一物在另一物之中
Located-outside: 一物在另一物之外
相近关系：
Similar-to: 相似
Near-to: 接近
时间关系：
Before：表示一个事件在一个事件之前发生
After：表示一个事件在一个事件之后发生。
多元逻辑关系：

• 框架表示法
  

框架之间的关系
	框架也分为类框架和实例框架。通过引入类-超类（AKO）
	及实例-类（ISA）关系来表示框架之间的包含关系和属于关系。
	框架理论将知识看成相互关系的成块组织。
推理方法：
	匹配：和语义网络一样遵循匹配原理。
	槽计算：继承（属性值、属性、限制），
	附加过程，即附加在数据结构上，启动时计算槽值。

• 脚本表示法

• 脚本方式是采用一个专用的框架，用来表示特定领域的知识。
• 脚本通过一些元语作为槽名来表代要表示的对象的基本行为。
• 有些像电影剧本。
  

第5章 机器学习

1、决策树学习

• 决策树学习是以实例为基础的归纳学习。
• 从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。

过程：
1 建立决策树，利用训练样本生成决策树模型。
开始，数据都在根节点
递归的进行数据分片
2 使用决策树对未知数据进行分类
按照决策树上采用的分割属性逐层往下，直到一个叶子节点

2、ID3的基本思想

• 构造决策树，决策树的每个节点对应一个非类别属性，每条边对应该属性的每个可能值。以信息熵的下降速度作为选取测试属性的标准，即所选的测试属性是从根到当前节点的路径上尚未被考虑的具有最高信息增益的属性。

例题：
第一步：计算适不适合运动的分类样本期望

第二步：计算属性天气的熵


第三步：计算信息增益

计算结果信息增益从大到小为：天气、湿度、风况、温度，则决策树为：

3、 朴素贝叶斯分类

因为P(X)是常量固定，所以只要看上面的表达式最大
又X的各个特征值独立： P(X|Ci)*P(Ci)=P(X1|Ci)P(X2|Ci)……P(Xn|Ci)*P(Ci)

4、 神经网络学习的基本概念

• 采用物理可实现的系统来模仿人脑神经细胞的结构和功能的系统。
• 人工神经网络的模型：

神经元
每一个细胞处于两种状态。突触联接有强度。多输入单输出。实质上传播的是脉冲信号，信号的强弱与脉冲频率成正比。

其中f称为特性函数，主要的特性函数有：二值函数，S形函数，分段函数
其中二值函数的定义为：

S型函数的定义为：

分段函数的定义为:

5、神经网络的分类、属性、优点

• 分类

（1）前馈网络：每层只与前层相联接 。信号由输入层到输出层单向传输。如BP网络，感知器
（2）反馈型全互联网络：所有计算单元之间都有联接。如：Hopfield网络

• 神经网络的属性

非线性，非局域性，非定常性，非凸性。

• 神经网络的优点

并行性；分布存储；容错性；学习能力

6、前馈型神经网

• 最初称之为感知器。应用最广泛的一种人工神经网络模型，最要原因是有BP学习方法。

• 简单（单层）感知器引入的学习算法称之为误差学习算法

• 多层感知器的输入输出关系与单层感知器完全相同。前一层的输出是下一层的输入。也被称为BP网络
  

8、BP（反向传播学习算法）

采用BP算法学习时要求传递函数为有界连续可微函数如sigmoid函数。先求误差，用梯度下降的方法求误差的传递，从后往前算。

BP 学习算法是由正向传播和反向传播两部分组成。在正向传播过程中，输入信息由输入层经隐节点单元逐层处理，并传向输出层。如果输出层不能得到期望的输出，则将误差信号沿原来的连接通路返回，通过修改各层神经元的连接权值，使得误差信号递减至最小。

做题补充：

ANN的中文意思是：人工神经元网络

反向传播( back-propagation,BP ）算法过程是从输出节点开始：将误差信号沿原来的连接通路返回，通过修改各层神经元的连接权值，使误差信号减至最小

语义网络下的推理是通过继承和匹配实现的