3.1产生式系统 3.1.3产生式系统的类型 可分解的产生式系统 用图搜索方式求解这个问题时,搜索得到的部分状态 空间图见图26。图中只给出两条达到目标的路径和一条失 败的路径。实际搜索时有可能去探索更多的路径,往往导 致效率降低。 对于个问题,为了避免搜索多余的路径,可以将初 始数据库分解成几个可以独立加以处理的分量,分别对它 们进行求解。即可以分别对每一个分量数据库,测试产 生式规则可以应用的条件,如此进行下去,直到分量数据 库满足某种结束条件为止。要注意一般结束条件应是所 有分量数据库都已满足结束条件。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 3 . 1 . 3 产生式系统的类型 可分解的产生式系统 用图搜索方式求解这个问题时, 搜索得到的部分状态 空间图见图26。图中只给出两条达到目标的路径和一条失 败的路径。实际搜索时有可能去探索更多的路径, 往往导 致效率降低。 对于个问题, 为了避免搜索多余的路径 , 可以将初 始数据库分解成几个可以独立加以处理的分量, 分别对它 们进行求解。 即可以分别对每一个分量数据库, 测试产 生式规则可以应用的条件, 如此进行下去, 直到分量数据 库满足某种结束条件为止。要注意一般结束条件应是所 有分量数据库都已满足结束条件
3.1产生式系统 3.1.3产生式系统的类型 可分解的产生式系统 能够分解产生式系统的综合数据库和结束条件的产生 式系统称为可分解的产生式系统。一个可分解的产生式系 统,其基本算法描述如下: (1)DATA:=初始数据库 (2){D}:=DATA的分解式;每个D元素都看成单独的数据库 (3)Untl{Di的所有元素都满足结束条件之前,do: (4) begin (5)从D中选一个不满足结束条件的D* (6)从{D中删去D (7)在规则集中选择一条可应用于D的规则R (8){d}:=R应用于D*的结果 (9)在{D上添加di (10) end 第3章产生式系统及其搜索方法
第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
下图为分解方式 (C,B,Z)初态 iR2 ↓R4 RI↓ (B, M, B, 4 (C, B, B, B, M) D, L, B, 2 IR3 LR2 IR3 M, M, M, B, 2(B, M, B, B, B, M)D, L, M,M, 4 LR3 ↓R3 R4 M, M, M, M, M,A(M, M, M, B, B, B, M)D, L, M, M, B, B, M) LR4JR3 ↓R3 ( M, M, M, M, M, B, B, M) ( D, L, M,M, M, B, M) IR3 IR3 (M,M,M, M,M,M,M, B, M)-1D,L, M,M, M,M,M,M, M) R3↓目标 (M, M, M,M, M, M, M, M, M, M) 图 26
第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.2产生式系统的搜索(控制)策略 在3.1.2节的算法中,如何选择一条可应用的规则, 作用于当前的综合数据库,生成新的状态以及记住选用的 规则序列是构成控制策略的主要内容。对大多数的智能应用 问题,所拥有的控制策略知识或信息并不足以使每次通过算 法E4时,一下子就能选出最合适的一条规则来,因而产生 式系统还必须把E4扩大成搜索(推理)算法,以至于基本算法 的每一循环中选一条规则试用,最终找出某一序列能产生 个满足结束条件的数据库为止。由此可见,高效率的控制 策略需要有关被求解问题的足够知识,这样才能在搜索过程 减少盲目性,比较快的找到解路径。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 2 产生式系统的搜索(控制)策略 在3 .1 . 2节的算法中, 如何选择一条可应用的规则, 作用于当前的综合数据库, 生成新 的状态以及记住选用的 规则序列是构成控制策略的主要内容。对大多数的智能应用 问题, 所拥有的控制策略知识或信息并不足以使每次通过算 法E4时, 一下子就能选出最合适的一条规则来, 因而产生 式系统还必须把E4扩大成搜索(推理)算法, 以至于基本算法 的每 一循环中选一条规则试用, 最终找出某一序列能产生 一个满足结束条件的数据库为止。由此可见, 高效率的控制 策略需要有关被求解问题的足够知识, 这样才能在搜索过程 减少盲目性, 比较快的找到解路径
3.2产生式系统的搜索(控制)策略 过去三十多年中,人们研究了许多种搜索算法,归纳起 来主要有两类:一类是非启发式算法;另一类是启发式算法。 非启发式算法是按预定的控制策略进行搜索,在其过程中获 得的中间信息不用来改进控制策略。由于搜索总是按预先 规定的路线进行,没有考虑问题本身的特性,所以不容易选 择到最优的搜索途径,效率较低,且出现"组合爆炸"的频率 高。启发式算法是在搜索中加入了与问题有关的启发性信 息,用以指导搜索朝着最有希望的方向前进加速问题的求 解过程并找到最优解。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 过去三十多年中, 人们研究了许多种搜索算法,归纳起 来主要有两类: 一类是非启发 式算法; 另一类是启发式算法。 非启发式算法是按预定的控制策略进行搜索, 在其过程中获 得的中间信息不用来改进控制策略。 由于搜索总是按预先 规定的路线进行, 没有考虑问题本身的特性, 所以不容易选 择到最优的搜索途径, 效率较低 , 且出现"组合爆炸"的频率 高。 启发式算法是在搜索中加入了与问题有关的启发性信 息, 用以指导搜索朝着最有希望的方向前进, 加速问题的求 解过程并找到最优解。 3.2 产生式系统的搜索(控制)策略