检测冗余规则的算法

Question

检测冗余规则的算法

javaalgorithmmathpattern-matchingdiscrete-mathematics

8

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

规则具有固定数量的输入参数，每个参数都有不同的域。

考虑三个规则参数：颜色、材料和尺寸：

- 颜色：红、绿、蓝 - 材料：木头、玻璃、铝 - 尺寸：小、中、大

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

       +--------------------------------------------------++-----------------
       |                   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

规则4由于规则1和2的组合是冗余的。冗余规则是指由于在该规则之前定义的规则（的组合）而永远不会被匹配的规则。在冗余检查中不评估规则动作。

如何高效地实现这个（Java）？它应该支持1000个带有10个参数和每个参数有100个值的规则。规则、参数和参数值从数据库中读取（即它们不能被硬编码）。

效率问题在于有100^10种输入参数的组合（每个参数都有100个值的域）。算法需要在规则编辑器GUI中使用，以支持创建规则的用户。它应该在几秒钟内找到所有的冗余规则。

GITHUB

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

- Jurriaan

3

我已投票关闭，因为该问题过于宽泛。这只是一份需求说明，而不是一个合适的SO问题。你应该尝试解决问题，如果遇到具体问题再回来询问。 - Duncan Jones

1

这个问题确实比较宽泛，缺少一些细节，但我认为它足够具体和清晰，可以鼓励回答有趣的潜在方法 - 因此，+1。 - Marco13

虽然不完全符合您的要求，但也许更好/更容易的方法是简单地寻找高效的存储和/或应用规则的方式（如果这些是问题），而不是试图消除冗余。原因是，考虑到规则数量与可能组合数量之间的比例，规则中的冗余程度很可能相当低，除非您有充分的理由相信其他情况。 - Nuclearman

@Nuclearman 检测冗余规则的原因是为了通知用户（而不是性能）。添加冗余规则的用户犯了一个错误。 - Jurriaan

具有讽刺意味的是，在努力证明我的观点仍然正确时，我想出了可能是解决问题的有效方法。这使得我的观点在指数增长的情况下变得无效。详见答案。 - Nuclearman

显示剩余6条评论

7个回答

1

由于评论，内容已经完全重写。（请注意，这可能与Khaled A Khunaifer所写的类似，但它是同时创建的。）

一种可能的方法是找到规则的“逻辑”描述。规则具有相当规律的形式，即总是由多个析取式组成的合取式。规则可以写成以下形式：

(Red) AND (Wood OR Glass) AND (Large)
(Red) AND (Aluminium) AND (Large)
...

现在，可以应用复杂的优化和最小化技术（例如Quine McCluskey或其他形式的minimization）。然而，我在这里勾勒了一个非常简单的实现。当规则只在其中一项析取上有所不同时，可以将它们“合并”。例如，上面的规则可以合并为

(Red) AND (Wood OR Glass OR Aluminium) AND (Large)

现在，如果有一个像这样的规则：

(Red) AND (Wood OR Glass OR Aluminium) AND (Medium)

当遇到它时，可以将其与前一个合并。

(Red) AND (Wood OR Glass OR Aluminium) AND (Large OR Medium)

如果我们找到了像这样的规则：

(Red) AND (Glass OR Aluminium) AND (Medium)

它可以被标记为“冗余”，因为它是由前面的内容暗示出来的。

再强调一遍：这个实现方式相当“hacky”而且远非“优雅”，肯定还有很多可能的改进。但至少它展示了这个总体思路是可行的。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class RulesChecker
{
    public static void main(String[] args)
    {
        List<Rule> rules = new ArrayList<Rule>();
        List<Set<String>> domains = new ArrayList<Set<String>>();
        domains.add(setOf("Red", "Green", "Blue"));
        domains.add(setOf("Wood", "Glass", "Aluminium"));
        domains.add(setOf("Small", "Medium", "Large"));

//      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

        rules.add(new Rule("$100", disOf("Red")          , disOf("Wood", "Glass"), disOf("Large")));
        rules.add(new Rule("$200", disOf("Red")          , disOf("Aluminium")    , disOf("Large")));
        rules.add(new Rule("$300", disOf("Blue", "Green"), disOf("Wood")         , disOf("Medium")));
        rules.add(new Rule("$310", disOf("Blue")         , disOf("Wood")         , disOf("Medium")));
        rules.add(new Rule("$350", disOf("Green")        , disOf("Aluminium")    , disOf("Medium")));
        rules.add(new Rule("$400", disOf("Red")          , disOf(domains.get(1)) , disOf("Large")));
        rules.add(new Rule("$500", disOf(domains.get(0)) , disOf(domains.get(1)) , disOf(domains.get(2))));

        System.out.println("Rules: ");
        for (Rule rule : rules)
        {
            System.out.println(rule);
        }


        List<Rule> mergedRules = new ArrayList<Rule>();
        mergedRules.add(rules.get(0));
        for (int i=1; i<rules.size(); i++)
        {
            add(mergedRules, rules.get(i));
        }
    }


    private static void add(List<Rule> mergedRules, Rule newRule)
    {
        for (int i=0; i<mergedRules.size(); i++)
        {
            Rule oldRule = mergedRules.get(i);
            if (implies(oldRule, newRule))
            {
                System.out.println("Redundant "+newRule);
                System.out.println("   due to "+oldRule);
                return;
            }
            int mergeIndex = mergeIndex(oldRule, newRule);
            if (mergeIndex != -1)
            {
                Rule mergedRule = merge(oldRule, newRule, mergeIndex);
                mergedRules.set(i, mergedRule);
                System.out.println("Merging "+oldRule);
                System.out.println("    and "+newRule);
                System.out.println("  gives "+mergedRule);
                return;
            }
        }
        mergedRules.add(newRule);
    }

    private static boolean implies(Rule oldRule, Rule newRule)
    {
        Conjunction c0 = oldRule.conjunction;
        Conjunction c1 = newRule.conjunction;
        List<Expression> es0 = new ArrayList<Expression>(c0.terms);
        List<Expression> es1 = new ArrayList<Expression>(c1.terms);
        for (int i=0; i<es0.size(); i++)
        {
            Disjunction d0 = (Disjunction) es0.get(i);
            Disjunction d1 = (Disjunction) es1.get(i);
            if (!d0.terms.containsAll(d1.terms))
            {
                return false;
            }
        }
        return true;
    }


    private static Disjunction disOf(String ... ss)
    {
        return disOf(Arrays.asList(ss));
    }

    private static Disjunction disOf(Collection<String> ss)
    {
        List<Variable> list = new ArrayList<Variable>();
        for (String s : ss)
        {
            list.add(new Variable(s));
        }
        return new Disjunction(list);
    }

    private static int mergeIndex(Rule r0, Rule r1)
    {
        Conjunction c0 = r0.conjunction;
        Conjunction c1 = r1.conjunction;
        List<Expression> es0 = new ArrayList<Expression>(c0.terms);
        List<Expression> es1 = new ArrayList<Expression>(c1.terms);
        int different = 0;
        int mergeIndex = -1;
        for (int i=0; i<es0.size(); i++)
        {
            Expression e0 = es0.get(i);
            Expression e1 = es1.get(i);
            if (!e0.equals(e1))
            {
                mergeIndex = i;
                different++;
                if (different > 1)
                {
                    return -1;
                }
            }
        }
        return mergeIndex;
    }

    private static Rule merge(Rule r0, Rule r1, int index)
    {
        Conjunction c0 = r0.conjunction;
        Conjunction c1 = r1.conjunction;
        List<Expression> es0 = new ArrayList<Expression>(c0.terms);
        List<Expression> es1 = new ArrayList<Expression>(c1.terms);

        Set<Disjunction> rc = new LinkedHashSet<Disjunction>();
        for (int i=0; i<es0.size(); i++)
        {
            Disjunction d0 = (Disjunction) es0.get(i);
            Disjunction d1 = (Disjunction) es1.get(i);
            if (i == index)
            {
                Set<Expression> merged = new LinkedHashSet<Expression>();
                merged.addAll(d0.terms);
                merged.addAll(d1.terms);
                Disjunction d = new Disjunction(merged);
                rc.add(d);
            }
            else
            {
                rc.add(d0);
            }
        }
        return new Rule("TRUE", new Conjunction(rc));
    }

    private static Set<String> setOf(String ... s)
    {
        return new LinkedHashSet<String>(Arrays.asList(s));
    }

    static class Expression
    {
    }

    static class Variable extends Expression
    {
        final String name;

        Variable(String name)
        {
            this.name = name;
        }

        @Override
        public String toString()
        {
            return name;
        }

        @Override
        public int hashCode()
        {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((name == null) ? 0 : name.hashCode());
            return result;
        }

        @Override
        public boolean equals(Object obj)
        {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Variable other = (Variable) obj;
            if (name == null)
            {
                if (other.name != null)
                    return false;
            }
            else if (!name.equals(other.name))
                return false;
            return true;
        }

    }

    static class Disjunction extends Expression
    {
        private final Set<Expression> terms;
        Disjunction(Collection<? extends Expression> expressions)
        {
            this.terms = new LinkedHashSet<Expression>(expressions);
        }
        @Override
        public String toString()
        {
            StringBuilder sb = new StringBuilder();
            sb.append("(");
            int n = 0;
            for (Expression e : terms)
            {
                sb.append(e);
                n++;
                if (n < terms.size())
                {
                    sb.append(" + ");
                }
            }
            sb.append(")");
            return sb.toString();
        }
        @Override
        public int hashCode()
        {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((terms == null) ? 0 : terms.hashCode());
            return result;
        }
        @Override
        public boolean equals(Object obj)
        {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Disjunction other = (Disjunction) obj;
            if (terms == null)
            {
                if (other.terms != null)
                    return false;
            }
            else if (!terms.equals(other.terms))
                return false;
            return true;
        }
    }

    static class Conjunction
    {
        private final Set<Expression> terms;
        Conjunction(Collection<? extends Expression> expressions)
        {
            this.terms = new LinkedHashSet<Expression>(expressions);
        }
        @Override
        public String toString()
        {
            StringBuilder sb = new StringBuilder();
            sb.append("(");
            int n = 0;
            for (Expression e : terms)
            {
                sb.append(e);
                n++;
                if (n < terms.size())
                {
                    sb.append(" * ");
                }
            }
            sb.append(")");
            return sb.toString();
        }
        @Override
        public int hashCode()
        {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((terms == null) ? 0 : terms.hashCode());
            return result;
        }
        @Override
        public boolean equals(Object obj)
        {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Conjunction other = (Conjunction) obj;
            if (terms == null)
            {
                if (other.terms != null)
                    return false;
            }
            else if (!terms.equals(other.terms))
                return false;
            return true;
        }
    }

    private static class Rule
    {
        Conjunction conjunction;
        String action;

        @SafeVarargs
        Rule(String action, Disjunction ... disjunctions)
        {
            this.action = action;
            this.conjunction = new Conjunction(Arrays.asList(disjunctions));
        }

        Rule(String action, Conjunction conjunction)
        {
            this.action = action;
            this.conjunction = conjunction;
        }

        @Override
        public String toString()
        {
            return conjunction+" -> "+action;
        }
    }
}

- Marco13

这样做是行不通的，因为你无法隔离输入参数的域。例如，在“规则3”中，“绿色”只会与木材和中等材料组合匹配。 - Jurriaan

正如评论中所提到的：提供更多细节可能会更有帮助。因此，必须假设存在或不存在100^10个可能的规则中的每一个，且指定了1000个涵盖整个域的规则 - 这正确吗？ - Marco13

您说的“覆盖整个域”的意思是什么？可能的输入方式有 100^10 种（已将此添加到描述中）。规则不需要涵盖每种组合。当没有规则匹配时，将始终执行默认操作。 - Jurriaan

我认为你提到的“应用复杂的优化和最小化”是解决这个问题高效的唯一途径？ - Jurriaan

1

布尔表达式最小化问题是NP难的，因此它本身和一般情况下都没有解决方案 - 我认为这可能暗示你的问题根本没有有效的解决方案。但由于我几乎无法想象在GUI中手动编辑具有10个参数和100个值的1000个规则，因此必须假设在现实中，该问题比您现在所述的要受到更多限制。例如：您是否真的有1000个形如 (99个值，99个值，...（10次）...，99个值) 的不同规则？如果是这样，我猜你运气不好了... - Marco13

显示剩余6条评论

1

每个规则都代表一个布尔条件。你的规则符号有多灵活并不太清楚（例如，我能否使用“非Wood”？），但Rule 1似乎表示为：

   Color==Red and (Material==Wood or Material==Glass) and Size==Large

您可能还有一些“领域限制”，C(k)，大概是以下形式：

   Color==Red ==>  Not(Color==Green)

其中 ==> 是逻辑蕴含运算符。

大致上，您想知道的是对于某些 i 和 j，其中 R(i) 表示 "第 i 条规则"：

   R(i) ==> R(j)

实际上，您需要知道以下内容是否为真：

   R(i) and C(1) and C(2) and ... C(K) ==> R(j)

你可以（也必须）通过进行布尔代数来解决这个问题。实际上，这相对容易做到，例如将整个方程（包括蕴含运算符）作为一个实际的符号公式，并应用布尔代数定律。

让我们从代数的角度来解决你的例子（较长）。

首先，对于你的规则系统示例，域约束C(i)如下：

  Color==Red ==> Not(Color == Green)
  Color==Red ==> Not(Color == Blue)
  Color==Blue ==> Not(Color == Green)
  Color==Blue ==> Not(Color == Red)
  Color==Green ==> Not(Color == Red)
  Color==Green ==> Not(Color == Blue)
  (Color==Red or Color==Blue or Color===Green) <==> true   [if only these 3 colors exist]

同样地，对于材料（木材、玻璃、铝）和尺寸（小、中、大）也是如此。

对于您的具体示例，R（1）为：

  Color==Red and (Material==Wood or Material==Glass) and Size==Large

而 R(4) 是：

  Color==Red and (true) and Size==Large

你想知道的是是否：

  R(1) and <domainconstraints> ==> R(4)

这是一个相当庞大的公式，但这只是对计算机而言的问题。在这种情况下，我们不需要域限制（我作为神谕说话），所以我会把它省略掉以消除庞大性：

  R(1) and true ==> R(4)

或者只是

  R(1) ==> R(4)

（实现提示：在尝试R(i)和==> R(j)之前，您可以始终先尝试R(i) ==> R(j)，因为前者意味着后者。如果检测到冗余信息，则可以使用此方法来保持术语大小）。

“a ==> b”运算符在布尔逻辑中等同于“~a或b”，因此您需要知道此公式是否为真：

  Not(R(1)) or R(4)

插入R（1）和R（4）的定义：

  Not(Color==Red and (Material==Wood or Material==Glass) and Size==Large) or (Color==Red and (true) and Size==Large)

使用德摩根定律并简化“and（true）”：

 Not(Color==Red) or Not( (Material==Wood or Material==Glass) ) or Not( Size==Large)  or Color==Red and Size==Large

再次运用德摩根定律（实际上我们并不需要这样做，因为Redness将决定答案，但我们还不知道这一点）：

 Not(Color==Red) or Not(Material==Wood) and Not(Material==Glass) or Not(Size==Large)  or Color==Red and Size==Large

一个事实：

 a and b ==> a

所以，对于任何b，

 a and b or a == a

使用此功能时，a 为 Not(Color==Red)，b 为 Size==Large：

 Not(Color==Red) and Size==Large or Not(Color==Red) or or Not(Material==Wood) and Not(Material==Glass) or Not(Size==Large)  or Color==Red and Size==Large

现在我们将类似项分组：

 Not(Color==Red) and Size==Large or Color==Red and Size==Large or Not(Color==Red) or or Not(Material==Wood) and Not(Material==Glass) or Not(Size==Large)

组合尺寸为Large的术语：

 ( Not(Color==Red) or Color==Red) and Size==Large Not(Color==Red) or Not(Material==Wood) and Not(Material==Glass) or Not(Size==Large)

使用a或者~a == true:

 ( true ) and Size==Large or Not(Color==Red) or Not(Material==Wood) and Not(Material==Glass) or Not(Size==Large)

简化和分组尺寸术语：

 (Size==Large or Not(Size==Large)) or Not(Color==Red) or Not(Material==Wood) and Not(Material==Glass)

给予（呼）

(true) or ...

这段文字的意思是，由于 R(1) 产生了 true 的结果，因此 R(1) ==> R(4)，因此 R(4) 是多余的。

实现方法（或 TL;DR）

显然，你不想手动完成这个过程。你可以将公式编码为布尔表达式（你已经做过这样的事情以便能够在系统中存储它们）。你想知道的是，这个语句作为一个整体是否是重言式；对于这一点，你可以使用王炜的推理规则。这有点笨拙，但可行。

二元决策图（BDD）（一个可怕的名称）是一种编码公式“真值表”的方法。你想知道的是，一种公式的真值表是否总是为真。正如其他帖子中指出的那样，你可以使用 BDD 包。如果你为这个蕴含式建立 BDD，并且它在任何地方都是“TRUE”（也就是说，你得到了一个平凡的 BDD），那么这个蕴含式是真的，你就有了一个冗余项。

检查这可能需要很长时间。您可以忍受这种开销，或者只是对每次尝试给出多少CPU设置一个上限；无论它产生“无冲突”，“冲突”或“超时”的答案，都将“超时”解释为“无冲突”。然后，您可以使其运行尽可能快，除了有时不会消除冗余规则。

由于您的规则是独立声明的，如果您有N个规则，则需要大约进行N^2次测试。（好消息是，如果您已经建立了可信的N个规则的数据库，则添加新规则仅需要N次测试）。

- Ira Baxter

请看我的BDD实现github链接。免责声明：这是我第一次使用BDD... - Jurriaan

我明白了。它的想法是正确的，即为每个规则建立一个BDD。一个令人困惑的问题是，我不知道如何在“ValueList”中表示您的单个公式；根据您在问题中的示例，我期望等价于“合取范式”，例如一系列“OR”项。从几个方面来看，实现看起来有问题：1）您为规则构建的BDD组装应该建立一个单独的OR项列表，然后用AND组合它们；您似乎建立了一堆OR，但我看不到它们的列表。... - Ira Baxter

你要把所有规则都连接起来; 我认为每条规则都需要一个BDD。
你的冗余比较是“所有规则一起等于这个规则”; 你想要的是“任何规则是否蕴含这个规则”? 你可以使用“~ a或b”的布尔等效来实现“a ==> b”。

- Ira Baxter

我认为你需要领域限制，但它们似乎不在视野范围内。你最大的问题将是理解你构建的BDD作为公式的真正含义；实现“BDD到等效规则”的打印机值得你花时间；BDD包应该有一种方法来拆分BDD，以便您可以检查各个部分并打印它们的含义。我不了解这个包。作为你的第一个尝试，它还不错。现在你可以学习如何正确使用它。

- Ira Baxter

让我们在聊天中继续这个讨论。 - Jurriaan

显示剩余8条评论

1

一种可能性是使用二元决策图。这些可以有效地操作布尔公式。正如其他人所提到的，您可以将规则视为二进制公式：规则1为(r OR (w AND g) OR l)，规则2为(r AND a AND l)，为了确定规则4是否冗余，我们需要检查(Rule4 AND (NOT (Rule1 OR Rule2 OR Rule3)))是否有解。此外，需要使用类似(NOT (w and g))的子句来禁止无效输入。有许多求解器可用，虽然不能保证运行时间或内存使用不会爆炸，但它们通常非常适用于实际输入。

- Falk Hüffner

我会研究一下BDD，这对我来说还很新。有没有关于Java的求解器建议？这个怎么工作呢？我不知道你说的“是否有解”。 - Jurriaan

我实际上还没有尝试过任何Java求解器。 "有解"意味着存在一种对布尔变量的赋值，使得公式的计算结果为真。 - Falk Hüffner

请查看我的BDD实现，位于github。免责声明：这是我第一次使用BDD... - Jurriaan

0

首先，让我们来看一下你的例子，而不是使用**ANY**，我们把所有选项都放进去。

       +---------------------------------++--------------
       |         Rule Parameters         || Rule Action
       +----------+-----------+----------++--------------
       | Color    | Material  | Size     || Price
       +----------+-----------+----------++--------------
Rule 1 | R        | W,G       | L        || $100
Rule 2 | R        | A         | L        || $200
Rule 3 | B,G      | W         | M        || $300
Rule 4 | R        | A,W,G     | L        || $400
Rule 5 | R,B,G    | A,W,G     | S,M,L    || $500

下一步，我们需要定义什么样的规则可以被视为冗余，以下是我的定义：

引用：引用：一条规则如果等于除自身之外的任意k条规则的合并，则被视为冗余。

根据这个定义（注意：其中1 ≤ k < n，其中n为规则数），我们可以看出查找所有冗余规则将花费很多时间。

所以，如果我们的规则集中有100条规则，这种暴力搜索法将花费大约n^3 * n！即100^3 * (1! + 2! + .. + 100!) = 10^6 * 9.4 * 10^158 = 9.333 * 10^164的时间。

以下是我版本的暴力检查算法，它的时间复杂度为O(n^3 * SUM { k! | k = 1..n } )：

boolean isRedundant (RuleList R, Rule d)
{
    // R is the set of rules
    // T is a copy of the set, without the rule to be checked
    // d is the rule to be checked

    T = new RuleList(R);
    T.remove(d);

    for (int i=0; i<T.size(); i++) // check single rules
        if (T.get(j).equal(d))
            return true;

    for (int k=1; k<R.size(); k++) // 1 <= k < n
    {
        // merge every k-permutation to check
        for (RuleList permutation : T.getPermutations(k))
        {
            Rule r = new Rule ();

            for (Rule p : permutation)
                r.merge(p);

            if (r.equal(d))
                return true;
        }
    }

    return false;
}

类规则

class Rule
{
    public boolean [3] color; // R,G,B
    public boolean [3] material; // A,W,G
    public boolean [3] size; // S,M,L

    public Rule ()
    {
        color = { false, false, false };
        material = { false, false, false };
        size = { false, false, false };
    }

    public void merge (Rule r)
    {
        color[0] = and(color[0], r.color[0]);
        color[1] = and(color[1], r.color[1]);
        color[2] = and(color[2], r.color[2]);

        material[0] = and(material[0], r.material[0]);
        material[1] = and(material[1], r.material[1]);
        material[2] = and(material[2], r.material[2]);

        size[0] = and(size[0], r.size[0]);
        size[1] = and(size[1], r.size[1]);
        size[2] = and(size[2], r.size[2]);
    }

    public boolean equal (Rule r)
    {
        return (color[0]==r.color[0]
                  && color[1]==r.color[1]
                  && color[2]==r.color[2]
                  && material[0]==r.material[0]
                  && material[1]==r.material[1]
                  && material[2]==r.material[2]
                  && size[0]==r.size[0]
                  && size[1]==r.size[1]
                  && size[2]==r.size[2]);
    }

    public boolean and(boolean a, boolean b)
    {
        return (a && b);
    }
}

替代方案

假设我们有表示每个参数的集合，那么我们可以将要检查的规则数量从总规则数量中减少，并且这可以优化时间复杂度，因为我们将从那个角度看到所有成员都是一个。然后通过简单的匹配算法进行匹配。

       +---------------------------------++--------------
       |         Rule Parameters         || Rule Action
       +----------+-----------+----------++--------------
       | Color    | Material  | Size     || Price
       +----------+-----------+----------++--------------
Rule 1 | R        | W,G       | L        || $100
Rule 2 | R        | A         | L        || $200
Rule 3 | B,G      | W         | M        || $300
Rule 4 | R        | A,W,G     | L        || $400
Rule 5 | R,B,G    | A,W,G     | S,M,L    || $500

我们有以下内容：

Color_R = { 1, 2, 4, 5 }
Color_B = { 3, 5 }
Color_G = { 3, 5 }

Material_A = { 2, 4, 5 }
Material_W = { 1, 3, 4, 5 }
Material_G = { 1, 4, 5 }

Size_S = { 5 }
Size_M = { 3, 5 }
Size_L = { 1, 2, 4, 5 }

现在，对于每个规则，我们取其参数集，然后进行匹配，而不考虑相同的规则..

例如：

Rule_4 = { Color_R, Material_A, Material_W, Material_G, Size_L }

Color_R    = { 1, 2, x, 5 }
Material_A = { 2, x, 5 }
Material_W = { 1, 3, x, 5 }
Material_G = { 1, x, 5 }
Size_L     = { 1, 2, x, 5 }

我们检查匹配所有成员资格的一组规则：

Matched = { 5, 1+2 }

然后我们将它们与所选规则进行比较，通过集合差异查找phi：

Rule_5 - Rule_4 = { Color_B, Color_G, Size_S, Size_M }

> Rule_5 does not match

(Rule_1 + Rule2) - Rule_4 = { }

> (Rule_1 + Rule2) match

最后，我们总结：

(Rule_1 + Rule2) = Rule_4

> Rule_4 is redundant

- Khaled.K

规则的内部数据结构是什么？merge实现将如何合并规则2和3？ - Jurriaan

1

嗯，不太确定。但是如果你有规则A、B、C、D，并且想要检查D是否多余，你需要检查D是否被A、B、C、A+B、A+C等所暗示（等等）。但是在你检查了它是否被A+B所暗示之后，你就不必再检查它是否被B+A所暗示（顺序无关紧要）。但也许我在这里误解了什么。 - Marco13

无论如何，我正在寻找一种更聪明的方法来解决这个问题，就像@Marco13提到的“应用复杂的优化和最小化”一样。 - Jurriaan

1

问题在于有两种方法来解决这类问题。一种是从空集开始，尝试找到多余的规则；另一种是从所有规则的集合开始，尝试确定哪些规则是必需的，然后验证所有剩余的规则是否实际上是多余的。第一种方法具有指数增长，而第二种方法则没有，因为您可以快速检查当规则组合在一起时是否等于正在考虑的规则。 - Nuclearman

1

@KhaledAKhunaifer：备选方案看起来不错，基本上与我在答案中使用的相符。但是，您如何将规则3排除为可能性可能更清晰。我认为您无法获得指数增长，但根据算法中步骤的处理方式，您可能会得到不正确的解决方案。在我的意见和答案中，应删除规则3，因为集合包含不在考虑规则中的元素。也就是说，((规则3) - (规则4))不是空集。 - Nuclearman

显示剩余5条评论

0

这个问题中规则的数量相当大，但是数值的数量有限。因此，我认为逐条评估规则不会给出最快的结果。如果按值将规则分组，则可以同时评估多个规则。我想出的算法仍然可能会爆炸，但我希望这种情况不太可能发生。

示例数据：

Rule #: [Color (R,G,B),Material (W,G,A),Size (S,M,L)]
Rule 1: [[1,0,0],[1,1,0],[0,1,0]]
Rule 2: [[1,0,0],[0,0,1],[0,1,0]]
Rule 3: [[0,1,1],[1,0,0],[0,0,1]]
Rule 4: [[1,0,0],[1,1,1],[0,1,0]]
Rule 5: [[1,1,1],[1,1,1],[1,1,1]]

（从Nuclearman复制）

步骤1：按参数1的值拆分规则

按参数1的值将规则分组到一个集合中。可能需要一种启发式来选择最佳的第一个参数。现在我只是按顺序选择它们。

Result:
Rules in Set R: 1,2,4,5
Rules in Set G: 3,5
Rules in Set B: 3,5

步骤2：合并相同的集合

在此级别，集合G和B包含相同的规则，因此可以合并。

Result:
Rules in Set R: 1,2,4,5
Rules in Set GB: 3,5

步骤三：按参数2的值拆分组

现在，对于所有集合，规则都是基于参数2进行检查。对于每个不同的值，集合被拆分成子集。第二步的集合已不再相关。

Result:
Rules in Set (R ,W): 1,4,5
Rules in Set (R ,G): 1,4,5
Rules in Set (R ,A): 2,4,5
Rules in Set (GB,W): 3,5
Rules in Set (GB,G): 5
Rules in Set (GB,A): 5

步骤4：删除单个规则

现在已经证明规则5是相关的。它单独捕捉到(G,G,*), (B,G,*), (G,A,*)和(B,A,*)。可以从评估中删除集合(GB,G)和(GB,A)，因为它们已经没有什么可证明的了。

步骤5：合并相等的集合

Result:
Rules in Set (R ,WG): 1,4,5
Rules in Set (R ,A ): 2,4,5
Rules in Set (GB,W ): 3,5

步骤3：按参数3的值拆分组

Result:
Rules in Set (R ,WG, S): 5
Rules in Set (R ,WG, M): 1,4,5
Rules in Set (R ,WG, L): 5
Rules in Set (R ,A ,S): 5
Rules in Set (R ,A ,M): 2,4,5
Rules in Set (R ,A ,L): 5
Rules in Set (GB,W ,S): 5
Rules in Set (GB,W ,M):5
Rules in Set (GB,W ,L): 3,5

规则5已被证明是有用的，不需要计算规则序列。1、2、3已经被证明是最高优先级的集合中的一部分。规则4从未被证明，并且是多余的。

现在是伪代码：

    void getProven(RuleList rulelist, RuleList provenlist, ParameterIterator i)
    {
        ValuesToRulelistMap subsets = new ValuesToRulelistMap(); 
        Parameter parameter = i.next();
        for (Rule rule : rulelist) {
            Valuelist valuelist = rule.getValuesByParameter(parameter);
            for (Value value : valueslist) {
                subsets.addToListInMap(value, rule);
            }
            KeyList doneKeys = new KeyList();
            for (RuleList subset : subsets.getRuleLists()) {
                if (subset.length == 0) {
                    // No rule for this case!!!
                } else 
                if (subset.length == 1) {
                    // Singly proven
                    provenlist.add(subset.getFirst());
                } else
                if (!i.hasNext()) {
                    // Proven by priority
                    provenlist.add(subset.getFirst());
                } else
                    Key key = subset.combineRulesInListToKey()
                    if (!doneKeys.containts(key)) {
                        getProven(subset, provenlist, i);
                        doneKeys.add(key);
                    }
                }
            }
        }
    }

- Eelco

我使用这种方法作为我发布的算法的垫脚石。问题在于，当有10个参数和每个参数100个值时，很可能会出现爆炸性问题。与你所想的“合并相等部分”相比，你也会得到更少的好处。在1000个规则中拥有完全相同的规则集的概率极低。因此，这种方法可能是O(V^P)，其中V是平均值的数量（100），而P是参数的数量（10）。我通过针对特定规则进行测试来解决了这个问题，这使你可以忽略不是该规则子集的规则。 - Nuclearman

我曾希望子集会很小（在有许多不同的单个值的情况下），或者集合会合并很多（在有许多任意元素的情况下）。但是，“每条规则的线性成本”听起来更好。 Nuclearman，您能否提供您算法的完整伪代码？ - Eelco

很遗憾，我的Java语言已经有些生疏，而且似乎无法想出一种我满意的Java伪代码。因此，我将我的Pythonic伪代码扩展成了实际的Python解决方案。我说在规则数量上是线性的，但更准确地说是在元素数量上是线性的。即O(R * P * V)，其中R是规则数量（预计1000个），P是参数数量（预计10个），V是每个规则的值数量（预计100个）。虽然在实现中有一些优化可以提高性能。 - Nuclearman

很好。虽然应该是每个参数的值而不是每个规则的值，但最终结果是相同的。 - Nuclearman

0

在强类型函数语言中，模式匹配领域有大量的工作。甚至在 stackoverflow 上也谈到了它的实际含义。

Luc Maranget 的出版页面包含了许多关于该主题的文章，这些文章在不同的环境中都起到了 OCaml 模式匹配算法的基础作用。

他关于将模式匹配编译为良好决策树的论文可能是您问题的最终灵感来源。它还提供了有关同一主题的先前文章的参考资料。其基本原则是将模式匹配集描述为整数矩阵，并进行代数运算。

我也强烈推荐尝试 OCaml 或任何 SML 实现，以感受 ML 语言家族的核心特性。你可能也会对 Scala 感兴趣，它实现了类似的功能。

- didierc

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dan.m was user2321368 · Accepted Answer

基本上，您的任务是实现决策树。每个层级对应一个参数，每个层级都会有一个节点，对应该参数可能具有的每个值。在叶子层，您将存储适用的规则操作。

例如，在颜色级别上，您将拥有3个节点：红色、蓝色、绿色。每个节点都有3个子节点（在材料级别上）：木材、玻璃、铝。每个节点都有3个子节点（小、中、大）。您将根据从数据库中学习到的参数和值构建此树。

构建完树之后，您将一次读取数据库中的规则，并在每个叶子处存储“规则操作”（在本例中为尺寸级别）。如果有一个规则想要应用于已经有动作的叶子上，则存在哪个规则适用的歧义。对于您的问题，您说您将采取第一个适用的规则-因此您不会更改存储的规则。

如果有一条规则，对于每个叶子它都已经有了定义的动作，那么根据您的示例，该规则将是“冗余”的。