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

Question

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

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

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

Answer 1

估计 RETE 的复杂性是一个不平凡的问题。

首先，您不能将规则的数量用作维度。您应该查看的是规则具有的单个约束或匹配项。您可以将规则视为组合在一起的约束集合。这就是RETE的全部原因。

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

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

最后，您需要考虑引擎冲突解决策略。如果您有多个相互冲突的规则，则可能需要花费大量时间来确定执行它们的顺序。

关于 RETE 性能，我建议你看看一篇非常好的博士论文。作者是 Robert B. Doorenbos，题目是“Production matching for large learning systems”。