Binary Decision Diagram Theory And Applications

Binary Decision Diagram(BDD)as this kind of construction of data is maily used to express the logical expression. Some measures have been developed, for example Binary Decision Tree(BDT),truth table,karnaugh map and so on, however the need of storage space is quite big, and also has the massive redundant data.Based on BDT,BDD reduces the requirement of storage space by removing the redundant nodes from BDT. Thus it enhances the speed of the solution question.In this paper, we fully introduce the basic theories of BDD.Firstly it draws out the expression measures of BBD by the Boolean-function which is expressed by BBT.Later we introduce the structure algorithm in detail. By the studies and researches of BDD theories, I present the algorithm that can solve the minimal hitting sets and constraint satisfied problem.Minimal hitting sets is the question based on model diagnosis.This method can not lose solutions because of pruning and it is not needed to find all hitting sets, but the solutions found contain all minimal hitting sets.As a research aspect of artificial intelligence, after decades of research, Binary Decision Diagram (CSP) has numbers of various solution-finding algorithm.This paper gives CSP solution-finding algorithm by BDD,and realizes N queens solution-finding algorithm by programming.