Проверка выполнения списка произвольных неравенств
Я пишу некоторый код на C ++, и мне нужно проверить, удовлетворяется ли список неравенств в двух неизвестных переменных.
Например, одним из возможных списков может быть P = Q, Q < S, P = S, который НЕ должен удовлетворяться
Другой пример, P = Q, Q < S, R = P, S> R должно быть удовлетворено
Я долго думал, как это сделать, но я не могу найти какой-либо другой метод, то длинный, утомительную тот, который включает в себя проверку, если каждое новое неравенство добавлено удовлетворяет все предыдущие.
Решение
Это больше упражнение в булевой логике, чем в C ++. Если вы знаете, Python используйте его.
Более быстрым способом было бы создать «упорядочение» (в математическом смысле) по одному утверждению за раз. Вот где у вас есть последовательность, предположим,
Предположим теперь, что каждая вещь в последовательности является вектором вещей, равных друг другу. В приведенном выше примере:
Р = Q
Наш заказ выглядит так:
[Р, Q]Следующий вопрос
Итак, теперь у нас есть заказ:
[Р, Q], [S]Мы знаем [P, Q]<[S]
Так что P = S — очевидное противоречие.
Другие решения
Сначала удалите все равенства P = Q заменив все вхождения Q с P,
Это уменьшает P = Q, Q < S, R = P, S > R в R < S, S > R,
Во-вторых, построить ориентированный граф с переменными в виде вершин и ребром из P в Q если ваш список содержит P < Q или же Q > P,
В-третьих, проверьте, содержит ли график циклы. Неравенства выполняются, если в графе нет циклов.
Вы можете использовать Google для 2-SAT, что связано с этой проблемой.