啓發式評估縮減有序二元決策圖的效率？

Question

Reduced Ordered Binary Decision Diagrams（ROBDD）是多變量布爾函數f(x1,x2,...,xn)的高效數據結構。我想直接獲得他們是如何高效的。例如，對於數據壓縮，我們知道具有低熵的數據（某些符號比其他重複出現更頻繁）可以很好地壓縮，而完全隨機數據不能被壓縮。

有沒有類似的直覺來估計ROBDDs如何有效地表示給定的布爾公式？有關此主題的任何文獻（最好在線）？

Answer 1

維基百科文章Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams中有文章給出了某些函數類（對稱，表示二進制算術）的下限和上限。我認爲在一般情況下，2n*log n >= 2^k成立，其中n是圖中的節點數，k是該函數的變量數。用完整的二叉樹實現的上限是n <= 2^(k+1) - 1。