Генерация булевского выражения

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
ezus
Сообщения: 4
Зарегистрирован: 28 июл 2009, 17:30

Ищу алгоритм или хотя-бы идею алгоритма для ршения следующей задачи:

На входе имеется дерево, у которого листья – булвские переменные(могут повторяться), а остальные вершины – булевские операторы типа AND, OR, NOT OR, XOR и тп.
Мне надо свернуть это дерево в вырожение, содержащее только AND, OR и NOT.

К сожалению подходящий стандартный алгоритм мне неизвестен.

На первый взгляд сам алгоритм не представляется очень сложным:
- рекурсия сверху вниз
- наверх поступает выражение как бы в скобках
- раскрытие скобок

Проблема возникает при возрастании размерностей.

В данный момент у меня основная проблема с оператором AND.
Алгоритм примитивный – реализует декартого произведение термов и представляет из себя 3 вложенных цикла:
Первый – перебор термов в первом операнде
Второй – перебор термов в втором операнде
Третий – перемножение двух текущих термов.

При размерностях выражений в сотни тысяч термов машина засыпает напрочь.

Буду рад любым идеям.
Ответить