Rete算法的时间复杂度是多少？

Question

Rete算法是一种有效的模式匹配算法，它将大量的模式集合与大量的对象集合进行比较。它还用于我现在正在探索的专家系统外壳中的一个: is drools。

基于我拥有的规则数，算法的时间复杂度是多少？

以下是Rete算法的链接：http://www.balasubramanyamlanka.com/rete-algorithm/也用于Drools：https://drools.org/

Answer 1

估计RETE的复杂性是一个非平凡的问题.

首先，不能将规则的数量用作维度。您应该查看的是规则所具有的单个约束或匹配。可以将规则视为组合在一起的约束的集合。这就是瑞特的所有理由。

一旦您粗略估计了您的规则库所具有的约束量，您将需要查看那些相互依赖的约束。依赖于间的约束是最复杂的匹配，在概念上与SQL查询中的联接非常相似。它们的复杂性取决于它们的性质以及工作记忆的状态。

然后，你需要看看你的工作记忆的大小。在基于RETE的专家系统中所断言的事实数量对其性能有很大影响。

最后，您需要考虑引擎冲突解决策略。如果您有几条相互冲突的规则，那么可能需要很长时间才能确定它们的执行顺序。

关于RETE的性能，有一个非常好的PhD论文我建议您看看。作者是RobertB.Doorenbos，题目是“大型学习系统的生产匹配”。