最近面试的时候,经常被问及自己参加的项目中rete算法的原理,但是RETE算法是一个比较复杂的算法,在短时间内不能阐述的足够清晰,在这里做个简单的介绍
。转载请注明来自 http://chillwarmoon.iteye.com
RETE算法是一个用来实现产生式规则系统的高效模式匹配算法。该算法是由卡内基美隆大学的Charles L. Forgy在1974年发表的论文中所阐述的算法。RETE算法提供了专家系统的一个高效实现。
规则推理引擎做为产生式系统的一部分,当进行事实的断言时,包含三个阶段:匹配、选择和执行,称做match-select-act cycle。RETE算法可以对匹配阶段进行高效实现,下面从鉴别网络和模式匹配过程两个方面对该算法进行介绍。
鉴别网络(如下图所示):
由RETE算法在进行模式匹配时,是根据生成的鉴别网络来进行的。网络中非根结点的类型有1-input结点(也称为alpha结点)和2-input结点(也称为beta结点)两种。1-input结点组成了Alpha网络,2-input结点组成了Beta网络。
每个非根结点都有一个存储区。其中1-input结点有alpha存储区和一个输入口;2-input结点有left存储区和right存储区和左右两个输入口,其中left存储区是beta存储区,right存储区是alpha存储区。存储区储存的最小单位是工作存储区元素(Working Memory Element,简称WME),WME是为事实建立的元素,是用于和非根结点代表的模式进行匹配的元素。Token是WME的列表,包含有多个WME,(在Forgy的论文中,把Token看成是WME的列表或者单个WME,为了阐述方便,本文将把Token只看成WME的列表,该列表可以包含一个WME或者多个WME),用于2-input结点的左侧输入。事实可以做为2-input结点的右侧输入,也可以做为1-input结点的输入。
每个非根结点都代表着产生式左部的一个模式,从根结点到终结点的路径表示产生式的左部。
规则匹配:
推理引擎在进行模式匹配时,先对事实进行断言,为每一个事实建立WME,然后将WME从RETE鉴别网络的根结点开始匹配,因为WME传递到的结点类型不同采取的算法也不同,下面对alpha结点和beta结点处理WME的不同情况分开讨论。
(1)如果WME的类型和根节点的后继结点TypeNode(alpha结点的一种)所指定的类型相同,则会将该事实保存在该TypeNode结点对应的alpha存储区中,该WME被传到后继结点继续匹配,否则会放弃该WME的后续匹配;
(2)如果WME被传递到alpha结点,则会检测WME是否和该结点对应的模式相匹配,若匹配,则会将该事实保存在该alpha结点对应的存储区中,该WME被传递到后继结点继续匹配,否则会放弃该WME的后续匹配;
(3)如果WME被传递到beta结点的右端,则会加入到该beta结点的right存储区,并和left存储区中的Token进行匹配(匹配动作根据beta结点的类型进行,例如:join,projection,selection),匹配成功,则会将该WME加入到Token中,然后将Token传递到下一个结点,否则会放弃该WME的后续匹配;
(4)如果Token被传递到beta结点的左端,则会加入到该beta结点的left存储区,并和right存储区中的WME进行匹配(匹配动作根据beta结点的类型进行,例如:join,projection,selection),匹配成功,则该Token会封装匹配到的WME形成新的Token,传递到下一个结点,否则会放弃该Token的后续匹配;
(5)如果WME被传递到beta结点的左端,将WME封装成仅有一个WME元素的WME列表做为Token,然后按照(4)所示的方法进行匹配;
(6)如果Token传递到终结点,则和该根结点对应的规则被激活,建立相应的Activation,并存储到Agenda当中,等待激发。
(7)如果WME被传递到终结点,将WME封装成仅有一个WME元素的WME列表做为Token,然后按照(6)所示的方法进行匹配;
以上是RETE算法对于不同的结点,来进行WME或者token和结点对应模式的匹配的过程。
分享到:
相关推荐
drools-rete算法简介.docx
改进Rete算法对电信计费规则引擎系统性能的提升,钟小安,,本文详细描述了改进电信计费系统中规则引擎组件Rete算法的两种实现方式-在Alpha存储区对Alpha节点进行哈希查找和在Beta存储区对Beta节点�
URULE是一款基于RETE算法的纯Java规则引擎,提供规则集、决策表、决策树、评分卡,规则流等各种规则表现工具及基于网页的可视化设计器,可快速开发出各种复杂业务规则。
从老外网站那里下载的最好的描述rete算法的ppt
在此理论基础上,将一种高效的模式匹配算法——Rete算法引入到实际的故障的诊断系统中,以保证故障诊断的高效性和准确性。为此在实际系统中,借助规则引擎将故障信息规则化,并将故障诊断流程以层次分明的XML文档...
行业分类-设备装置-一种结合Rete算法的RDF数据分布式并行推理方法
基于RETE算法的纯Java规则引擎,提供规则集、决策表、决策树、评分卡,规则流等各种规则表现工具及
生锈的网 Rete 算法在 Rust 中的实现。
URule是一款纯Java规则引擎,它以RETE算法为基础,提供了向导式规则集、脚本式规则集、决策表、交叉决策表(PRO版提供)、决策树、评分卡及决策流共六种类型的规则定义方式,配合基于WEB的设计器,可快速实现规则的...
#资源达人分享计划#
针对传统的规则引擎算法――Rete算法会缓存大量的部分匹配结果,而RFID事件通常具有时间约束的特点,提出一种基于部分匹配过期的过期数据回收机制,及时删除过期的部分匹配结果,减小计算过程中缓存的压力。...
提供规则集、决策表、决策树、评分卡,规则流等各种规则表现工具及基于网页的可视化设计器,可快速开发出各种复杂业务规则。 开发工具在软件开发生命周期中扮演着至关重要的角色,它们旨在简化和加速从概念设计到...
Improved rete算法, 基于规则的专家系统采用的快速算法
动态演化系统中规则引擎的改进Rete算法
Treat 算法论文原文 英文 treat 算法 rete算法相关 This paper presents the TREAT match algorithm for AI production systems. The TREAT algorithm introduces a new method of state saving in production ...