第 3 章 产生式系统及其搜索方法
人工智能与机器翻译
主讲：杨宪泽
—— 产生式系统及其搜索方法
第 3 章 产生式系统及其搜索方法
第 3 章 产生式系统及其搜索方法
3.1 产生式系统
3.2 产生式系统的搜索 (控制 )策略
3.3 图搜索算法
3.4 产生式系统的规则问题
3.5 应用举例
3.6 产生式系统的不确定性问题
3.7 系统设计技巧
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
产生式系统使用类似于文法的规则,对符号
串作替换运算。 它是智能软件中使用最普遍、最典
型的一种结构。为什么要采用产生式系统作为智能
软件的主要结构呢? 这可以有 两点理由,
(1) 用产生式系统结构求解问题的过程和人类求
解问题时的思维过程很相象,因而可以用它来模拟
人类求解问题时的思维过程 ;
(2) 可以把产生式系统作为智能软件中的基本结
构单元或基本模式看待,就好象是 积木世界中的积
木块一样,因而研究产生式系统的基本问题就具有
一般意义。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
一个智能软件用产生式系统设计的基本组
成是, 一个综合数据库 ; 一组产生式规则 ;
一个控制系统。
综合数据库是产生式系统所使用的主要数
据结构,用来表述问题的状态或有关事实。
它包含求解问题的信息,其中有些部分可以
是不变的,有些部分可能只与当前问题的解
有关。人们可以根据问题的性质,用适当的方
法来构造综合数据库的信息。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
产生式规则的一般形式为,
条件 ─→行动 或 前提 ─→结论
即表示成为, if┄┄ then┄┄ 的形式。
其中,左边确定了该规则可应用的先决条件 ; 右边
描述了应用这条规则所采取的行动或得出的结论。
一条产生式规则满足了应用的先决条件之后,就可
对综合数据库进行操作,使其发生变化。如综合数
据库代表当前状态,则应用规则后就使状态发生转
换,生成新状态。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
控制系统是软件的控制程序,也是规则的解释 (推理 )程
序。 它规定了如何选择一条 可应用的规则对数据库进行操
作,即确定了求解过程的推理路线。 当数据库满足结束条件
时,系统就应停止运行 ; 还要使系统在求解过程中记住应用
过的规则序列,以便最终能给出解的路径。
控制系统也称控制策略,它也可以是从规则集中选择规
则并作用于状态的一种广义选取函数。确定某一种策略后,
可以算法的形式给出。在建立产生式系统描述时,还要给出
初始状态和目标条件,具体说明所求解的问题。 产生式系
统中控制策略的作用就是从初始状态出发,寻求一个满足一
定条件的问题状态。 目标条件也是产生式系统结束条件的
基础。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
上述产生式系统的定义具有一般性,它可用来模拟任
一可计算过程。 在研究人类进行问题求解过程时,完全可用
一个产生式系统来模拟求解过程,及可作为描述搜索的一种有
效方法。作为智能中的一种形式体系,它还具有以下优点,
(1) 适合于模拟强数据驱动特点的智能行为。
当一些新的数据数入时,系统的行为就要改变 ;
(2) 易于添加新规则去适应新的情况,而不破
坏系统的其他部分。 这是由于产生式系统的各组成
部分具有相对的独立性,因而便于扩展和修改。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
用产生式系统来求解问题,首先必须建立起问题的产生式
系统描述,即规定出数据库、规则集合及其控制策略。这
种把一个问题的叙述转化为产生式系统的三个组成部分,
在智能技术中通常称为问题的表示。一般来说一个问题可有
多种表示方式,而选择一种较好的表示是运用智能技术解决
实际问题首先要考虑的,而且要有一定的技巧。
建立了产生式系统描述之后,通过控制策略,可求得实现
目标的一个规则序列,这就是所谓问题的解,这个解序列是
根据控制系统记住搜索目标过程中用过的所有规则而构造出
来的。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
在一般情况下,问题可能有多个解的序列,但有时会要
求得到有某些附加约束条件的解,例如要求步数最少、距离
最短等。 这些约束条件通常是用耗散或代价这一概念来概
括,这时问题可称为寻找具有最小耗散的解。
在用产生式系统求解问题时,有时引入状态空间图。状
态空间图是一个有向图,其节点可表示问题的各种状态 (综
合数据库 ),节点之间的弧线代表一些操作 (产生式规则 ),它
们可把一种状态导向另一种状态。这样建立起来的状态空间
图,描述了问题所有可能出现的状态及状态和操作之间的关
系,因而可以较直观地看出问题的解路径及其性质。当然,
只有问题空间规模较小才可能作出状态空间图。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
建立产生式系统描述的过程,就是所谓问题的表示。对
问题表示的好坏,往往对求 解过程的效率有很大的影响。一
种较好的表示法会简化状态空间和规则集表示,此外,高
效率的问题求解过程与控制策略有关,合适的控制策略可缩
小状态空间的搜索范围,提高求解的效率。
从以上论述可知,用产生式系统来描述和求解问题,就
是在问题空间中搜索一条从初始状态到达某一个目标状态的
路径。这完全可以模拟人的求解过程,也就是可以把产生式
系统作为求解问题思考过程的一种模拟。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 2 产生式系统的基本算法
? E1,DATA←初始事实库
? E2,until DATA 满足结束条件以前,do
? E3,begin
? E4,在规则集中,选某一条可用于 DATA的规则
? E5,DATA←规则应用到 DATA得到的结果
? E6,结束
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
正向、逆向、双向产生式系统
用产生式系统求解某一问题时,如果按照规则使用的
方式或者说按推理方向来划分的话,有正向、逆向和双向产
生式系统。 正向产生式系统是从初始状态出发朝着目标状
态这个方向使用规则,即正推的方式工作,称这些规则为 F
规则 ; 若选目标状态作为初始 数据库逆向进行求解,即逆
向使用规则,产生子目标状态,反方向一步一步朝着初始
状态方向求解,整个逆推方式工作,称逆向产生式系统,
逆向应用的规则称 B规则 ; 若以双向搜索的方式 (即正向和
逆向同时进行 )去求解问题,则称为双向产生式系统。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
可交换的产生式系统
可交换式产生式系统的可交换性指几条规则的应用可
以任意交换次序而不影响求解。
一般来说,当一个产生式系统对任何一个数据库 D都
具有如下性质时,这样一个产生式系 统是可交换的。
(1) 可应用于 D的规则集合,使用了其中任意一条规则之后所生
成的任何数据库,这样一个规则集合还适用 ;
(2) 满足目标条件的某个数据库 D,当应用任何一个可应用于数
据库 D 的规则之后所 生成的任何数据库,任然满足目标条件 ;
(3) 若对 D应用某一规则序列后得到的一个数据库 D'(并能达到
解 ),当改变这些规则次序后,任然可求得解,即求得 D'与使用满足
D的可应用规则集合中的规则次序无关。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
可交换的产生式系统
例, 给定一个整数集合的初始状态 {a,b,c},设目标状态为
具有 a,b,c,ab,bc,ca这六个元素组成的集合。可应用的
规则集合为
R1,if {a,b,c} then {a,b,c,ab}
R2,if {a,b,c} then {a,b,c,bc}
R3,if {a,b,c} then {a,b,c,ca}
显然,这个产生式实例具有可交换性。
一个产生式系统具有可交换性,求解时只需搜索其中
任一条途径,只要解存在就一 定能找到目标,不必探索
多条途径,因此不可撤回的控制方式 (下节论述 ) 在这种
系统中使用很合适,因解与最初可应用的规则系列的次
序无关,系统不必提供特殊选择规则的机理 。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
可分解的产生式系统
先研究一个重写问题的产生式系统,初始数据库为
(C,B,Z),产生式规则如下,
? R1,C→(D,L)
? R2,C→(B,M)
? R3,B→(M,M)
? R4,Z→(B,B,M)
结束条件是生成只包含 M组成的数据库,即 (M,…,M) 。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
可分解的产生式系统
用图搜索方式求解这个问题时,搜索得到的部分状态
空间图见图 26。 图中只给出两条达到目标的路径和一条失
败的路径。实际搜索时有可能去探索更多的路径,往往导
致效率降低。
对于个问题,为了避免搜索多余的路径,可以将初
始数据库分解成几个可以独立加以处理的分量,分别对它
们进行求解。 即可以分别对每一个分量数据库,测试产
生式规则可以应用的条件,如此进行下去,直到分量数据
库满足某种结束条件为止。 要注意一般结 束条件应是所
有分量数据库都已满足结束条件。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
可分解的产生式系统
能够分解产生式系统的综合数据库和结束条件的产生
式系统称为可分解的产生式系统。一个可分解的产生式系
统,其基本算法描述 如下,
? (1) DATA:=初始数据库
? (2) {Di}:=DATA的分解式 ; 每个 Di元素都看成单独的数据库
? (3) Until {Di}的所有元素都满足结束条件之前,do:
? (4) begin
? (5) 从 {Di}中选一个不满足结束条件的 D*
? (6) 从 {Di}中删去 D*
? (7) 在规则集中选择一条可应用于 D*的规则 R
? (8) {di}:=R应用于 D*的结果
? (9) 在 {Di}上添加 di
? (10) end
第 3 章 产生式系统及其搜索方法
下图为分解方式 (C,B,Z)初态
┌──────┼──────┐
↓R2 ↓ R4 R1 ↓
(B,M,B,Z) (C,B,B,B,M) (D,L,B,Z)
↓R3 ↓R2 ↓R3
(M,M,M,B,Z) (B,M,B,B,B,M) (D,L,M,M,Z)
↓R3 ↓R3 ↓R4
(M,M,M,M,M,Z) (M,M,M,B,B,B,M) (D,L,M,M,B,B,M)
│ ┌─────┘ │
↓R4↓R3 ↓R3
(M,M,M,M,M,B,B,M) (D,L,M,M,M,B,M)
↓R3 ↓R3
(M,M,M,M,M,M,M,B,M) ─┐ (D,L,M,M,M,M,M,M,M)
R3↓目标
(M,M,M,M,M,M,M,M,M,M)
图 26
第 3 章 产生式系统及其搜索方法
3, 2 产生式系统的搜索 (控制 )策略
在 3,1, 2节的算法中,如何选择一条可应用的规则,
作用于当前的综合数据库,生成新 的状态以及记住选用的
规则序列是构成控制策略的主要内容。对大多数的智能应用
问题,所拥有的控制策略知识或信息并不足以使每次通过算
法 E4时,一下子就能选出最合适的 一条规则来,因而产生
式系统还必须把 E4扩大成搜索 (推理 )算法,以至于基本算法
的每 一循环中选一条规则试用,最终找出某一序列能产生
一个满足结束条件的数据库为止。由此可见,高效率的控制
策略需要有关被求解问题的足够知识,这样才能在搜索过程
减少盲目性,比较快的找到解路径。
第 3 章 产生式系统及其搜索方法
过去三十多年中,人们研究了许多种搜索算法,归纳起
来主要有两类, 一类是非启发 式算法 ; 另一类是启发式算法。
非启发式算法是按预定的控制策略进行搜索,在其过程中获
得的中间信息不用来改进控制策略。 由于搜索总是按预先
规定的路线进行,没有考虑问题本身的特性,所以不容易选
择到最优的搜索途径,效率较低,且出现 "组合爆炸 "的频率
高。 启发式算法是在搜索中加入了与问题有关的启发性信
息,用以指导搜索朝着最有希望的方向前进,加速问题的求
解过程并找到最优解。
3.2 产生式系统的搜索 (控制 )策略
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3, 2, 1 产生式系统控制策略分类
可分解的产生式系统
控制策略可划分为两大类,
┌不可撤回方法 ┌回溯方法
└试探性方法 ─ ┤
└图搜索方法
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3, 2, 2 不可撤回方法
这种方法相当于沿着单独一条路搜索下去,利用问题给
出的局部知识决定如何选取规则,就是说根据当前可靠的局
部知识选一条可应用规则并作用于当前综合数据库。 接着
再根据新状态继续选取规则,搜索过程一直进行,不必考虑
撤回用过的规则。 这是由于在搜索过程中如能有效利用局
部知识,即使使用了一条不理想的规则,也不妨碍下一步选
得另一条更合适的规则。这样不撤消用过的规则,并不影响
求到解,只是解序列中可能多了一些不必要的规则。显然这
种策略具有控制简单的优点。
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3, 2, 2 不可撤回方法
爬山法不仅适用于爬山问题,那些目标为极大值,搜索
过程是不断接近目标的单值问题都可应用这一方法。使用不
可撤回策略,虽然不可能对任何状态总能选得最优的规则,
但是如果应用了一条不合适的规则之后,不去撤消它并不排
除下一步应用一条合适的规则,那么只是解序列有些多余的
规则而已,求得的解不是最优解,但控制较简单。此外还应当
指出,一般很难对给定问题构造出任何情况下都能通用的爬
山函数,因而不 可撤回的方法具有一定的局限性。
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3.2.3 回溯方法
在问题求解过程中,有时会发现应用一条不合适的规则会阻扰或
拖延达到目标的过程。在这种情况下,需要有这样的控制策略, 先试一试
某一条规则,如果以后发现这条规则不合适,则允许退回去,另选一条
规则来试。回溯方法不保留完整的搜索树结构,只记住当前工作的一条
路径,回溯就是对这条路径进行修正。
使用回溯策略首要的问题要研究在什么情况下应该回溯,即要确定
回溯条件的问题。其次就是如何利用有用知识进行规则排序,以减少回
溯次数。 回溯应发生在以下三种情况,
(1) 新生成的状态在通向初始状态的路径上已出现过 ;
(2) 从初始状态开始,应用的规则数目达到所规定的数
目之后还未找到目标状态 (这一组规则的数目实际上就是
搜索深度范围所规定的 );
(3) 对当前状态,再没有可应用的规则。
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3.2.3 回溯方法
搜索深度的设置是一个值得注意的问题,设置太浅,有
可能找不到解 ; 设置太深,有可能导致回溯次数巨增。因而
应根据实际情况来规定搜索范围,先设置适中的深度搜索,
失败时再逐步加深。
回溯过程是一种可试探的方法,从形式上无论是否存
在对选择规则有用的知识,都可以采用这种策略。即如果没
有有用的知识来引导规则选取,那么规则可按任意方式 (固
定排序或随机 )选取 ; 如果有好的选择规则的知识可用,那么
用这种知识来引导规则选取,就会减少盲目性,降低回溯次
数,甚至不回溯就能找到解,总之一般来说有利于提高效率。
此外由于引入回溯机理,可以避免陷入局部极大值的情况,
继续寻找其他达到目标的路径。
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3.2.3 回溯方法
可用递归算法描述回溯策略,
YX0,选择一条新路径搜索 ;
YX1,搜索已超出规定指标 (无新路径、超时,超深度等 ),失败退出 ;
否则搜索继续 ;
YX2,搜索的状态找不到可用规则,回溯到 YX0;
YX3,搜索的状态依某种原则 (任意排列或按启发式准则 )取有用规则 ;
YX4,若规则用完未找到目标,回溯 YX0;
YX5,取头条可用规则 Ri;
YX6,删去头条规则,减少搜索中规则集长度 (注意,这不动原始规则
集 );
YX7,规则 Ri作用于当前状态,生成新状态 ;
YX8,若找到目标,成功退出 ; 若生成的 "新状态 "已出现过,回溯到
YX0;
YX9,记录新状态,对新状态递规调用 YX1～ YX7;
第 3 章 产生式系统及其搜索方法
产生式系统求解问题时,如果控制系统
保留所有规则应用后生成并链接起来的状态
记录图,则称工作在这种方式下的控制系统
使用了图搜索策略。 实际上图搜索策略是实
现从一个隐含图中,生成一部分确实含有一个
目标节点的显式表示的子图搜索过程。
3, 3 图搜索算法
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3,3, 1 一般性图搜索算法
步骤 1 G←S,OPEN←(S); 建立一个搜索图 G,它只含有
初始节点 S,建立一个 OPEN表 (今后它用于存储生成的节点 ),
开始它只含有初始节点 S。
步骤 2 CLOSED←( ); 建立一个 CLOSED表 (今后它用
于存储已扩展节点或将要扩展的某个节点 ),它的初始状态
为空表。
步骤 3 LOOP,if OPEN=( ) then return FAIL; 进入循
环。 如果 OPEN表已空,说明没有节点可扩展,就返回 FAIL,
即失败。
步骤 4 n←FIRST(OPEN),CLOSED←(n,CLOSED);
从 OPEN表中取出一个节点 n,将其 放入 CLOSED表中。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3.3.2 典型的非启发式图搜索算法分析与改进
广度优先搜索法
该方法从初始节点开始,序扩展生成下一级各子节点,
OPEN 表中已有的节点后 面 (实现先生成的子节点先扩展 ),
然后从 OPEN 表中提取最前的一个节点检查是否是目标节
点,否则再扩展,再重复上述操作。 这种方法认为同一级
各节点对问题求解的价值是同等的,因而对全部节点沿广
度进行横向扫描,按各节点生成的先后次序,先生成、先检
查、先扩展,沿广度遍历所有节点。
这种方法只要问题有解,即若树图上存在目标节点,
经搜索一定能找到。 所以,广度优先搜索法是完备的,是一
种推理算法。 但是,在问题大节点多,且目标节点距离初
始节点较远时将会产生许多无用节点,搜索效率低,还可能
产生组合爆炸。 因此,这种方法较适宜问题不大的环境中
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3.3.2 典型的非启发式图搜索算法分析与改进
深度优先搜索法
该方法从初始节点开始,顺序扩展生成下一级各子节点,放在
OPEN表中已有的节点前面 (实现后生成的子节点先扩展 ),然后从
OPEN 表中提取最前的一个节点检查是否是目标节点,否则再扩
展,再重复上述操作。 这种方法每一次扩展最晚生成的子节点,
沿着最晚生成的子节点分支,逐级纵向深入发展。
这种方法搜索一旦进入某个分支,就将沿着该分支一直向下搜
索。 如果目标节点恰 好在此分支上,则可较快地得到解。 但是,
如果目标节点不在此分支上,不回溯就不可能得到解。 所以,深
度优先搜索是不完备的,只是推理步骤。 如果回溯,不难证明其平
均效率与广度优先搜索法相同。 因此,深度优先搜索法如果没有
启发信息,很难有实用价值。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3.3.2 典型的非启发式图搜索算法分析与改进
代价驱动搜索法
该方法考虑了从一个节点经过一条支路,转移到另一个节点时所需
要支付的代价,如费用、时间等。 该方法从初始节点开始,扩展生成下
一级各子节点,这些子节点中若没有目标节点需再扩展搜索。 把它们放
进 OPEN表中,依据初始节点到它们各自所付出的代价 大小进行排序,代
价小的节点放在前面扩展,周而复始重复上述操作,直至找到目标节点
为止。
这种方法根据各条支路所需支付的代价有差别,所以具有同样路径
长度 ( 所经过的支路数 )的搜索过程,其搜索代价 (所支付的总代价 )可能
不同,优选最小代价的搜索路径,进行推理求解问题。 代价驱动搜索无
论在理论研究方面还是实际应用方面都很有前景,例如最短路径问题。
进一步的研究认为最短路径问题的改进应为以下几点,
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3.3.2 典型的非启发式图搜索算法分析与改进
代价驱动搜索法
1) OPEN表的节点排序问题,特别是在问题节点多达成千上万时尤
为重要,这一排序应采用映射排序,它是一个基于地址计算的排序,在
预置路径最大代价 dmax后,开辟一个数组 P(dmax),就可把节点送入其
值与 P数组下标相等的对应元素中,显然 di=50它对应 P(50); dj=500,对
应 P(500)。 相同代价值的节点落在同一数组元素中,用计数方式 可知有
几个。 由于数组元素是有序的,500>50,数组元素的下标自然把节点
一次定好了位置,排序即完成。 这一排序的时间复杂性为 O(N),对于
OPEN表面临的无数次排序操作,极大的提高了效率,
2) 搜索过程中,如果到达某一节点的代价 ≥任一初始节点到目标节
点的路径代价,这一节点的路径删去。
3) 搜索过程中,如果同时出现了两条到达某一节点的路径,代价大
的那条路径即时删去。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
搜索过程中,如果在确定扩展那一个节点时能充分利
用与问题求解有关的特性信息,就可以估计出节点的重
要性,就能使搜索选择重要性较高的节点,以利于求得
最优解。 象这样 就可用于指导搜索过程,且与具体问
题求解有关的控制性信息称为启发性信息。 启发性信息
可以用于估价节点重要性,表示为函数形式,
f(x)=g(x)+h(x)
其中,g(x)为初始节点 S。到节点 x已经付出的代价 ;
h(x)是从节点 x到目标节点 Sg的最优 路径的估计代价,它
体现了问题的启发性信息,其形式根据问题的特性确定。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法
如果对一般性图搜索算法作以下限制,则它成为 A*算法,
(1) OPEN表中的节点按估价函数 f(x)=g(x)+h(x) 的值
从小至大进行排序,
(2) g(x)是到目前为止,从 S。到 x的一条最小耗散值路
径的耗散值,是作为从 S。到 x 最小耗散值路径的耗散值
g*(x)的估计值,g(x)>0。
(3) h(x)是 h*(x)的下界,即对所有 x均有 h(x)≤h*(x)。 而
h*(x)是从节点 x到目标节点的最小代价,若有多个目标节点,
则为其中最小的一个。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 1 对于有限图,A*算法一定会在有限
步内终止,
证明,对于有限图,其节点个数是有限的,
A* 算法在经过若干次循环后会出现两种情
况, 或者搜索到目标节点在步骤 5结束 ; 或
者 OPEN表中的节点被取完在步骤 3结束。
不 管那种情况,A*算法都在有限步内终止。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 2 对于无限图,只要从初始节点到目标节点有路径存在,A*算法
也必然终止。
证明, 分两步, 第一步证明 A*算法结束前,OPEN表中存在节点 x‘,它
是最优路径上 的一个节点,且满足 f(x')≤f*(s).。
设最优路径是 S。 x1,x2,…,S*g
由于 A*算法中的 h(x)满足 h(x)≤h*(x)
所以 f(s0),f(x1),f(x2),…,f(xm) 均不大于 f(sg*)=f*(s0).
又因为 A*算法是广度代价择优,所以在它结束之前,OPEN表中一
定含有 S。 x1,x2,…,S*g 中的一些节点,设 x'是其中最前面的一个,
则它必然满足 f(x')≤f*(S0)
至此,第一步证明结束 ;
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 2 对于无限图,只要从初始节点到目标节点有路径存在,A*算法
也必然终止。
第二步证明：用反证法,假设 A*算法不终止,并设 e是图中各条边的最
小代价,d*(xn )是从 S。到节点 xn的最短路径长度,则显然有
g*(xn)≥d*(xn)× e
又因为 g(xn)≥g*(xn)
所以有 g(xn)≥d*(xn)× e
再因 h(xn)≥0,f(xn)≥g(xn)
故得到 f(xn)≥d*(xn)× e
由于 A*算法不终止,随着搜索的进行,d*(xn)会无限增大,从而使
f(xn)也无限增大。 这与第一步证明得出的结论矛盾,因对可解状
态空间来说,f*(s0)一定是有限值。
所以,只要从初始节点到目标节点有路径存在,即使对于无限图,
A* 算法也一定会终止。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 3 A*算法一定终止在最佳路径上
证明, 假设 A*算法不是在最优路径上终止,而是在
某个目标节点 t处终止,则 f(t)=g(t)>f*(s0)。但是由
性质 2证明可知,在 A*算法结束之前,OPEN表中
存在着节点 x‘,它应该在最优路径上,且满足
f(x')≤f*(s0) 此时,A *算法一定会选择 x'来扩展
而不会选择 t,这就与假设矛盾,所以,A*算法
一定会终止在最优路径上。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 4 A*算法是最优的
证明, A*算法的搜索效率很大程度上取决 h(x),在满足
h(x)≤h*(x)的前提下,h(x)的值越大越好。 h(x)值越大,
表明它携带的启发信息越多,搜索时扩展的节点数越
少,搜索的效率越高。
设 f1(x)与 f2(x)是对同一问题的两个估价函数
f1(x)=g1(x)+h1(x)
f2(x)=g2(x)+h2(x)
A1*和 A2*分别是以 f1(x)及 f2(x)为估价函数的 A*算法,
且对于所有的非目标节点 x均有 h1(x)<h2(x)。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 4 A*算法是最优的
证明（接前页 ),此情况下证明 A1*扩展的节点数不会
比 A*2扩展的节点数少,用归纳法,
设 K表示搜索树的深度
当 K=0时,结论显然成立 ;
设当搜索树的深度为 K-1时结论成立,即 A*2扩展了的节
点,A*1也扩展了 ;
现仅证明 A*2扩展的第 K代的任一节点 xk也被 A*1扩展,
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 4 A*算法是最优的
证明（接前页 ),由假设可知,A*2扩展的前 K-1代节点 A*1也都扩
展了,因此 A1* 搜索树中有一条从初始节点 S。到 xk的路径,其费用不
会比 A*2搜索树从 S。到 xk的费用更大。 即 g1(xk)≤g2(xk)
假设 A*1不扩展节点 xk,这表示 A* 1能找到另一个具有更小估价值
的节点进行扩展并找到最优解,
此时有 f1(xk)≥f*(S0) 即 g1(xk)+h1(xk)≥f*(S0)
应用关系式 g1(xk)≤g2(xk)到上列不等式中,得 h1(xk)≥f*(S0)-
g2(xk),
由于 h2(xk)=f*(S0)-g2(xk),这就得到 h1(xk)≥h2(xk)
这与最初的假设 h1(x)<h2(x)相矛盾 证毕。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法的改进
改进 1 OPEN表中自始至终的排序,采用 3.3.2.3
节中介绍的映射方法。
改进 2 h(x)单调限制, A*算法中,每当扩展一
个节点时都要检查其子节点是否已在 OPEN表或
CLOSED表中,有时还需调整指向父节点的指针,
这就增加了搜索代价。 如果对启发函数 h(x)单调限
制,可减少检查和调整的工作量,从而提高搜索效率。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法的改进
所谓单调限制 h(x)应满足两个条件,
(1) h(Sg)=0
(2) 设 xj是节点 xi的任一子节点,则有 h(xi)-
h(xj)≤c(xi,xj)
其中,Sg是目标节点 ; c(xi,xj)是节点 xi到其子节
点 xj的边代价。
若把上式改写 h(xi)≤h(xj)+c(xi,xj),可看出节点
xi到目标节点的估价不会超过 x i 到其子节点 xj边
代价加从 xj到目标节点的估价。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法的改进
当 A*算法的启发函数 h(x)满足单调限制时,可得出以下
两个结论,
(1) 若 A*算法选择节点 xn进行扩展,则 g(xn)=g*(xn)
(2) 由 A*算法所扩展的节点序列其 f值是非递减的。
这两个结论都是在 h(x)满足单调限制时才成立, 对于第 2
个结论,当 h(x)不满足单调 限制时,有可能某个要扩展
的节点比以前扩展的节点具有较小的 f值,
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法的改进
改进 3 引入感兴趣集的算法, 这一改进的思路是
这样的,问题求解时,人们往往知道最佳路径上有关节
点的某些启发信息。 例如,在求城市 A到城市 B的最
佳路径时,人们往往凭自己的经验断定所要求的最佳
路径必经城市 C和城市 H,这里我们称 {C,H} 是感兴 趣
集合。 若知道感兴趣集且启发式搜索算法恰当地应用
感兴趣集,则肯定可以改善算法的搜索效率。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法的改进
算法的改进使用 OPEN1和 OPEN2,CLOSED1和
CLOSED2四个表,对任一节点 x,若从 s 到节点 x的当前
路径中不含感兴趣集中的节点,则 x放入 OPEN1中 ; 否
则放入 OPEN2中。 选择 节点扩展时,首先扩展
OPEN2中的节点,因为 OPEN2中含有感兴趣集中的节
点,可能比 OPEN1中的节点更有希望在最佳路径上,
而且所扩展的节点数目总不会多于原算法。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
讨论 (1)
启发式搜索算法在大问题中一般优于非启发
式搜索算法,因此,有效地分析利用启发信息尤为
重要。 含有启发信息的评价函数可写成下列形式,
f(x)=v·g(x)+w·h(x)
其中,v,w为权系数且 ≥0,当 w↑,强调启发信息,
搜索过程沿最有希望的方向进行,效率肯定高,但
降低了完备性 ; 当 v↑,强调历史信息,搜索过程沿横
向扫描,有利于完 备性,但降低了搜索效率。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
讨论 (2)
根据启发信息,可将复杂的、规模大的问题分解为简
单的规模小的若干子问题。 那么各子问题的搜索过程
A1,A2,…,An 是完备的,则搜索过程 A也是完备的。
A=A1∩A2∩…∩An
根据启发信息,可将原始的问题进行同构或同态的等价
变换,转换为若干等价问题。 那么等价问题的搜索过程
A1,A2,…,An 是完备的,则搜索过程 A也是完备的。
A=A1∪ A2∪ … ∪ An.
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 4 AND/OR图搜索算法
上节探讨的算法具有重要的意义。 但对于复杂的
问题,它们并不是唯一的途径,若利用它们直接求解往
往还比较困难。 AND/OR 图算法是用于表示问题及
其求解过程的又一 种形式化方法。
定义 1 AND图及 AND图算法把 一个复杂的问题
分解成若干个较为简单的子问题,每个子问题又可继
续分解为更为简单的子问题,重复此过程,直到不需要
再分解或者不能再分解为止。 这个分解图是与图,根
据这个图对每个子问题分别求解,然后把这些解合并
起来得到原问题解的过程是 AND图算法。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 4 AND/OR图搜索算法
定义 2 OR图及 OR图算法把 一个复杂问题利用同
构或同态的等价变换,使之成为若干个较容易求解的
新问题。 这个变换图是 OR图,根据这个图对新问题
求解,当且仅当新问 题有一个可解,就得到原问题的
解的解过程是 AO图算法。
定义 3 可解节点 在 AND/OR图中,满足下列条件
之一者为可解节点,
(1) 它是一个终止节点,
(2) 它是一个 OR节点,且子节点中至少有一个是可解节
点,
(3) 它是一个 AND节点,且其子节点全部是可解节点。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 4 AND/OR图搜索算法
定义 4 不可解节点 定义 3中三个条件全部不满足
的节点称为不可解节点。
下面分析 AND/OR图 AO*搜索算法,作一些改进探讨 ;
探讨类比搜索方法,为此,我们首先给出 AND/OR图的一般
搜索过程,
(1) 把原始问题作为初始节点,并作为当前节点。
(2) 应用分解或等价变换算符对当前节点进行扩展。
(3) 为每个子节点设置指向父节点的指针。
(4) 选择合适的子节点作为当前节点,反复执行 (2)和 (3),
直至找到可解节点或不可解节点为止。
下班可解或不可解的搜索过程都是至上而下的。 如果
确定某个节点是可解节点,则不可 解的后裔节点不再有用,
可从搜索图中删去 ; 同样,如果确定某个节点是不可解节点,
则全部后裔节点都不在有用,也可从搜索图中删去。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
定义
定义 5 设 AND/OR图 G,则从节点 n到一立即可解的叶
节点集合 N的一解图 G'定义为,
(1) G'是 G的子图 ;
(2) 若节点 n是集合 N中的元素,则 G'是由单一节点 n组
成的 ;
(3) 若节点 n有一个指向节点 {n1,n2,…,nk} 的 k-连接
符,使得从每个后继节点 ni到集合 N有一个解图 (i=1,2,…,
k),则 G'由节点 n,k-连接符、节点 {n1,n2,…,nk } 以及从
{n1,n2,…,nk} 中的每个节点到集合 N的解图组成。
(4) 否则,从节点 n到集合 N不存在解图。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
定义
定义 6 从 AND/OR图任意节点 n到一立即可解
的叶节点集合 N的解图耗散值 k(n,N) 可递归地定义
为：
(1) 若节点 n是集合 N中的元素,则 k(n,N)=0;
(2) 否则,节点 n 有一 个通到解图中后继节点集
合 {n1,n2,…,ni} 的连接符, 令该连接符的耗散值为
Cn,则
k(n,N)=Cn+k(n1,N)+k(n2,N)+…+k(ni,N)
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
定义
定义 7 AND/OR图求解中,从起始节点到一可解叶节点
集合具有最小耗散值的一个解 图称为最佳解图。 令函数
h*(n)表示从 AND/OR图中的节点 n 到一可解的叶节点集合的
最佳 解图的耗散值 ; 启发式估价函数 h(n)是 h*(n)的估计。
定义 8 若启发式估价函数 h满足单调限制,即对
AND/OR图中任意节点 n及其适用于 n的任一 k-连接符,有
h(n)≤Ck+h(n1)+…+h(nk)
其中,Ck为 k-连接符的耗散值,n1,n2,…,nk 是应用 k- 连接
符于节点 n所得的全部后继节点。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
AO*算法
A1,建立一个搜索图 G,G:=s,计算 q(s)=h(s),IF GOAL(s) THEN
M(s,SOLVED);开始时图 G只包含 s,耗散值估计为 h(s),若 s是终节点,则标
记能解,
A2,Until s已标记上 SOLVED,do,
A3,begin
A4,G':=FIND(G); 根据连接符标记 (指针 )找出一个待扩展的局部解
图 G'.
A5,n:=G'中的任一非终节点 ; 选一个非终节点作为当前节点,
A6,EXPAND(n),生成子节点集 {nj},G:=ADD({nj},G),计算
q(nj)=h(nj),其中 nj∈ G,IF GOAL(nj) THEN M(nj,SOLVED); 把 n的子
节点添加到 G中,对 G中未出现的子节点 计算耗散值,若有终节点则加能
解标记,
A7,S:={n}; 建立含 n的单一节点集合 S.
A8,Until S 为空,do
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
AO*算法 (接前页 )
A9,begin
A10,REMOVE (m,S),mc∈ {S}; 这个 m的子节点 mc应不在 S中,
A11,(1) 修改 m的耗散值 q(m):
对 m指向节点集 {n1i,n2i,…,nki} 的每一个连接符 i分别计算 qi,
qi(m)=Ci+q(n1i)+…+q(nki),
q(m):=min qi(m); 对 m个的 i个连接符,取计算结果最小的那个
耗散值为 q(m).
(2) 加指针到 min qi(m)的连接符上,或把指针修改到 min qi(m)的
连接符上,即原来指针与新确定的不一致时应删去,
(3) IF M(nji,SOLVED) THEN M(m,SOLVED); 若该连接符的所
有子节点都是能解的,则 m也标上能解,
A12,IF M(m,SOLVED)∨ (q(m)≠q0(m)) THEN ADD(ma,S); m能解
或修正的耗散值与原先估算 q0不同,则把 m的所有先辈节点 ma添加到 S中,
A13,end
A14,end
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
分析与改进
算法 AO*可以理解为两个主要运算, A1～ A6,完成自上而下的图生成,
通过有标记的 连接符,寻找最好的局部解图,然后对其中一个非终节点进
行扩展,并对其后继节点赋 给耗散值 ; A7～ A12,完成自下而上的耗
散值修正、连接符标记和节点的能解标记。
(1) 耗散值的修正从刚被扩展的节点 n开始,其修正耗散值 q(n)取估计
h*(n) 的所有值中最小的一个,然后根据耗散值递归计算公式逐级向上修
正先辈节点的耗散值,只有下层节点耗散值修正后,才可能影响上一层节
点的耗散值,因此必须自底向上一直修正 到初始节点。
(2) 在 A6中扩展节点 n时,若不存在后继节点 (即限入死胡同 ),则可
在 A11中对 m(即 n) 赋一个高的 q值,这个高的 q值会依次传递到 s,使得
含有节点 n的子图具有高的 q(s),从而排除了被当作后选局部解图的可能
性。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
分析与改进
(3) A5中怎样选 G'中的一个非终节点扩展值得研究, 一般
可以选一个最可能导致该局部解图耗散值发生较大变化的那
个节点先扩展,因为选这个节点先扩展,会促使及时修改局
部解图的标记。
(4) 与 3.3.3.2节 A算法类似,应让 h(n)满足单调限制条件,这
样,当 h(n)≤h*(n) 则 AO* 一定能找到最佳解图。 当 h(n)≡0时,
AO*成宽度优先算法。
(5) AO*中评价函数只考虑 h(n)分量,计算 g没有必要也
不可能。 其次由于 k- 连接符 连接的有关子节点,对于父节
点能解与否以及耗散值都有影响,因而不能象 A算法那样优
先扩展其中具有最小耗散值的节点。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 6 类比搜索方法探讨
构思
在 AO*和 A算法中,所使用的启发信息大多是人们依据具体领域问题靠
经验总结得来的,启发信息获取十分困难,且精确性和可靠性也难以保证。
此外,搜索算法一般执行一次性搜索,将同一问题的多次搜索视为彼此独
立、毫无相关的过程。 每次求解问题时,面临的都是全新的搜索图,即使
求解的是相同问题,算法仍然从零开始,这显然与人类求解问题的方式不
符。 人类求解问题的一个重要特点,就是常常利用以前求解相同 或相似问
题的经验来指导新问题的求解。 这实际上是一种类比学习机制,如果将这种
机制引入搜索算法,则多次搜索被看成相互关联的过程,前面搜索积累的
经验将有助于提高后 面搜索的效率。 即,利用类比获得与新问题相似的过
去问题的求解过程,作为启发信息来指导新问题的求解,这样可以缩小搜
索范围,降低问题求解的复杂性。 也就是说,如果算法设计恰当,可以自
动获得启发信息。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 6 类比搜索方法探讨
方法探讨
AO*,A及其它算法在问题的求解过程中利用与该问题
相关的启发信息来帮助搜索,启发信息通常被用于三种情况,
(1) 帮助确定扩展节点。
(2) 在扩展节点的过程中,帮助决定产生后继节点。
(3) 在扩展节点的过程中,决定那些节点可从搜索树上
删除。值得注意的是,启发信息是一种局部信息,只在搜索
路径的每个节点上为选择操作提供参考。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 6 类比搜索方法探讨
方法探讨
类比搜索方法把类比推理技术与状态空间的启发式搜索
相结合,实际上是对人类求 解问题、积累经验和增加求解问
题能力的一种模拟。 要实现它,需要解决如下一些主要问题,
(1) 如何积累问题求解的经验,即在一个问题的求解过
程中,需要记录那些有用信息。
(2) 如何定义和判断两个问题的求解情况是相似的,如
何高效的进行检索。
(3) 如何有效地使用类比结论,即相似的过去问题的
求解经验,作为特殊的启发信息指导新问题的求解。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 6 类比搜索方法探讨
方法探讨
基于上述几点,需要建立一个类比的启发式搜索求解模型。 它主要包括
生成求解事例、检索及指导求解三个推理过程。类比搜索方法在每次求解一
个新问题时,不是直接去搜索给定的状态空间,而是首先在求解事例库中检索,
查找与该问题相似的过去问题的求解事例。 若存在相似问题的求解事例,则
以此作为启发信息,指导该问题的求解。 具体地说,就是在新问题的求解过
程中,对过去问题的求解事例中记录的成功搜索路径上每个操作的依据条件
重新测试, 如果依据条件仍满足,则算法根随成功的求解路径。 否则,对
原求解过程进行改写,形成的新问题求解过程作为一个新事例存储在事例库
中,以便指导将来相似问题的求解。 过去问题与新问题的相似性越高,求解
过程需要的搜索就越少。 在最理想的情况下,甚至不需要搜索。 当没有检索
到一个与新问题相似的过去问题的求解事例时,则使用 A*或 AO*等算法进行,
并在获得解时将求解过程作为一个求 解事例存储在事例库中。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 6 类比搜索方法探讨
方法探讨
系统最初使用时,由于事例库中缺少求解事例,
只有使用 A*或 AO*等算法。 随着求解次数的增加,
求解事例将不断积累,类比的资料增多 (启发信息增
多 ),从而使求解问题 的效率不断提高。
由此可知,类比搜索方法的特点是, 类比启发
信息不仅包含了局部信息,而且提供了指导求解的
搜索方向,这样就可以将一个庞大空间的搜索压缩
为对一个或数个很小空间的搜索,极大地提高了求
解效率。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 7 讨论
用 AND/OR图算法求解问题时,求解过程就是对一
个隐含的 AND/OR图进行搜索。 初始数据库对应于
AND/OR图的根节点,规则对应于 k-连接符,结束条
件的数据库对应于一组 终节点集合,搜索算法的任务就
是找到从初始节点到一组终节点集的一个解图。
AND/OR图的启发式搜索算法 AO*是通过评价函
数 f(n)=h(n)来引导搜索过程,适用于分解得到的子问题
不存在相互作用的情况。若 S→N集存在解图,当
h(n)≤h*(n)且 h(n) 满足单调限制条件时,AO*算法一定
能找到最佳解图,在这种情况下,AO*具有可采纳性。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 7 讨论
类比搜索方法实施的关键技术在于生成求解事例、相似性度量和检索、
以及指导求 解。 生成求解事例就是积累问题的求解经验,其生成过程主要
解决的问题是对于一个 求解事例需要记录和保存问题求解过程中的那些特
征信息,以及如何进行表示,抽取和存储 这些信息。 求解一个复杂问题时,
经常面临庞大的搜索。 大量被搜索的节点中,有成功的、也有失败的。 为
了给相似问题的求解提供有用信息,就要确定保存搜索过程中的哪些有用特
征信息。显然,走两个极端最简单, 第 一是记下整个搜索过程 ; 第二是只记
问题的最终解。 这两个极端都不圆满,具体地作法除了保留问题的最终解
外,还应该记录有关选择这 些操作的情境和依据条件。 这是一个很有意义
的研究课题。 相似性的度量也是类比搜 索方法的一个关键问题。 相似程度
越高,度量方法恰当,相似问题的检索俞易获得。 关于这方面,目前还是
主要根据新、老问题的特征和关系来确定它们之间的相似性。 此外,还可设
置相似度阀值,检索采用直接映射式方法。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 7 讨论
指导求解是类比搜索方法的控制程序,主要考虑灵活的处理
策略。 一般要考虑以下 几点,
(1) 当检索没有类比启发信息时,程序能转向常规搜索方
法。
(2) 当检索到一个与新问题完全相似的过去问题的求解
事例时,程序能直接转换解。
(3) 当检索到一个与新问题部分相似的过去问题的求解
事例时,程序能提取相似部 分解过程,还能组织部分搜索、
衔接新的解过程。 此外,应有裁剪过去问题多余解过程 的
功能。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 1 规则不一致原因及解决方法
规则集中存在的不一致是影响系统性能的重要因
素之一。系统建立初期,由于规则集较小,内容也比
较简单,设计人员能对每一条规则的条件和结论部分反
复推敲和精心 构造,这类问题容易防止。但随着时间
的推移,新的规则不断加入,规则集合越来越大,内
容也越来越丰富,这时规则间的相互影响和相互联系
就随之变得复杂。在此情况下,规则的不一致就将自
然产生,当然,对它的认识和解决也就显得很重要。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 1 规则不一致原因及解决方法
主要的不一致规则种类
(1) 循环规则, 由数个规则的前提和结论形成一个循环链,
最终由末尾规则的结果 子句推出起始规则的前提部分 ;
(2) 冲突规则, 两个规则的前提条件等价,但一个或多个结
果子句有矛盾或者前提 子句有矛盾而结论部分完全等价 ; 也
有可能由多条规则链形成冲突规则集 ;
(3) 冗余规则, 两个规则的前提条件等价,一个或多个子结
果子句也等价 ;
(4) 从属规则, 两个规则有相同的结果,但其中一个包含有
多余的约束条件。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 1 规则不一致原因及解决方法
不一致规则的检查解决方法
(1) 对于循环规则,可构造规则集的 IF---THEN图,从起始规则的
条件部分开始搜索,如果搜索过程中遇到的 THEN部分已在前面出现,
就可以 中断搜索,规则集中包含的循环规则子集合需设计人员检查,解
决 ;
(2) 对于冲突规则,构造 IF---IF表,对规则集内有相同的 IF 规则子句
构造规则树,形成推理图。同时建立 THEN---THEN表用以判断是否有
冲突规则出现。 对相同 IF部分的规则继续用它的各自 THEN部分作为其
它可以匹配的 IF前提条件,递归地构造,如发现两个推理图上分别有节点
在 THEN---THEN表上是矛盾的,则检测出冲突规则,人工予以解决。
(3) 对冗余规则和从属规则的检查类似于冲突规则链的方法, 不同
之处是前者在推理图中的遍历是试图发现有 THEN部分等价的两条规则。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法原则
依赖规则：如果 Ri的结论部份包含有 Rj的条件部份，则
Rj是一个依赖规则，即 Rj 依 赖规则 Ri，或称 Ri是一个被依
赖规则。
优先规则, 如果 Ri被 Pi个其它规则所依赖次数 pi越大,Ri
被援引的可能性越大。
静态规则排列：亦是在原文分析、原文译文转换、译文
生成之前,对规则集中已有 的规则按优先次序排列。
动态规则排列：这相当于自学习能力，即某些句子分析、
转换、生成时,会增加一 条或几条规则。这些规则有可能
还与未完成的其它语句有关。因此,在对其它语句和完成
速度影晌不大的情况下，同时再排列规则称之为动态规则排
列。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法原则
映射排列：是一个基于地址计算的排序。例如，求出上
述 Pi(i=1,2,...,N）的最大值后，若开辟一个数组 D
（ Pmax）,就可把数据送入数据值下标相等的对应元素中。
显然 Pi=50，对应 D(50); Pj=500,对应 D(500)。相同数据落在
同一数组元素中,用计数方式可知有几个。由于数组元素
是有序的,500>50,数组元素的下标自然把数据一次定好
位置，最后只要按规定的方式调非零元秦，相同元素按计数
值次数调动，排序即完成。
枚举计数：如果规则 Ri被规则 Rj依赖 (j=1,2,...,N)，则
Pi=pi+1（ Pi初值赋 1) 。 显然，对于 N条规则，每一条都将
确定与其它规则的依赖关系并计算，这一过程称之为枚举计
数。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
静态算法（上）
B1,[初始化 ]，有 N条规则，置 P1至 PN皆为 1。
B2:〔 对 i循环 〕 对 i=N,N— 1,N-2,…, 2执行 B3;
然后转 B5。
B3:〔 对 j循环 〕 对 j=i-1,i-2,…, 1执行 B4; 然后转
B2。
B4:〔 寻求 Ri被 Rj依赖次数 〕 若 Ri被 Rj依赖，
Pi←Pi＋ 1；否则转 B3。
B5,一遍扫描 Pi（ i=1,2,...,N)，求 Pmax。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
静态算法（上）
静态算法进行到这里，求出了任一规则 Ri被依赖次
数 Pi。 Pi对应于 Ri，相当于 Ri 被 依赖次数 Pi。 Pi对
应 Ri，相当于 Ri的关键字。其中，很可能出现 Pi=Pj
(i≠j),这说明 Ri和 Rj被其它规则依赖的条数相同。怎样
快速地按关键字 Pi(i=1,2,...,N) 大小把规 则快速地排
列起来，并满足动态需要，我们采用高效算法 —— 映射
排序
算法初始按关键字值以映射关系作一次扫描，基本
排定规则位置,Ri→Pi→D（ Pi）。 对相同关键字的处
理，算法附加了三个数组空间：每一记录的链指针空间
L（ i）,链首指针空间 Q，链当前指针空间 W。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
静态算法（上）
关键字值 Pi与 D数组元素下标映射关系有一次时,D(Pi)=1；这
时 Q(Pi)←1，记录了具 有这唯一对应关系 Pi所在规则的地址 i，并
作为最后排序调整位置的首地址。 W（ Pi） ←i 为出现相同关键字
提供链接地址作准备。
映射时出现相同关键字，如 Pi=Pj，这时 D（ Pi） >1，我们把
Pi和 Pj 对应的两条规则 链接起来，入口地址仍是 Q（ Pi） =i，但 L
（ W（ Pi）） ←j，相当于 L(i)=j,此外,W（ Pj） ←j，为链接出现
多个相同关键字作准备。
实施映射和链接处理后，最后再实施一次扫描，根据 D数组下
标值的有序性,D=0 不实施操作,D≥l从相对应的 Q数组下标值作
为入口地址调整一次规则位置即完成排列。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
静态算法（下）
B6,[映射初始化，开辟链指针空间 L，容量 N; 映
射计数空间 D，链首指针空间 Q，链当前指针空间 W，
容量均为 Dmax，赋初值 i=1。
B7,扫描 Pi，让 D（ Pi） ←D（ Pi）＋ 1 ；以映射关
系确定 Pi的位置，记录相同 Pi 的 个数。
B8：若 D(Pi)=1，作 W(Pi)←i和 Q(Pi)←i，转 B10。
B9,若 D（ Pi） >1，作 L（ W（ Pi）） ←i和 W(Pi)←i。
B10,i←i+1，直至 i=N为止，实施 B7～ B9。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
静态算法（下）
B11:（ Z=1)，从 J=Dmax开始，若 D（ J） =0转 B12;
D（ J） ≠0，作递减排列。
(1) T←Q（ J）；链首指针送 T。
(2) 输出 RT。
(3) z←z ＋ 1，若 Z≠D(J),T←L（ T）后转 (2)；否
则转 B12。
B12,J←J-1，实施 B11，直至 J=0结束。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
动态算法
规则匹配过程中，如果系统自学习新增一条规则
RN+1，将立即置人规则集适当位置，自动启动的算法
是：
C1：对 i=1,2,...,N，若 RN+1被 Ri依赖，
PN+1←PN+1+l（ PN+1初值赋 1）；反之,若 Ri被
RN+1依赖,Pi←Pi+1。
C2：若 PN+1>Pmax,Pmax←PN＋ 1
C3，调静态算法（下），其中修改 N←N + 1。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
算法分析
1）静态算法（上）时间复杂性为 O（ N2），因为
B1～ B5执行步骤共需
(N-1)+(N-2)+...+2+1+N=1/2(N2+N)。
2）静态算法（下）时间复杂性为 O（ N），因为算法
的构思来源于映射排序算法中的一 部份，其证明可参
阅书末文献。由于动态算法仅 C1一 C2引进附加操作，
显然为 O(N),C3为 O(N)，所以动态算法时间复杂性为
O(N)
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
算法分析
3）由于静态算法（下）附加存储空间 3Pmax+N，因
此,动态算法获得的高效率是由空间代 价换取的。
4） 算法假设了规则自身依赖，所以 Pi的初值赋 1。
5) 算法将规则优先排列，使规则匹配花费平均时间
最小。平均时间最小亦说明，一 般状况下，分折的句
子越多，其效率越高；但也可能存在某些状况,所需
规则恰好排列在最后。所以，这一算法是平均时间较优
算法。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
实验结果
排序算法的实验是这样进行的，在上述规则集中，
分析 4条语句。设计第 1 条语句产 生 1条规则，该规则 2、
3,4条语句都将涉及。把这条规则分别放于最后和进行
动态排列，结果后者完成 2,3,4条语句分析较前者速
度提高 1倍多。这是一个目前具有 3380条规则的 实验系
统，有如此实验效果足以说明此算法的实用性。
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
任何一种自然语言,总是要遵循一定的语法规则
的,计算机要理解、翻译自然语言,就要对理解和翻
译的语言建立一套规则,也就是语法,并且提供一种
适合计算机处理的语法描述形式。上下文无关语法
是适合描述自然语言的一种体系。作为一个例子,
先来考察汉语的一个很小子集,它的上下文无关语
法由以下一系列重写规则组成,
(1) <一种句子结构 >→<名词 ><动词 ><数词 ><名词 >
(2) <名词 >→电脑 │学院 │中国 │地图 │卫星 │…
(3) <动词 >→购买 │绘制 │发射 │…
(4) <数词 >→一颗 │十台 │一幅 │…
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
在这些重写规则中,尖括号称之为非终极符 ; 而
电脑、学院 … 称终极符 ;竖线 "│"表示或的意思。这
种语法之所以是上下文无关的,是因为在这些重写
规则中,左边项都是孤立的非终极符,它们可以被右
边的符号串所替换,而不管左边出现的上下文。
这种语法既可用于生成语法正确的汉语句子,也
可用于分析输入的汉语句子是否合乎语法。
下面三例计算机可以简单验证是正确的句子,
1> 中国发射一颗卫星
2> 学院购买十台电脑
3> 电脑绘制一幅地图
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
即 一种句子结构
│ │ │ │
┌──┘ │ │ └──┐
名词 动词 数词 名词
│ │ │ │
中国 发射 一颗 卫星
学院 购买 十台 电脑
电脑 绘制 一幅 地图
上下文无关语法的形式化描述严谨且规范,计算机程序便
于实现,其算法大致上可分为以下三种,自顶向下分析法 ;自底向
上分析法 ;融合自顶向下和自底向上分析法。 本节仅 探讨自顶
向下算法。
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
自顶向下分析算法 (仅针对上述子集 ):
D1,从规则 (1)开始,即从 <一种句子结构 >开始,替换成 <名
词 ><动词 ><数词 ><名词 >。
D2,句首切分出的第一词语与 (2)中词语匹配,找到转 D3;否
则转 D6。
D3,句子第 二词语与 (3)中词语匹配,找到转 D4;否则转 D6。
D4,句子第三词语与 (4)中词语匹配,找到转 D5;否则转 D6。
D5,句末词语与 (2)中词语匹配,找到成功结束 ;否则转 D6。
D6,失败退出。
产生式规则还可描述成, 条件 →行动 或 前提 →结论。 这
与重写规则相似,但使用产生式规则的方法作句法分析,容易
分析复杂的句子,操作灵活,也易于模块化和结构化。
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
用于句法分析的产生式模块经过改进,但仍
包含三个基本组成部分,
(1) 事实库,改进后的词语库,它进行了词类
标注等,如,的 /P;涌现 /V;价值 /A;技术 /N; 产品 /N;
科技园 /N;高新 /DET…
(2) 规则集,存储有关语法的状态转移、性质
变化等规则的过程性知识。
(3) 控制器,将规则与事实进行匹配,控制句
法分析过程。
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
例, 定义分析有限个汉语句子的产生式规则
(限于篇幅,仅选有关一小部分 ),终结目标 S。
(1) N→NP (2) A NP→NP
(3) DET NP→DNP (4) P DNP→PP
(5) DNP PP→DNP (6) V DNP→VP
(7) DNP VP→S
下面用计算机程序 (产生式模块 )来分析一个
汉语句子是否合法,
"高新技术的高新价值产品涌现高新科技园 ".
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
算法执行过程,
经自动分词和算法 E1,已得到,
DET N P DET A N V DET N
继续执行算法 E2～ E6,
将 N→NP(1),DET NP P DET A NP V DET NP
将 A NP→NP(2),DET NP P DET NP V DET NP
将 DET NP→DNP(3),DNP P DNP V DNP
将 P DNP→PP(4),DNP PP V DNP
将 DNP PP→DNP(5),DNP V DNP
将 V DNP→VP(6),DNP VP
将 DNP VP→S(7),S (合法而结束 )
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
产生式系统在应用中,结论可能是不完全确
定的。因此,产生式系统的设计应考虑不确定性
的搜索过程, 有两种不确定性, 证据不确定性和
结论不确定性。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 1 关于证据不确定性
当在考虑问题时,所遇到的经常具有某种不
确定性。例如,当你观察某种动物的颜色时,有
可能认为这种动物是白色的,但也可能是灰色的。
这就是说,你的观察具有某 种不确定性。 在考
虑问题时,所带有的干扰或不精确性都会导致证
据的不确定性。 目前人们用来处理不确定性的
启发式方法,在理论上应该还是不严格的,但在
实际应用中却可解决某些实际问题。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 1 关于证据不确定性
一般通过对事实赋于一个介于 0和 1之间的
系数来表示事实的不确定性。 1代表完全确定,0
代表完全不确定。 这个系数称为可信度 (也有取
可信度的范围 -1到 +1)。 当规则具有 一个以上的
条件时,就需要根据各条件的可信度来求得总条
件部分的可信度。 已有的方法有两类,
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 1 关于证据不确定性
(1) 以模糊集理论为基础的方法
按这种方法,把所有条件中最小的可信度作为总
条件的可信度。 例如,具有三个条 件的规则,对每
个证据各自的可信度分别赋于 0.9,0.5以及 1.0的可信
度。 如果从每个证 据各自的可信度得到这个规则的
总输入的可信度,取最小值就是 0.5。 产生式规则的
各个 条件之间是合取的关系,取其可信度的最小值
代表总的可信度,这也符合模糊理论。
总之,这种方法类似于,当把几根绳子连接起来
时,总的绳子的强度等于其中最差 的绳子强度。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 1 关于证据不确定性
(2) 以概率论为基础的方法
这种方法同样赋于每个证据可信度。 但当把单独条件的
可信度结合起来求总的可信 度时,它取决于各可信度的乘积。
采用上述例子,这时规则的输入部分的可信度为 0.45。
因为规则的输入部分的各个条件之间是合取关系,总的
可信度是各个分量的可信度 乘积,这看起来是符合概率理论
的。 因此这种方法称为以概率为基础的方法。 但根据概率
论,若要总的概率为各分量概率之乘积的先决条件是各分量之
间是独立的。 然而,这里并不能检验各条件之间是否相互独
立。 因此,从这点上讲,这是一种不完全合法的应 用。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 2 关于结论的不确定性
关于结论的不确定性是在规则的条件被完全满
足时,产生某种不确定的结论。 这种 结论不确定的
程度,是以赋以规则一个在 0和 1之间的系数的方法来
表示的。 例如,有以下规则,
IF 启动器发出刺耳的噪声 THEN 启动器坏的
可能性是 0.8
以上规则表示,若事实完全肯定即可信度应为
1.0; 但规则的条件部分不能完全确定,即证据的可信
度不为 1时,求结论的可信度有两种方法,
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 2 关于结论的不确定性
(1) 取结论的可信度为条件的可信度与上述系数的乘积。 例
如,如果取条件可信度为 0.5,则结论可信度 Cout=0.5× 0.8=0.4.
(2) 按照某种概率理论的解释,可以假设规则的条件部分的可
信度 Cin和其结论部分 的可信度 Cout存在某种关系,这种关系可
用来代表规则的不确定性。 下面为三种这样的关系曲线。（图
28）
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 2 关于结论的不确定性
Cout Cout Cout
↑ ↑ ↑ ↓先验值
1.0┼ 1.0┼ 1.0 ┼ - - - - - - ┊
┊
┊ ←先验值
└───┼→Cin └────┼→Cin └────┼→Cin
(a) 1.0 (b) 1.0 (c) 1.0
图 28
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 2 关于结论的不确定性
(a)所示的 Cin与 Cout的关系所代表的就是乘积方法,结论
的可信度 Cout 等于条件的可信度 Cin和某个系数的乘积 ;
(b)所示的关系即使条件这边完全确定,即 Cin=0时,结论
的可信度 Cout仍为 0.2,这意味着,即使条件这边的证据不存在,
也可以得到结论。
在大多数情况下,Cin与 Cout的关系曲线由两条直线组成,
如 ( c) 所示。 这种状况,Cin和 Cout之间的关系不仅要反映终
点的条件,而且要反映开始分析以前的估计。 这种估 计也称
为先验值,这个值说明当完全没有要处理情况的预置可信度。
例如,你要接手某问题时,你可以估计这个问题的许多方面,
当然,这是依据你的经验得出的,即赋于一定程度的可信度,。
这就是给予的先验可信度。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3.6.3 多个规则支持的同一事实的不确定性
当多个规则支持同一事实时,这些规则之间的关系是析取,
也有两种方法,
(1) 基于模糊理论的方法
取支持这个事实的各规则的可信度的最大值作为事实的
可信度,这类似于模糊集理论中当多个条件相析取时,取这些
条件中的隶属函数的最大值作为总的隶属函数值。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3.6.3 多个规则支持的同一事实的不确定性
(2) 基于概率论的方法
这里论述的只是基于概率的方法中的一种,一组规则支持
的事实的可信度,可用以下方法求得,首先把各个证据的可信
度转换成可信性比例 r。 可信性比例 r和可信度 C之间 的关系
可表示为
r=C/(1-C) 或 C=r/(r+1)
把各证据的可信性比例简单相乘就可以求得这些证据所
支持的事实的可行性比例。然后,再利用上述公式转换回相应
的可信度。这样就可求得这个事实的可信度。当 C=0.5时,相
应的 r=1,这时称为中性的可信性比例。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3.6.3 多个规则支持的同一事实的不确定性
例, C1=0.9 C2=0.25,与此相应的 r1和 r2分别为
r1=0.9/(1-0.9)=9
r2=0.25/(1-0.25)=1/3
取 r1和 r2的乘积作为这个事实的可信性比例 r
r=r1× r2=9× 1/3=3
因此相应的可信度 C为
C=r/(r+1)=3/(3+1)=0.75
这样求得的可信度为 0.75,这个数值比按以模糊集理论
为基础的方法求得的可信度 0.9低。 这是因为其中一个证据的
可信度为 0.25,这实际上是否定这个事实。 如果这个证据的可
信度大于 0.5,按这种方法求得的可信度就会大于 0.9。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3.6.3 多个规则支持的同一事实的不确定性
应用以概率论为基础的方法有以下两个困难,
(1) 按照概率论,应该检查支持同一事实的各个规则之间
是否相互独立,而实际上难以进行这样的检查。
(2) 如果有以下规则
IF 启动器发出刺耳噪声 THEN 启动器坏的可能 0.75
按概率论,意味着还存在另一条规则,
IF 启动器发出刺耳噪声 THEN 启动器好的可能 0.25
在许多问题中,不允许同时使用这样的规则。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3,6, 4 非精确推理的原理
智能系统的设计将面临两个问题,
(1) 在实际问题中,我们模拟人所处理的信息有许多是不确定的,不精
确的,不完 全知道的。只要是智能系统,一般都处在这样的设计环境中。
(2) 为了防止辅助知识和规则太多而引起组合爆炸,有意识引入非精确
推理方法。 这样,既减少了智能系统设计的复杂性,又可提高系统运行的
速度。
非精确推理用于基本规则的智能系统的核心思想是, 为原始证据和
规则本身赋于一个不确定的度量,在给出一组算法,在此基础上利用这组
算法,求出规则中的结论部分的不确定性。
非精确推理一个可采用规则为下述结构,
IF E THEN H(X)
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3,6, 4 非精确推理的原理
其中,E是证据,H是假设,X是规则的不确定因子,
或称规则强度。 证据 E和假设 H都是由命题构成的。
证据 E或者是单独例题,或者是由其它命题的逻辑组合
而生成的复合命题。假设 H有时又是其它规则的证据,
由此构成推理网络。 规则强度 X表示证据 E对 H 的影响
程度,它描述了知识的不确定性。 这一规则的含义是,
如果证据 E为真,则假设 H 为真 的程度严重地依赖规
则强度 X。 非精确推理就是根据 E的不确定性值和规则
强度 X更新假设 H的不确性值,重复上述过程,直到求
出所需假设的不确定值,从而做出判断和假设。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3,6, 4 非精确推理的原理
从上面论述可知,在非精确推理的结构中,必须包
括对证据不确定性描述,对知识不确定性描述的描述和
更新命题不确定性的算法。 此外,一个非精确推理规
则的命题不确定性描述,知识不确定性描述,更新命题
不确定性值的算法都不是随意定义的,必须 满足上下
文相关约束。
对于规则 IF E THEN H(X) 的采用,E和 H(X)的描
述和表达视具体问题而设计,并不一定是繁难的,有些
场合简单的表达描述比复杂的表达描述更有效。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3,6, 4 非精确推理的原理
举例, 在设计英语水平测试系统中,若某一部分类容采用逆
向推理。
即,若被测试者对某一深度试题回答错误,不简单定论被
测试者没有掌握这一深度内容。自动假设被 测试者还是
掌握了这一深度的内容,换一相同深度测试题再测试。 若还
不正确,就假设 被测试者水平只在较低的某一深度,继续测
试,仍不正确,再假设,再测试,直到判别出被测试者对这
一部分内容掌握清况而停止。
这一问题选用逆向推理欠妥,为了判断被测试者是否已
经掌握某一部分内容,往往要测试多次,使用大量的知识和
规则,速度慢,而且判断还不一定准确,被测试者因为不认识
一个英语单词被降低水平的情况常常出现。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3,6, 4 非精确推理的原理
对这一问题的改进可采用非精确推理,对规则强
度是这样处理的,
设测试题为 X,它由各种成分 X1X2……Xn 构成。 对每一
成分 Xi(i=1,2,…,n) 都将规定 隶属度 μ(Xi),那么,
X=μ(X1)/X1+μ(X2)/X2+…+μ(Xn)/Xn
如果测试题 X被测试者回答错误,这时不降低水平量选试题,
而是让 X分解 {X1,X2,… Xn} 让被测试者测试,根据各部分测
试清况来判断,如果 Xi又出错,还要调出与 Xi成份相同水平的试
题再测。
这种简单的非精确推理方式,不仅减少了大量辅助知识和规
则,使系统结构简化,层次分明,提高了运行速度,而且与原选用
的逆向推理方式比,测试英语水平准确性有 可能提高
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 1 处理中的分层
处理中的分层可以提高系统的运行速度,事
实上,它类似于传统程序设计的模块化技术,把
一个大问题化成若干小问题。
设计一个智能系统,应该先建立一个实验骨
架。 这个实验骨架可以不完善,甚至包含不准
确性,但它是完成目标的起点,可以得到一些具
体的实验数据,以之改进。 在这 一基础上,注意
分层,分层多少视具体情况而定,一般为三层。
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 1 处理中的分层
第一层描述问题的总体,以便化分各个子问题。 这一层即
使是实验骨架也应考虑周全,相当于科研开题报告或教学大纲。
这一层没有描述的问题,下一层是没法解决的。
第二层对每一问题进行详细描述,提出解的各种方法。 这
一层在实验系统中可以考虑不周全,将根据假设来进行各种观
测,选择最佳策略,逐步充实,修改,完善。
第三层是问题归约,对描述的问题,通 过一列变换成为子问
题集合,应用一系列算符求解,子问题的解都能得到,从而解决
了 初始问题。 显然,第三层必须是问题可解,否则系统运行以
失败告终。
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 1 处理中的分层
智能系统的分层技术,目前还应用不成熟。 在系
统设计时,人们总是希望它具有专 家的解题能力。, 于
是,在知识库中增加了大量的辅助信息,又不注意分层,
使得规则太 多,而控制推理又是基于匹配的,最后造成
系统的运行速度太慢 ---求解问题能力差。
举例,
在设计电视维修专家系统时,采用产生式规则,
把知识分成三层。
第一层, 知识和规则描述了问题的总体,无光栅,
有光栅有缺陷,无图象,无声,图象有缺陷,伴音有故
障, 显然,这些描述和规则已经表达了电视故障的全
面印象。
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 1 处理中的分层
第二层, 对每一具体问题的详细描述,这一知识
表达和制定的规则,与维修人员的 素质有关,很可能
是不全面的,但可以不断充实,修改。
第三层, 具体故障的指定,对一上一层描述的每
一问题都能按知识表达和制定的规则寻求出元件故
障。 这一级主要涉及电子技术的分析,是成熟的。
若系统不分层就直接推理匹配,由于规则过多,
经测试比分层后的系统运行速度约低六倍,可见分层
的重要性。
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 2 处理中的规则参数技巧
由于智能系统的应用和研究时间不长,不十分普及,
技术上也不成熟,所以多数设 计是基于规则的。 这主
要是规则易于模块化,简单,便于修改,扩充等优点。 然
而,这 也带来了问题,如,
某一智能系统有这样几条规则,
IF A1∧ A2∧ … ∧ Am∧ B1 THEN D1
IF A1∧ A2∧ … ∧ Am∧ B2 THEN D2
……
IF A1∧ A2∧ … ∧ Am∧ Bn THEN Dn
第 3 章 产生式系统及其搜索方法
3,7 相关技术
3, 7, 2 处理中的规则参数技巧
这 n个规则的前提中都有条件 A1∧ A2∧ … ∧ Am,
当它被匹配为真,若要判别上述任何 规则的前提是否成
立,只需判断第 m+1个条件是否为真就可以了。 但是,
智能系统的推理机是逐步匹配的,它将逐个条件重复检
查是否为真才能作作出决定。显然,这大大降低了系统
的运行速度。
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 2 处理中的规则参数技巧
如果在规则中设计参数,上述缺陷可以克服,
IF A1∧ A2∧ … ∧ Am THEN g=1
ELSE g=0
IF g∧ B1 THEN D1
IF g∧ B2 THEN D2
…
IF g∧ Bn THEN Dn
这一类问题在智能系统中出现很多,总之,如
果 规则中恰当的设计参数,有助于提高智能系统的
运行速度。 返回
人工智能与机器翻译
主讲：杨宪泽
—— 产生式系统及其搜索方法
第 3 章 产生式系统及其搜索方法
第 3 章 产生式系统及其搜索方法
3.1 产生式系统
3.2 产生式系统的搜索 (控制 )策略
3.3 图搜索算法
3.4 产生式系统的规则问题
3.5 应用举例
3.6 产生式系统的不确定性问题
3.7 系统设计技巧
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
产生式系统使用类似于文法的规则,对符号
串作替换运算。 它是智能软件中使用最普遍、最典
型的一种结构。为什么要采用产生式系统作为智能
软件的主要结构呢? 这可以有 两点理由,
(1) 用产生式系统结构求解问题的过程和人类求
解问题时的思维过程很相象,因而可以用它来模拟
人类求解问题时的思维过程 ;
(2) 可以把产生式系统作为智能软件中的基本结
构单元或基本模式看待,就好象是 积木世界中的积
木块一样,因而研究产生式系统的基本问题就具有
一般意义。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
一个智能软件用产生式系统设计的基本组
成是, 一个综合数据库 ; 一组产生式规则 ;
一个控制系统。
综合数据库是产生式系统所使用的主要数
据结构,用来表述问题的状态或有关事实。
它包含求解问题的信息,其中有些部分可以
是不变的,有些部分可能只与当前问题的解
有关。人们可以根据问题的性质,用适当的方
法来构造综合数据库的信息。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
产生式规则的一般形式为,
条件 ─→行动 或 前提 ─→结论
即表示成为, if┄┄ then┄┄ 的形式。
其中,左边确定了该规则可应用的先决条件 ; 右边
描述了应用这条规则所采取的行动或得出的结论。
一条产生式规则满足了应用的先决条件之后,就可
对综合数据库进行操作,使其发生变化。如综合数
据库代表当前状态,则应用规则后就使状态发生转
换,生成新状态。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
控制系统是软件的控制程序,也是规则的解释 (推理 )程
序。 它规定了如何选择一条 可应用的规则对数据库进行操
作,即确定了求解过程的推理路线。 当数据库满足结束条件
时,系统就应停止运行 ; 还要使系统在求解过程中记住应用
过的规则序列,以便最终能给出解的路径。
控制系统也称控制策略,它也可以是从规则集中选择规
则并作用于状态的一种广义选取函数。确定某一种策略后,
可以算法的形式给出。在建立产生式系统描述时,还要给出
初始状态和目标条件,具体说明所求解的问题。 产生式系
统中控制策略的作用就是从初始状态出发,寻求一个满足一
定条件的问题状态。 目标条件也是产生式系统结束条件的
基础。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
上述产生式系统的定义具有一般性,它可用来模拟任
一可计算过程。 在研究人类进行问题求解过程时,完全可用
一个产生式系统来模拟求解过程,及可作为描述搜索的一种有
效方法。作为智能中的一种形式体系,它还具有以下优点,
(1) 适合于模拟强数据驱动特点的智能行为。
当一些新的数据数入时,系统的行为就要改变 ;
(2) 易于添加新规则去适应新的情况,而不破
坏系统的其他部分。 这是由于产生式系统的各组成
部分具有相对的独立性,因而便于扩展和修改。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
用产生式系统来求解问题,首先必须建立起问题的产生式
系统描述,即规定出数据库、规则集合及其控制策略。这
种把一个问题的叙述转化为产生式系统的三个组成部分,
在智能技术中通常称为问题的表示。一般来说一个问题可有
多种表示方式,而选择一种较好的表示是运用智能技术解决
实际问题首先要考虑的,而且要有一定的技巧。
建立了产生式系统描述之后,通过控制策略,可求得实现
目标的一个规则序列,这就是所谓问题的解,这个解序列是
根据控制系统记住搜索目标过程中用过的所有规则而构造出
来的。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
在一般情况下,问题可能有多个解的序列,但有时会要
求得到有某些附加约束条件的解,例如要求步数最少、距离
最短等。 这些约束条件通常是用耗散或代价这一概念来概
括,这时问题可称为寻找具有最小耗散的解。
在用产生式系统求解问题时,有时引入状态空间图。状
态空间图是一个有向图,其节点可表示问题的各种状态 (综
合数据库 ),节点之间的弧线代表一些操作 (产生式规则 ),它
们可把一种状态导向另一种状态。这样建立起来的状态空间
图,描述了问题所有可能出现的状态及状态和操作之间的关
系,因而可以较直观地看出问题的解路径及其性质。当然,
只有问题空间规模较小才可能作出状态空间图。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 1 产生式系统的组成部分
建立产生式系统描述的过程,就是所谓问题的表示。对
问题表示的好坏,往往对求 解过程的效率有很大的影响。一
种较好的表示法会简化状态空间和规则集表示,此外,高
效率的问题求解过程与控制策略有关,合适的控制策略可缩
小状态空间的搜索范围,提高求解的效率。
从以上论述可知,用产生式系统来描述和求解问题,就
是在问题空间中搜索一条从初始状态到达某一个目标状态的
路径。这完全可以模拟人的求解过程,也就是可以把产生式
系统作为求解问题思考过程的一种模拟。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 2 产生式系统的基本算法
? E1,DATA←初始事实库
? E2,until DATA 满足结束条件以前,do
? E3,begin
? E4,在规则集中,选某一条可用于 DATA的规则
? E5,DATA←规则应用到 DATA得到的结果
? E6,结束
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
正向、逆向、双向产生式系统
用产生式系统求解某一问题时,如果按照规则使用的
方式或者说按推理方向来划分的话,有正向、逆向和双向产
生式系统。 正向产生式系统是从初始状态出发朝着目标状
态这个方向使用规则,即正推的方式工作,称这些规则为 F
规则 ; 若选目标状态作为初始 数据库逆向进行求解,即逆
向使用规则,产生子目标状态,反方向一步一步朝着初始
状态方向求解,整个逆推方式工作,称逆向产生式系统,
逆向应用的规则称 B规则 ; 若以双向搜索的方式 (即正向和
逆向同时进行 )去求解问题,则称为双向产生式系统。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
可交换的产生式系统
可交换式产生式系统的可交换性指几条规则的应用可
以任意交换次序而不影响求解。
一般来说,当一个产生式系统对任何一个数据库 D都
具有如下性质时,这样一个产生式系 统是可交换的。
(1) 可应用于 D的规则集合,使用了其中任意一条规则之后所生
成的任何数据库,这样一个规则集合还适用 ;
(2) 满足目标条件的某个数据库 D,当应用任何一个可应用于数
据库 D 的规则之后所 生成的任何数据库,任然满足目标条件 ;
(3) 若对 D应用某一规则序列后得到的一个数据库 D'(并能达到
解 ),当改变这些规则次序后,任然可求得解,即求得 D'与使用满足
D的可应用规则集合中的规则次序无关。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
可交换的产生式系统
例, 给定一个整数集合的初始状态 {a,b,c},设目标状态为
具有 a,b,c,ab,bc,ca这六个元素组成的集合。可应用的
规则集合为
R1,if {a,b,c} then {a,b,c,ab}
R2,if {a,b,c} then {a,b,c,bc}
R3,if {a,b,c} then {a,b,c,ca}
显然,这个产生式实例具有可交换性。
一个产生式系统具有可交换性,求解时只需搜索其中
任一条途径,只要解存在就一 定能找到目标,不必探索
多条途径,因此不可撤回的控制方式 (下节论述 ) 在这种
系统中使用很合适,因解与最初可应用的规则系列的次
序无关,系统不必提供特殊选择规则的机理 。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
可分解的产生式系统
先研究一个重写问题的产生式系统,初始数据库为
(C,B,Z),产生式规则如下,
? R1,C→(D,L)
? R2,C→(B,M)
? R3,B→(M,M)
? R4,Z→(B,B,M)
结束条件是生成只包含 M组成的数据库,即 (M,…,M) 。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
可分解的产生式系统
用图搜索方式求解这个问题时,搜索得到的部分状态
空间图见图 26。 图中只给出两条达到目标的路径和一条失
败的路径。实际搜索时有可能去探索更多的路径,往往导
致效率降低。
对于个问题,为了避免搜索多余的路径,可以将初
始数据库分解成几个可以独立加以处理的分量,分别对它
们进行求解。 即可以分别对每一个分量数据库,测试产
生式规则可以应用的条件,如此进行下去,直到分量数据
库满足某种结束条件为止。 要注意一般结 束条件应是所
有分量数据库都已满足结束条件。
第 3 章 产生式系统及其搜索方法
3, 1 产生式系统
3, 1, 3 产生式系统的类型
可分解的产生式系统
能够分解产生式系统的综合数据库和结束条件的产生
式系统称为可分解的产生式系统。一个可分解的产生式系
统,其基本算法描述 如下,
? (1) DATA:=初始数据库
? (2) {Di}:=DATA的分解式 ; 每个 Di元素都看成单独的数据库
? (3) Until {Di}的所有元素都满足结束条件之前,do:
? (4) begin
? (5) 从 {Di}中选一个不满足结束条件的 D*
? (6) 从 {Di}中删去 D*
? (7) 在规则集中选择一条可应用于 D*的规则 R
? (8) {di}:=R应用于 D*的结果
? (9) 在 {Di}上添加 di
? (10) end
第 3 章 产生式系统及其搜索方法
下图为分解方式 (C,B,Z)初态
┌──────┼──────┐
↓R2 ↓ R4 R1 ↓
(B,M,B,Z) (C,B,B,B,M) (D,L,B,Z)
↓R3 ↓R2 ↓R3
(M,M,M,B,Z) (B,M,B,B,B,M) (D,L,M,M,Z)
↓R3 ↓R3 ↓R4
(M,M,M,M,M,Z) (M,M,M,B,B,B,M) (D,L,M,M,B,B,M)
│ ┌─────┘ │
↓R4↓R3 ↓R3
(M,M,M,M,M,B,B,M) (D,L,M,M,M,B,M)
↓R3 ↓R3
(M,M,M,M,M,M,M,B,M) ─┐ (D,L,M,M,M,M,M,M,M)
R3↓目标
(M,M,M,M,M,M,M,M,M,M)
图 26
第 3 章 产生式系统及其搜索方法
3, 2 产生式系统的搜索 (控制 )策略
在 3,1, 2节的算法中,如何选择一条可应用的规则,
作用于当前的综合数据库,生成新 的状态以及记住选用的
规则序列是构成控制策略的主要内容。对大多数的智能应用
问题,所拥有的控制策略知识或信息并不足以使每次通过算
法 E4时,一下子就能选出最合适的 一条规则来,因而产生
式系统还必须把 E4扩大成搜索 (推理 )算法,以至于基本算法
的每 一循环中选一条规则试用,最终找出某一序列能产生
一个满足结束条件的数据库为止。由此可见,高效率的控制
策略需要有关被求解问题的足够知识,这样才能在搜索过程
减少盲目性,比较快的找到解路径。
第 3 章 产生式系统及其搜索方法
过去三十多年中,人们研究了许多种搜索算法,归纳起
来主要有两类, 一类是非启发 式算法 ; 另一类是启发式算法。
非启发式算法是按预定的控制策略进行搜索,在其过程中获
得的中间信息不用来改进控制策略。 由于搜索总是按预先
规定的路线进行,没有考虑问题本身的特性,所以不容易选
择到最优的搜索途径,效率较低,且出现 "组合爆炸 "的频率
高。 启发式算法是在搜索中加入了与问题有关的启发性信
息,用以指导搜索朝着最有希望的方向前进,加速问题的求
解过程并找到最优解。
3.2 产生式系统的搜索 (控制 )策略
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3, 2, 1 产生式系统控制策略分类
可分解的产生式系统
控制策略可划分为两大类,
┌不可撤回方法 ┌回溯方法
└试探性方法 ─ ┤
└图搜索方法
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3, 2, 2 不可撤回方法
这种方法相当于沿着单独一条路搜索下去,利用问题给
出的局部知识决定如何选取规则,就是说根据当前可靠的局
部知识选一条可应用规则并作用于当前综合数据库。 接着
再根据新状态继续选取规则,搜索过程一直进行,不必考虑
撤回用过的规则。 这是由于在搜索过程中如能有效利用局
部知识,即使使用了一条不理想的规则,也不妨碍下一步选
得另一条更合适的规则。这样不撤消用过的规则,并不影响
求到解,只是解序列中可能多了一些不必要的规则。显然这
种策略具有控制简单的优点。
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3, 2, 2 不可撤回方法
爬山法不仅适用于爬山问题,那些目标为极大值,搜索
过程是不断接近目标的单值问题都可应用这一方法。使用不
可撤回策略,虽然不可能对任何状态总能选得最优的规则,
但是如果应用了一条不合适的规则之后,不去撤消它并不排
除下一步应用一条合适的规则,那么只是解序列有些多余的
规则而已,求得的解不是最优解,但控制较简单。此外还应当
指出,一般很难对给定问题构造出任何情况下都能通用的爬
山函数,因而不 可撤回的方法具有一定的局限性。
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3.2.3 回溯方法
在问题求解过程中,有时会发现应用一条不合适的规则会阻扰或
拖延达到目标的过程。在这种情况下,需要有这样的控制策略, 先试一试
某一条规则,如果以后发现这条规则不合适,则允许退回去,另选一条
规则来试。回溯方法不保留完整的搜索树结构,只记住当前工作的一条
路径,回溯就是对这条路径进行修正。
使用回溯策略首要的问题要研究在什么情况下应该回溯,即要确定
回溯条件的问题。其次就是如何利用有用知识进行规则排序,以减少回
溯次数。 回溯应发生在以下三种情况,
(1) 新生成的状态在通向初始状态的路径上已出现过 ;
(2) 从初始状态开始,应用的规则数目达到所规定的数
目之后还未找到目标状态 (这一组规则的数目实际上就是
搜索深度范围所规定的 );
(3) 对当前状态,再没有可应用的规则。
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3.2.3 回溯方法
搜索深度的设置是一个值得注意的问题,设置太浅,有
可能找不到解 ; 设置太深,有可能导致回溯次数巨增。因而
应根据实际情况来规定搜索范围,先设置适中的深度搜索,
失败时再逐步加深。
回溯过程是一种可试探的方法,从形式上无论是否存
在对选择规则有用的知识,都可以采用这种策略。即如果没
有有用的知识来引导规则选取,那么规则可按任意方式 (固
定排序或随机 )选取 ; 如果有好的选择规则的知识可用,那么
用这种知识来引导规则选取,就会减少盲目性,降低回溯次
数,甚至不回溯就能找到解,总之一般来说有利于提高效率。
此外由于引入回溯机理,可以避免陷入局部极大值的情况,
继续寻找其他达到目标的路径。
第 3 章 产生式系统及其搜索方法
3.2 产生式系统的搜索 (控制 )策略
3.2.3 回溯方法
可用递归算法描述回溯策略,
YX0,选择一条新路径搜索 ;
YX1,搜索已超出规定指标 (无新路径、超时,超深度等 ),失败退出 ;
否则搜索继续 ;
YX2,搜索的状态找不到可用规则,回溯到 YX0;
YX3,搜索的状态依某种原则 (任意排列或按启发式准则 )取有用规则 ;
YX4,若规则用完未找到目标,回溯 YX0;
YX5,取头条可用规则 Ri;
YX6,删去头条规则,减少搜索中规则集长度 (注意,这不动原始规则
集 );
YX7,规则 Ri作用于当前状态,生成新状态 ;
YX8,若找到目标,成功退出 ; 若生成的 "新状态 "已出现过,回溯到
YX0;
YX9,记录新状态,对新状态递规调用 YX1～ YX7;
第 3 章 产生式系统及其搜索方法
产生式系统求解问题时,如果控制系统
保留所有规则应用后生成并链接起来的状态
记录图,则称工作在这种方式下的控制系统
使用了图搜索策略。 实际上图搜索策略是实
现从一个隐含图中,生成一部分确实含有一个
目标节点的显式表示的子图搜索过程。
3, 3 图搜索算法
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3,3, 1 一般性图搜索算法
步骤 1 G←S,OPEN←(S); 建立一个搜索图 G,它只含有
初始节点 S,建立一个 OPEN表 (今后它用于存储生成的节点 ),
开始它只含有初始节点 S。
步骤 2 CLOSED←( ); 建立一个 CLOSED表 (今后它用
于存储已扩展节点或将要扩展的某个节点 ),它的初始状态
为空表。
步骤 3 LOOP,if OPEN=( ) then return FAIL; 进入循
环。 如果 OPEN表已空,说明没有节点可扩展,就返回 FAIL,
即失败。
步骤 4 n←FIRST(OPEN),CLOSED←(n,CLOSED);
从 OPEN表中取出一个节点 n,将其 放入 CLOSED表中。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3.3.2 典型的非启发式图搜索算法分析与改进
广度优先搜索法
该方法从初始节点开始,序扩展生成下一级各子节点,
OPEN 表中已有的节点后 面 (实现先生成的子节点先扩展 ),
然后从 OPEN 表中提取最前的一个节点检查是否是目标节
点,否则再扩展,再重复上述操作。 这种方法认为同一级
各节点对问题求解的价值是同等的,因而对全部节点沿广
度进行横向扫描,按各节点生成的先后次序,先生成、先检
查、先扩展,沿广度遍历所有节点。
这种方法只要问题有解,即若树图上存在目标节点,
经搜索一定能找到。 所以,广度优先搜索法是完备的,是一
种推理算法。 但是,在问题大节点多,且目标节点距离初
始节点较远时将会产生许多无用节点,搜索效率低,还可能
产生组合爆炸。 因此,这种方法较适宜问题不大的环境中
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3.3.2 典型的非启发式图搜索算法分析与改进
深度优先搜索法
该方法从初始节点开始,顺序扩展生成下一级各子节点,放在
OPEN表中已有的节点前面 (实现后生成的子节点先扩展 ),然后从
OPEN 表中提取最前的一个节点检查是否是目标节点,否则再扩
展,再重复上述操作。 这种方法每一次扩展最晚生成的子节点,
沿着最晚生成的子节点分支,逐级纵向深入发展。
这种方法搜索一旦进入某个分支,就将沿着该分支一直向下搜
索。 如果目标节点恰 好在此分支上,则可较快地得到解。 但是,
如果目标节点不在此分支上,不回溯就不可能得到解。 所以,深
度优先搜索是不完备的,只是推理步骤。 如果回溯,不难证明其平
均效率与广度优先搜索法相同。 因此,深度优先搜索法如果没有
启发信息,很难有实用价值。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3.3.2 典型的非启发式图搜索算法分析与改进
代价驱动搜索法
该方法考虑了从一个节点经过一条支路,转移到另一个节点时所需
要支付的代价,如费用、时间等。 该方法从初始节点开始,扩展生成下
一级各子节点,这些子节点中若没有目标节点需再扩展搜索。 把它们放
进 OPEN表中,依据初始节点到它们各自所付出的代价 大小进行排序,代
价小的节点放在前面扩展,周而复始重复上述操作,直至找到目标节点
为止。
这种方法根据各条支路所需支付的代价有差别,所以具有同样路径
长度 ( 所经过的支路数 )的搜索过程,其搜索代价 (所支付的总代价 )可能
不同,优选最小代价的搜索路径,进行推理求解问题。 代价驱动搜索无
论在理论研究方面还是实际应用方面都很有前景,例如最短路径问题。
进一步的研究认为最短路径问题的改进应为以下几点,
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3.3.2 典型的非启发式图搜索算法分析与改进
代价驱动搜索法
1) OPEN表的节点排序问题,特别是在问题节点多达成千上万时尤
为重要,这一排序应采用映射排序,它是一个基于地址计算的排序,在
预置路径最大代价 dmax后,开辟一个数组 P(dmax),就可把节点送入其
值与 P数组下标相等的对应元素中,显然 di=50它对应 P(50); dj=500,对
应 P(500)。 相同代价值的节点落在同一数组元素中,用计数方式 可知有
几个。 由于数组元素是有序的,500>50,数组元素的下标自然把节点
一次定好了位置,排序即完成。 这一排序的时间复杂性为 O(N),对于
OPEN表面临的无数次排序操作,极大的提高了效率,
2) 搜索过程中,如果到达某一节点的代价 ≥任一初始节点到目标节
点的路径代价,这一节点的路径删去。
3) 搜索过程中,如果同时出现了两条到达某一节点的路径,代价大
的那条路径即时删去。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
搜索过程中,如果在确定扩展那一个节点时能充分利
用与问题求解有关的特性信息,就可以估计出节点的重
要性,就能使搜索选择重要性较高的节点,以利于求得
最优解。 象这样 就可用于指导搜索过程,且与具体问
题求解有关的控制性信息称为启发性信息。 启发性信息
可以用于估价节点重要性,表示为函数形式,
f(x)=g(x)+h(x)
其中,g(x)为初始节点 S。到节点 x已经付出的代价 ;
h(x)是从节点 x到目标节点 Sg的最优 路径的估计代价,它
体现了问题的启发性信息,其形式根据问题的特性确定。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法
如果对一般性图搜索算法作以下限制,则它成为 A*算法,
(1) OPEN表中的节点按估价函数 f(x)=g(x)+h(x) 的值
从小至大进行排序,
(2) g(x)是到目前为止,从 S。到 x的一条最小耗散值路
径的耗散值,是作为从 S。到 x 最小耗散值路径的耗散值
g*(x)的估计值,g(x)>0。
(3) h(x)是 h*(x)的下界,即对所有 x均有 h(x)≤h*(x)。 而
h*(x)是从节点 x到目标节点的最小代价,若有多个目标节点,
则为其中最小的一个。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 1 对于有限图,A*算法一定会在有限
步内终止,
证明,对于有限图,其节点个数是有限的,
A* 算法在经过若干次循环后会出现两种情
况, 或者搜索到目标节点在步骤 5结束 ; 或
者 OPEN表中的节点被取完在步骤 3结束。
不 管那种情况,A*算法都在有限步内终止。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 2 对于无限图,只要从初始节点到目标节点有路径存在,A*算法
也必然终止。
证明, 分两步, 第一步证明 A*算法结束前,OPEN表中存在节点 x‘,它
是最优路径上 的一个节点,且满足 f(x')≤f*(s).。
设最优路径是 S。 x1,x2,…,S*g
由于 A*算法中的 h(x)满足 h(x)≤h*(x)
所以 f(s0),f(x1),f(x2),…,f(xm) 均不大于 f(sg*)=f*(s0).
又因为 A*算法是广度代价择优,所以在它结束之前,OPEN表中一
定含有 S。 x1,x2,…,S*g 中的一些节点,设 x'是其中最前面的一个,
则它必然满足 f(x')≤f*(S0)
至此,第一步证明结束 ;
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 2 对于无限图,只要从初始节点到目标节点有路径存在,A*算法
也必然终止。
第二步证明：用反证法,假设 A*算法不终止,并设 e是图中各条边的最
小代价,d*(xn )是从 S。到节点 xn的最短路径长度,则显然有
g*(xn)≥d*(xn)× e
又因为 g(xn)≥g*(xn)
所以有 g(xn)≥d*(xn)× e
再因 h(xn)≥0,f(xn)≥g(xn)
故得到 f(xn)≥d*(xn)× e
由于 A*算法不终止,随着搜索的进行,d*(xn)会无限增大,从而使
f(xn)也无限增大。 这与第一步证明得出的结论矛盾,因对可解状
态空间来说,f*(s0)一定是有限值。
所以,只要从初始节点到目标节点有路径存在,即使对于无限图,
A* 算法也一定会终止。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 3 A*算法一定终止在最佳路径上
证明, 假设 A*算法不是在最优路径上终止,而是在
某个目标节点 t处终止,则 f(t)=g(t)>f*(s0)。但是由
性质 2证明可知,在 A*算法结束之前,OPEN表中
存在着节点 x‘,它应该在最优路径上,且满足
f(x')≤f*(s0) 此时,A *算法一定会选择 x'来扩展
而不会选择 t,这就与假设矛盾,所以,A*算法
一定会终止在最优路径上。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 4 A*算法是最优的
证明, A*算法的搜索效率很大程度上取决 h(x),在满足
h(x)≤h*(x)的前提下,h(x)的值越大越好。 h(x)值越大,
表明它携带的启发信息越多,搜索时扩展的节点数越
少,搜索的效率越高。
设 f1(x)与 f2(x)是对同一问题的两个估价函数
f1(x)=g1(x)+h1(x)
f2(x)=g2(x)+h2(x)
A1*和 A2*分别是以 f1(x)及 f2(x)为估价函数的 A*算法,
且对于所有的非目标节点 x均有 h1(x)<h2(x)。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 4 A*算法是最优的
证明（接前页 ),此情况下证明 A1*扩展的节点数不会
比 A*2扩展的节点数少,用归纳法,
设 K表示搜索树的深度
当 K=0时,结论显然成立 ;
设当搜索树的深度为 K-1时结论成立,即 A*2扩展了的节
点,A*1也扩展了 ;
现仅证明 A*2扩展的第 K代的任一节点 xk也被 A*1扩展,
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法几个重要性质,
性质 4 A*算法是最优的
证明（接前页 ),由假设可知,A*2扩展的前 K-1代节点 A*1也都扩
展了,因此 A1* 搜索树中有一条从初始节点 S。到 xk的路径,其费用不
会比 A*2搜索树从 S。到 xk的费用更大。 即 g1(xk)≤g2(xk)
假设 A*1不扩展节点 xk,这表示 A* 1能找到另一个具有更小估价值
的节点进行扩展并找到最优解,
此时有 f1(xk)≥f*(S0) 即 g1(xk)+h1(xk)≥f*(S0)
应用关系式 g1(xk)≤g2(xk)到上列不等式中,得 h1(xk)≥f*(S0)-
g2(xk),
由于 h2(xk)=f*(S0)-g2(xk),这就得到 h1(xk)≥h2(xk)
这与最初的假设 h1(x)<h2(x)相矛盾 证毕。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法的改进
改进 1 OPEN表中自始至终的排序,采用 3.3.2.3
节中介绍的映射方法。
改进 2 h(x)单调限制, A*算法中,每当扩展一
个节点时都要检查其子节点是否已在 OPEN表或
CLOSED表中,有时还需调整指向父节点的指针,
这就增加了搜索代价。 如果对启发函数 h(x)单调限
制,可减少检查和调整的工作量,从而提高搜索效率。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法的改进
所谓单调限制 h(x)应满足两个条件,
(1) h(Sg)=0
(2) 设 xj是节点 xi的任一子节点,则有 h(xi)-
h(xj)≤c(xi,xj)
其中,Sg是目标节点 ; c(xi,xj)是节点 xi到其子节
点 xj的边代价。
若把上式改写 h(xi)≤h(xj)+c(xi,xj),可看出节点
xi到目标节点的估价不会超过 x i 到其子节点 xj边
代价加从 xj到目标节点的估价。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法的改进
当 A*算法的启发函数 h(x)满足单调限制时,可得出以下
两个结论,
(1) 若 A*算法选择节点 xn进行扩展,则 g(xn)=g*(xn)
(2) 由 A*算法所扩展的节点序列其 f值是非递减的。
这两个结论都是在 h(x)满足单调限制时才成立, 对于第 2
个结论,当 h(x)不满足单调 限制时,有可能某个要扩展
的节点比以前扩展的节点具有较小的 f值,
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法的改进
改进 3 引入感兴趣集的算法, 这一改进的思路是
这样的,问题求解时,人们往往知道最佳路径上有关节
点的某些启发信息。 例如,在求城市 A到城市 B的最
佳路径时,人们往往凭自己的经验断定所要求的最佳
路径必经城市 C和城市 H,这里我们称 {C,H} 是感兴 趣
集合。 若知道感兴趣集且启发式搜索算法恰当地应用
感兴趣集,则肯定可以改善算法的搜索效率。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
A*算法的改进
算法的改进使用 OPEN1和 OPEN2,CLOSED1和
CLOSED2四个表,对任一节点 x,若从 s 到节点 x的当前
路径中不含感兴趣集中的节点,则 x放入 OPEN1中 ; 否
则放入 OPEN2中。 选择 节点扩展时,首先扩展
OPEN2中的节点,因为 OPEN2中含有感兴趣集中的节
点,可能比 OPEN1中的节点更有希望在最佳路径上,
而且所扩展的节点数目总不会多于原算法。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
讨论 (1)
启发式搜索算法在大问题中一般优于非启发
式搜索算法,因此,有效地分析利用启发信息尤为
重要。 含有启发信息的评价函数可写成下列形式,
f(x)=v·g(x)+w·h(x)
其中,v,w为权系数且 ≥0,当 w↑,强调启发信息,
搜索过程沿最有希望的方向进行,效率肯定高,但
降低了完备性 ; 当 v↑,强调历史信息,搜索过程沿横
向扫描,有利于完 备性,但降低了搜索效率。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 3 典型的启发式搜索算法分析与改进
讨论 (2)
根据启发信息,可将复杂的、规模大的问题分解为简
单的规模小的若干子问题。 那么各子问题的搜索过程
A1,A2,…,An 是完备的,则搜索过程 A也是完备的。
A=A1∩A2∩…∩An
根据启发信息,可将原始的问题进行同构或同态的等价
变换,转换为若干等价问题。 那么等价问题的搜索过程
A1,A2,…,An 是完备的,则搜索过程 A也是完备的。
A=A1∪ A2∪ … ∪ An.
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 4 AND/OR图搜索算法
上节探讨的算法具有重要的意义。 但对于复杂的
问题,它们并不是唯一的途径,若利用它们直接求解往
往还比较困难。 AND/OR 图算法是用于表示问题及
其求解过程的又一 种形式化方法。
定义 1 AND图及 AND图算法把 一个复杂的问题
分解成若干个较为简单的子问题,每个子问题又可继
续分解为更为简单的子问题,重复此过程,直到不需要
再分解或者不能再分解为止。 这个分解图是与图,根
据这个图对每个子问题分别求解,然后把这些解合并
起来得到原问题解的过程是 AND图算法。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 4 AND/OR图搜索算法
定义 2 OR图及 OR图算法把 一个复杂问题利用同
构或同态的等价变换,使之成为若干个较容易求解的
新问题。 这个变换图是 OR图,根据这个图对新问题
求解,当且仅当新问 题有一个可解,就得到原问题的
解的解过程是 AO图算法。
定义 3 可解节点 在 AND/OR图中,满足下列条件
之一者为可解节点,
(1) 它是一个终止节点,
(2) 它是一个 OR节点,且子节点中至少有一个是可解节
点,
(3) 它是一个 AND节点,且其子节点全部是可解节点。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 4 AND/OR图搜索算法
定义 4 不可解节点 定义 3中三个条件全部不满足
的节点称为不可解节点。
下面分析 AND/OR图 AO*搜索算法,作一些改进探讨 ;
探讨类比搜索方法,为此,我们首先给出 AND/OR图的一般
搜索过程,
(1) 把原始问题作为初始节点,并作为当前节点。
(2) 应用分解或等价变换算符对当前节点进行扩展。
(3) 为每个子节点设置指向父节点的指针。
(4) 选择合适的子节点作为当前节点,反复执行 (2)和 (3),
直至找到可解节点或不可解节点为止。
下班可解或不可解的搜索过程都是至上而下的。 如果
确定某个节点是可解节点,则不可 解的后裔节点不再有用,
可从搜索图中删去 ; 同样,如果确定某个节点是不可解节点,
则全部后裔节点都不在有用,也可从搜索图中删去。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
定义
定义 5 设 AND/OR图 G,则从节点 n到一立即可解的叶
节点集合 N的一解图 G'定义为,
(1) G'是 G的子图 ;
(2) 若节点 n是集合 N中的元素,则 G'是由单一节点 n组
成的 ;
(3) 若节点 n有一个指向节点 {n1,n2,…,nk} 的 k-连接
符,使得从每个后继节点 ni到集合 N有一个解图 (i=1,2,…,
k),则 G'由节点 n,k-连接符、节点 {n1,n2,…,nk } 以及从
{n1,n2,…,nk} 中的每个节点到集合 N的解图组成。
(4) 否则,从节点 n到集合 N不存在解图。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
定义
定义 6 从 AND/OR图任意节点 n到一立即可解
的叶节点集合 N的解图耗散值 k(n,N) 可递归地定义
为：
(1) 若节点 n是集合 N中的元素,则 k(n,N)=0;
(2) 否则,节点 n 有一 个通到解图中后继节点集
合 {n1,n2,…,ni} 的连接符, 令该连接符的耗散值为
Cn,则
k(n,N)=Cn+k(n1,N)+k(n2,N)+…+k(ni,N)
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
定义
定义 7 AND/OR图求解中,从起始节点到一可解叶节点
集合具有最小耗散值的一个解 图称为最佳解图。 令函数
h*(n)表示从 AND/OR图中的节点 n 到一可解的叶节点集合的
最佳 解图的耗散值 ; 启发式估价函数 h(n)是 h*(n)的估计。
定义 8 若启发式估价函数 h满足单调限制,即对
AND/OR图中任意节点 n及其适用于 n的任一 k-连接符,有
h(n)≤Ck+h(n1)+…+h(nk)
其中,Ck为 k-连接符的耗散值,n1,n2,…,nk 是应用 k- 连接
符于节点 n所得的全部后继节点。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
AO*算法
A1,建立一个搜索图 G,G:=s,计算 q(s)=h(s),IF GOAL(s) THEN
M(s,SOLVED);开始时图 G只包含 s,耗散值估计为 h(s),若 s是终节点,则标
记能解,
A2,Until s已标记上 SOLVED,do,
A3,begin
A4,G':=FIND(G); 根据连接符标记 (指针 )找出一个待扩展的局部解
图 G'.
A5,n:=G'中的任一非终节点 ; 选一个非终节点作为当前节点,
A6,EXPAND(n),生成子节点集 {nj},G:=ADD({nj},G),计算
q(nj)=h(nj),其中 nj∈ G,IF GOAL(nj) THEN M(nj,SOLVED); 把 n的子
节点添加到 G中,对 G中未出现的子节点 计算耗散值,若有终节点则加能
解标记,
A7,S:={n}; 建立含 n的单一节点集合 S.
A8,Until S 为空,do
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
AO*算法 (接前页 )
A9,begin
A10,REMOVE (m,S),mc∈ {S}; 这个 m的子节点 mc应不在 S中,
A11,(1) 修改 m的耗散值 q(m):
对 m指向节点集 {n1i,n2i,…,nki} 的每一个连接符 i分别计算 qi,
qi(m)=Ci+q(n1i)+…+q(nki),
q(m):=min qi(m); 对 m个的 i个连接符,取计算结果最小的那个
耗散值为 q(m).
(2) 加指针到 min qi(m)的连接符上,或把指针修改到 min qi(m)的
连接符上,即原来指针与新确定的不一致时应删去,
(3) IF M(nji,SOLVED) THEN M(m,SOLVED); 若该连接符的所
有子节点都是能解的,则 m也标上能解,
A12,IF M(m,SOLVED)∨ (q(m)≠q0(m)) THEN ADD(ma,S); m能解
或修正的耗散值与原先估算 q0不同,则把 m的所有先辈节点 ma添加到 S中,
A13,end
A14,end
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
分析与改进
算法 AO*可以理解为两个主要运算, A1～ A6,完成自上而下的图生成,
通过有标记的 连接符,寻找最好的局部解图,然后对其中一个非终节点进
行扩展,并对其后继节点赋 给耗散值 ; A7～ A12,完成自下而上的耗
散值修正、连接符标记和节点的能解标记。
(1) 耗散值的修正从刚被扩展的节点 n开始,其修正耗散值 q(n)取估计
h*(n) 的所有值中最小的一个,然后根据耗散值递归计算公式逐级向上修
正先辈节点的耗散值,只有下层节点耗散值修正后,才可能影响上一层节
点的耗散值,因此必须自底向上一直修正 到初始节点。
(2) 在 A6中扩展节点 n时,若不存在后继节点 (即限入死胡同 ),则可
在 A11中对 m(即 n) 赋一个高的 q值,这个高的 q值会依次传递到 s,使得
含有节点 n的子图具有高的 q(s),从而排除了被当作后选局部解图的可能
性。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 5 AO*搜索算法分析与改进
分析与改进
(3) A5中怎样选 G'中的一个非终节点扩展值得研究, 一般
可以选一个最可能导致该局部解图耗散值发生较大变化的那
个节点先扩展,因为选这个节点先扩展,会促使及时修改局
部解图的标记。
(4) 与 3.3.3.2节 A算法类似,应让 h(n)满足单调限制条件,这
样,当 h(n)≤h*(n) 则 AO* 一定能找到最佳解图。 当 h(n)≡0时,
AO*成宽度优先算法。
(5) AO*中评价函数只考虑 h(n)分量,计算 g没有必要也
不可能。 其次由于 k- 连接符 连接的有关子节点,对于父节
点能解与否以及耗散值都有影响,因而不能象 A算法那样优
先扩展其中具有最小耗散值的节点。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 6 类比搜索方法探讨
构思
在 AO*和 A算法中,所使用的启发信息大多是人们依据具体领域问题靠
经验总结得来的,启发信息获取十分困难,且精确性和可靠性也难以保证。
此外,搜索算法一般执行一次性搜索,将同一问题的多次搜索视为彼此独
立、毫无相关的过程。 每次求解问题时,面临的都是全新的搜索图,即使
求解的是相同问题,算法仍然从零开始,这显然与人类求解问题的方式不
符。 人类求解问题的一个重要特点,就是常常利用以前求解相同 或相似问
题的经验来指导新问题的求解。 这实际上是一种类比学习机制,如果将这种
机制引入搜索算法,则多次搜索被看成相互关联的过程,前面搜索积累的
经验将有助于提高后 面搜索的效率。 即,利用类比获得与新问题相似的过
去问题的求解过程,作为启发信息来指导新问题的求解,这样可以缩小搜
索范围,降低问题求解的复杂性。 也就是说,如果算法设计恰当,可以自
动获得启发信息。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 6 类比搜索方法探讨
方法探讨
AO*,A及其它算法在问题的求解过程中利用与该问题
相关的启发信息来帮助搜索,启发信息通常被用于三种情况,
(1) 帮助确定扩展节点。
(2) 在扩展节点的过程中,帮助决定产生后继节点。
(3) 在扩展节点的过程中,决定那些节点可从搜索树上
删除。值得注意的是,启发信息是一种局部信息,只在搜索
路径的每个节点上为选择操作提供参考。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 6 类比搜索方法探讨
方法探讨
类比搜索方法把类比推理技术与状态空间的启发式搜索
相结合,实际上是对人类求 解问题、积累经验和增加求解问
题能力的一种模拟。 要实现它,需要解决如下一些主要问题,
(1) 如何积累问题求解的经验,即在一个问题的求解过
程中,需要记录那些有用信息。
(2) 如何定义和判断两个问题的求解情况是相似的,如
何高效的进行检索。
(3) 如何有效地使用类比结论,即相似的过去问题的
求解经验,作为特殊的启发信息指导新问题的求解。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 6 类比搜索方法探讨
方法探讨
基于上述几点,需要建立一个类比的启发式搜索求解模型。 它主要包括
生成求解事例、检索及指导求解三个推理过程。类比搜索方法在每次求解一
个新问题时,不是直接去搜索给定的状态空间,而是首先在求解事例库中检索,
查找与该问题相似的过去问题的求解事例。 若存在相似问题的求解事例,则
以此作为启发信息,指导该问题的求解。 具体地说,就是在新问题的求解过
程中,对过去问题的求解事例中记录的成功搜索路径上每个操作的依据条件
重新测试, 如果依据条件仍满足,则算法根随成功的求解路径。 否则,对
原求解过程进行改写,形成的新问题求解过程作为一个新事例存储在事例库
中,以便指导将来相似问题的求解。 过去问题与新问题的相似性越高,求解
过程需要的搜索就越少。 在最理想的情况下,甚至不需要搜索。 当没有检索
到一个与新问题相似的过去问题的求解事例时,则使用 A*或 AO*等算法进行,
并在获得解时将求解过程作为一个求 解事例存储在事例库中。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 6 类比搜索方法探讨
方法探讨
系统最初使用时,由于事例库中缺少求解事例,
只有使用 A*或 AO*等算法。 随着求解次数的增加,
求解事例将不断积累,类比的资料增多 (启发信息增
多 ),从而使求解问题 的效率不断提高。
由此可知,类比搜索方法的特点是, 类比启发
信息不仅包含了局部信息,而且提供了指导求解的
搜索方向,这样就可以将一个庞大空间的搜索压缩
为对一个或数个很小空间的搜索,极大地提高了求
解效率。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 7 讨论
用 AND/OR图算法求解问题时,求解过程就是对一
个隐含的 AND/OR图进行搜索。 初始数据库对应于
AND/OR图的根节点,规则对应于 k-连接符,结束条
件的数据库对应于一组 终节点集合,搜索算法的任务就
是找到从初始节点到一组终节点集的一个解图。
AND/OR图的启发式搜索算法 AO*是通过评价函
数 f(n)=h(n)来引导搜索过程,适用于分解得到的子问题
不存在相互作用的情况。若 S→N集存在解图,当
h(n)≤h*(n)且 h(n) 满足单调限制条件时,AO*算法一定
能找到最佳解图,在这种情况下,AO*具有可采纳性。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 7 讨论
类比搜索方法实施的关键技术在于生成求解事例、相似性度量和检索、
以及指导求 解。 生成求解事例就是积累问题的求解经验,其生成过程主要
解决的问题是对于一个 求解事例需要记录和保存问题求解过程中的那些特
征信息,以及如何进行表示,抽取和存储 这些信息。 求解一个复杂问题时,
经常面临庞大的搜索。 大量被搜索的节点中,有成功的、也有失败的。 为
了给相似问题的求解提供有用信息,就要确定保存搜索过程中的哪些有用特
征信息。显然,走两个极端最简单, 第 一是记下整个搜索过程 ; 第二是只记
问题的最终解。 这两个极端都不圆满,具体地作法除了保留问题的最终解
外,还应该记录有关选择这 些操作的情境和依据条件。 这是一个很有意义
的研究课题。 相似性的度量也是类比搜 索方法的一个关键问题。 相似程度
越高,度量方法恰当,相似问题的检索俞易获得。 关于这方面,目前还是
主要根据新、老问题的特征和关系来确定它们之间的相似性。 此外,还可设
置相似度阀值,检索采用直接映射式方法。
第 3 章 产生式系统及其搜索方法
3, 3 图搜索算法
3, 3, 7 讨论
指导求解是类比搜索方法的控制程序,主要考虑灵活的处理
策略。 一般要考虑以下 几点,
(1) 当检索没有类比启发信息时,程序能转向常规搜索方
法。
(2) 当检索到一个与新问题完全相似的过去问题的求解
事例时,程序能直接转换解。
(3) 当检索到一个与新问题部分相似的过去问题的求解
事例时,程序能提取相似部 分解过程,还能组织部分搜索、
衔接新的解过程。 此外,应有裁剪过去问题多余解过程 的
功能。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 1 规则不一致原因及解决方法
规则集中存在的不一致是影响系统性能的重要因
素之一。系统建立初期,由于规则集较小,内容也比
较简单,设计人员能对每一条规则的条件和结论部分反
复推敲和精心 构造,这类问题容易防止。但随着时间
的推移,新的规则不断加入,规则集合越来越大,内
容也越来越丰富,这时规则间的相互影响和相互联系
就随之变得复杂。在此情况下,规则的不一致就将自
然产生,当然,对它的认识和解决也就显得很重要。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 1 规则不一致原因及解决方法
主要的不一致规则种类
(1) 循环规则, 由数个规则的前提和结论形成一个循环链,
最终由末尾规则的结果 子句推出起始规则的前提部分 ;
(2) 冲突规则, 两个规则的前提条件等价,但一个或多个结
果子句有矛盾或者前提 子句有矛盾而结论部分完全等价 ; 也
有可能由多条规则链形成冲突规则集 ;
(3) 冗余规则, 两个规则的前提条件等价,一个或多个子结
果子句也等价 ;
(4) 从属规则, 两个规则有相同的结果,但其中一个包含有
多余的约束条件。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 1 规则不一致原因及解决方法
不一致规则的检查解决方法
(1) 对于循环规则,可构造规则集的 IF---THEN图,从起始规则的
条件部分开始搜索,如果搜索过程中遇到的 THEN部分已在前面出现,
就可以 中断搜索,规则集中包含的循环规则子集合需设计人员检查,解
决 ;
(2) 对于冲突规则,构造 IF---IF表,对规则集内有相同的 IF 规则子句
构造规则树,形成推理图。同时建立 THEN---THEN表用以判断是否有
冲突规则出现。 对相同 IF部分的规则继续用它的各自 THEN部分作为其
它可以匹配的 IF前提条件,递归地构造,如发现两个推理图上分别有节点
在 THEN---THEN表上是矛盾的,则检测出冲突规则,人工予以解决。
(3) 对冗余规则和从属规则的检查类似于冲突规则链的方法, 不同
之处是前者在推理图中的遍历是试图发现有 THEN部分等价的两条规则。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法原则
依赖规则：如果 Ri的结论部份包含有 Rj的条件部份，则
Rj是一个依赖规则，即 Rj 依 赖规则 Ri，或称 Ri是一个被依
赖规则。
优先规则, 如果 Ri被 Pi个其它规则所依赖次数 pi越大,Ri
被援引的可能性越大。
静态规则排列：亦是在原文分析、原文译文转换、译文
生成之前,对规则集中已有 的规则按优先次序排列。
动态规则排列：这相当于自学习能力，即某些句子分析、
转换、生成时,会增加一 条或几条规则。这些规则有可能
还与未完成的其它语句有关。因此,在对其它语句和完成
速度影晌不大的情况下，同时再排列规则称之为动态规则排
列。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法原则
映射排列：是一个基于地址计算的排序。例如，求出上
述 Pi(i=1,2,...,N）的最大值后，若开辟一个数组 D
（ Pmax）,就可把数据送入数据值下标相等的对应元素中。
显然 Pi=50，对应 D(50); Pj=500,对应 D(500)。相同数据落在
同一数组元素中,用计数方式可知有几个。由于数组元素
是有序的,500>50,数组元素的下标自然把数据一次定好
位置，最后只要按规定的方式调非零元秦，相同元素按计数
值次数调动，排序即完成。
枚举计数：如果规则 Ri被规则 Rj依赖 (j=1,2,...,N)，则
Pi=pi+1（ Pi初值赋 1) 。 显然，对于 N条规则，每一条都将
确定与其它规则的依赖关系并计算，这一过程称之为枚举计
数。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
静态算法（上）
B1,[初始化 ]，有 N条规则，置 P1至 PN皆为 1。
B2:〔 对 i循环 〕 对 i=N,N— 1,N-2,…, 2执行 B3;
然后转 B5。
B3:〔 对 j循环 〕 对 j=i-1,i-2,…, 1执行 B4; 然后转
B2。
B4:〔 寻求 Ri被 Rj依赖次数 〕 若 Ri被 Rj依赖，
Pi←Pi＋ 1；否则转 B3。
B5,一遍扫描 Pi（ i=1,2,...,N)，求 Pmax。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
静态算法（上）
静态算法进行到这里，求出了任一规则 Ri被依赖次
数 Pi。 Pi对应于 Ri，相当于 Ri 被 依赖次数 Pi。 Pi对
应 Ri，相当于 Ri的关键字。其中，很可能出现 Pi=Pj
(i≠j),这说明 Ri和 Rj被其它规则依赖的条数相同。怎样
快速地按关键字 Pi(i=1,2,...,N) 大小把规 则快速地排
列起来，并满足动态需要，我们采用高效算法 —— 映射
排序
算法初始按关键字值以映射关系作一次扫描，基本
排定规则位置,Ri→Pi→D（ Pi）。 对相同关键字的处
理，算法附加了三个数组空间：每一记录的链指针空间
L（ i）,链首指针空间 Q，链当前指针空间 W。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
静态算法（上）
关键字值 Pi与 D数组元素下标映射关系有一次时,D(Pi)=1；这
时 Q(Pi)←1，记录了具 有这唯一对应关系 Pi所在规则的地址 i，并
作为最后排序调整位置的首地址。 W（ Pi） ←i 为出现相同关键字
提供链接地址作准备。
映射时出现相同关键字，如 Pi=Pj，这时 D（ Pi） >1，我们把
Pi和 Pj 对应的两条规则 链接起来，入口地址仍是 Q（ Pi） =i，但 L
（ W（ Pi）） ←j，相当于 L(i)=j,此外,W（ Pj） ←j，为链接出现
多个相同关键字作准备。
实施映射和链接处理后，最后再实施一次扫描，根据 D数组下
标值的有序性,D=0 不实施操作,D≥l从相对应的 Q数组下标值作
为入口地址调整一次规则位置即完成排列。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
静态算法（下）
B6,[映射初始化，开辟链指针空间 L，容量 N; 映
射计数空间 D，链首指针空间 Q，链当前指针空间 W，
容量均为 Dmax，赋初值 i=1。
B7,扫描 Pi，让 D（ Pi） ←D（ Pi）＋ 1 ；以映射关
系确定 Pi的位置，记录相同 Pi 的 个数。
B8：若 D(Pi)=1，作 W(Pi)←i和 Q(Pi)←i，转 B10。
B9,若 D（ Pi） >1，作 L（ W（ Pi）） ←i和 W(Pi)←i。
B10,i←i+1，直至 i=N为止，实施 B7～ B9。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
静态算法（下）
B11:（ Z=1)，从 J=Dmax开始，若 D（ J） =0转 B12;
D（ J） ≠0，作递减排列。
(1) T←Q（ J）；链首指针送 T。
(2) 输出 RT。
(3) z←z ＋ 1，若 Z≠D(J),T←L（ T）后转 (2)；否
则转 B12。
B12,J←J-1，实施 B11，直至 J=0结束。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
动态算法
规则匹配过程中，如果系统自学习新增一条规则
RN+1，将立即置人规则集适当位置，自动启动的算法
是：
C1：对 i=1,2,...,N，若 RN+1被 Ri依赖，
PN+1←PN+1+l（ PN+1初值赋 1）；反之,若 Ri被
RN+1依赖,Pi←Pi+1。
C2：若 PN+1>Pmax,Pmax←PN＋ 1
C3，调静态算法（下），其中修改 N←N + 1。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
算法分析
1）静态算法（上）时间复杂性为 O（ N2），因为
B1～ B5执行步骤共需
(N-1)+(N-2)+...+2+1+N=1/2(N2+N)。
2）静态算法（下）时间复杂性为 O（ N），因为算法
的构思来源于映射排序算法中的一 部份，其证明可参
阅书末文献。由于动态算法仅 C1一 C2引进附加操作，
显然为 O(N),C3为 O(N)，所以动态算法时间复杂性为
O(N)
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
算法分析
3）由于静态算法（下）附加存储空间 3Pmax+N，因
此,动态算法获得的高效率是由空间代 价换取的。
4） 算法假设了规则自身依赖，所以 Pi的初值赋 1。
5) 算法将规则优先排列，使规则匹配花费平均时间
最小。平均时间最小亦说明，一 般状况下，分折的句
子越多，其效率越高；但也可能存在某些状况,所需
规则恰好排列在最后。所以，这一算法是平均时间较优
算法。
第 3 章 产生式系统及其搜索方法
3, 4 产生式系统的规则问题
3, 4, 2 规则排序算法
排序算法描述与分析
实验结果
排序算法的实验是这样进行的，在上述规则集中，
分析 4条语句。设计第 1 条语句产 生 1条规则，该规则 2、
3,4条语句都将涉及。把这条规则分别放于最后和进行
动态排列，结果后者完成 2,3,4条语句分析较前者速
度提高 1倍多。这是一个目前具有 3380条规则的 实验系
统，有如此实验效果足以说明此算法的实用性。
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
任何一种自然语言,总是要遵循一定的语法规则
的,计算机要理解、翻译自然语言,就要对理解和翻
译的语言建立一套规则,也就是语法,并且提供一种
适合计算机处理的语法描述形式。上下文无关语法
是适合描述自然语言的一种体系。作为一个例子,
先来考察汉语的一个很小子集,它的上下文无关语
法由以下一系列重写规则组成,
(1) <一种句子结构 >→<名词 ><动词 ><数词 ><名词 >
(2) <名词 >→电脑 │学院 │中国 │地图 │卫星 │…
(3) <动词 >→购买 │绘制 │发射 │…
(4) <数词 >→一颗 │十台 │一幅 │…
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
在这些重写规则中,尖括号称之为非终极符 ; 而
电脑、学院 … 称终极符 ;竖线 "│"表示或的意思。这
种语法之所以是上下文无关的,是因为在这些重写
规则中,左边项都是孤立的非终极符,它们可以被右
边的符号串所替换,而不管左边出现的上下文。
这种语法既可用于生成语法正确的汉语句子,也
可用于分析输入的汉语句子是否合乎语法。
下面三例计算机可以简单验证是正确的句子,
1> 中国发射一颗卫星
2> 学院购买十台电脑
3> 电脑绘制一幅地图
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
即 一种句子结构
│ │ │ │
┌──┘ │ │ └──┐
名词 动词 数词 名词
│ │ │ │
中国 发射 一颗 卫星
学院 购买 十台 电脑
电脑 绘制 一幅 地图
上下文无关语法的形式化描述严谨且规范,计算机程序便
于实现,其算法大致上可分为以下三种,自顶向下分析法 ;自底向
上分析法 ;融合自顶向下和自底向上分析法。 本节仅 探讨自顶
向下算法。
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
自顶向下分析算法 (仅针对上述子集 ):
D1,从规则 (1)开始,即从 <一种句子结构 >开始,替换成 <名
词 ><动词 ><数词 ><名词 >。
D2,句首切分出的第一词语与 (2)中词语匹配,找到转 D3;否
则转 D6。
D3,句子第 二词语与 (3)中词语匹配,找到转 D4;否则转 D6。
D4,句子第三词语与 (4)中词语匹配,找到转 D5;否则转 D6。
D5,句末词语与 (2)中词语匹配,找到成功结束 ;否则转 D6。
D6,失败退出。
产生式规则还可描述成, 条件 →行动 或 前提 →结论。 这
与重写规则相似,但使用产生式规则的方法作句法分析,容易
分析复杂的句子,操作灵活,也易于模块化和结构化。
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
用于句法分析的产生式模块经过改进,但仍
包含三个基本组成部分,
(1) 事实库,改进后的词语库,它进行了词类
标注等,如,的 /P;涌现 /V;价值 /A;技术 /N; 产品 /N;
科技园 /N;高新 /DET…
(2) 规则集,存储有关语法的状态转移、性质
变化等规则的过程性知识。
(3) 控制器,将规则与事实进行匹配,控制句
法分析过程。
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
例, 定义分析有限个汉语句子的产生式规则
(限于篇幅,仅选有关一小部分 ),终结目标 S。
(1) N→NP (2) A NP→NP
(3) DET NP→DNP (4) P DNP→PP
(5) DNP PP→DNP (6) V DNP→VP
(7) DNP VP→S
下面用计算机程序 (产生式模块 )来分析一个
汉语句子是否合法,
"高新技术的高新价值产品涌现高新科技园 ".
第 3 章 产生式系统及其搜索方法
3, 5 应用举例
算法执行过程,
经自动分词和算法 E1,已得到,
DET N P DET A N V DET N
继续执行算法 E2～ E6,
将 N→NP(1),DET NP P DET A NP V DET NP
将 A NP→NP(2),DET NP P DET NP V DET NP
将 DET NP→DNP(3),DNP P DNP V DNP
将 P DNP→PP(4),DNP PP V DNP
将 DNP PP→DNP(5),DNP V DNP
将 V DNP→VP(6),DNP VP
将 DNP VP→S(7),S (合法而结束 )
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
产生式系统在应用中,结论可能是不完全确
定的。因此,产生式系统的设计应考虑不确定性
的搜索过程, 有两种不确定性, 证据不确定性和
结论不确定性。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 1 关于证据不确定性
当在考虑问题时,所遇到的经常具有某种不
确定性。例如,当你观察某种动物的颜色时,有
可能认为这种动物是白色的,但也可能是灰色的。
这就是说,你的观察具有某 种不确定性。 在考
虑问题时,所带有的干扰或不精确性都会导致证
据的不确定性。 目前人们用来处理不确定性的
启发式方法,在理论上应该还是不严格的,但在
实际应用中却可解决某些实际问题。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 1 关于证据不确定性
一般通过对事实赋于一个介于 0和 1之间的
系数来表示事实的不确定性。 1代表完全确定,0
代表完全不确定。 这个系数称为可信度 (也有取
可信度的范围 -1到 +1)。 当规则具有 一个以上的
条件时,就需要根据各条件的可信度来求得总条
件部分的可信度。 已有的方法有两类,
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 1 关于证据不确定性
(1) 以模糊集理论为基础的方法
按这种方法,把所有条件中最小的可信度作为总
条件的可信度。 例如,具有三个条 件的规则,对每
个证据各自的可信度分别赋于 0.9,0.5以及 1.0的可信
度。 如果从每个证 据各自的可信度得到这个规则的
总输入的可信度,取最小值就是 0.5。 产生式规则的
各个 条件之间是合取的关系,取其可信度的最小值
代表总的可信度,这也符合模糊理论。
总之,这种方法类似于,当把几根绳子连接起来
时,总的绳子的强度等于其中最差 的绳子强度。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 1 关于证据不确定性
(2) 以概率论为基础的方法
这种方法同样赋于每个证据可信度。 但当把单独条件的
可信度结合起来求总的可信 度时,它取决于各可信度的乘积。
采用上述例子,这时规则的输入部分的可信度为 0.45。
因为规则的输入部分的各个条件之间是合取关系,总的
可信度是各个分量的可信度 乘积,这看起来是符合概率理论
的。 因此这种方法称为以概率为基础的方法。 但根据概率
论,若要总的概率为各分量概率之乘积的先决条件是各分量之
间是独立的。 然而,这里并不能检验各条件之间是否相互独
立。 因此,从这点上讲,这是一种不完全合法的应 用。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 2 关于结论的不确定性
关于结论的不确定性是在规则的条件被完全满
足时,产生某种不确定的结论。 这种 结论不确定的
程度,是以赋以规则一个在 0和 1之间的系数的方法来
表示的。 例如,有以下规则,
IF 启动器发出刺耳的噪声 THEN 启动器坏的
可能性是 0.8
以上规则表示,若事实完全肯定即可信度应为
1.0; 但规则的条件部分不能完全确定,即证据的可信
度不为 1时,求结论的可信度有两种方法,
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 2 关于结论的不确定性
(1) 取结论的可信度为条件的可信度与上述系数的乘积。 例
如,如果取条件可信度为 0.5,则结论可信度 Cout=0.5× 0.8=0.4.
(2) 按照某种概率理论的解释,可以假设规则的条件部分的可
信度 Cin和其结论部分 的可信度 Cout存在某种关系,这种关系可
用来代表规则的不确定性。 下面为三种这样的关系曲线。（图
28）
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 2 关于结论的不确定性
Cout Cout Cout
↑ ↑ ↑ ↓先验值
1.0┼ 1.0┼ 1.0 ┼ - - - - - - ┊
┊
┊ ←先验值
└───┼→Cin └────┼→Cin └────┼→Cin
(a) 1.0 (b) 1.0 (c) 1.0
图 28
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3, 6, 2 关于结论的不确定性
(a)所示的 Cin与 Cout的关系所代表的就是乘积方法,结论
的可信度 Cout 等于条件的可信度 Cin和某个系数的乘积 ;
(b)所示的关系即使条件这边完全确定,即 Cin=0时,结论
的可信度 Cout仍为 0.2,这意味着,即使条件这边的证据不存在,
也可以得到结论。
在大多数情况下,Cin与 Cout的关系曲线由两条直线组成,
如 ( c) 所示。 这种状况,Cin和 Cout之间的关系不仅要反映终
点的条件,而且要反映开始分析以前的估计。 这种估 计也称
为先验值,这个值说明当完全没有要处理情况的预置可信度。
例如,你要接手某问题时,你可以估计这个问题的许多方面,
当然,这是依据你的经验得出的,即赋于一定程度的可信度,。
这就是给予的先验可信度。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3.6.3 多个规则支持的同一事实的不确定性
当多个规则支持同一事实时,这些规则之间的关系是析取,
也有两种方法,
(1) 基于模糊理论的方法
取支持这个事实的各规则的可信度的最大值作为事实的
可信度,这类似于模糊集理论中当多个条件相析取时,取这些
条件中的隶属函数的最大值作为总的隶属函数值。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3.6.3 多个规则支持的同一事实的不确定性
(2) 基于概率论的方法
这里论述的只是基于概率的方法中的一种,一组规则支持
的事实的可信度,可用以下方法求得,首先把各个证据的可信
度转换成可信性比例 r。 可信性比例 r和可信度 C之间 的关系
可表示为
r=C/(1-C) 或 C=r/(r+1)
把各证据的可信性比例简单相乘就可以求得这些证据所
支持的事实的可行性比例。然后,再利用上述公式转换回相应
的可信度。这样就可求得这个事实的可信度。当 C=0.5时,相
应的 r=1,这时称为中性的可信性比例。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3.6.3 多个规则支持的同一事实的不确定性
例, C1=0.9 C2=0.25,与此相应的 r1和 r2分别为
r1=0.9/(1-0.9)=9
r2=0.25/(1-0.25)=1/3
取 r1和 r2的乘积作为这个事实的可信性比例 r
r=r1× r2=9× 1/3=3
因此相应的可信度 C为
C=r/(r+1)=3/(3+1)=0.75
这样求得的可信度为 0.75,这个数值比按以模糊集理论
为基础的方法求得的可信度 0.9低。 这是因为其中一个证据的
可信度为 0.25,这实际上是否定这个事实。 如果这个证据的可
信度大于 0.5,按这种方法求得的可信度就会大于 0.9。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3.6.3 多个规则支持的同一事实的不确定性
应用以概率论为基础的方法有以下两个困难,
(1) 按照概率论,应该检查支持同一事实的各个规则之间
是否相互独立,而实际上难以进行这样的检查。
(2) 如果有以下规则
IF 启动器发出刺耳噪声 THEN 启动器坏的可能 0.75
按概率论,意味着还存在另一条规则,
IF 启动器发出刺耳噪声 THEN 启动器好的可能 0.25
在许多问题中,不允许同时使用这样的规则。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3,6, 4 非精确推理的原理
智能系统的设计将面临两个问题,
(1) 在实际问题中,我们模拟人所处理的信息有许多是不确定的,不精
确的,不完 全知道的。只要是智能系统,一般都处在这样的设计环境中。
(2) 为了防止辅助知识和规则太多而引起组合爆炸,有意识引入非精确
推理方法。 这样,既减少了智能系统设计的复杂性,又可提高系统运行的
速度。
非精确推理用于基本规则的智能系统的核心思想是, 为原始证据和
规则本身赋于一个不确定的度量,在给出一组算法,在此基础上利用这组
算法,求出规则中的结论部分的不确定性。
非精确推理一个可采用规则为下述结构,
IF E THEN H(X)
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3,6, 4 非精确推理的原理
其中,E是证据,H是假设,X是规则的不确定因子,
或称规则强度。 证据 E和假设 H都是由命题构成的。
证据 E或者是单独例题,或者是由其它命题的逻辑组合
而生成的复合命题。假设 H有时又是其它规则的证据,
由此构成推理网络。 规则强度 X表示证据 E对 H 的影响
程度,它描述了知识的不确定性。 这一规则的含义是,
如果证据 E为真,则假设 H 为真 的程度严重地依赖规
则强度 X。 非精确推理就是根据 E的不确定性值和规则
强度 X更新假设 H的不确性值,重复上述过程,直到求
出所需假设的不确定值,从而做出判断和假设。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3,6, 4 非精确推理的原理
从上面论述可知,在非精确推理的结构中,必须包
括对证据不确定性描述,对知识不确定性描述的描述和
更新命题不确定性的算法。 此外,一个非精确推理规
则的命题不确定性描述,知识不确定性描述,更新命题
不确定性值的算法都不是随意定义的,必须 满足上下
文相关约束。
对于规则 IF E THEN H(X) 的采用,E和 H(X)的描
述和表达视具体问题而设计,并不一定是繁难的,有些
场合简单的表达描述比复杂的表达描述更有效。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3,6, 4 非精确推理的原理
举例, 在设计英语水平测试系统中,若某一部分类容采用逆
向推理。
即,若被测试者对某一深度试题回答错误,不简单定论被
测试者没有掌握这一深度内容。自动假设被 测试者还是
掌握了这一深度的内容,换一相同深度测试题再测试。 若还
不正确,就假设 被测试者水平只在较低的某一深度,继续测
试,仍不正确,再假设,再测试,直到判别出被测试者对这
一部分内容掌握清况而停止。
这一问题选用逆向推理欠妥,为了判断被测试者是否已
经掌握某一部分内容,往往要测试多次,使用大量的知识和
规则,速度慢,而且判断还不一定准确,被测试者因为不认识
一个英语单词被降低水平的情况常常出现。
第 3 章 产生式系统及其搜索方法
3, 6 产生式系统的不确定性问题
3,6, 4 非精确推理的原理
对这一问题的改进可采用非精确推理,对规则强
度是这样处理的,
设测试题为 X,它由各种成分 X1X2……Xn 构成。 对每一
成分 Xi(i=1,2,…,n) 都将规定 隶属度 μ(Xi),那么,
X=μ(X1)/X1+μ(X2)/X2+…+μ(Xn)/Xn
如果测试题 X被测试者回答错误,这时不降低水平量选试题,
而是让 X分解 {X1,X2,… Xn} 让被测试者测试,根据各部分测
试清况来判断,如果 Xi又出错,还要调出与 Xi成份相同水平的试
题再测。
这种简单的非精确推理方式,不仅减少了大量辅助知识和规
则,使系统结构简化,层次分明,提高了运行速度,而且与原选用
的逆向推理方式比,测试英语水平准确性有 可能提高
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 1 处理中的分层
处理中的分层可以提高系统的运行速度,事
实上,它类似于传统程序设计的模块化技术,把
一个大问题化成若干小问题。
设计一个智能系统,应该先建立一个实验骨
架。 这个实验骨架可以不完善,甚至包含不准
确性,但它是完成目标的起点,可以得到一些具
体的实验数据,以之改进。 在这 一基础上,注意
分层,分层多少视具体情况而定,一般为三层。
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 1 处理中的分层
第一层描述问题的总体,以便化分各个子问题。 这一层即
使是实验骨架也应考虑周全,相当于科研开题报告或教学大纲。
这一层没有描述的问题,下一层是没法解决的。
第二层对每一问题进行详细描述,提出解的各种方法。 这
一层在实验系统中可以考虑不周全,将根据假设来进行各种观
测,选择最佳策略,逐步充实,修改,完善。
第三层是问题归约,对描述的问题,通 过一列变换成为子问
题集合,应用一系列算符求解,子问题的解都能得到,从而解决
了 初始问题。 显然,第三层必须是问题可解,否则系统运行以
失败告终。
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 1 处理中的分层
智能系统的分层技术,目前还应用不成熟。 在系
统设计时,人们总是希望它具有专 家的解题能力。, 于
是,在知识库中增加了大量的辅助信息,又不注意分层,
使得规则太 多,而控制推理又是基于匹配的,最后造成
系统的运行速度太慢 ---求解问题能力差。
举例,
在设计电视维修专家系统时,采用产生式规则,
把知识分成三层。
第一层, 知识和规则描述了问题的总体,无光栅,
有光栅有缺陷,无图象,无声,图象有缺陷,伴音有故
障, 显然,这些描述和规则已经表达了电视故障的全
面印象。
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 1 处理中的分层
第二层, 对每一具体问题的详细描述,这一知识
表达和制定的规则,与维修人员的 素质有关,很可能
是不全面的,但可以不断充实,修改。
第三层, 具体故障的指定,对一上一层描述的每
一问题都能按知识表达和制定的规则寻求出元件故
障。 这一级主要涉及电子技术的分析,是成熟的。
若系统不分层就直接推理匹配,由于规则过多,
经测试比分层后的系统运行速度约低六倍,可见分层
的重要性。
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 2 处理中的规则参数技巧
由于智能系统的应用和研究时间不长,不十分普及,
技术上也不成熟,所以多数设 计是基于规则的。 这主
要是规则易于模块化,简单,便于修改,扩充等优点。 然
而,这 也带来了问题,如,
某一智能系统有这样几条规则,
IF A1∧ A2∧ … ∧ Am∧ B1 THEN D1
IF A1∧ A2∧ … ∧ Am∧ B2 THEN D2
……
IF A1∧ A2∧ … ∧ Am∧ Bn THEN Dn
第 3 章 产生式系统及其搜索方法
3,7 相关技术
3, 7, 2 处理中的规则参数技巧
这 n个规则的前提中都有条件 A1∧ A2∧ … ∧ Am,
当它被匹配为真,若要判别上述任何 规则的前提是否成
立,只需判断第 m+1个条件是否为真就可以了。 但是,
智能系统的推理机是逐步匹配的,它将逐个条件重复检
查是否为真才能作作出决定。显然,这大大降低了系统
的运行速度。
第 3 章 产生式系统及其搜索方法
3,7 系统设计技巧
3, 7, 2 处理中的规则参数技巧
如果在规则中设计参数,上述缺陷可以克服,
IF A1∧ A2∧ … ∧ Am THEN g=1
ELSE g=0
IF g∧ B1 THEN D1
IF g∧ B2 THEN D2
…
IF g∧ Bn THEN Dn
这一类问题在智能系统中出现很多,总之,如
果 规则中恰当的设计参数,有助于提高智能系统的
运行速度。 返回
