Эвристика для оценки эффективности сокращенных упорядоченных двоичных диаграмм решений?
Сокращенные упорядоченные двоичные диаграммы решений (ROBDD) - это эффективная структура данных для логических функций от нескольких переменных f (x1, x2, .. ., xn) . Я хотел бы получить интуитивное представление о , насколько они эффективны.
Например, для сжатия данных мы знаем, что данные с низкой энтропией (некоторые символы появляются чаще, чем другие, много повторений) могут быть очень хорошо сжаты, в то время как полностью случайные данные не могут быть сжаты.
Есть ли аналогичная интуиция для оценки того, насколько эффективно ROBDD может представлять заданную булеву формулу? Есть ли литература по этой теме (желательно в Интернете)?
1 ответ
В статье Википедии Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams есть статья, в которой приводятся нижние и верхние границы для некоторых классов функций (симметричных, представляющих двоичную арифметику). Я думаю, что в среднем случае 2n*log n >= 2^k, где n - количество узлов диаграммы, а k - количество переменных функции. Верхняя граница n <= 2^(k+1) - 1 достигается с помощью полного двоичного дерева.