rete算法学习

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

在上篇博客中,介绍了策略型业务逻辑处理中几种选择,其中有一种选择就是利用规则引擎来进行逻辑处理。其实藏在规则引擎的底层中还是有很多算法的,其中有一种算法是rete算法,最近正好也关注算法,就简单的学习了一下,因为对这个算法理解的非常清楚,所以如果有有对这个算法熟悉的朋友,可以给予指正。

 

RETE算法是一个用于产生式系统的高效模式匹配算法。在一个产生式系统中,被处理的数据叫做working memory,用于判定的规则分为两个部分LHSleft-hand-side)和RHSright hand side),分别表示前提和结论。主要流程可以分为以下步骤:

  1. Match:找出符合LHS部分的working memory集合
  2. Confilict resolution:选出一个条件被满足的规则
  3. Act:执行RHS的内容
  4. 返回1  

RETE算法主要改进Match的处理过程,通过构建一个网络进行匹配。

 

算法详细描述

 

RETE网络主要分为两个部分,alpha网络和beta网络。如下图所示(图片引用其他网站)。

 

 

 

1alpha网络:过滤working memory,找出符合规则中每一个模式的集合,生成alpha memory(满足该模式的集合)。有两种类型的节点,过滤type的节点和其他条件过滤的节点。

2Beta网络:有两种类型的节点Beta MemoryJoin Node。前者主要存储Join完成后的集合。后者包含两个输入口,分别输入需要匹配的两个集合,由Join节点做合并工作传输给下一个节点。

 

 匹配过程描述

  1. 导入需要处理的事实到facts集合中。
  2. 如果facts不为空,选择一个fact进行处理。否则停止匹配过程。
  3. 选择alpha网的第一个节点运行(建立网络的时候设定的),通过该节点则进入alpha网的下一个节点,直到进入alpha memory。否则跳转到下一条判断路径
  4. alpha memory的结果加入到beta memory中,如果不为Terminal节点,则检测另一个输入集合中是否存在满足条件的事实,满足则执行join,进入到下一个beta memory重复执行3。若另一个输入集合无满足条件的事实,返回到2。如果该节点为Terminal节点,执行ACT并添加到facts中。

 用一个例子描述过程

1)现在WME中有以下这些事实。

w1:(B1 ^on B2

w2:(B1 ^on B3

w3:(B1 ^color red

w4:(B2 ^on table

w5:(B2 ^left-of B3

w6:(B2 ^color blue

w7:(B3 ^left-of B4

w8:(B3 ^on table

w9:(B3 ^color red

 

2)下面描述规则

下面是三条匹配条件

C1: <x> ^on <y>

C2:(<y> ^left-of <z>

C3:(<z> ^color red

下面是规则要满足的所有条件,即所有LHS

p1 has conditions C1^C2^C3

p2 has conditions C1^C2^C4^C5

p3 has conditions C1^C2^C4^C3

 

3)推理描述

     根据Ci,图中的蓝色alpha结点应该有三种,分别判定onleft-ofcolor。则黄色的alpha memory中包含三个集合,分别是

满足C1{w1 w2 w4 w8}

满足C2{w5 w7}

满足C3{w2 w6 w9}

     以p1为例,首先以C1C2为输入,在绿色Dummy Input节点中进行操作,并传入到梅红色beta momory中,此时这个节点存储的是(w1^w5,w2^w7)。然后以这个集合和C3为输入,操作得出w1^w5^w9,此时发现没有更多的模式需要匹配,到达Terminal节点,匹配结束。这样就得到满足规则的集合组合了。

 

通过这些理论和一个实例应该对rete算法清除了些,下面博客介绍drools规则引擎工具,它是一个实现Rete算法的很好的规则引擎框架。


有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:lfsf802

查看原文:rete算法学习

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

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