基于重量分析的OBDD变量排序算法

摘要

有序的二叉判决图(OBDD)是布尔表达式的一种有效表示方法,但它的体积对变量排序具有较强的依赖性.本文提出一种电路结构图,并在此基础上定义了原始输入重量和节点重量等参数,并建立了用重量分析来指导的OBDD变量排序算法.由于从考虑变量对输出函数的影响出发与从考虑OBDD节点共享性出发对变量排序的要求不同,本文分别设计了两类算法.实验结果表明,本文对大多数标准电路变量排序的效果都优于国际上的同类算法,尤其是对一些较难排序的电路(如C2670)效果更加突出.