3.1产生式系统 3.1.2产生式系统的基本算法 >E1:DATA←初始事实库 >E2: until Data满足结束条件以前,do E3: begin E4:在规则集中选某一条可用于DATA的规则 >E5:DATA←规则应用到DATA得到的结果 >E6:结束 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 3 . 1 . 2 产生式系统的基本算法 ➢ E1: DATA←初始事实库 ➢ E2: until DATA 满足结束条件以前, do ➢ E3: begin ➢ E4: 在规则集中,选某一条可用于DATA的规则 ➢ E5: DATA←规则应用到DATA得到的结果 ➢ E6: 结束
3.1产生式系统 3.1.3产生式系统的类型 正向、逆向、双向产生式系统 用产生式系统求解某一问题时,如果按照规则使用的 方式或者说按推理方向来划分的话,有正向、逆向和双向产 生式系统。正向产生式系统是从初始状态出发朝着目标状 态这个方向使用规则,即正推的方式工作,称这些规则为F 规则;若选目标状态作为初始数据库逆向进行求解,即逆 向使用规则,产生子目标状态,反方向一步一步朝着初始 状态方向求解,整个逆推方式工作,称逆向产生式系统, 逆向应用的规则称B规则;若以双向搜索的方式(即正向和 逆向同时进行)去求解问题,则称为双向产生式系统 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 3 . 1 . 3 产生式系统的类型 正向、逆向、双向产生式系统 用产生式系统求解某一问题时, 如果按照规则使用的 方式或者说按推理方向来划分的话, 有正向、逆向和双向产 生式系统。正向产生式系统是从初始状态出发朝着目标状 态这个方向使用规则, 即正推的方式工作, 称这些规则为F 规则; 若选目标状态作为初始 数据库逆向进行求解, 即逆 向使用规则, 产生子目标状态, 反方向一步一步朝着初始 状态方向求解, 整个逆推方式工作, 称逆向产生式系统, 逆向应用的规则称B规则; 若以双向搜索的方式(即正向和 逆向同时进行)去求解问题, 则称为双向产生式系统
人3.1产生式系统 3.1.3产生式系统的类型 可交换的产生式系统 可交换式产生式系统的可交换性指几条规则的应用可 以任意交换次序而不影响求解。 般来说,当一个产生式系统对任何一个数据库D都 具有如下性质时,这样一个产生式系统是可交换的 (1)可应用于D的规则集合,使用了其中任意一条规则之后所生 成的任何数据库,这样一个规则集合还适用; (2)满足目标条件的某个数据库D,当应用任何一个可应用于数 据库D的规则之后所生成的任何数据库,任然满足目标条件; (3)若对D应用某一规则序列后得到的一个数据库D(并能达到 解),当改变这些规则次序后,任然可求得解,即求得D与使用满足 D的可应用规则集合中的规则次序无关。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 3 . 1 . 3 产生式系统的类型 可交换的产生式系统 可交换式产生式系统的可交换性指几条规则的应用可 以任意交换次序而不影响求解。 一般来说, 当一个产生式系统对任何一个数据库D都 具有如下性质时, 这样一个产生式系统是可交换的。 (1) 可应用于D的规则集合, 使用了其中任意一条规则之后所生 成的任何数据库, 这样一个规则集合还适用; (2) 满足目标条件的某个数据库D, 当应用任何一个可应用于数 据库D 的规则之后所生成的任何数据库, 任然满足目标条件; (3) 若对D应用某一规则序列后得到的一个数据库D'(并能达到 解), 当改变这些规则次序后, 任然可求得解, 即求得D'与使用满足 D的可应用规则集合中的规则次序无关
3.1产生式系统 13.1.3产生式系统的类型 可交换的产生式系统 例:给定一个整数集合的初始状态{a,b,c},设目标状态为 具有a,b,C,ab,bc,ca这六个元素组成的集合。可应用的 规则集合为 RI: 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 章 产生式系统及其搜索方法 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.1产生式系统 3.1.3产生式系统的类型 可分解的产生式系统 先研究一个重写问题的产生式系统,初始数据库为 (C,B,Z,产生式规则如下: Rl:C→(D,L) R2:C→(B,M) R3:B→→(M,M R4:Z→>(B,B,M) 结束条件是生成只包含M组成的数据库,即(M,,M) 第3章产生式系统及其搜索方法
第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)