Частичная проверка сложного ряда условий

Question

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

Я мог бы реализовать это как крысиное гнездо операторов if / else, но это было бы кошмаром для удобства обслуживания, поскольку правила меняются довольно регулярно. Поскольку в графе нет циклов, я думаю, что некоторая форма подхода в ширину, вероятно, является оптимальной. Я на правильном пути? Существуют ли другие альтернативные методы для выполнения такого рода задач?

Answer 1

Похоже, вы пытаетесь решить общую проблему компиляции, называемую [постоянное свертывание] [1]. (http://en.wikipedia.org/wiki/Constant_folding).

Хорошая новость заключается в том, что она применяется к DAG (прямой ациклический граф), а не только к деревьям. По сути, идея состоит в том, чтобы вычислить то, что вы можете из частичных выражений. Такие простые вещи, как True AND X = X или True OR X = True, помогают обрезать большие части дерева. (Тривиальная реализация, о которой я знаю, это вопрос глубины и возврата назад, а не ширины, но в любом случае это не так уж много кода).

Мне все еще интересно, почему у вас есть график, а не дерево выражений. Если вы можете вычислить A из B или B из A, у вас обычно нет одновременно и A, и B в качестве входных данных. Тогда должна быть возможность выразить проблему как набор деревьев выражений в зависимости от доступных входных данных. Но это грубое предположение. Можете ли вы дать более подробную информацию (пример), почему у вас есть этот график?

Answer 2

Решение полностью зависит от того, что на самом деле представляет направленный ациклический граф (DAG), о котором вы говорите. Являются ли узлы И и ИЛИ узлами или они являются условными ветвями?

Если это условные ветви, вам не нужен поиск в ширину, потому что искать нечего; Вы просто берете ветки в соответствии с оцененными условиями. Да, это может быть легко реализовано как спагетти GOTO. Другой вариант - создать базу данных узлов (или структуру данных) и иметь «виртуальную машину», которая выполняется через узлы один за другим. Это делает его более легким в обслуживании, но также и более медленным.

Если это график И / ИЛИ / НЕ, вам нужно оценить истинные значения для узлов, начиная с листьев. Это не поиск в ширину, а своего рода обратный поиск в ширину. Вы вычисляете значения для листьев, а затем вычисляете значения внутренних узлов в обратном направлении; в конце концов вы получите оценку корневого узла (true / false).