Rete算法总结

基本介绍

来源： Dr. Charles Forgy （ 1978-79）

Rete算法历史来源：伴随着人工智能的发展，出现了规则引擎和产生式系统（图中5.1.3），rete算法正是在这个阶段产生的。

算法组成：rule compilation and runtime execution（规则编译和执行）

算法的应用：
RETE是一种模式匹配算法（将事实与规则进行匹配的算法）。常见的模式匹配算法有RETE,LFA,TREAI,LEAPS。Drools采用的匹配算法就是RETE，该算法被认为是目前世界上最先进的模式匹配算法。
相关链接：https://blog.csdn.net/liuxingtianshi9570/article/details/43819371

rete算法执行过程

相关概念：

（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，直到所有规则处理完毕

更多细节参考（Drools中的实现等）
https://blog.csdn.net/lthirdonel/article/details/80948922