Эвристика для оценки эффективности сокращенных упорядоченных двоичных диаграмм решений?

Question

Сокращенные упорядоченные двоичные диаграммы принятия решений (ROBDD) - это эффективная структура данных для логических функций нескольких переменных f(x1,x2,...,xn).Я хотел бы получить интуицию для насколько они эффективны .

Например, для сжатия данных мы знаем, что данные с низкой энтропией (некоторые символы появляются чаще других, много повторений)) могут быть сжаты очень хорошо, в то время как совершенно случайные данные не могут быть сжаты.

Существует ли аналогичная интуиция для оценки того, насколько эффективно ROBDD могут представлять данную булеву формулу?Любая литература на эту тему (желательно онлайн)?

Answer 1

В статье в Википедии есть статья Символическое булево манипулирование с упорядоченными двоичными диаграммами решений , которое дает нижнюю и верхнюю границы для определенных классов функций (симметричных, представляющих двоичную арифметику).Я думаю, что в среднем случае 2n*log n >= 2^k имеет место, где n - это число узлов на диаграмме, а k - это число переменных функции.Верхняя граница n <= 2^(k+1) - 1 достигается с полным двоичным деревом.