алгоритм поиска в ширину для решения системы логических уравнений

Question

Я пытаюсь найти решение проблем, как в следующем примере:

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

Сколько переменных истинно, а сколько ложно?Насколько я узнал, я должен попытаться использовать поиск в ширину, но моя проблема в том, с чего начать, и в том, что граф будет ориентированным (я подключаю xi к !xj, где существует равенство).Может ли кто-нибудь указать мне правильное направление?

Answer 1

Это проблема раскраски графа.Вершины: A, B, C, … Edge (u, v) в этом неориентированном графе присутствует тогда и только тогда, когда u != v.

2-раскраска является одним из применений поиска в ширину.Смотри: http://en.wikipedia.org/wiki/Breadth-first_search#Testing_bipartiteness

Answer 2

Я не думаю, что вам вообще нужен поиск. Рассмотрим ваши ограничения как граф, соединяющий вершины xi и xj, если есть ограничение xi =! Xj. Возьмем связную компоненту графа (то есть ту, где существует путь, соединяющий каждую пару вершин). Предполагая, что ваши ограничения согласованы (т.е. не указывайте одновременно xi = xj и xi =! Xj), вы можете выбрать любую вершину xi в компоненте и сразу определить, равна ли любая связанная вершина xj xi или! Xi. После этого можно просто выполнить задания, необходимые для максимизации или минимизации количества истинных переменных.