ZDD
「多く場合分けを持つ複雑な論理関数」を高速に処理できるデータ構造
基本的な考え方：
論理関数を全ての変数に対して場合分けした結果は二分決定木で表せる． 途中の分岐により同じ終端に到達すると決まる場合には直接終端へと到達するようにエッジを結べば論理関数の結論を導くために生じる分岐回数を減らせる（BDD）． さらに冗長接点を削除して透過接点を共有するなどしたらより分岐回数を減らせる（ZDD）． 基本的な離散構造の1つに論理関数があり、一般に論理関数の値をすべての変数について場合分けした結果は二分決定木（Binary Decision Tree）として表現できる。
コンピューターの処理に置き換えると、分岐の数は処理の回数を意味する。
処理回数を減らすための工夫として、BDD（Binary Decision Diagram）というデータ構造を用いたアルゴリズムが1986年に米国で考案された。
https://gyazo.com/c0cc3a94e414919d63557305c6509c9f
ーーーーー
2025/3/30 15:38