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

Joint Improved Method of Implementing Optimal BDD Structure

作　　者：罗航[1] 廖俊必[1] 王厚军[2] 黄建国[2] 龙兵[2] 

机构地区：[1]四川大学制造科学与工程学院,成都610065 [2]电子科技大学自动化工程学院,成都611731

出　　处：《电子科技大学学报》2012年第1期48-53,共6页Journal of University of Electronic Science and Technology of China

基　　金：国家自然科学基金(60934002);部级预研基金;高等学校博士点基金(20070614008);四川大学青年基金(2011SCU11120)的资助

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

关 键 词：二元决策图 代价 等价节点 标识符 指标顺序 最优解 

分 类 号：TP202.1[自动化与计算机技术—检测技术与自动化装置]