c++ - 检查是否满足任意不等式列表

Question

我正在用 C++ 编写一些代码，需要检查两个未知变量中的不等式列表是否得到满足。

例如，一个可能的列表可能是 P = Q, Q < S, P = S 不应该满足

另一个例子，P = Q, Q < S, R = P, S > R 应该满足

我已经想了很长时间，但我似乎找不到任何方法，除了一个冗长乏味的方法，它涉及检查每个添加的新不等式是否满足所有以前的不等式。

Answer 1

与 C++ 相比，这更像是布尔逻辑的练习。如果您知道 Python，请使用它。

一种更快的方法是一次构造一个“排序”（在数学意义上）一个语句。那就是你有一个序列的地方， abc 假设和 a

假设现在序列中的每个事物都是彼此相等的事物的向量。在上面的例子中：

P=Q

我们的订购看起来像：

[P,Q]

下一个 Q

所以现在我们有一个订单：

[P,Q],[S]

我们知道 [P,Q]<[S]

所以 P=S 是一个明显的矛盾。

Answer 2

首先，P = Q通过将所有出现的 替换为Q删除所有等式P。这减少P = Q, Q < S, R = P, S > R到R < S, S > R。

其次，如果您的列表包含或，则构建一个以变量为顶点和从P到的边的有向图。QP < QQ > P

第三，检查图形是否包含循环。如果图不包含环，则不等式是可满足的。

您可能想在谷歌上搜索与此问题相关的 2-SAT。