代码之家 › 专栏 › 技术社区 › Shawn Chin

给定一组条件,算法上只确定一个条件是真的

condition logic validation language-agnostic algorithm

Shawn Chin · 技术社区 · 14 年前

给定一组两个或多个逻辑条件,是否可以通过算法确定其中一个条件的计算结果为真?例如:

# this should pass, since for every X, only one condition is taken
cond 1: (X >= 1.0) 
cond 2: (X < 1.0)

# this should fail
cond 1: (X < 1.0)
cond 2: (X > 2.0)

# this should also fail, since X=1.0 would meet both conditions
cond 1: (X < 2.0)
cond 2: (X > 0.0)

# there may be more than one variable involved
cond 1: (X >= 1.0 && Y >= 0)
cond 2: (X < 1.0 && Y <= -1)

这些条件由特定于域的语言生成,用于确定下一个执行路径。也就是说,当执行树拆分为多个路径时,用户为每个选项组合一个条件,并且计算结果为真的条件确定要采用的路径。为了使模拟有效,对于任何给定的值,这些应该只是一个可能的路径。

目前,我在运行时评估这些条件,如果其中有一个(或没有一个)以上是真的,我就会发脾气。

我希望能够在解析阶段(从域语言到可编译源代码)检查错误情况。有可能吗?如何验证这些条件?

更新

至于条件中可以包括哪些内容,在实践中范围相当广泛。所有这些都是可能的条件:

X >= Y && Y < Z
X.within_radius(0.4)
X IN some_array
X * Y < Z

最后更新

似乎解决方案涵盖了所有可能的条件是不可能的(或者至少,考虑到我有限的知识,在分配给问题的时间内是不可能的)。总有一天会重温这一点,但现在我接受了最能让我前进的答案。

4 回复 | 直到 14 年前

Gian 14 年前

编辑:我要重申一下,因为其他答案似乎都假设了一系列已经确认的事情:

如果你能用以下的方式陈述你的条件(以及只有一个是真的约束条件) Presburger arithmetic ,然后可以编写一个决策过程来静态验证该属性。从上面的例子看来,这是完全可以实现的。

“Blunt Instrument”方法基本上是与自动定理证明器或SMT解算器(在这里,您将尝试证明语句“存在满足constraint1 x or constraint2的某个值x”)的否定。我以编程方式与 CVC3 以前,我发现和它合作很好,但我的理解是,它已经被其他SMT解决方案所超越。

我认为,你为解决这个问题所做的任何其他事情,最终都可能接近于我所建议的一些工具的实现。根据具体的约束是如何指定的,您可能可以不必为诸如普氏算法 .

Eric Mickelsen 14 年前

一般来说,没有,但是如果你真正要问的是,给定一组有限的自变量和常量,由不相等的布尔逻辑组合构成的条件是否可能,那么就有希望了。您可以通过将变量与出现在不等式中的常量(以及这些常量的+1和-1)排列在一起,并验证保持为真的条件的数量始终为1来彻底检查。

Community Maksym Gontar 7 年前

如果您想找出是否只有一个条件是真的(两个或多个可能条件中的一个),可以参考下面的xor问题: xor-of-three-values . 直接从答案中得出:

(a ^ b ^ c) && !(a && b && c)

在你的情况下:

(cond 1 ^ cond 2 ^ cond 3) && !(cond 1 && cond 2 && cond 3)

还有一个通用的解决方案,当任何条件为真时,都要增加一个计数,然后在测试完所有条件后,对照1检查计数。

Frank 14 年前

你的基本条件是

一个整数变量,
中的比较运算符(<、<=、>、>=),
数字(假设为整数)?

最终条件是根据这些使用和

我们能假设所有的整数变量都是独立的吗?

在这些条件下,我假设它可以通过算法进行检查。我将把每个变量的所有有效范围放入一个数据结构中,并检查是否存在交集。

编辑:由于似乎不是这样,最好的解决方案可能是对不同类型的条件进行分组,以便对每个组中的条件进行静态评估。我从你的第一个描述中假定的条件类型将只是这些组中的一个。