One heuristic to minimize BDD representation of the Fault Tree

摘要

It is well known that the Fault Tree can efficiently be represented by binary decisionrndiagrams. Another well known fact is that the essential number of nodes to represent the BDDs isrnextremely sensitive to the chosen order of variables. The problem of finding an optimal order ofrnvariables that form the BDDs falls under the class of NP-complete problems. This paper presents onernheuristic approach to the problem of finding the initial order of variables utilized for the BDDrnconstruction which can be improved further by various dynamical reordering schemes. In our paperrnwe have shown that compared to the known methods of finding the initial order this approachrnfrequently brings noticeable better results with respect to the required working memory and timernneeded to finish the BDD construction.rnWe have compared the method on Fault Tree models against work with well known methods such asrndepth-first, breadth-first search procedures. The method may be applied to find an initial order forrnfault trees being created from basic events by means of logical operations (e.g. negation, and, or,rnexclusive or).rnWith some models a significant reduction of necessary memory has been achieved, sometimes evenrnmore than two times. Such significant reductions have been achieved by means of a slight increase inrntime necessary for the creation of the initial order. Which is fully acceptable since the time for therninitial order determination is negligible compared to the time needed for the BDD construction.