人工智能导论复习资料

题型

1、简答题（5题）

2、设计题

3、综合题

4、论述题（10分）

考点

第一章

1、人工智能的定义、发展；

2、人工智能的学派、认知观及其间的关系；

3、人工智能要素及系统分类；

4、人工智能的研究、应用领域（新的研究热点）；

第二章

1、状态空间法（渡河问题）；

2、谓词公式；

3、语义网络表示；

4、例题（三选一）；

第三章

1、图搜索过程、重排OPEN和重排原则；

2、盲目搜索（BFS、DFS、等代价搜索）；

3、启发式搜索，八数码难题（h1x=错放棋子数、h2x=曼哈顿距离）→ A*算法求解（OPEN、CLOSED标识）；

4、子句集求取；

5、推理：消去互补对，消解式；

6、含变量的消解式（置换）；

7、消解反演（PPT第122页【例1】、教材P101例3.9【储蓄问题】、PPT第127页【例3】、Happy Student【未找到】），反演求解；

8、规则演绎系统；

第四章

1、AI和CI（非数值方式+知识、数值数据，ABC交互关系）；

2、神经计算（研究进展、ANN结构及示例、基于NN的知识表示与推理）【设计一个NN，实现异或操作{P144-145}】；

3、遗传算法（教材P160执行实例、习题4-14）；

第六章

1、机器学习定义及其基本结构（习题6-1）；

2、决策树学习（CLS、ID3）；

3、神经网络学习（BP）；

4、归纳学习、类比学习、解释学习、知识发现、增强学习、深度学习；

第一章

一、人工智能的定义与发展

1、定义

• 【学科】计算机科学中涉及研究、设计和应用智能机器的一个分支。近期主要目标在于研究用机器模仿和执行人脑的某些智力功能，并开发相关理论和技术。
• 【能力】智能机器所执行的通常与人类智能有关的智能行为，如判断、推理、证明、识别、感知、理解、设计、思考、规划、学习和问题求解等思维活动。

2、发展

• 孕育期（1956年前）
• 形成期（1956－1970年）
• 暗淡期（1966－1974年）
• 知识应用期（1970－1988年）
• 集成发展期（1986－2010年)
• 融合发展期（2011年至今)

二、人工智能的认知观

1、符号主义（逻辑主义、心理学派、计算机学派）

        原理：物理符号系统假设和有限合理性原理；

        认为人工智能源于数理逻辑，人的认知基元是符号，认知过程即符号操作过程，人是一个物理符号系统，计算机也是，因此能用计算机模拟人的智能行为。

2、连接主义（仿生学派、生理学派）

        原理：神经网络及神经网络间的连接机制与学习算法；

        认为人工智能源于仿生学，特别是人脑模型的研究，人的思维基元是神经元，不是符号处理过程；

3、行为主义（进化主义、控制论学派）

        原理：控制论及感知-动作型控制系统；

        认为人工智能源于控制论，智能取决于感知和行动，智能不需要知识、表示、推理，人工智能可以逐步进化。

关系：长期共存与合作，取长补短，并走向融合和集成，为人工智能的发展作出贡献。

三、人工智能的要素和系统分类

1、要素

• 知识是人工智能之源
• 数据是人工智能之基
• 算法是人工智能之魂
• 算力是人工智能之力
• 人才是人工智能发展的关键

2、系统分类

        专家系统、模糊逻辑系统、神经网络系统、机器学习系统、仿生进化系统 、群体智能系统、分布式智能系统、集成智能系统、自主智能系统、人机协同智能系统。

四、人工智能的研究和应用领域

1、第一种解答

        问题求解与博弈；逻辑推理与定理证明；计算智能；分布式人工智能与Agent；自动程序设计；专家系统；机器学习；自然语言理解；机器人学；模式识别；机器视觉；神经网络；智能控制；智能调度与指挥；智能检索；系统与语言工具。

2、第二种解答

        问题求解(下棋程序)，逻辑推理与定理证明(四色定理证明)，自然语言理解，自动程序设计，专家系统，机器学习，神经网络，机器人学(星际探索机器人)，模式识别(手写识别，汽车牌照识别，指纹识别)，机器视觉(机器装配，卫星图像处理)，智能控制，智能检索，智能调度与指挥(汽车运输高度，列车编组指挥)，系统与语言工具。

        新的研究热点：分布式人工智能与Agent，计算智能与进化计算，数据挖掘与知识发现(超市市场商品数据分析)，人工生命。

第二章

一、状态空间表示

1、状态

        描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合。

2、算符

        使问题从一种状态变化为另一种状态的手段称为操作符或算符。

3、状态空间方法

        是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合（所有可能的问题初始状态集合S、操作符集合F、目标状态集合G），即三元状态（S，F，G）。

4、状态图示法

• 有向图： 一对节点用弧线连接起来，从一个节点指向另一个节点。父辈节点->后裔节点。
• 路径：节点序列（ni1，ni2，…,nik），长度为k的路径。
• 代价：节点ni指向节点nj这段弧线的代价cni,nj，两节点路径的代价等于该路径上所有弧线代价之和。
• 显示图：各节点及其具有代价的弧线由一张表明确给出，不适用于大型图。
• 隐示图：节点的无限集合{si}作为起始节点是已知的。后继节点算符Γ也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。

5、例题

（1）猴子和香蕉问题

（2）传教士野人问题

        设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？

        方法一

        1、状态

        三元表列(Nx,Ny,C)来表示修道士和野人在河的左岸的状态

        Nx表示修道士在左岸的实际人数

        Ny表示野人在左岸的实际人数

        C用来指示船是否在左岸（C=1表示在左岸，C=0表示在右岸）

        2、算符

        L(i,j)：把i个修道士和j个野人从左岸运输到右岸，R(i,j)：把i个修道士和j个野人从右岸运输到左岸【约束：i+j≤2，Nx≥Ny】

        3、状态空间
        初始状态集合S{(3，3，1)}

        操作序列集合F{L(1,0)，L(2,0)，L(1,1)，L(0,1)，L(0,2)，R(1,0)，R(2,0)，R(1,1)，R(0,1)，R(0,2)}

        目标状态集合G{(0，0，0)}

        4、求解

二、问题归约表示——以四梵塔问题为例

        试用四元数列结构表示四圆盘梵塔问题，并画出求解该问题的与或图。

        用四元数列（nA, nB, nC, nD）来表示状态，其中nA表示A盘落在第nA号柱子上，nB表示B盘落在第nB号柱子上，nC表示C盘落在第nC号柱子上，nD表示D盘落在第nD号柱子上。

        初始状态为1111，目标状态为3333

三、谓词逻辑表示——以习题2-6为例

        用谓词演算公式表示下列英文句子(多用而不是省用不同谓词和项。例如不要用单一的谓词字母来表示每个句子。)

        A computer system is intelligent if it can perform a task which,if performed by a human, requires intelligence.

        先定义基本的谓词

I(x) ：x is intelligent

P(x,y) ：x can perform y

Q(x) ：x requires intelligence

C(x) ：x is a computer system

        上面的句子可以表达为

※ 其他例子

---

---

---

四、语义网络表示

1、小燕从春天到秋天占有一个巢

2、John给Mary一个礼物

3、Semantic Network

4、习题2-7

        把下列语句表示成语义网络描述：

        (1) All man are mortal.

        (2) Every cloud has a silver lining.

        (3) All branch managers of DEC participate in a profit-sharing plan.

第三章

一、图搜索过程——以习题3-1为例

        什么是图搜索过程？其中，重排OPEN表意味着什么，重排的原则是什么?

        图搜索的一般过程如下：（描述图搜索（GRAPHSERCH）的一般过程）

(1) 建立一个搜索图G(初始只含有起始节点S)，把S放到未扩展节点表中（OPEN表）中。

(2) 建立一个已扩展节点表（CLOSED表），其初始为空表。

(3) LOOP：若OPEN表是空表，则失败退出。

(4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n，它是CLOSED表中节点的编号

(5) 若n为一目标节点，则有解并成功退出。此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)

(6) 扩展节点n，生成不是n的祖先的那些后继节点的集合M。将M添入图G中。

(7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针，并将它们加进OPEN表。

        · 对已经在OPEN或CLOSED表上的每个M成员，确定是否需要更改通到n的指针方向。

        · 对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。

(8) 按某一任意方式或按某个探试值，重排OPEN表。

(9) GO LOOP。

        重排OPEN表意味着，在第(6)步中，将优先扩展哪个节点，不同的排序标准对应着不同的搜索策略。

        重排的原则当视具体需求而定，不同的原则对应着不同的搜索策略，如果想尽快地找到一个解，则应当将最有可能达到目标节点的那些节点排在OPEN表的前面部分，如果想找到代价最小的解，则应当按代价从小到大的顺序重排OPEN表。

• OPEN表：存放已访问但未扩展节点；
• CLOSED表：存放已扩展节点；

二、盲目搜索

1、BFS

※ OPEN表是一个队列，CLOSED表是一个顺序表

2、DFS

※ OPEN表为一个堆栈，当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制，即有界深度优先搜索。

3、等代价搜索

三、启发式搜索

1、估价函数

        用于估计节点位于解路径上的“希望”，提供一个评定侯选扩展节点的方法 。估价函数的值越小，“希望”越大。 

2、有序搜索（最佳优先搜索）

        总是选择“最有希望”的节点作为下一个被扩展节点。

3、A*算法

4、八数码问题

（1）有序搜索

（2）A*算法

5、城市交通问题

四、消解原理

1、子句集的获取——以习题3-3为例

        将下列谓词演算公式化为一个子句集

        (∀x)｛P(x) → (∀y)［P(y) → P(f(x,y))］∧～(∀y)[Q(x,y)→P(y)］｝｝

（1）消去蕴涵符号：应用∨和～符号，以～A∨B替换A→B

（2）减少否定符号的辖域：每个否定符号～最多只用到一个谓词符号

（3）对变量标准化：对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元

（4）消去存在量词ョ：对于全称量词辖域内的存在量词，以Skolem函数代替存在量词内的约束变量；对于自由存在量词，以一个新常量替代（本题式中，w=g(x)为Skolem函数）

（5）化为前束形：把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分【前束形={前缀}(全称量词串) {母式}(无量词公式)】

（6）把母式化为合取范式：任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取(分配律)

（7）消去全称量词：所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词

（8）消去连词符号∧：用{A,B}代替(A∧B)，消去符号∧。最后得到一个有限集，其中每个公式是文字的析取

（9）更换变量名称：可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中

2、消解反演——以PPT例题为例

---

---

---

3、反演求解（详见教材P103-104）

第四章

一、计算智能含义

        计算智能借鉴仿生学的思想，基于人们对生物体智能机理的认识，采用数值计算的方法模拟实现人类的智能。涉及神经计算、模糊计算、进化计算、粒群计算、蚁群计算、自然计算、免疫计算、人工生命。

二、神经计算

1、人工神经网络结构

        许多神经元组成的信息处理网络：

• 对于每个节点i存在一个状态变量xi；
• 从节点i到节点j，存在一个连接权系数wji；
• 对于每个节点i，存在一个阈值θi；
• 对于每个节点i，定义一个变换函数fi(xi, wji, θi)，i≠j。

        主要学习算法有：

• 有师学习：根据期望和实际的网络输出的差来调整神经元间连接的强度或权；
• 无师学习：不需要知道期望输出；
• 增强学习：有师学习特例，不需要给出目标输出。

        人工神经网络结构分类：

• 递归网络：多个神经元互连以组织一个互连神经网络，有些神经元的输出被反馈至同层或前层神经元，因此信号能从正向和反向流通。
• 前馈网络：具有递阶分层结构，由一些同层神经元间不存在互连的层级组成，从输入层至输出层的信号通过单向连接流通；神经元从一层连接至下一层，不存在同层神经元间的连接。

2、基于神经网络的知识表示与推理——以习题4-6为例

        设计一个神经网络，用于计算含有两个输入的XOR函数。

三、 遗传算法——以教材实例和习题4-14为例

1、遗传算法的执行实例

2、试述遗传算法的基本原理，并说明遗传算法的求解步骤？

        基本原理：在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。

        求解步骤：

(1) 初始化群体;

(2) 计算群体上每个个体的适应度值;

(3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体;

(4) 按概率Pc进行交叉操作;

(5) 按概率Pc进行突变操作;

(6) 若没有满足某种停止条件，则转第(2)步， 否则进入下一步。

(7) 输出群体中适应度值最优的染色体作为问题的满意解或最优解。

第六章

一、机器学习的定义——以习题6-1为例

什么是学习和机器学习?为什么要研究机器学习?

        按照人工智能大师西蒙的观点，学习就是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样任务或类似任务时，会比现在做得更好或效率更高。

        机器学习是研究如何使用机器来模拟人类学习活动的一门学科，是机器学习是一门研究机器获取新知识和新技能，并识别现有知识的学问。这里所说的“机器”，指的就是计算机。

        现有的计算机系统和人工智能系统没有什么学习能力，至多也只有非常有限的学习能力，因而不能满足科技和生产提出的新要求。

二、机器学习的基本结构——以习题6-2为例

试述机器学习系统的基本结构，并说明各部分的作用。

        环境向系统的学习部分提供某些信息，学习部分利用这些信息修改知识库，以增进系统执行部分完成任务的效能，执行部分根据知识库完成任务，同时把获得的信息反馈给学习部分。

        影响学习系统设计的最重要的因素是环境向系统提供的信息。更具体地说是信息的质量。

三、决策树学习

1、构造算法CLS

2、学习算法ID3——以习题6-4为例

        或简答为：

• 创建树的Root（根）节点；
• 若Examples均为正，则返回label= ＋ 的单节点树Root；
• 若Examples都为反，则返回label= －的单节点树Root；
• 若Attributes为空，则返回单节点树Root，label = Examples中最普遍的Target_attribute值；
• 否则进一步求解Target_attribute值；
• 结束；
• 返回Root。

四、反向传播（BP）学习算法的实现——以习题6-9为例

1、初始化

2、输入训练样本对，计算各层输出

3、计算网络输出误差

4、计算各层误差信号

5、调整各层权值

6、检查网络总误差是否达到精度要求。满足则训练结束；不满足则返回步骤2