Как эффективно реализовать бинарные диаграммы принятия решений (BDD)?

Question

Справочную информацию о бинарных диаграммах решений можно найти здесь BDD в википедии .

Самый простой подход - построить BDT (Binary Decision Tree), а затем уменьшить его из-за двух правил:
- Объединить любые изоморфные подграфы.
- Устранить любой узел, два ребенка которого изоморфны.
Но есть одна большая проблема, БДТ может быть действительно огромной по сравнению с БДД. Есть ли способ построить BDD без предварительного создания BDT?

Answer 1

Используйте алгоритмы Mk (make node) и Build (construct BDD) из Andersen , стр. 16-17. Я давно не играл с BDD, но я считаю, что H или T должны быть хеш-таблицами. Используйте оба хеш-таблицы, чтобы быть в безопасности.

Answer 2

Способ построения BDD - из дерева разбора для выражения, представляющего булеву функцию, которую вы пытаетесь построить.

Т.е., если вы хотите BDD для (A + B). (C + D), вы сначала анализируете (A + B). (C + D) в дерево:

   .
  / \
 +   +
/ \ / \
A B C D

затем рекурсивно создайте BDD - вам нужны методы, которые могут формировать И и ИЛИ двух BDDS, и базовый случай (одна переменная BDD).

Это работает так же хорошо и для логических схем (в виде разобранного DAG вместо дерева).

Эти примечания к BDD объясняют, как реализовать AND и OR, а также хеш-таблицы, которые необходимы для эффективной работы: http://bit.ly/cuClGe

Answer 3

Попробуйте прочитать Кнут, если вы хотите сделать все правильно.

https://www -cs-faculty.stanford.edu / ~ knuth /asc1b.ps.gz

Чтобы быть более точным, алгоритм «R», начальная страница 14 этой главы книги, является точным и полным ответом на ФП;

В целом главы книги Кнута являются очень хорошим справочным пособием, так случилось, что он написал один на (RO) BDD, который чрезвычайно удачливКто-нибудь серьезно пытается внедрить BDD.