检测冗余规则的算法

Question

我正在寻找一种检测冗余规则的算法.

规则具有固定数量的输入参数,并且每个参数具有不同的域.

考虑三个规则参数颜色,材质和尺寸:

• 颜色:红色,绿色,蓝色
• 材质:木材,玻璃,铝
• 尺寸:小,中,大

每个规则可以匹配参数的多个值或匹配任何值.选择匹配所有参数值的第一个规则.没有否定规则,但域是固定的,因此可以通过添加所有其他域来实现否定.

       +--------------------------------------------------++-----------------
       |                   Rule Parameters                || Rule Action
       +----------------+------------------+--------------++-----------------
       | Color          | Material         | Size         || ==> Price
       +----------------+------------------+--------------++-----------------
Rule 1 | Red            | Wood, Glass      | Large        || $100
Rule 2 | Red            | Aluminium        | Large        || $200
Rule 3 | Blue or Green  | Wood             | Medium       || $300
Rule 4 | Red            | ** Any **        | Large        || $400  <== Redundant
Rule 5 | ** Any **      | ** Any **        | ** Any **    || $500

由于规则1和规则2的组合,规则4是冗余的.冗余规则是由于在该规则之前定义的(组合)规则而永远不会匹配的规则.冗余检查中不评估规则操作.

如何有效地实现这一点(在Java中)？它应该支持1000条规则,每条参数有10个参数,每个参数100个 从数据库中读取规则,参数和参数值(即,它们不能被硬编码).

效率问题是有100 ^ 10个输入参数组合(每个参数具有100个值的域).规则编辑器gui中需要该算法,以支持创建规则的用户.它应该在几秒钟内找到所有冗余规则.

Github上

我已经创建了一个存储库来测试提出的解决方案:https://github.com/qlp/redundant-rules 目前只有一个BDD实现,它失败了这个大小的问题.也许我的BDD实施可以改进？

Answer 1

从本质上讲,您的任务是实施决策树.树的每个级别对应于每个参数,并且在每个级别,将存在参数可以容纳的每个值的节点.在叶级别,您将存储适用的规则操作.

例如,在"颜色"级别,您将有3个节点,红色,蓝色,绿色.每个人都有3个孩子(在材料层面)木材,玻璃,铝.每个人都有3个孩子(小,中,大).您将基于从数据库中学习参数和值来构造此树.

一旦树被构建,你会在同一时间从数据库中读取,一个规则,并存储在每个叶子的"规则操作"(在这种情况下,在尺寸级别).如果有一条规则想要在已经有一个动作的叶子上应用,那么对于适用哪个规则存在歧义.对于您的问题,您声明您已采用应用的第一条规则 - 因此您不会更改存储的规则.

如果有一条规则,那么对于每个叶子,它已经有一个已定义的动作,那么根据你的例子,该规则将是"多余的".