A Binary Decision Diagram(BDD),proposed by Akers,is a directed acyclic graph,
representing a boolean function.Through the development of the efficient algorithms
of boolean operations by Bryant,it is used in various fields,such as VLSI CAD
and AI.Since the size of a BDD depends on the variable ordering,it is important
to find a good variable ordering which minimizes the size of a BDD.But for a
general function,it is hard to find a best ordering that minimizes the size of
a BDD.
In this thesis,we show that we can construct a BDD representing a threshold
function efficiently in a top-down manner which Tani and Imai have proposed.
Specifically we show that the equivalence check is executed in a constant time
after preprocessing that uses a dynamic programming,and that the time complexity to construct the BDD after preprocessing is proportional to the output-size.
We implement the algorithm and estimate its efficiency by experiments. We also
test various-orderings to find a good variable-ordering.As an application of
the BDD,We solve the Knapsack Problem by using the BDD and estimate its efficiency by experiments.