RETE算法的描述(原创)

ipointer · · 1772 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

通过一周左右的研究,对规则引擎有了一定的了解。现在写点东西跟大家一起交流,本文主要针对RETE算法进行描述。我的文笔不太好,如果有什么没讲明白的或是说错的地方,请给我留言。

首先申明,我的帖子借鉴了网上很流行的一篇帖子,好像是来自CSDN;还有一点,我不想做太多的名词解释,因为我也不是个研究很深的人,定义的不好怕被笑话。

好现在我们开始。

首先介绍一些网上对于规则引擎比较好的帖子。

1、  来自JAVA视频网

http://forum.javaeye.com/viewtopic.php?t=7803&postdays=0&postorder=asc&start=0

2、  RETE算法的最原始的描述,我不知道在哪里找到的,想要的人可以留下E-mail

3、  CMU的一位博士生的毕业论文,个人觉得非常好,我的很多观点都是来自这里的,要的人也可以给我发mail   mailto:ipointer@163.com

 

接着统一一下术语,很多资料里的术语都非常混乱。

1、  facts 事实,我们实现的时候,会有一个事实库。用F表示。

2、  patterns 模板,事实的一个模型,所有事实库中的事实都必须满足模板中的一个。用P表示。

3、  conditions 条件,规则的组成部分。也必须满足模板库中的一条模板。用C表示。我们可以这样理解factspatternsconditions之间的关系。Patterns是一个接口,conditions则是实现这个接口的类,而facts是这个类的实例。

4、  rules 规则,由一到多个条件构成。一般用andor连接conditions。用R表示。

5、  actions 动作,激活一条rule执行的动作。我们这里不作讨论。

6、  还有一些术语,如:working-memoryproduction-memory,跟这里的概念大同小异。

7、  还有一些,如:alpha-networkbeta-networkjoin-node,我们下面会用到,先放一下,一会讨论。

 

引用一下网上很流行的例子,我觉得没讲明白,我在用我的想法解释一下。

 

假设在规则记忆中有下列三条规则

 

if A(x) and B(x) and C(y) then add D(x)

if A(x) and B(y) and D(x) then add E(x)

if A(x) and B(x) and E(x) then delete A(x)

 

RETE算法会先将规则编译成下列的树状架构排序网络


而工作记忆内容及顺序为
{A(1)A(2)B(2)B(3)B(4)C(5)},当工作记忆依序进入网络后,会依序储存在符合条件的节点中,直到完全符合条件的推论规则推出推论。以上述例子而言, 最后推得D(2)

 

让我们来分析这个例子。

 

模板库:(这个例子中只有一个模板,算法原描述中有不同的例子, 一般我们会用tuple,元组的形式来定义facts,patterns,condition

P: (?A , ?x)  其中的A可能代表一定的操作,如例子中的A,B,C,D,E ; x代表操作的参数。看看这个模板是不是已经可以描述所有的事实。

 

条件库:(这里元组的第一项代表实际的操作,第二项代表形参)

C1: (A , <x>)

C2: (B , <x>)

C3: (C , <y>)

C4: (D , <x>)

C5: (E , <x>)

C6: (B , <y>)

 

事实库:(第二项代表实参)

F1: (A,1)

F2: (A,2)

F3: (B,2)

F4: (B,3)

F5: (B,4)

F6: (C,5)

 

       规则库:

         R1: c1^c2^c3

         R2: c1^c2^c4

         R3: c1^c2^c5

 

      

       有人可能会质疑R1: c1^c2^c3,没有描述出,原式中:

if A(x) and B(x) and C(y) then add D(x)A=B的关系。但请仔细看一下,这一点已经在条件库中定义出来了。

 

       下面我来描述一下,规则引擎中RETE算法的实现。

       首先,我们要定一些规则,根据这些规则,我们的引擎可以编译出一个树状结构,上面的那张图中是一种简易的表现,其实在实现的时候不是这个样子的。

       这就是beta-network出场的时候了,根据rules我们就可以确定beta-network,下面,我就画出本例中的beta-network,为了描述方便,我把alpha-network也画出来了。

      

 

上图中,左边的部分就是beta-network,右边是alpha-network,圆圈是join-node.

从上图中,我们可以验证,在beta-network中,表现出了rules的内容,其中r1,r2,r3共享了许多BMjoin-node,这是由于这些规则中有共同的部分,这样能加快match的速度。

右边的alpha-network是根据事实库构建的,其中除alpha-network节点的节点都是根据每一条condition,从事实库中match过来的,这一过程是静态的,即在编译构建网络的过程中已经建立的。只要事实库是稳定的,即没有大幅度的变化,RETE算法的执行效率应该是非常高的,其原因就是已经通过静态的编译,构建了alpha-network。我们可以验证一下,满足c1的事实确实是w1,w2

下面我们就看一下,这个算法是怎么来运行的,即怎么来确定被激活的rules的。从top-node往下遍历,到一个join-node,AM for c1的节点汇合,运行到match c1节点。此时,match c1节点的内容就是:w1,w2。继续往下,与AM for c2汇合(所有可能的组合应该是w1^w3,w1^w4,w1^w5,w2^w3,w2^w4,w2^w5),因为c1^c2要求参数相同,因此,match c1^c2的内容是:w2^w3。再继续,这里有一个扇出(fan-out),其中只有一个join-node可以被激活,因为旁边的AM只有一个非空。因此,也只有R1被激活了。

解决扇出带来的效率降低的问题,我们可以使用hashtable来解决这个问题。

RETE算法还有一些问题,如:facts库变化,我们怎么才能高效的重建alpha-network,同理包括rules的变化对beta-network的影响。这一部分我还没细看,到时候再贴出来吧。

 帮我点一下旁边的google广告,谢谢了。

 

 

 

 

 

 

本文来自:博客园

感谢作者:ipointer

查看原文:RETE算法的描述(原创)

入群交流(和以上内容无关):Go中文网 QQ 交流群:798786647 或加微信入微信群:274768166 备注:入群;关注公众号:Go语言中文网

1772 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传