人工智能期末复习（以柴玉梅老师教材为主）

人工智能期末复习

第一章 人工智能概述

1.什么是人工智能？人工智能的研究目标和意义是什么？

答：人工智能又称机器智能，粗略地概括为：用机器模拟或实现人类智能。

人工智能的研究目标和意义：主要研究用人工的方法和技术开发智能机器或智能系统，以模仿、延申和扩展人的智能、生物智能、自然智能，实现机器的智能行为。

人工智能定义分为四类： （1）像人一样思考的系统 （2）像人一样行动的系统 （3）理性地思考的系统 （4）理性地行动的系统

2.人工智能的三大研究学派、途径与方法。

答：

传统划分方法：

• 符号主义学派（Symbolicism）（功能模拟）

• 连接主义学派（Connectionism）（结构模拟）

• 行为主义学派（Evolutionism）（行为模拟）

现代划分方法：

• 符号智能流派

• 计算智能流派

• 群体智能流派

3.人工智能的基本技术有哪些？

答：

（1）知识表示技术 （2）知识推理、计算和搜索技术 （3）系统实现技术

4.人工智能的分支领域（基于应用领域）。

答：人工智能的研究涉及智能科学、认知科学、心理科学、脑及神经科学、生命科学、语言学、逻辑学、行为科学、教育科学、系统科学、数理科学以及控制论、科学方法论、哲学甚至经济学等众多学科领域。

5.人工智能何时、何地、怎么诞生？发展史。

答：1956年夏，十位来自数学、心理学、神经生理学、信息论和计算机方面的专家在美国达特莫斯大学召开一次历时两个月的会议，讨论了机器智能有关问题，会上麦卡锡提议用“人工智能”一词，标志人工智能学科的正式诞生。 发展： （1）推理期 （2）知识期 （3）学习期

6.什么是人工智能?它的近期、远期研究目标是什么?

答：用机器模拟或实现人类智能

近期目标：部分或某种程度实现机器智能，使现有的计算机更灵活好用、更聪明有用。 远期目标：制造智能机器，使其具有看、听、说、写等感知和交互能力，联想、学习、推理、理解等高级思维能力，分析、解决问题和发明创造的能力。

7.何为智能?人类智能主要包括哪些方面?

• 答：从微观和宏观的角度认识智能。微观上，考虑的是智能产生的根源或机理。人的智能产生于人的大脑，人在思维时，大脑中不同部位的神经元分工、协作，产生或传递各种信号，并产生相应的输出结果，支配人的具体行为。而人脑是一个由10¹¹～10¹²个神经元连接形成的巨系统，结构和活动规律都极其复杂，受相关学科发展的限制，人们至今还无法清楚地了解和解释智能的微观产生过程。智能的产生作为自然界的四大奥秘(物质的本质、宇宙的起源、生命的本质、智能的产生)之一仍然需要进一步的深入研究。目前，广泛应用的人工神经网络仅仅是对人脑极其粗浅的模拟。宏观上，从智能产生的认知过程来理解，人脑的智能都是某种心理活动或思维过程的结果；也可以从智能的外在表现来理解四智能是人类和一些动物特有的在解决具体问题时所表现出的智力或行为能力智能系统通常包括感知、记忆与思维、效应三大部分，甚至更狭义地理解为智能系统主要完成思维活动。

• 从知识工程的角度认识智能。人们常说“知识是人类智慧的结晶”,也常说“知识是智慧的源泉”。总之，知识和智慧或智能密不可分。所以，对智能还有一种解释：从内涵上，智能=知识十思维；从外延上，智能就是发现规律、运用规律的能力和分析问题、解决问题的能力(或者说获取知识、处理知识、运用知识的能力)。

第二章 基于图的知识表示与图搜索技术

状态图知识表示

知识的定义

• 心理学中对知识的定义是：知识是个体通过与环境相互作用后获得的信息及其组织。

• 费根鲍姆(Feigenbaum)认为：知识是经过消减、塑造、解释和转换的信息。

• 博恩斯坦(Bernstein)给出的定义是：知识是由特定领域的描述、关系和过程组成的。

• 概括地说，知识是高度组织起来的信息集团，是人们在长期的生活和社会实践中、科学研究和科学实验中积累起来的经验或对客观世界规律的认识等。

知识的分类

从不同的角度可以对知识进行不同的分类：

1)从应用领域来划分，知识可分为棠识性知识和领域(专业)性知识。

2)从在问题求解中的作用来划分，知识可分为叙述性知识、过程性知识和控制性知识。

3)从确定性来划分，知识可分为确定性知识和非确定性知识。

4)从表现形式来划分，知识可分为文字、符号、声音、图形、图像等。

问题求解框架

通常来说，问题是指事件或事物的已知或当前状态与目标状态之间有差异。而问题求解是指在一定的控制策略下，通过一系列的操作或运算来改变问题的状态，使之与目标状态接近或一致。

问题求解所需要的知识：

（1）叙述性知识（描述问题状态）

（2）过程性知识（描述状态之间变换）

（3）控制性知识（描述如何在当前状态下选择合适操作）

知识表示：

知识表示就是研究在计算机中如何用最合适的形式表示问题求解过程中所需要的各种知识，包括构成问题求解框架的全部知识。

知识表示技术是人工智能的基本技术之一，在整个问题求解过程中占有重要的地位。因此，问题求解时首先要解决知识在计算机中的表示问题，以便于知识的存储、检索、使用和修改等。

常用的知识表示形式有：状态空间图、与或图、谓词逻辑、产生式、框架、语义网络等，随着人工智能的发展，近年来又出现了许多新的知识表示形式。

图搜索技术

基于图的知识表示，其问题求解所使用的技术主要是搜索技术。在介绍具体的搜索技术之前，先简单介绍几个与搜索相关的概念。

1.搜索

搜索简单地说就是“寻找”,目的是找到问题的解。在问题求解过程中，待求解的问题被抽象成一定空间上的图，搜索过程就是从图中初始节点出发，沿着与之相连的边试探着前进，寻找目标节点或可解节点的过程。

2.搜索树

搜索过程中经过(考察过)的节点和边，按原图的连接关系，便会构成一个树形的有向图，称为搜索树。搜索树是一个搜索过程的搜索轨迹，或称之为搜索空间。

依据节点之间的关系，从搜索树中可以很容易地找出从初始节点到目标节点的路径(问题的解)。

3.搜索策略

在搜索过程中，当前节点可能有多个后继节点，如何在其中选择一个节点作为下一个搜索的节点就是搜索策略要解决的问题。

搜索策略将决定搜索过程按照什么样的顺序考察节点和经过状态空间图的哪些节点，不同的搜索过程将产生结构、规模不同的搜索树，甚至不同的解。显然，搜索树规模越小对应的搜索过程效率越高。

按照有无导向可区分为盲目搜索和启发式搜索

• 盲目搜索：无向导的搜索，也称穷举搜索。 在搜索过程中，没有任何背景知识作指导，不考虑任何与解有关的信息，随机地按预先规定的顺序（如广度优先和深度优先）机械地生成树的节点，并判断是否为解，直到找到解或证明问题无解为止。（对于较大或无限状态空间问题，盲目搜索效率太低）

• 启发式搜索：利用“启发性信息”作为导航的搜索过程。“启发性信息”就是与问题有关的、有利于尽快找到问题的信息或知识，如待解问题解的分布规律、求解该问题的经验、窍门等。（博弈、机器学习、数据挖掘、智能检索等）

深度优先和宽度优先搜索的优缺点

• 深度优先效率高，可能进入无限分支，在问题有解的情况下肯找不到解，并且不能保证是最优解。

• 宽度优先效率低，但是如果问题有解，一定能找到解，而且是最优解。

OPEN表和CLOSED表的作用

• OPEN表：动态数据结构，登记记录当前待考察的节点

• CLOSED表 ：动态数据结构，记录考察过的节点。

状态图搜索

状态空间图（P24）

把叙述性知识抽象成点，过程性知识抽象成边，那么很多问题都可以抽象成图形表示，最典型的就是状态空间图表示。

1.状态

状态对应叙述性知识，描述一个问题在开始、结束或中间的某一时刻所处的状况或状态。通常引进一组变量q₁,Q₂,…,qn,表示与问题状态相关的各种要素，并用这组变量所构成的多元组(q₁,q₂,…,qn)来表示状态。

状态在状态空间图中表示为节点。

2.操作

操作对应过程性知识，即状态转换规则，描述状态之间的关系。一个操作作用于状态通常是有条件的，所以描述一个操作要包含两个部分：条件和动作。条件指明被作用的状态要满足的约束条件，动作指明一个操作对状态的分量所做的改变。

操作的表示形式可以是一个机械性的步骤、过程、规则或算子。在程序中，状态转换规则可用数据对、条件语句、规则、函数、过程等表示。例如：如果室内温度低于26℃,则关闭空调。“温度低于26℃”是动作实施的条件，“关闭空调”是动作，其作用是改变状态，即提高室内的温度。

操作在状态空间图中表示为边。

3.状态空间图

状态空间常记为三元组：<S,F,G>。其中，S为初始状态的集合，F为操作的集合，G为目标状态的集合。

问题的状态空间图是一个描述该问题全部可能的状态及相互关系的有向图，如考虑操作的代价，状态空间图就是一个赋值有向图。

由问题的状态空间表示就可以构造出状态空间图。具体做法是，先画出全部合法状态对应的节点，然后，按照操作所要求的条件和动作画出所有节点之间的边。

4.求解

基于状态空间图表示，问题求解过程转化为在图中寻找从初始状态Qs到目标状态Qg的路径的搜索过程，也就是寻找操作序列a=fi,f₂,…,fn使得a(Q)=Qg,fi作用于Qs产生后继状态Q₁,f2作用于Q₁产生后继状态Q₂,……,fn作用于Qn-1产生后继状态Qg。存在这样的路径说明问题有解，否则问题无解。

状态空间的解可表示为三元组〈Qs,a,Qg>:表示以Qs为初始状态，Qg为目标状态的问题有解，且解为操作序列a。 在状态空间图表示中，对于简单问题求解，可以按照某种次序遍历状态空间图。

隐式状态空间图

以上给出的状态空间图的例子中表示了问题所有可能的状态及状态之间的关系，这种表示方式称为显式状态空间图，或称为状态空间图的显式表示。 对于复杂的问题，状态空间图所包含的节点数目可能非常大，甚至是无穷大，这时无法存储状态空间图的全部节点，只能采用状态空间图的隐式存储方式。

状态空间图的盲目搜索（穷举搜索）

根据在数据结构中所学知识可知，任何有向图都可以构造其对应的生成树。为简化讨论，本节考虑的状态空间图为树形结构，而且是非代价树。非代价树是指不计边上代价的树，或将所有边上的代价看做是相同的树，如都认为是单位1。在这种情况下，解的优劣就以解路径的长短为衡量标准。

盲目搜索是指搜索时不参考与具体待求解问题相关的任何信息，只是按预先设定的顺序逐个考察节点。盲目搜索与问题无关，具有通用性。

图和树的搜索算法在数据结构课程中已经学习过，分为递归算法和非递归算法。为了便于引入各种启发性知识，介绍不同的搜索策略，这里仅考虑非递归的搜索算法。

实现搜索算法时，为了控制节点的搜索顺序和记录搜索的轨迹，需要定义相关的数据结构，其中最重要的是两张表：OPEN表和CLOSED表。

OPEN表：专门登记已经生成但还没有考察的节点，即待考察节点。算法执行时总是从OPEN表的首部取出节点，不同的控制策略就是通过节点在OPEN表中的不同排序来实现的。

CLOSED表：用来记录考察过的节点以及节点之间的关系，如每个节点指向父节点的编号(返回指针)。搜索结束时，可以利用节点之间的关系，找到问题的解路径或解树。实际上，CLOSED表中存放的就是一定搜索策略下的搜索树。

广度优先搜索（BFS）

广度优先搜索是严格按节点在树中的出现位置一层一层向下的搜索过程。通过将OPEN表设计为一个队列来实现，将新生成的子节点放在OPEN表的尾部，保证先生成的节点先考察。

广度优先搜索算法：

• 步1把初始节点S₀放入OPEN表中；

• 步2若OPEN表为空，则搜索失败，退出；

• 步3否则取OPEN表中第一个节点N放在CLOSED表中，并冠以顺序编号n;

• 步4若节点N为目标节点，则搜索成功，利用CLOSED表中的返回指针找出S。到N的路径即为所求解，退出；

• 步5若N不可扩展，转步2;

• 步6否则扩展N,将其所有子节点配上指向N的返回指针放入OPEN表的尾部，转步2。

广度优先搜索又称为宽度优先或横向搜索

• 优点是：它是完备的，即如果问题有解，则它一定可以在一层层向下寻找的过程中找到解；同时，它又是可采纳的，即如果问题有解，它总是能够找到最优解，即该算法一定优先找到路径最短(层数最小)的解。

• 缺点是效率低。

深度优先搜索(DFS)

深度优先搜索是一种一直向下的搜索过程，它优先在自己的子节点集合中选择下一个被考察的节点，不断向纵深方向前进，直到到达叶子节点或受到深度限制时，才返回到上一级节点并沿另一个方向继续前进。在算法描述上，与广度优先搜索策略唯一不同的就是OPEN表被设计成后进先出的栈，新生成的子节点放在OPEN表的首部，后生成的节点优先被考察。

深度优先搜索算法：

• 步1把初始节点S₀放入OPEN表中；

• 步2若OPEN表为空，则搜索失败，退出；

• 步3否则取OPEN表中第一个节点N放在CLOSED表中，并冠以顺序编号n;

• 步4若节点N为目标节点，则搜索成功，利用CLOSED表中的返回指针找出S。到N的路径即为所求解，退出；

• 步5若N不可扩展，转步2;

• 步6否则扩展N,将其所有子节点配上指向N的指针放入OPEN表的首部，转步2。

状态空间图的启发式搜索

盲目搜索是按照算法预先安排好的顺序考察节点，应用于实际问题中不能保证在最短时间内得到最优路径，在搜索过程中没有考虑被求解的实际问题自身的一些特性或解决同类问题的经验窍门等。而启发式搜索过程，正是以这些相关知识为导航，指导搜索朝着最有希望找到解的方向前进，可以获得较高的搜索效率和近似最优解或最优解。

1.启发性知识和启发函数

启发式搜索的目的是利用启发性知识来引导搜索，减少搜索范围，降低问题复杂度。究竟什么是启发性知识呢? 通常来讲，启发性知识就是与被求解问题自身特性相关的知识，包括被求解问题的解的特性、解的分布规律和在实际当中求解此类问题的经验、技巧等，对应于问题求解框架中的控制性知识。显然，求解不同的问题需要使用不同的启发性知识，求解同一问题也可以使用不同的启发性知识。

例如，在游戏过程中要取得最终的胜利，玩者仅仅了解“任意格局下下一步怎样走是合法的”是远远不够的，要根据求解该类问题的经验、窍门等，在多个候选走法中选择一个对自己最有利的走法。一个玩者的水平高低正是体现在这些知识的运用上，这些知识就是启发性知识。要实现启发式搜索，需要把启发性知识形式化，即用一定的函数表示出来，并通过函数计算来评价每种选择的价值大小，用以指导搜索过程，这样的函数称为启发函数。

2.启发函数的设计

启发式搜索的关键就是设计启发函数，通常，启发函数用来估计搜索树中节点x与目标节点接近程度，记为h(x)。在实际设计过程中，启发函数可以是： 1)一个节点到目标节点的某种距离或差异的量度。 2)一个节点处在最佳路径上的概率。 3)根据主观经验给节点打分等。

在搜索过程中，启发函数主要用于指导扩展哪些节点或生成哪些节点或删除哪些节点的选择。然而，对于一个实际问题，设计一个好的启发函数往往是很困难的，因为在很多情况下人类解决问题的经验、窍门等知识很难形式化，甚至很难用语言表达出来。

启发式搜索要用启发函数来导航，其搜索算法就要在一般状态空间图搜索算法基础上，再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。

启发式搜索算法

以启发性知识为导航的搜索就是启发式搜索，按照考察节点的选择范围不同，算法分为全局择优和局部择优两种。

1.全局择优

全局择优搜索也叫最好优先搜索，它是在启发性知识导航下的广度优先搜索。此算法在OPEN表中保留所有已生成而未考察的节点，对其中的每个节点x计算启发函数h(x),从全部节点中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。

全局择优搜索算法：

• 步1把初始节点S₀放入OPEN表中，计算h(S₀);

• 步2若OPEN表为空，则搜索失败，退出；

• 步3否则，移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n;

• 步4若目标节点Sg=N,则搜索成功，利用CLOSED表中的返回指针找出S。到N的路径即为所求解，退出；

• 步5若N不可扩展，则转步2;

• 步6否则，扩展N,计算N的每个子节点x的启发函数值h(x),并将N所有子节点x配以指向N的返回指针后放入OPEN表中，依据启发函数值h(x)对节点的计算，对OPEN表中所有节点按其启发函数值的大小以升序排列，转步2。

全局择优搜索的完备性和可采纳性与所设计的启发函数有关。

2.局部择优

局部择优搜索是在启发性知识导航下的深度优先搜索，在OPEN表中保留所有已生成而未考察的节点，对其中新生成的每个子节点x计算启发函数h(x),从全部子节点中选出最优节点进行扩展，其选择下一个要考察节点的范围是刚刚生成的全部子节点，与全局择优搜索算法的区别仅在步6:

步6否则，扩展N,计算N的每个子节点x的启发函数值h(x),并将N的所有子节点x配以指向节点N的指针后，将全部子节点按启发函数值升序排列后放入OPEN表的首部，转步2。

启发式搜索很难保证是完备的，更不能保证是可采纳的。原因是由于人们对被求解问题特性的把握存在一定的局限性，因此，所设计的启发函数往往是对求解问题的一种估计，尤其是对于复杂的问题，无法保证它总是最准确的估计。

启发式搜索的A算法和A*算法

启发函数h(x)是对当前节点到达目标节点将要付出的代价的估计。在全局择优和局部择优搜索算法中，都没有考虑从初始节点到当前节点已经付出的实际代价g(x),但在很多实际问题中，已经付出的实际代价是必须考虑的，如TSP问题等。将两者同时考虑，用于指导搜索的算法称为A算法。

1.A算法

在A算法中，将启发函数h(x)与代价函数g(x)相结合得到估价函数f(x),定义为：f(x)=g(x)+h(x) 计算代价函数g(x)时，根节点对应初始状态，没有代价付出，所以代价为0。其余节点的代价可以用该节点的父节点的代价与由父节点生成该节点所付出的代价之和来计算。若用g(x)表示从初始节点S。到节点x的代价，用c(xi,xj)表示父节点xi到子节点x,的代价，则每个节点的代价计算如下：

g(S0) = 0(x为初始节点)； g(xi) = g(xi) + c(xi,xj).

现在，A算法中的导航是f(x)=g(x)+h(x),当其中的h(x)=0时，算法将仅由代价函数g(x)导航，这时得到的是代价树的非启发式搜索算法。此时，将全局择优搜索算法中的h(x)直接替换为g(x),可以得到分支界限法；将局部择优搜索算法中的h(x)直接替换为g(x),可以得到瞎子爬山法。这里不再对这两种算法做详细讨论。

设计A算法时，只需将启发式搜索算法中的h(x)换成f(x),并增加g(x)的计算即可。但在这里将给出的是基于图结构的(考虑回路)状态空间图的搜索算法。

• 步1把附有f(S₀)的初始节点S。放入OPEN表中；

• 步2若OPEN表为空，则搜索失败，退出；

• 步3否则，移出OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n;

• 步4 若目标节点Sg=N,则搜索成功，利用CLOSED表中的返回指针找出路径即为所求解，退出；

• 步5若N不可扩展，则转步2;

• 步6 否则，扩展N,生成一组子节点x;,并计算f(xi),对这组节点x;做如下处理： 1)若x;是N的先辈节点，则删除； 2)若x;存在于OPEN或CLOSED表中，也删除之，但表明此时存在两条初始节点S₀到x,的路径；如果新路径较短，则修改x;节点的返回指针(指向N),并修改x;及其后裔节点和f值；同时若x;存在于CLOSED表中，则将其移出放入OPEN表重新考察； 3)对其余子节点配上指向N的返回指针放入OPEN表；

• 步7对OPEN表中所有节点按f值以升序排列，转步2。

2.A * 算法 在A算法中，如果估价函数中的启发函数h(x)对所有的节点x均满足： h(x)≤h* (x) 则称其为A* 算法，其中，h* (x)是从节点x到目标节点的实际最小代价。 A* 算法也称为最佳图搜索算法，如果问题存在最优解，A* 算法能保证找到最优解。如 果h(x)=0,一定满足A* 算法的条件h(x)≤h* (x),但它已经退化为分支界限法，具备完备性和可采纳性，但效率低。因此，使用A* 算法时，定义的h应尽可能大一些，使其接近h*,以得到较高的搜索效率。当然，对很多实际问题来说，做到这一点是很困难的。

加权状态图搜索

上述的分支界限和瞎子爬山

与或图知识表示

在问题求解过程中，常常将一个复杂的问题P分解为一组子问题P,P₂,…,Pn,当这些子问题全部可解时，原问题P可解；任何一个子问题无解时，都将导致原问题P无解。即一个问题与一组子问题的“与”等价。例如，保送研究生的条件是每门课程成绩都在85分以上。

有时将一个复杂的问题P变换为与之等价的一组子问题P₁,P₂,…,Pn,其中任何一个子问题可解时，原问题P可解；全部子问题无解时，原问题P无解。即一个问题与一组子问题的“或”等价。如保送研究生的条件中，要求英语成绩是通过六级考试，或者通过GRE考试。

将问题对应节点，分解或变换关系对应边，这样就可以将一个问题求解过程中的分解和变换过程表示为一棵与或图。与状态空间图的意义不同，这里的与或图对应的是问题空间图。

与或图中节点代表问题，子节点为与关系的节点为与节点，子节点为或关系的节点为或节点，在与或图中无子节点的节点称为端节点。包含与或节点的图称为与或图。需要注意的是，与或图表示的是问题空间，与状态空间图的意义不同。

直接可解的问题称为本原问题，对应的节点称为终止节点。

与或图也可以用三元组表示：(Q,F,Qn)。其中，Q。表示初始问题，F表示问题分(解变换规则集，Q,表示本原问题集。

节点的可解性判别：

1)终止节点是可解节点；

2)一个与节点可解，当且仅当其全部子节点可解；

3)一个或节点可解，只要其子节点至少有一个可解；

4)非终止节点的端节点是不可解节点；

5)一个与节点不可解，只要其子节点至少有一个不可解；

6)一个或节点不可解，当且仅当其全部子节点不可解。

与或树的解树：由能判别(标记)根节点是可解节点的全部节点和边所组成的子树。

与或图搜索

与或树的盲目搜索

为简单起见，这里仅考虑与或树(不考虑带有回路的图)的搜索。与或树的搜索也分为盲目搜索和启发式搜索，盲目搜索又分为广度优先搜索和深度优先搜索。与或树搜索与状态树搜索的不同之处在于：

1)搜索过程中包含可解性标记过程。一旦生成已知可解或不可解的节点，需要向上标记其先辈节点的可解性，当根节点的可解性得到标记后，搜索终止，根据根节点的可解性返回解树或证明问题无解。

2)包含从OPEN表中删除“具有可解或不可解先辈节点”的节点的过程。因为先辈节点的可解性或不可解性一旦确定之后，就不需要再通过其他子节点对它进行标记。

与或树的广度优先搜索

与或树的广度优先搜索与状态树(或树)的搜索过程类似，也是一层一层向下搜索。与或树的广度优先搜索算法：

• 步1把初始节点S。放入OPEN表；

• 步2把OPEN表中的第一个节点N取出放入CLOSED表，并冠以编号n;

• 步3 如果节点N可扩展，则做如下工作： 1)扩展节点N,将其子节点放入OPEN表尾部，并为每个子节点配置指向父节点N的返回指针。 2)考察这些节点中是否有终止节点。若有，将它们放入CLOSED表，标记这些节点为可解节点。应用节点的可解性判别，对节点N的先辈节点进行可解性标记。如果初始节点S₀也被标记为可解节点，搜索成功，按照CLOSED表中的返回指针给出解树，退出。 3)若S。不能确定为可解节点，则从OPEN表中删除具有可解先辈节点的节点， 转步2。

• 步4 如果节点N不可扩展，则做如下工作： 1)标示节点N为不可解节点。 2)应用节点的可解性判别，对节点N的先辈节点进行不可解标记。如果初始节点S。也被标记为不可解节点，则搜索失败，退出。 3)如果不能确定S。为不可解节点，则从OPEN表中删去具有不可解先辈节点的 节点。转步2。

与或树的深度优先搜索策略

与或树的深度优先搜索过程也类似

于或树的深度优先搜索，即优先考察子节点；同时，也要包含可解性标记过程和删除“具有可解和不可解先辈节点”的节点的过程。其算法可对与或树的广度优先搜索算法的步3中1)做如下修改：

步3如果节点N可扩展，则做下列工作： 1)扩展节点N,将其子节点放入OPEN表首部，并为每个子节点配置指向父节点N的返回指针。

与或树的启发式搜索

在与或树的搜索过程中，搜索树的生长方向是从根节点开始，自上而下进行的；而与或树的解树是由终止节点(可解节点)自下而上进行标记的。有代价时，代价的计算也是自下而上进行的；在搜索没到达端节点之前，无法知道根节点和中间节点的实际代价，所以，在决定扩展哪些节点的时候只能先估计其代价。

为求得最小代价解树，每次在确定要扩展的节点时，只能是先往前多看几步，利用启发信息，通过对更深层节点代价的估计，计算(估计)扩展一个节点可能要付出的代价，然后，选择代价最小的节点进行扩展，这种根据对代价的估计决定搜索路线的方法称为与或树的有序搜索或启发式搜索。

1.解树的代价(树根的代价)

与或树中解树的代价是从树叶开始自下而上逐层计算求得的。用g(x)表示节点x的代价，c(x,y)表示节点x到其子节点y的代价(即边xy的代价)。

解树代价的计算方法是： 1)若x是终止节点，则g(x)=0。 2)若x是或节点，则g(x)=min{c(x,y:)+g(y.)}。 3)若x是与节点，则有两种计算法则： g(x)=2ic(r,y)+g(y))和代价法则：最大代价法则：g(x)=max{c(x,y:)+g(y:)} 4)若x是非终止的端节点，则g(x)=无穷。 或节点的最小代价法则容易理解，因为解树中，或节点的任何一个子节点可解都能标记该或节点是可解的，所以，取代价最小的子节点的代价作为或节点的代价。 对与节点是采用和代价法则还是采用最大代价法则进行计算，则要根据实际情况进行选择。

如在软件开发中，某一系统A可以分解为三个子系统A₁、A₂、A₃(即原问题与三个子问题的“与”等价),三个子系统相对独立，单独开发三个子系统的时间分别为t₁、t₂、t₃,将开发耗费的时间作为系统A开发的代价。如果采用并行开发模式，即A₁、A₂、A₃同时开发，那么这时系统A开发的代价是max{t₁,t₂,t₃},即采用最大代价法则；如果采用串行开发模式，即先开发A₁,再开发A₂,之后是A₃,那么这时系统A开发的代价是t₁+t₂+t₃,即采用和代价法则。

希望树

如前所述，节点的代价要通过其子节点的代价来计算，与先父节点、后子节点的搜索方向相反，在搜索过程中，只能利用估价函数对节点的代价进行估计。

具体做法是： 1)按扩展深度扩展节点，得到新的子节点x,用估价函数来计算x的代价g(x)称为x的估计值。 2)向上倒推计算x的父节点及先辈节点y的代价g(y),称为y的倒推值，并用y的倒推值代替y原来的估计值。 3)重复步骤1)、2),直到扩展到端节点，能够标记初始节点的可解性为止。不断用节点的倒推值代替其估计值的依据是：越接近端节点，估计越准确。

有序搜索的目的是求最优解树，因此，要求在搜索过程中，按照估价函数，任一时刻求出的部分解树都是代价最小的。为此，每次挑选欲扩展的节点都应该挑选最有希望成为最优解树一部分的节点。由这些节点及其先辈节点所构成的与或树是最优解树的近根部分，称为希望树，或希望解树。

希望树的定义如下： 1)初始节点S₀在希望解树中。

2)节点x在希望解树中，则一定有：如果x是具有子节点的或节点，则它具有最小代价的子节点一定在希望解树中；如果x是具有子节点的与节点，则它的全部子节点都在希望解树中。

与或树的有序搜索过程就是寻找希望树的过程，随着扩展深度的增加，希望树也会不断变化。

与或树的有序搜索算法：

• 步1把初始节点S。放入OPEN表中；

• 步2根据当前搜索树中节点的代价值求出以S。为根的希望树T;

• 步3依次把OPEN表中T的末端节点N选出放入CLOSED表中；

• 步4 如果节点N是终止节点，则做下列工作： 1)标记N为可解节点； 2)对T应用可解标记过程，标记N的先辈节点；3)若初始节点S。被标记为可解节点，则T就是最优解树，成功退出； 4)若初始节点S₀还不能被标记为可解节点，则从OPEN表中删去具有可解先辈的所有节点；

• 步5 如果节点N是不可扩展节点，则做下列工作： 1)标记N为不可解节点； 2)对T应用不可解标记过程，标记N的先辈节点； 3)若初始节点S。被标记为不可解节点，则失败退出； 4)若初始节点S。还不能被标记为不可解节点，则从OPEN表中删去具有不可解先辈的所有节点；

• 步6 如果节点N可扩展，则： 1)扩展节点N,产生N的所有子节点。并把这些子节点都放入OPEN表中，并为每一个子节点配置指向父节点(节点N)的指针； 2)用估价函数计算这些子节点的估计值，并计算其先辈节点的倒推值；

• 步7否则，转步2。

博弈树搜索

博弈，广义地理解为由若干主体参加的斗智、斗勇的竞争过程。在对弈、军事、经济、商业、游戏等领域广泛地存在。常常狭义地理解为对弈类游戏。

博弈问题的状态空间 博弈问题中，棋局用状态表示，对弈双方任意合法地走一步，都使棋局从一个状态变到另一个状态，所以，所有合法的走步就是操作。开局是初始状态，终局可能有多种，站在某一方的角度，有胜局、和局和负局之分。有了状态和操作的描述，就可以构造博弈问题的状态空间。

值得注意的是，对弈与迷宫类(如重排九宫)问题不同，对于迷宫问题，探索者有完全的选择权，每一步都可以沿着他认为有利的路线走下去。而对弈问题中对弈双方都只有一半选择权，双方的利益是完全冲突的。因此，讨论对弈问题时，评价一个棋局的好坏与胜负，一定要站在某方的立场上。另外，还需要假定双方都是精通博弈者，即每步选择都是理智的。

【博弈树：博弈问题的状态空间就是以状态为节点、以合法走步为边的一个树形图，称为博弈树。】

博弈树的特点

假设博弈过程是由双方来完成的，称我方为MAX方，对方为MIN方，以下总是站在MAX方的立场讨论问题。由于双方的利益是完全冲突的，在博弈树中存在与、或两种节点。

与节点：博弈过程中，对手(MIN)每走一着棋(半个回合),都力图干扰MAX的选择，使其偏离取胜的目标。轮到MIN走棋时，由于它掌握着出棋的主动权，此时只要全部走法中有一个能导致对方(MAX)败局，或者说，有一个走法能让对手(MAX)取得更低的得分，它就会毫不犹豫地选择这一走法，因此，站在我方(MAX)的立场上，由MIN出棋的节点具有与节点的性质。

或节点：博弈过程中，我方(MAX)每走一着棋(半个回合),都力图使自己通往取胜的目标。轮到MAX走棋时，由于它掌握着出棋的主动权，此时只要各种走法中有一个能通向胜局，或者说，有一个走法能让它取得更高的得分，它就会毫不犹豫地选择这一走法，因此，站在我方(MAX)的立场上，MAX出棋的节点具有或节点的性质。

博弈的过程是双方轮流走步，因此，博弈树中的与、或节点就会按层交替出现。这就是博弈树的特点。

常见的博弈树包含大量的节点(状态),从初局开始，随着对弈步数的增加，所产生的状态数目会以指数规模增加，即出现所谓的棋局组合爆炸现象。因此，博弈树的搜索也必须是在隐式图的基础上进行的启发式搜索。

为简单起见，这里仅讨论二人零和、全信息、非偶然性博弈。

“二人零和”是指对弈双方的利益是完全冲突的，利益之和永远为零；博弈的结果有三种情况：MAX方胜，MIN方败；MAX方败，MIN方胜；双方平局。很多博弈问题都满足“二人零和”这一条件，如国际象棋。但囚徒困境是经典的非零和博弈例子。

“全信息”是指在对弈过程中，当前的格局及双方对弈的历史是公开的。

“非偶然性”是指对弈双方的每一步选择都是“理智”的，即在采取行动前，都要根据自己的静态估值函数(启发函数)进行得失分析，选取对自己最有利而对对方最不利的对策，不存在“碰运气”式的随机因素。

在对弈问题中，为了从众多可供选择的行动方案中选出一个对自己最为有利的行动方案，就需要对当前的情况以及将要发生的情况进行分析，从中选出最佳走步。最常用的方法为极小极大分析及α-β剪枝技术，以下将进行简单介绍。

极小极大分析法

先介绍两个术语： 静态估值：为了找到当前的最佳走步，一般要向前看多个回合。为此，需要根据问题的特性信息(来自博弈者的经验)定义一个静态估值函数，估价当前博弈树末端节点的得分，称为格局的静态估值。

倒推值：当末端节点的估值计算出来后，再向上推算出各节点的得分，称为倒推值。极小极大分析方法就是根据当前棋局的静态估值，计算先辈节点倒推值，为其中的一方(例如MAX)寻找一个最佳走步。其基本思想可通俗地概括为“立足于最坏，争取最好”。

【极小极大分析法：对与节点求极小值、对或节点求极大值计算各先辈节点倒推值的方法。】

对与节点，选其子节点中一个极小得分作为父节点的得分(倒推值),因为与节点是对方(MIN)的节点，站在我方(MAX)的观点，对方的选择一定设法使我方取得极小分，这就是我方考虑与节点得分时所谓的“立足于最坏”。

对或节点，选其子节点中一个极大得分作为父节点的得分(倒推值),因为或节点是我方的节点，站在我方的观点，我方的选择一定要争取得到极大分，这就是我方考虑或节点得分时所谓的“争取最好”。

用极小极大分析方法求最佳走步的具体过程是：

• 首先，按扩展深度限制(回合数)扩展节点，对末端节点求静态估值；

• 然后，对内部节点按极小极大分析方法求倒推值；

• 最后，根据根节点的倒推值决定一个最佳走步。

• 每扩展一次，对内部节点都用新的倒推值代替原来的静态估值或原来的倒推值。如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。

α-β剪枝

极小极大分析法需要按深度限制生成全部端节点，并通过计算全部节点的静态估值或倒推值选择当前节点的一个最佳走步，得到当前格局的后继格局。这种方法将“生成后继”和“估计棋局”两个过程分开考虑。然而，博弈问题往往随着向前看步数的增加，要估计的端节点的个数以指数级增加。因此，极小极大分析法的缺点是效率低。

为此，考虑把“生成后继”和“估计棋局”两个过程结合起来，边生成博弈树边计算各节点的倒推值，并且根据已知倒推值的范围，及时停止那些不必要节点的生成，即相当于对这些节点(及其以下分支)“剪枝”,从而减少搜索节点的数目，提高搜索效率，α-β剪枝就是一种典型的在极小极大分析中使用的剪枝技术。

α剪枝：对于一个与节点MIN,若能估计出其倒推值的上确界β,并且β不大于它的父节点(或节点)的倒推值的下确界α,即α≥β,则不必生成该节点的其余子节点(因为这些子节点的估值不会提高MIN的父节点的倒推值),这一过程称为α剪枝。

β剪枝：对于一个或节点MAX,若能估计出其倒推值的下确界α,并且α不小于MAX的父节点(与节点)的倒推值的上确界β,即α≤β,则不必生成该节点的其余子节点(因为这些子节点的估值不会降低MAX的父节点的倒推值),这一过程称为β剪枝。

需要说明的是，对与节点求上确界β,对其子节点(或节点)考虑是否可以进行α剪枝；对或节点求下确界α,对其子节点(与节点)考虑是否可以进行β剪枝。

对于与节点，如果它的父节点(或节点)的α值已求出，就逐个用它的子节点去判断该与节点的β值，一旦发现α,对其余子节点立即进行α剪枝。但如果一个与节点的父节点(或节点)的α值还没有求出，就要用该与节点的全部子节点求出极小值，再倒推出父节点的α值。对或节点情况类似。对于不能剪枝的节点仍然要使用极小极大分析方法。

第三章 基于谓词逻辑的知识表示与机器推理技术

▪ 谓词逻辑简介

基于命题逻辑的知识表示

用大写字母来表示命题 特定命题----命题常量 抽象命题（含未知参数x）----命题变量 从符号上无法表达不同对象的相同特征 >> 发展了谓词逻辑

谓词逻辑

谓词形如P(x1,x2,…,xn) 命题函数：谓词公式 如果一个谓词公式中所有的个体变量都被量化，或者所有的变量都用常量代替，这时谓词公式就变成了一个命题

基于谓词逻辑的知识表示

任意+蕴含 存在+合取

▪ 自然演绎推理

从一组用谓词公式表示的事实出发，利用常用的逻辑等价式对公式进行等价变换，再使用推理定律以及推理规则推出结论，这一过程称之为自然演绎推理

逻辑等价式/推理定律

• 优点：证明的过程比较自然，容易理解

• 缺点：容易出现中间结论的组合爆炸，针对复杂实际推理问题时效率较低

▪ 化子句集的过程

1、消去蕴含词和等值词。 2、使否定词仅作用于原子公式。 3、适当改名使量词间不含同名指导变元。 4、消去存在量词。 5、消去全称量词。 6、化公式为合取范式。 7、适当改名，使子句间无同名变元。 8、消去合取词，以子句为元素组成一个集合S。

▪ 命题逻辑的归结原理

归结反演本质上是一种反证法，即要证明命题Q在前提F下为真，只需要证明反命题恒假

设C1， C2是命题逻辑中的两个子句 C1中有文字L1 ，C2中有文字L2 ，且L1与L2互补， 从C1 、 C2中分别删除L1 、L2 ，再将剩余部分析取起来，记构成的新子句为C1 2，则C1 2为C1 、 C2的归结式。

▪ 替换与合一

一个替换（Substitution）是形如 {t1/x1, t2/x2, …, tn/xn}的有限集合

设σ是原子公式集S的一个合一，如果对S 的任何一个合一θ都存在一个替换λ，使得 θ ＝ σ •λ 则称σ为S的最一般合一(Most General Unifier),简称MGU。

▪ 谓词逻辑中的归结原理

• C1，C2为无相同变元的子句；

• L1，L2为其中的两个文字；

• L1和¬L2有最一般合一σ； C1，C2的二元归结式（二元消解式）为： C1σ －{L1 σ}） ∪ （ C2 σ－ {L2 σ}）

▪ 应用归结原理求取问题答案

（1）先为待求解的问题找一个合适的求证目标谓词； （2）再对目标否定子句增配（以析取形式）一个辅 助谓词，该谓词的变元必须与对应目标谓词中的变 元完全一致； （3）进行归结； （4）当归结是刚好只剩下辅助谓词时，辅助谓词中 原变元位置上的项就是所求的结果。

▪ 归结策略

▪ 删除策略

参加归结的子句越少，归结速度越快，所以，提高归结效率的最简单办法是使用删除策略，减少大量无用子句的产生。

首先，删除含有永真式PV-P的子句，因为它不影响子句集的不可满足性。其次，在归结演绎过程会出现被别的子句类含的子句。

定义

类含 设C₁和C₂是两个子句，若存在替换σ,使得C₁oCC₂,则称C₁类含C₂。

被类含的子句被类含它的子句所逻辑蕴含，所以它是多余的，删除被类含的子句不会影响子句集的不可满足性。

纯文字 在子句集中无补的文字称为纯文字。

因为纯文字在子句集中无互补文字存在，所以包含纯文字的子句参与归结，永远也得不到空子句，因此，删除含有纯文字的子句不影响子句集的不可满足性。总之，删除策略是在归结过程中可随时删除以下子句： (1)含有永真式的子句。 (2)被子句集中别的子句类含的子句。 (3)含有纯文字的子句。

删除策略有如下特点： 删除策略的思想是及早删除无用子句，以避免无效归结，缩小搜索范围，并尽可能使搜索规模朝小的方向发展。另外，删除策略是完备的。删除策略属于简化性策略。

▪ 支持集策略

支持集策略是沃斯(Wos)等人在1965年提出的一种归结策略，它要求：每次归结时，两个亲本子句中至少要有一个是目标公式否定的子句或者其后裔。目标公式否定所得的子句及其后裔子句组成的子句集称为支持集，也称为支架集。支持集策略属于限制性策略。

因为待求证目标公式的前提通常是一致的，为避免在可满足的子句集中做归结。支持集策略总是让目标公式的否定的子句参与归结，以便尽早地发现前提和结论的否定之间的不一致，提高搜索效率。所以，支持集策略是一种目标制导的反向推理。另外支持集策略也是完备的。

▪ 线性归结策略

线性归结策略(Linear Resolution)是1970年由罗弗兰德(Loveland)和卢克哈姆(Luckham)分别独立提出来的，它类似于链式推导法，可大大提高归结效率。

线性归结策略是在归结过程中，除第一次归结外，其他每次归结都至少要有一个亲本子句是上次归结的结果。线性归结的过程如图3-2所示，其中Ci(i=0,1,2,…,n)称为线性归结的中心子句，Bi(i=0,1,2,…,n)称为线性归结的边子句。

线性归结策略是完备的，而且也是高效的，同时，线性归结策略也可以与其他的策略兼容。线性归结策略属于限制性策略。

▪ 单元归结策略

单元归结策略是指在归结过程中，每次参加归结的两个亲本子句中必须至少有一个是单元子句。

使用单元子句归结可以使归结式含有较少的文字，因而有利于尽快推出空子句。但如果子句集中没有单元子句时，就不能采用单元归结策略进行归结，因此，单元归结策略是不完备的。单元归结策略是有序性策略。

▪ 语义归结策略

语义归结策略是斯莱格尔在1967年提出来的，语义归结策略的基本思想是利用解释I把子句集S中的子句分成两组，只考虑组间子句的归结，再引入谓词顺序，只允许子句中最大的谓词被归结。

因为S子句集不可满足，所以在同一个解释I下，子句集S中的一部分子句为真，记这部分子句的集合为S₁,而另一部分子句为假，记这部分子句的集合为S₂。对于不可满足的非空子句集S,即S≠{},任何解释I将使某些子句为真，至少会使某个子句为假，所以S₁和S₂都是非空的集合，这两个集合是最有可能产生矛盾的，也即是如果在这样的S₁和S₂之间进行归结，有可能较快地归结出空子句，提高归结效率。

在S中，还可以人为地引入一个谓词符号的顺序。例如S的原子集为{A₁,A₂,…,An},可给定顺序 P:A₁>A₂>…>An 其中A;大于A;,当且仅当i<j,谓词的大小顺序可以任意指定。 语义互撞 设I是子句集S的一个解释，P是S中谓词符号的一个顺序，称为限子句序列。E₁,…, E₄,N(q≥1)为关于P和I的语义互撞(Semantic Clash,简称PI-互撞),当且仅当以下条件同时成立： (1)E₁,…,E。在I下为假； (2)令N=R,对每个i=1,…,q,E₁和R,有归结式R;+1; (3)E,中的归结文字是E,中有最大谓词符号者； (4)R₄+1在I下为假。称N为互撞的核，E₁,…,E₉为互撞的电子，R₉+1为(E₁,…,E。,N)的PI-归结式。

PI-演绎 设有一个从子句集S推出C的演绎，其中被归结的子句或者属于子句集S,或者是由S推出的某一个PI-归结式，则称该演绎为从S推出的C的PI-演绎。

在语义归结策略中，电子的顺序将影响归结的效率。语义归结策略也是完备的，属于限制性归结策略。

▪ 祖先过滤型策略

祖先过滤型策略要求参加归结的两个子句，要么至少有一个是初始子句集中的子句，要么一个是另一个的祖先。

祖先过滤型策略是线性归结策略的改进，属于限制性策略，同时祖先过滤型策略是完备的。

第四章 不确定知识的表示与推理技术

不确定性类型及特点

（1）随机不确定性 即知道会发生的所有结果，但不知道发生哪个，而且知道每个发生的概率。 （2）模糊不确定性 就是指没有标准（例如：小王是高个子）。 （3）不完全性 就是指对某事物了解不完全。 （4）不一致性 就是指随着时间推移，前后结论不相容。

▪ 不确定性推理中要解决哪些基本问题

（1）不确定性的表示与度量

（2）不确定性的匹配算法

（3）不确定性的计算与传播

注：确定性理论和证据理论解决随机不确定性 模糊推理解决模糊不确定性

▪ 确定性理论（不确定知识表示和推理 第5题）

▪ 证据理论（不确定知识表示和推理 第7题）

▪ 模糊推理（不确定知识表示和推理 第9题）

第六章 机器学习

▪ 学习与机器学习的定义

学习：系统在不断重复的工作中对本身能力的增强和改进，使得系统在下一次执行同样任务或类似任务时会比现在做得更好或效率更高（西蒙）。 机器学习：实现通过经验来提高对某任务处理性能的行为的计算机程序。

▪ 机器学习习系统的基本结构

• 模型可换为知识库

• 环境：提供外界信息

• 学习环节：处理环境提供的信息并接收执行环境的反馈

• 信息，以便改善知识库中的知识，满足性能要求

• 知识库：学到的知识

• 执行环节：测试所学习到的知识的性能

第八章 自然语言处理

▪ 什么是自然语言处理？

是指用计算机来分析、处理自然语言，让计算机理解并能表达自然语言，实现人与计算机的自然语言交流。（IBM Watson核心）

▪ 自然语言处理涉及的层次。

（语言有语音和文字两个属性）

（1）语音分析： （2）词法分析：识别和词性判断

汉语分词有哪些方法

（1）基于词的方法（与已有的词表进行匹配）

（2）基于字的方法（根据字在词中的位置进行标记，然后扫描）

（3）句法分析（语法分析）：判断是否合法 分为句法结构分析和依存关系分析

（4）语义分析：一段文字的意义

A.词义消歧方法：

• 基于知识的方法

• 基于监督学习的方法

• 基于无监督学习的方法

B.语义角色标识

（5）语用分析

自然语言的特点

（1）新词不断出现，很难完全收入词典 （2）自然语言的表达非常灵活，很难完全形式化 （3）自然语言充满歧义，很难完全消解 读音、分词、词性、句法结构、词义歧义 （4）自然语言中有各种语言创新，机器很难应付

自然语言处理的应用

（1）语音识别和合成 （2）机器翻译 （3）信息检索 （4）问答系统 （5）信息抽取 （6）文本摘要 （7）文本分类 （8）社会计算

语言知识库

（1）语法知识库（现代汉语语法信息词典）

（2）语义知识库（语义网络->知网）