广度优先搜索算法用于解决一组逻辑方程

4
我将尝试构思解决以下示例中出现的问题的解决方案:
A != B
B != C
D != B
C != B
E != D
E != A

有多少变量是真的,有多少是假的?据我所知,应该尝试使用广度优先搜索,但我的问题是从哪里开始以及图将是一个定向图(我将xi连接到!xj,其中存在等式关系)。有人能指点我方向吗?


这是问题的续篇:https://dev59.com/LVfUa4cB1Zd3GeqPFTDA 和 http://stackoverflow.com/questions/6003098/boolean-system-for-c-c-java - forsvarir
你误解了解决方案。它不会是一个有向图。!xj 不会是一个节点,xj 才是。 - Aryabhatta
2个回答

5

0

我认为在这里根本不需要搜索。将您的约束条件视为一个图,将顶点xi和xj连接起来,如果有一个约束条件xi =!xj,则连接它们。选择图的一个连通分量(即,存在一条路径连接每对顶点)。假设您的约束条件是一致的(即,不同时指定xi = xj和xi =!xj),则可以选择组件中的任何顶点xi,并立即确定任何相连的顶点xj是否等于xi或!xi。然后很容易计算出所需的分配,以最大化或最小化真变量的数量。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接