实现最优BDD结构的联合改进方法

针对文献13]的最优BDD指标顺序算法,详细研究了该方法的计算机实现。在分析实现各个关键技术的过程中,阐明了存储每个指标值的真值表的冗余性,分析了获取一个最优解(当对象含有多个最优解时)的弊端,提出了改进方法——删除存储指标值的真值表,获得所有最优解。为了实现形式最优BDD结构,详细研究了"去除"操作在简化"等价"节点上的原理。将最优指标顺序的理论和"等价"节点的简化操作方法联合起来,实现了理论和形式都最优的BDD结构。最后,以具体的例证阐释了联合改进方法在获取最优BDD结构中的突出特点。

Joint Improved Method of Implementing Optimal BDD Structure

In this paper, the computer implementation of optimal index-order of binary decision diagram (BDD) structure is researched based on analyzing the principle of optimal index-order presented by Friedman etc. In process of analyzing key techniques, the redundancy to store truth table of all indexes in original method is pointed out. At the same time, the defect that the original method could only obtain an optimal solution (when the object had several optimal solutions) was analyzed, and then the original method was improved, i.e., the truth table used for storing index value is deleted and the algorithm is modified to get all optimal solutions. To realize optimal BDD structure in formality, the principle simplifying ‘equivalent' nodes with ‘deleting' operations is analyzed in detail. The theory of optimal index-order and method of simplifying ‘equivalent' nodes are united to implement optimal BDD structure with theoretic and formal angle. Finally, the advantages of joint improved method used for achieving optimal BDD structure are validated with an example.