User:Alex G Yang/Rete算法 (2)

Rete算法是一个模式匹配算法，用于实现一个处理系统。 (英语的发音/ˈriːtiː/ REE-tee or /ˈreɪtiː/ RAY-tee, rarely /ˈriːt/ REET or /rɛˈteɪ/ re-TAY)  他决定哪些系统规则被触发，触发的条件基于这个系统存储的数据。

‘Rete’来自拉丁语文的“网”一词

概述

一个简装的专家系统通过检查知识库里的已知实例(facts)，触发哪些对应的规则，然后移到下一个规则(然后循环返回到第一个规则)。 但是这样的简单实现，即使规则和实例的数据量不大，执行速度也很慢。

Rete算法可以更高效的实现一个专家系统。基于Rete算法的专家系统建立一个节点网络，每一个网络节点(除了根节点)对应一个模式，其由左手侧(LHS Left-Hand-Side)规则产生。从根节点到叶节点的路径就是完整的左手规则。

每个节点都在内存保存了与模式匹配的实例。这个结构是一个基本的字典树应用。当一个新实例被插入，或被修改，他们就会沿着这个网络传播，并与节点进行比配。当路径上的节点条件都被满足，他就到达了一个叶节点，对应的规则就会被触发。

卡内基梅隆大学的Charles L. Forgy设计了这套Rete算法，最迟发表于1974的一篇论文，并在他1979的博士论文和1982的另一篇论文中进行了完善(参阅参考文献)。 paper (see References). Rete算法最初被运用在OPS5的核心引擎上。现在已经被广泛的应用在各种专家系统中。（如： Tibco Business Events,Newgen OmniRules, CLIPS, Jess, Drools, IBM Operational Decision Management, OPSJ, Blaze Advisor, BizTalk Rules Engine, Soar, and Sparkling Logic SMARTS.)

Rete算法是一种用空间(内存)换时间(处理速度)的设计思想。多数情况下，与简装的系统比速度会成几何级数增长(速度的Rete算法的性能理论上依存于系统中规则的数量)。但是在大型的专家系统中，容易产生内存枯竭的问题。为了减少内存的使用，衍生出了Rete算法的改良版。(如:Rete2[2],收集导向匹配[3]).

描述

Illustrates the basic Rete.

另见

• Action selection mechanism
• Inference engine

参考文献

[[Category:决策论]] [[Category:专家系统]]