第三章 搜索推理技术
教学内容：本章在上一章知识表示的基础上研究问题求解的方法，是人工智能研
究的又一核心问题。内容包括早期搜索推理技术，如图搜索策略和消解原理；以
及高级搜索推理技术，如规则演绎系统、产生式系统、系统组织技术、不确定性
推理和非单调推理。
教学重点：图搜索策略、消解原理、规则演绎系统、产生式系统。
教学难点：启发式搜索、规则双向演绎系统等。
教学方法：课堂教学为主，辅以恰当的实验。注意结合前面所学知识表示的基础
内容，将其与问题求解方法融为一体。及时提问、收集学生学习情况。尽量使用
实例和网络课程中的多媒体素材进行讲解。
教学要求：重点掌握一般图搜索策略和消解原理，掌握各种搜索方法和产生式系
统原理，了解规则演绎系统的基本原理，对系统组织技术、不确定性推理和非单
调推理等高级推理技术作一般性了解。
图搜索策略
教学内容：本节介绍图搜索的一般策略，作为各种图搜索技术的基础。
教学重点：图搜索的一般过程、OPEN 表和 CLOSE 表的概念。
教学难点：OPEN 表和 CLOSE 表的物理意义。
教学方法：课堂教学为主，通过提问彻底弄清图搜索的基本概念。
教学要求：重点掌握图搜索一般策略，掌握 OPEN 表和 CLOSE 表的构成及作用。
1、图搜索策略的定义
图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代
表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的
规则序列问题就等价于求得图中的一条路径问题。研究图搜索的一般策略，能够
给出图搜索过程的一般步骤。
2、图搜索算法中的几个重要名词术语
（1）OPEN 表与 CLOSE 表
（2）搜索图与搜索树
3、图搜索(GRAPHSEARCH)的一般过程
(1) 建立一个只含有起始节点 S 的搜索图 G，把 S 放到一个叫做 OPEN 的未
扩展节点表中。
(2) 建立一个叫做 CLOSED 的已扩展节点表，其初始为空表。
(3) LOOP：若 OPEN 表是空表，则失败退出。
(4) 选择 OPEN 表上的第一个节点，把它从 OPEN 表移出并放进 CLOSED
表中。称此节点为节点 n。
(5) 若 n 为一目标节点，则有解并成功退出，此解是追踪图 G 中沿着指针
从 n 到 S 这条路径而得到的(指针将在第 7 步中设置)。
(6) 扩展节点 n，同时生成不是 n 的祖先的那些后继节点的集合 M。把 M 的
这些成员作为 n 的后继节点添入图 G 中。
(7) 对那些未曾在 G 中出现过的(既未曾在 OPEN 表上或 CLOSED 表上出现
过的)M 成员设置一个通向 n 的指针。把 M 的这些成员加进 OPEN 表。对已经
在 OPEN 或 CLOSED 表上的每一个 M 成员，确定是否需要更改通到 n 的指针方
向。对已在 CLOSED 表上的每个 M 成员，确定是否需要更改图 G 中通向它的每
个后裔节点的指针方向。
(8) 按某一任意方式或按某个探试值，重排 OPEN 表。
(9) GO LOOP。
提问：图搜索是针对什么知识表示方法的问题求解方法？
4、图搜索方法分析：
图搜索过程的第 8 步对 OPEN 表上的节点进行排序，以便能够从中选出一
个“最好”的节点作为第 4 步扩展用。这种排序可以是任意的即盲目的(属于盲目
搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。
每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重
现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向 S 返回
追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某些节点最
终可能没有后继节点，所以 OPEN 表可能最后变成空表)。在失败终止的情况下，
从起始节点出发，一定达不到目标节点。
提问：什么是图搜索? 其中，重排 OPEN 表意味着什么，重排的原则是什么?
盲目搜索
教学内容：介绍三种盲目搜索方法，即宽度优先搜索、深度优先搜索和等代价搜
索。
教学重点：盲目搜索的特点，宽度优先搜索。
教学难点：等代价搜索中代价的概念。
教学方法：以实例强化内容的学习，通过提问引导学生对三种方法的特点进行比
较。
教学要求：掌握盲目搜索的特点，比较三种盲目搜索方法的优缺点。
宽度优先搜索
1、定义
如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽
度优先搜索(breadth-first search)。
2、特点
这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完
本层的所有节点。
3、宽度优先搜索算法
(1) 把起始节点放到 OPEN 表中(如果该起始节点为一目标节点，则求得一
个解答)。
(2) 如果 OPEN 是个空表，则没有解，失败退出；否则继续。
(3) 把第一个节点(节点 n)从 OPEN 表移出，并把它放入 CLOSED 的扩展节
点表中。
(4) 扩展节点 n。如果没有后继节点，则转向上述第(2)步。
(5) 把 n 的所有后继节点放到 OPEN 表的末端，并提供从这些后继节点回到
n 的指针。
(6) 如果 n 的任一个后继节点是个目标节点，则找到一个解答，成功退出；
否则转向第(2)步。
4、宽度优先搜索方法分析：
宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第 8 步
具体化为本算法中的第 6 步，这实际是将 OPEN 表作为“先进先出”的队列进行操
作。
宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；
这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，我
们就说该法失败退出；对于无限图来说，则永远不会终止)。
5、例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要
把初始棋局变为如下目标棋局的问题：
1 2 3
8 4
7 6 5
提问：宽度优先搜索方法中 OPEN 表需要按什么方式进行操作？
A．先进后出 B．先进先出
深度优先搜索
1、定义
在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任
意排列。
这种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。
2、特点
首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始
节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替
代的路径。
3、深度界限
为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给
出一个节点扩展的最大深度棗深度界限。任何节点如果达到了深度界限，那么都
将把它们作为没有后继节点处理。
4、含有深度界限的深度优先搜索算法
请同学们课后自学，并回答课后思考题。
思考题：有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最
短途径吗？
等代价搜索
1、定义
宽度优先搜索可被推广用来解决寻找从起始状态至目标状态的具有最小代
价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。
2、等代价搜索中的几个记号
起始节点记为 S；
从节点 i 到它的后继节点 j 的连接弧线代价记为 c(i，j)；
从起始节点 S 到任一节点 i 的路径代价记为 g(i)。
3、等代价搜索算法
（请同学们课后认真阅读本算法，指出与宽度优先、深度优先算法有何特别
之处。）
4、等代价搜索方法分析
如果所有的连接弧线具有相等的代价，那么等代价算法就简化为宽度优先搜
索算法。
思考：试比较各种盲目搜索搜索方法的效率，找出影响算法效率的原因。
启发式搜索
教学内容：启发式搜索策略概述和有序搜索。启发式搜索弥补盲目搜索的不足，
提高搜索效率。
教学重点：启发式搜索策略、启发信息和有序搜索。
教学难点：估价函数的设计、A*算法原理。
教学方法：通过实例加深对原理的理解，鼓励同学扩大阅读范围。
教学要求：掌握启发式搜索策略和估价函数的设计方法，了解 A*算法原理。
启发式搜索策略和估价函数
1、为什么需要启发式搜索
盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形
式。
2、定义
进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫
做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。
3、启发式搜索策略
有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也
较大)的利用启发信息的方法是应用某些准则来重新排列每一步 OPEN 表中所有
节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。
应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数
(evalution function)。
4、估价函数
为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以
便确定哪个节点最有可能在通向目标的最佳路径上 。
f(n)——表示节点 n 的估价函数值
建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提
出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中
根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一
步的希望程度有关。
有序搜索
1、定义
用估价函数 f 来排列 GRAPHSEARCH 第 8 步中 OPEN 表上的节点。应用某
个算法(例如等代价算法)选择 OPEN 表上具有最小 f 值的节点作为下一个要扩
展的节点。这种搜索方法叫做有序搜索(ordered search)或最佳优先搜索(best-first
search)，而其算法就叫做有序搜索算法或最佳优先算法。
尼尔逊(Nilsson)曾提出一个有序搜索的基本算法。估价函数 f 是这样确定的：
一个节点的希望程序越大，其 f 值就越小。被选为扩展的节点，是估价函数最小
的节点。
2、实质
选择 OPEN 表上具有最小 f 值的节点作为下一个要扩展的节点，即总是选择
最有希望的节点作为下一个要扩展的节点。
3、有序状态空间搜索算法
(1) 把起始节点 S 放到 OPEN 表中，计算 f(S)并把其值与节点 S 联系起来。
(2) 如果 OPEN 是个空表，则失败退出，无解。
(3) 从 OPEN 表中选择一个 f 值最小的节点 i。结果有几个节点合格，当其
中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节
点 i。
(4) 把节点 i 从 OPEN 表中移出，并把它放入 CLOSED 的扩展节点表中。
(5) 如果 i 是个目标节点，则成功退出，求得一个解。
(6) 扩展节点 i，生成其全部后继节点。对于 i 的每一个后继节点 j：
(a)计算 f(j)。
(b)如果 j 既不在 OPEN 表中，又不在 CLOSED 表中，则用估价函数 f 把它添入
OPEN 表。从 j 加一指向其父辈节点 i 的指针，以便一旦找到目标节点时记住一
个解答路径。
(c)如果 j 已在 OPEN 表上或 CLOSED 表上，则比较刚刚对 j 计算过的 f 值和前面
计算过的该节点在表中的 f 值。如果新的 f 值较小，则
(i) 以此新值取代旧值。
(ii) 从 j 指向 i，而不是指向它的父辈节点。
(iii) 如果节点 j 在 CLOSED 表中，则把它移回 OPEN 表。
(7) 转向(2)，即 GO TO(2)。
4、有序搜索方法分析
宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对
于宽度优先搜索，选择 f(i)作为节点 i 的深度。对于等代价搜索，f(i)是从起始节
点至节点 i 这段路径的代价。
有序搜索的有效性直接取决于 f 的选择，如果选择的 f 不合适，有序搜索就
可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么 f
的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一
方面是保证有一个最优的解或任意解。
5、例：八数码难题
采用了简单的估价函数
f(n)=d(n)+W(n)
其中：d(n)是搜索树中节点 n 的深度；W(n)用来计算对应于节点 n 的数据库
中错放的棋子个数。因此，起始节点棋局
2 8 3
1 4
7 6 5
的 f 值等于 0+4=4。
A*算法
A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。
1、几个记号
令 k(ni，nj)表示任意两个节点 ni 和 nj 之间最小代价路径的实际代价(对于两
节点间没有通路的节点，函数 k 没有定义)。于是，从节点 n 到某个具体的目标
节点 ti，某一条最小代价路径的代价可由 k(n,ti)给出。令 h*(n)表示整个目标节点
集合｛ti｝上所有 k(n,ti)中最小的一个，因此，h*(n)就是从 n 到目标节点最小代
价路径的代价，而且从 n 到目标节点能够获得 h*(n)的任一路径就是一条从 n 到
某个目标节点的最佳路径(对于任何不能到达目标节点的节点 n，函数 h*没有定
义)。
2、估价函数的定义
定义 g*为 g*(n)=k(S,n)
定义函数 f*，使得在任一节点 n 上其函数值 f*(n)就是从节点 S 到节点 n 的
一条最佳路径的实际代价加上从节点 n 到某目标节点的一条最佳路径的代价之
和，即
f*(n)=g*(n)+h*(n)
希望估价函数 f 是 f*的一个估计，此估计可由下式给出：
f(n)=g(n)+h(n)
其中：g 是 g*的估计；h 是 h*的估计。对于 g(n)来说，一个明显的选择就是
搜索树中从 S 到 n 这段路径的代价，这一代价可以由从 n 到 S 寻找指针时，把
所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到
的从 S 到 n 的最小代价路径)。这个定义包含了 g(n)≥g*(n)。h*(n)的估计 h(n)依赖
于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数 W(n)所用
的那种信息相似。把 h 叫做启发函数。
3、A*算法定义
定义 1 在 GRAPHSEARCH 过程中，如果第 8 步的重排 OPEN 表是依据
f(x)=g(x)+h(x)Ⅱ进行的，则称该过程为 A 算法。
定义 2 在 A 算法中，如果对所有的 x 存在 h(x)≤h*(x),则称 h(x)为 h*(x)的下
界，它表示某种偏于保守的估计。
定义 3 采用 h*(x)的下界 h(x)为启发函数的 A 算法，称为 A*算法。当 h=0
时，A*算法就变为有序搜索算法。
4、A*算法
A*算法描述参考教材。
提问：由 g*(n)和 g(n)的定义知 g*(n)≤g(n)
A．对 B．错
思考：试比较宽度优先搜索、有界深度优先搜索及有序搜索的搜索效率，并以实
例数据加以说明
消解原理
教学内容：消解原理是针对谓词逻辑知识表示的问题求解方法。本节内容主要包
括子句集的求取、消解推理的规则和消解反演问题求解方法。
教学重点：子句集的求取、消解推理的规则和消解反演问题求解方法。
教学难点：消解反演的思想。
教学方法：实例讲解，注重课堂练习。
教学要求：重点掌握子句集的求解步骤和消解反演过程，掌握消解推理的规则。
消解原理的基础知识：
（1）谓词公式、某些推理规则以及置换合一等概念。
（2）子句：由文字的析取组成的公式(一个原子公式和原子公式的否定都叫
做文字)。
（3）消解：当消解可使用时，消解过程被应用于母体子句对，以便产生一
个导出子句。例如，如果存在某个公理 E1ⅡE2 和另一公理～E2ⅡE3，那么 E1ⅡE3
在逻辑上成立。这就是消解，而称 E1ⅡE3 为 E1ⅡE2 和～E2ⅡE3 的消解式(resolvent)。
子句集的求取
1、步骤
(1) 消去蕴涵符号
只应用Ⅱ和～符号，以～AⅡB 替换 A→B。
提问：现有公式[(A→B) →B] ⅡC，在消去蕴涵符号后得到公式：
A．[～(A→B) ⅡB] ⅡC B．[～(AⅡB) ⅡB] ⅡC
C．[～(～AⅡB) ⅡB] ⅡC D．[ (AⅡB) ⅡB] ⅡC
(2) 减少否定符号的辖域
每个否定符号～最多只用到一个谓词符号上，
并反复应用狄·摩根定律。例如：
以～AⅡ～B 代替～(AⅡB)
以～AⅡ～B 代替～(AⅡB)
以 A 代替～(～A)
以( x)｛～A｝代替～( x)A
以( x)｛～A｝代替～( x)A
提问：设有公式( x)( y)｛( y)P(x,y)→( x)Q(x,y)｝，在经过对变量标准化后
得到公式为：
A．( x)( y)｛( y)P(x,y)→( y)Q(y,y)｝
B．( x)( y)｛( x)P(x,x)→( x)Q(x,y)｝
C．( x)( y)｛( z)P(x,z)→( q)Q(q,y)｝
D．( x)( y)｛( z)P(x,z)→( q)Q(q,z)｝
E．( x)( y)｛( z)P(q,z)→( q)Q(q,z)｝
(3) 对变量标准化
在任一量词辖域内，受该量词约束的变量为一哑元(虚构变量)，它可以在该
辖域内处处统一地被另一个没有出现过的任意变量所代替，而不改变公式的真值。
合适公式中变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑
元。
(4) 消去存在量词
用 Skolem 函数代替存在的 x,就可以消去全部存在量词，并写成：
( y)P〔g(y),y〕
从一个公式消去一个存在量词的一般规则是以一个 Skolem 函数代替每个出
现的存在量词的量化变量，而这个 Skolem 函数的变量就是由那些全称量词所约
束的全称量词量化变量，这些全称量词的辖域包括要被消去的存在量词的辖域在
内。Skolem 函数所使用的函数符号必须是新的，即不允许是公式中已经出现过
的函数符号。例如：
( y)( x)P(x,y)被〔( y)P(g(y),y)〕代替，其中 g(y)为一 Skolem 函数。
如果要消去的存在量词不在任何一个全称量词的辖域内，则用不含变量的
Skolem 函数即常量。例如，( x)P(x)化为 P(A)，其中常量符号 A 用来表示人们
知道的存在实体。A 必须是个新的常量符号，它未曾在公式中其它地方使用过。
(5) 化为前束形
把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公
式的整个部分。所得公式称为前束形。
(6) 把母式化为合取范式
任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集
组成的合取。这种母式叫做合取范式。
(7) 消去全称量词
消去明显出现的全称量词。
提问：对于公式( z)( y){( x)P(x,y,z)Ⅱ( q)( w)( e)Q(q,w,e,z)，在经过消去存
在量词后，正确的公式为：
A．( y){P(B,y,A)Ⅱ( w)Q(C,w,D,A)
B．( y){P(B,y,A)Ⅱ( w)Q(C,w,g(w),A) , g(w)为一 Skolem 函数
C．( y){P(g1(y),y,A)Ⅱ( w)Q(g２(y),w,g３(w),A)
式中，(g1(y)，g２(y)和 g３(w)为 Skolem 函数
D．( y){P(g1(y),y,A)Ⅱ( w)Q(g２(y),w,g３(y,w),A)
式中，(g1(y)，g２(y)和 g３(y,w)为 Skolem 函数
(8) 消去连词符号Ⅱ
用｛A，B｝代替(AⅡB)，以消去明显的符号Ⅱ。反复代替的结果，最后得到
一个有限集，其中每个公式是文字的析取。任一个只由文字的析取构成的合适公
式叫做一个子句。
(9) 更换变量名称
可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。
2、例
将下列谓词演算公式化为一个子句集
( x)｛P(x)→｛( y)〔P(y)→P(f(x,y))〕Ⅱ～( y)〔Q(x,y)→P(y)〕｝｝
3、说明
并不是所有问题的谓词公式化为子句集都需要上述 9 个步骤。对于某些问题，
可能不需要其中的一些步骤。
消解推理规则
1、消解式
令 L1 为任一原子公式，L2 为另一原子公式；L1 和 L2 具有相同的谓词符号，
但一般具有不同的变量。已知两子句 L1Ⅱα和～L2Ⅱβ,如果 L1 和 L2 具有最一般合
一者σ，那么通过消解可以从这两个父辈子句推导出一个新子句(αⅡβ)σ。这个新
子句叫做消解式。它是由取这两个子句的析取，然后消去互补对而得到的。
2、消解式求法
(1) 假言推理
父辈子句 PⅡⅡⅡ ～PⅡQ(即 P→Q)
\ /
\ /
消解式 Q
(2) 合并
(3) 重言式
(4) 空子句(矛盾)
～P ⅡⅡP
\ /
\ /
NIL
(5) 链式(三段论)
即取各子句的析取，然后消去互补对。
说明：对合并、重言式、链式(三段论)请同学们自行阅读。
含有变量的消解式
1、消解式求法
为了对含有变量的子句使用消解规则，必须找到一个置换，作用于父辈子句
使其含有互补文字。
2、例子
Ⅱ P(x)ⅡQ(x)ⅡⅡ～Q〔f(y)〕
ⅡⅡⅡⅡ 置换σ=｛f(y)/x｝
P〔f(y)〕
消解反演求解过程
1、基本思想
把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，
然后添加到命题公式集中去，把消解反演系统应用于联合集，并推导出一个空子
句(NIL)，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，
定理得证，问题得到解决，与数学中反证法的思想十分相似。
2、消解反演
反演求解的步骤
给出一个公式集 S 和目标公式 L，通过反证或反演来求证目标公式 L，其证
明步骤如下：
(1)否定 L，得～L；
(2)把～L 添加到 S 中去；
(3)把新产生的集合｛～L，S｝化成子句集；
(4)应用消解原理，力图推导出一个表示矛盾的空子句 NIL。
反演求解的正确性
设公式 L 在逻辑上遵循公式集 S，那么按照定义满足 S 的每个解释也满足 L。
决不会有满足 S 的解释能够满足～L 的，所以不存在能够满足并集 SⅡ｛～L｝
的解释。如果一个公式集不能被任一解释所满足，那么这个公式是不可满足的。
因此，如果 L 在逻辑上遵循 S，那么 SⅡ｛～L｝是不可满足的。可以证明，如
果消解反演反复应用到不可满足的子句集，那么最终将要产生空子句 NIL。因此，
如果 L 在逻辑上遵循 S，那么由并集 SⅡ｛～L｝消解得到的子句，最后将产生
空子句；反之，可以证明，如果从 SⅡ｛～L｝的子句消解得到空子句，那么 L
在逻辑上遵循 S。
3、反演求解过程
步骤：
(1)把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句
中去。
(2)按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。
(3)用根部的子句作为一个回答语句。
分析：
答案求取涉及到把一棵根部有 NIL 的反演树变换为在根部带有可用作答案
的某个语句的一颗证明树。由于变换关系涉及到把由目标公式的否定产生的每个
子句变换为一个重言式，所以被变换的证明树就是一棵消解的证明树，其在根部
的语句在逻辑上遵循公理加上重言式，因而也单独地遵循公理。因此被变换的证
明树本身就证明了求取办法是正确的。
例：储蓄问题
前提：每个储蓄钱的人都获得利息。
结论：如果没有利息，那么就没有人去储蓄钱
思考：应用消解反演求解如下问题：
“如果无论约翰(John)到哪里去，菲多(Fido)也就去那里，那么如果约翰在学校里，
菲多在哪里呢?”
规则演绎系统
教学内容：规则演绎系统属于高级搜索推理技术，用于解决比较复杂的系统和问
题。本节介绍规则演绎系统的定义及其三种推理方法：规则正向演绎系统、规则
逆向演绎系统和规则双向演绎系统。
教学重点：规则演绎系统的定义、正向推理和逆向推理过程。
教学难点：双向演绎的匹配问题等。
教学方法：课堂教学为主。通过比较揭示正向推理、逆向推理和双向推理的特点。
教学要求：掌握规则演绎系统的定义和正向推理、逆向推理的过程，了解规则双
向演绎系统。
规则演绎系统的定义：
基于规则的问题求解系统运用下述规则来建立：
If→Then
其中，If 部分可能由几个 if 组成，而 Then 部分可能由一个或一个以上的 then
组成。
在所有基于规则系统中，每个 if 可能与某断言(assertion)集中的一个或多个
断言匹配。有时把该断言集称为工作内存。在许多基于规则系统中，then 部分用
于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rule
based deduction system)。在这种系统中，通常称每个 if 部分为前项(antecedent)，
称每个 then 部分为后项(consequent)。
规则正向演绎系统
1、定义
正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推
理的，也就是从 if 到 then 的方向进行推理的。
2、正向推理过程
（1）事实表达式的与或形变换
把事实表示为非蕴涵形式的与或形，作为系统的总数据库。具体变换步骤与
前述化为子句形类似。
注意：我们不想把这些事实化为子句形，而是把它们表示为谓词演算公式，
并把这些公式变换为叫做与或形的非蕴涵形式。
例：有事实表达式
( u)( v)｛Q(v，u)Ⅱ～〔(R(v)ⅡP(v))ⅡS(u，v)〕｝把它化为
Q(v,A)Ⅱ｛〔～R(v)Ⅱ～P(v)〕Ⅱ～S(A,v)｝
对变量更名标准化，使得同一变量不出现在事实表达式的不同主要合取式中，
得：
Q(w,A)Ⅱ｛〔～R(v)Ⅱ～P(v)〕Ⅱ～S(A,v)｝
（2）事实表达式的与或图表示
将上例与或形的事实表达式用与或图来表示，见图 。
图 一个事实表达式的与或树表示
一般把事实表达式的与或图表示倒过来画，即把根节点画在最下面，而把其
后继节点往上画。上节的与或图表示，就是按通常方式画出的，即目标在上面。
（3）与或图的 F 规则变换
这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。把
允许用作规则的公式类型限制为下列形式：
L→W
式中：L 是单文字；W 为与或形的唯一公式。
将这类规则应用于与或图进行推演。假设有一条规则 L=>W，根据此规则及
事实表达式 F(L)，可以推出表达式 F(W)。F(W)是用 W 代替 F 中的所有 L 而得
到的。当用规则 L=>W 来变换以上述方式描述的 F(L)的与或图表示时，就产生
一个含有 F(W)表示的新图；也就是说，它的以叶节点终止的解图集以 F(W)子句
形式代表该子句集。这个子句集包括在 F(L)的子句形和 L=>W 的子句形间对 L
进行所有可能的消解而得到的整集。该过程以极其有效的方式达到了用其它方法
要进行多次消解才能达到的目的。
（4）作为终止条件的目标公式
应用 F 规则的目的在于从某个事实公式和某个规则集出发来证明某个目标
公式。在正向推理系统中，这种目标表达式只限于可证明的表达式，尤其是可证
明的文字析取形的目标公式表达式。用文字集表示此目标公式，并设该集各元都
为析取关系。
结论：
当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功
地终止。
规则逆向演绎系统
1、定义
基于规则的逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到
事实的操作过程，从 then 到 if 的推理过程。
2、逆向推理过程
（1）目标表达式的与或形式
逆向演绎系统能够处理任意形式的目标表达式。首先，采用与变换事实表达
式同样的过程，把目标公式化成与或形。
（2）与或图的 B 规则变换
B 规则是建立在确定的蕴涵式基础上的，正如正向系统的 F 规则一样。不过，
我们现在把这些 B 规则限制为
W→L ()
形式的表达式。其中，W 为任一与或形公式，L 为文字，而且蕴涵式中任何变量
的量词辖域为整个蕴涵式。
（3）作为终止条件的事实节点的一致解图
逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解
图。
提问：逆向推理与正向推理的区别有哪些？
规则双向演绎系统
1.基于规则的正向演绎系统和逆向演绎系统的特点和局限性
正向演绎系统能够处理任意形式的 if 表达式，但被限制在 then 表达式为由
文字析取组成的一些表达式。逆向演绎系统能够处理任意形式的 then 表达式，
但被限制在 if 表达式为文字合取组成的一些表达式。双向(正向和逆向)组合演绎
系统具有正向和逆向两系统的优点，克服各自的缺点。
2.双向(正向和逆向)组合演绎系统的构成
正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总
数据库由表示目标和表示事实的两个与或图结构组成，并分别用 F 规则和 B 规
则来修正。
3.终止条件
组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的
适当交接处。当用 F 规则和 B 规则对图进行扩展之后，匹配就可以出现在任何
文字节点上。
在完成两个图间的所有可能匹配之后，目标图中根节点上的表达式是否已经
根据事实图中根节点上的表达式和规则得到证明的问题仍然需要判定。只有当求
得这样的一个证明时，证明过程才算成功地终止。若能够断定在给定方法限度内
找不到证明时过程则以失败告终。
产生式系统
教学内容：本节介绍产生式系统的定义、组成和推理技术。
教学重点：产生式系统与规则演绎系统的差别和产生式系统的组成。
教学难点：产生式系统的控制策略等。
教学方法：课堂教学和实验相结合。重点讲解原理，通过实验进一步领会系统的
精髓。充分利用网络课程中的多媒体素材来表示抽象概念。
教学要求：掌握产生式系统的组成结构，通过实践掌握产生式系统的设计和工作
过程。
定义：
在基于规则系统中，每个 if 可能与某断言(assertion)集中的一个或多个断言
匹配，then 部分用于规定放入工作内存的新断言。当 then 部分用于规定动作时，
称这种基于规则的系统为反应式系统(reaction system)或产生式系统(production
system)。
提问：产生式系统与规则演绎系统有什么区别？
产生式系统的组成
1.产生式系统的组成
产生式系统由 3 个部分组成，即总数据库(或全局数据库)、产生式规则和控
制策略，如图 所示。
图 产生式系统的主要组成
总数据库有时也被称作上下文，当前数据库或暂时存储器。总数据库是产生式规则的注
意中心。产生式规则的左边表示在启用这一规则之前总数据库内必须准备好的条件。例如在
上述例子中，在得出该动物是食肉动物的结论之前，必须在总数据库中存有“该动物是哺乳
动物”和“该动物吃肉”这两个事实。执行产生式规则的操作会引起总数据库的变化，这就使
其他产生式规则的条件可能被满足。
产生式规则是一个规则库，用于存放与求解问题有关的某个领域知识的规则
之集合及其交换规则。规则库知识的完整性、一致性、准确性、灵活性和知识组
织的合理性，将对产生式系统的运行效率和工作性能产生重要影响。
控制策略为一推理机构，由一组程序组成，用来控制产生式系统的运行，决
定问题求解过程的推理线路，实现对问题的求解。产生式系统的控制策略随搜索
方式的不同可分为可撤回策略、回溯策略、图搜索策略等。
2.产生式系统的控制策略
控制策略的作用是说明下一步应该选用什么规则，也就是如何应用规则。通
常从选择规则到执行操作分 3 步：匹配、冲突解决和操作。
（1）匹配
在这一步，把当前数据库与规则的条件部分相匹配。如果两者完全匹配，则
把这条规则称为触发规则。当按规则的操作部分去执行时，称这条规则为启用规
则。被触发的规则不一定总是启用规则，因为可能同时有几条规则的条件部分被
满足，这就要在解决冲突步骤中来解决这个问题。在复杂的情况下，在数据库和
规则的条件部分之间可能要进行近似匹配。
（2）冲突解决
当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用
哪一条规则，这称为冲突解决。
（3）操作
操作就是执行规则的操作部分，经过操作以后，当前数据库将被修改。然后，
其他的规则有可能被使用。
产生式系统的推理
1.正向推理
从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词
公式或命题是否成立。
一般策略：先提供一批事实（数据）到总数据库中。系统利用这些事实与规
则的前提相匹配，触发匹配成功的规则，把其结论作为新的事实添加到总数据库
中。继续上述过程，用更新过的总数据库的所有事实再与规则库中另一条规则匹
配，用其结论再次修改总数据库的内容，直到没有可匹配的新规则，不再有新的
事实加到总数据库中。
2.逆向推理
从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成
立，即首先提出一批假设目标，然后逐一验证这些假设。
一般策略：首先假设一个可能的目标，然后由产生式系统试图证明此假设目
标是否在总数据库中。若在总数据库中，则该假设目标成立；否则，若该假设为
终叶（证据）节点，则询问用户。若不是，则再假定另一个目标，即寻找结论部
分包含该假设的那些规则，把它们的前提作为新的假设，并力图证明其成立。这
样反复进行推理，直到所有目标均获证明或者所有路径都得到测试为止。
3.双向推理
双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推
理过程中的某个步骤，实现事实与目标的匹配。
产生式系统举例
说明：请同学们课后认真阅读本部分内容，并以此为参考进行实验准备！
思考：规则演绎系统和产生式系统有哪几种推理方式?各自的特点为何?
系统组织技术
教学内容：系统组织技术属于高级搜索推理技术，能够用于求解比较复杂的系统。
本节简要介绍三种系统组织技术：议程表法、黑板法和Ⅱ极小搜索法。
教学重点：系统组织技术如何实现模块之间的合作。
教学难点：无要求。
教学方法：课堂教学。
教学要求：了解系统组织技术的基本原理。
议程表
1.定义
议程表(agenda)是一个系统能够执行的任务表列。与每个任务有关的有两件
事，即提出该任务的理由和表示对该任务是有用的证据总权的评价。
2.模块间的合作
从组织大系统的观点看，议程表方法的意义在于它允许几个独立模块进行通
讯。其通讯方法是每个模块可将支持(或反对)某个具体任务的证据，加到一个证
明选择该任务是正确的表中。这样就使系统能够选出从各方面都有充分证据的任
务。虽然各模块共同使用关于为什么要执行各项任务的证据，但一个模块并不需
要了解其它模块如何工作，以及它们所包含的知识。这样，议程表方法便具有大
系统中模块化的一切优点，而无相互隔离的缺点。
黑板法
1.定义
黑板法(the Blackboard Approach)首先是在 HEARSAY-Ⅱ语音理解系统中发
展起来的。它的思想比较简单。整个系统由一组称为知识资源(KS)的独立模块和
一块黑板组成。这里，知识资源含有系统中专门领域的知识，而黑板则是一切 KS
可以访问的公用数据结构。
2.模块间的合作
当一个 KS 被激发时，它检查当时黑板上的内容，并应用其知识产生一个新
的假设写到黑板上，直到完成任务为止。当时间表没有发现未解决的活动记录时，
系统便停止执行。
Δ-极小搜索法
1、定义
Δ值表示一假设的级别与参加竞争的最佳假设的级别之差，提供了一种选择
最有希望假设的技术。
2、工作过程
一次接受一串输入，顺序地处理，使其形成一个关于输入的统一而相容的解
释。Δ-极小法是这样来解决这类问题的：在适当的时刻，触发某 KS，然后为它
生成所有它认为是可能的假设，并赋给某个假设一种级别。由这些级别计算出的
Δ值，表示一假设的级别与参加竞争的最佳假设的级别之差。而在该假设最后导
致不相容时，再考虑参加竞争的另一假设。
不确定性推理
教学内容：本节介绍两种不确定性(uncertainty)，即关于证据的不确定性和关于
结论的不确定性。
教学要点：不确定性如何表示和推理。
教学难点：不确定性的推理。
教学方法：课堂教学为主。
教学要求：了解不确定性的表示和推理方法。
关于证据的不确定性
1.不确定性的表示
一般通过对事实赋于一个介于 0 和 1 之间的系数来表示事实的不确定性。1
代表完全确定，0 代表完全不确定。这个系数被称为可信度(也有一些专家系统，
如 MYCIN 和 EXPERT 等，取可信度的范围为-1 到+1)。
2.不确定性的处理
当规则具有一个以上的条件时，就需要根据各条件的可信度来求得总条件部
分的可信度。已有的方法有两类：
（1）以模糊集理论为基础的方法
按这种方法，把所有条件中最小的可信度作为总条件的可信度。这种方法类
似于当把几根绳子连接起来使用时，总的绳子强度与强度最差的绳子的相同。
（2）以概率为基础的方法
这种方法同样赋予每个证据以可信度。但当把单独条件的可信度结合起来求
取总的可信度时，它取决于各可信度的乘积。
关于结论的不确定性
1、不确定性的表示
关于结论的不确定性也叫做规则的不确定性，它表示当规则的条件被完全满
足时，产生某种结论的不确定程度。它也是以赋予规则在 0 和 1 之间的系数的方
法来表示的。
例：有以下规则：
如果 启动器发生刺耳的噪声那么这个启动器坏的可能性是 。
以上规则表示，如果“启动器发生刺耳的噪声”这事实完全肯定的可信度为
，那么得出“这个启动器坏”的结论的可信度为 。
2、不确定性的处理
如果规则的条件部分不完全确定，即可信度不为 1 时，如何求得结论的可信
度的方法有以下两种：
(1)取结论可信度为条件可信度与上述系数的乘积。
(2)按照某种概率论的解释，我们假设规则的条件部分的可信度 Cin 和其结论部分的可信
度 Cout 存在某种关系，这种关系可用来代表规则的不确定性。
多个规则支持同一事实时的不确定性
当多个规则支持同一事实时，这些规则之间的关系是析取。如何根据证据的
可信度求得事实的可信度? 与关于证据的可信度类似，也有两种方法，分别基于
模糊集理论和概率理论。
1.基于模糊集理论的方法
取支持这个事实的各规则的可信度的最大值作为事实的可信度。
2.基于概率论的方法
这里介绍的只是基于概率的方法中的一种。按这种方法由一组规则支持的事
实的可信度，可用以下方法求得，首先把各个证据的可信度转换成可信性比例 r。
可信性比例 r 和可信度 c 之间的关系可表示为
把各证据的可信性比例简单地相乘就可以求得这些证据所支持的事实的可
信性比例。然后，再利用上述公式转换回相应的可信度。这样就求得这个事实的
可信度。
非单调推理
教学内容：用于解决现实问题领域中的 3 类情况：不完全的信息、不断变化的情
况、以及求解复杂问题过程中生成的假设，具有较为有效的求解效率。本节简要
介绍两种非单调推理技术：缺省推理和正确性维持系统 TMS。
教学要点：缺省推理和正确性维持系统 TMS 的基本原理。
教学难点：无特别要求。
教学方法：课堂教学。
教学要求：了解缺省推理和正确性维持系统 TMS 的基本原理。
缺省推理
1.定义
当缺乏信息时，只要不出现相反的证据，就可以作一些有益的猜想。构造这
种猜想称为缺省推理(default reasoning)。
缺省推理的定义 1：如果 X 不知道，那么得结论 Y。
缺省推理的定义 2：如果 X 不能被证明，那么得结论 Y。
缺省推理的定义 3：如果 X 不能在某个给定的时间内被证明，那么得结论 Y。
2.例子
一个安排会议程序：程序必须求解一个约束满足问题，即找出每个参加者都
有空闲的开会日期与时刻，并有可供开会的房间。
非单调推理系统
1.正确性维持系统(Truth Maintenane System,TMS)
这是一个已经实现的非单调推理系统。它用以协助其它推理程序维持系统的
正确性，所以它的作用不是生成新的推理，而是在其它程序所产生的命题之间保
持相容性。一旦发现某个不相容，它就调出自己的推理机制，面向从属关系的回
溯，并通过修改最小的信念集来消除不相容。
2.工作原理
在 TMS 中，每一命题或规则均称为节点，且对任一节点，以下两种状态必
居其一：
IN 相信为真
OUT 不相信为真，或无理由相信为真，或当前没有可相信的理由。
IN 节点是指那些至少有一个在当前说来是有效证实的节点。OUT 结点则指
那些当前无任何有效证实的节点。
在系统中，有两种方式可用来证实一个节点的有效性可依赖于其它节点的有
效性：
(1) 支持表 (SL (IN-节点) (OUT-节点))
(2) 条件证明 (CP (结论)
(IN-假设)
(OUT-假设))
小 结
对本章讨论过的各种搜索推理技术加以归纳总结。
