Задать вопрос
@Raynemar

Как определить есть ли противоречия в цепочке логических выражений?

Есть список из n объектов
Каждый объект обладает значением (некое целое число) и списком свойств ограничивающих его возможное значение через сравнение с другими объектами в списке или сравнение с постоянными значениями
Например:
1. Объект 'a' : a >= 0. a > b. a <= c
2. Объект 'b' : b == f. b < c
3. Объект 'c' : c != f. c < d
4. Объект 'd' : d < e. d > 7
5. Объект 'e' : e < a
6. Объект 'f' : f > 12

Придумать алгоритм, который определит наличие или отсутствие противоречий
  • Вопрос задан
  • 225 просмотров
Подписаться 1 Средний 1 комментарий
Решения вопроса 1
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Алгоритм называется "обход в глубину на графе". Работает за линию, все очень быстро. Правда, его придется применить несколько раз.

Все неравенства "==" замените на пару "<=" и ">=".
Добавьте неравенства 1 < 2, 3 < 4 и т.д. для каждой пары соседних на числовой прямой чисел во входных данных

Постройте граф: Каждой переменной и уникальному числу во входных данных сопоставьте одну вершину. Проведите для каждого неравнества ребро от меньшей вершины к большей, раскрашенное в 2 цвета: черный, если неравнество нестрогое (<=), белый - иначе.

Теперь, если в этом графе нет циклов, содержащих белые ребра (строгие неравенства) - то противоречий нет: Все циклы целиком из черных ребер означают, что все вершины имеют одинаковое значение. Можно эти вершины все объединить в одну новую. Раз белые ребра (<) циклов не образуют, то получившийся граф будет ациклическим и можно назначить всем вершинам какие-то числовые значения, удовлетворяющие условиям. Проблема может еще быть, что нет целых решений вроде 1== a < b < c == 2, но это можно потом проверить в топологической сортировке жадно назначая всем вершинам числа. Или противоречия вида 2==3. Тоже решается после получения компонент связности.

Итак, алгоритм: найдите в этом графе компоненты сильной связности. Потом проверьте все ребра. Если белое ребро (строгое неравнество) имеет оба конца в одной и той же компоненте - вы нашли противоречие.

Теперь надо постараться назначить кадой компоненте числовое значение так, чтобы не было противоречий. Это можно делать жадно, назначая каждой компоненте минимально возможное значение.

Пройдитесь по компонентам в топологическом порядке (они в таком виде уже будут получены алгоритмом выше). Если в компоненте есть вершина-число, то назначаете всей компоненте это значение. Если есть несколько вершин-чисел - то это противоречие. Также посмотрите все обратные ребра из всех вершин в компоненте. Если они ведут в другую компоненту, то обновите минимально возможное значение в данной компоненте как равное, или на 1 большее уже известного значения для второй компоненты (в зависимости от цвета ребра, т.е. строгости неравнества). Если получили, что это минимально возможное значение больше уже фиксированного за счет вершины-числа - то вы нашли противоречие.

В конце вы получите для каждой компоненты ее численное значение без каких-либо противоречий.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
mayton2019
@mayton2019
Bigdata Engineer
Можно попробовать на Prolog написать. Правила (rules) известны. А в качестве утверждений - просто
проверить что существуют ли целые числа которые удовлетворяют всем rules.
Ответ написан
Комментировать
Griboks
@Griboks
Полный ленивый перебор. Разумеется, это сработает только на небольшом объёме данных.

Для большого, боюсь, придётся решать систему логических уравнений.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы