CODEWITHSUNDEEP
algorithmlogic
DDD
DDD

Reputation: 171

breadth-first search algorithm for solving set of logic equations

I am trying to conceive a solution for problems like in the following example:

A != B
B != C
D != B
C != B
E != D
E != A

How many variables are true and how many are false? As far as I found out I should try to use breadth-first search, but my problem is where to start and the fact that the graph will be an oriented one (I am connecting xi to !xj where the equality relation exists). Can someone point me in the right direction?

Upvotes: 4

Views: 773

Answers (2)

Rafe
Rafe

Reputation: 5295

I don't think you need search at all here. Consider your constraints as a graph connecting vertices xi and xj iff there is a constraint xi = !xj. Take a connected component of the graph (i.e., one where a path exists connecting every pair of vertices). Assuming your constraints are consistent (i.e., don't simultaneously specify xi = xj and xi = !xj) then you can pick any vertex xi in the component and immediately work out whether any connected vertex xj is equal to xi or !xi. It's then straightforward to work out the assignments you need to maximise or minimise the number of true variables.

Upvotes: 0

Ivan Krechetov
Ivan Krechetov

Reputation: 19220

It's a graph 2-coloring problem. Vertices: A, B, C, … Edge (u, v) in this undirected graph is present if and only if u != v.

2-coloring is one of the applications of the breadth-first search. See: http://en.wikipedia.org/wiki/Breadth-first_search#Testing_bipartiteness

Upvotes: 5

Related Questions