用于确定表达式中哪些变量不是确定答案所必需的算法

Algorithm to determine which variables in an expression aren’t necessary to determine the answer

提问人：Mike Pennington 提问时间：10/29/2017 更新时间：10/29/2017 访问量：93

问：

我正在做一个遍历决策树的项目。决策树中的每个节点都有一个公式，该公式可以包含多个变量并且相当复杂。应用程序要求用户逐个输入变量的值。

申请的两个要求是：

  1. 应用程序必须要求用户按照变量在表达式中出现的顺序回答变量。
  2. 应用程序必须跳过确定答案不需要的任何变量。

如果语句的格式为：

if(expression;pass;fail)

例如，请考虑以下表达式：

if((a=1&b=1)|(c=1&d=1&e=1)|f=1;1;2)

如果我们已经知道 a=1 和 b=1，那么无论 c、d、e 和 f 的值如何，我们都知道答案将是 1。因此，无需要求用户输入这些变量的值。

这些表达式可能相当复杂，包含多个比较运算符和嵌入的 if。例如：

if(a>1;if(b<5;1;if(c=2;2;0));if(d!=2;if(e=1;1;if(f=2;2;0));0))

我很难想出一种算法来有效地做到这一点。是否有现有的算法来决定哪些变量在给定表达式中无关紧要？或者也许只是一种思考问题的新方式，可能会对我有帮助？

算法 逻辑 代数

评论

0赞 rici 10/29/2017
从左到右修剪表达式很容易。更有趣的案例：（1）我们已经知道了。我们是否立即计算而不要求？（2） 我们知道并且都是 1.我们要求吗？似乎答案应该是“是”和“否”......f=11acde
0赞 Patrick87 10/29/2017
在我看来，一个有效的算法就是一个有效的布尔表达式满足性算法。如果这是正确的，您可能不走运，因为这是 NP-Complete。
0赞 Mike Pennington 10/29/2017
@rici 从左到右修剪是什么意思？对于您提出的情况，在情况 （1） 中，它应该不问任何问题并计算 1。在情况 （2） 中，它应该问 a 并从左到右继续。
0赞 Mike Pennington 10/29/2017
@Patrick87 这也是我的结论（尽管我承认我不知道技术术语）。我应该能够通过测试所有比较的每个真/假组合来解决这个问题，但这是指数级的低效。也许我可以提前运行通用路径，并将这些知识缓存到运行时。
1赞 rici 10/31/2017
每个比较要么有一个已知值，要么没有已知值，因此有三个可能的值：true、false、unknown。未知值不会变得已知（除非有您没有提及的副作用），因此没有什么可说的。布尔运算符可以用这种三元方式计算，因此“true and unknown”（例如）是“unknown”，而“true or unknown”是“true”，而“false and unknown”是false。

答：

0赞 sigh 10/29/2017 #1

如何构建语法树？

enter image description here

正如你所看到的，文字数字被认为是已解决的。每当用户为变量提供值时，相应的 leaves 节点就会解析为该值。然后遍历树解析值，直到无法解析更多节点。如果到达根节点，则可以确定答案。

enter image description here

编辑：表达式可以表示为三元运算符节点（有三个子节点）。如果已解析为 和 为某个值，则此表达式解析为 。情况也是如此.if(e1;e2;e3)e1truee2vve1=false

上一个：如何在 Python 中从 '[1， 1， 0， 0， 0] == [0， 0， 1， 1， 0]' 中获取“True”？

下一个：布尔逻辑 - 如何确定布尔语句列表中是否只有一个布尔值为真