前边说了,Drools采用的是RETE算法。那啥是rete算法。 定义:Rete算法由 Carnegie Mellon University 的Dr Charles L. Forgy设计发明,是一个用来实现产生式规则系统(前边提到的production/inference好像就该翻译为产生式规则)的高效模式匹配算法。它可以被分为两部分:规则编译和运行时执行。规则编译是指根据规则集生成推理网络的过程,运行时执行指将数据送入推理网络进行筛选的过程。 相关概念: (1)事实(Fact):对象之间及对象属性之间的关系 (2)规则(rule):是由条件和结论构成的推理语句,一般表示为if...Then。一个规则的if部分称为LHS,then部分称为RHS。 (3)模式(module):就是指IF语句的条件。这里IF条件可能是有几个更小的条件组成的大条件。模式就是指的不能在继续分割下去的最小的原子条件。 RETE推理网络的生成过程: 简单点说,就是从规则集{规则1,规则2........}中拿出一条来,根据一定算法,变成RETE推理网络的节点。不断循环将所有规则都处理完,RETE推理网络就生成了。 这里的一定算法具体过程如下: 1、创建root节点(根节点),推理网络的入口。 2、拿到规则1,从规则1中取出模式1(前面说了,模式就是最小的原子条件,所以规则模式的关系是1:n)。 a)检查模式1中的参数类型,如果是新类型,添加一个类型节点。 b)检查模式1对应的Alpha节点是否存在,如果存在记录下节点的位置;如果没有,将模式1作为一个Alpha节点加入到网络中。同时根据Alpha节点建立Alpah内存表。 c)重复b,直到处理完所有模式。 d)组合Beta节点: Beta(2)左输入节点为Alpha(1),右输入节点为Alpha(2) Beta(i)左输入节点是Beta(i-1),右输入节点为Alpha(i) e)重复d,直到所有Beta节点处理完毕 f)将动作Then部分封装成最后节点做为Beta(n) 3、重复2,直到所有规则处理完毕 下面是一个从网上找得例子: 规则P1: LHS: C1:(年纪:研2) C2:(性别:男) C3:(身材:较瘦) C4:(身高:大于175cm) RHS: 韩启超 RETE图如下: 图中各图形与节点的对应关系是:
TypeNode: AlphaNode: BetaNode: 有关RETE正式的解释,到http://docs./drools/release/6.0.0.Final/drools-docs/html/HybridReasoningChapter.html#ReteOO。 |
|
来自: 贾朋亮博客 > 《Drools引擎》