所有 AND 条件的布尔表达式优化

Question

我正在尝试解决简单规则引擎的布尔表达式优化问题。

这是我正在尝试做的，假设我是否有以下 5 个条件(其中 a，b，c，d，e，f 是复杂的布尔表达式(

if (a AND b AND c AND d AND e AND f) then do-1 
if (a AND b AND c AND d AND e) then do-2 
if (a AND b AND c AND d) then do-3
if (a AND b AND c) then do-4
if (a AND b) then do-5

如果我以线性顺序执行这些条件，我将

- evaluate "a" for 5 times
- evaluate "b" for 5 times
- evaluate "c" for 4 times
- evaluate "d" for 3 times
- evaluate "e" for 2 times
- evaluate "f" for 1 time

我想从中创建一个表达式执行树，以便每个表达式(a，b，c，d，e，f(的计算次数最少。完美的解决方案是每个表达式仅计算一次。我认为这可以通过创建树来实现，其中所有这些条件都是树的一部分。

树可能看起来像这样

if(a AND b) then do-5  {
    if(c) then do-4 {
        if(d) then do-3 {
            if(e) then do-2 {
                if(f) then do-1 
            }
        }
    }       
}

我的问题是 - 如何从上面列出的布尔表达式集制作这棵树？

相关问题：

用于计算嵌套逻辑表达式的算法

将表达式转换为带有扭曲的合取范式

在 C# 中应用 DeMorgan 定理手动优化条件语句中的布尔表达式(例如 if 条件(是否有用

Answer 1

你可以这样处理它：

var booleans = [a, b, c, d, e, f];
var i = 0;
while(booleans[i]) i++;
switch(i) {
    case 0:
        // do something
        break;
    case 1:
        // do something
        break;
    ...
}

我很确定有一种方法可以将 while 循环与开关运算符合并，以从中获得更优化的东西。