| 一种基于熵的OBDD变量排序算法 |
| |
| 引用本文： | 赵岭忠,王雪松,古天龙,钱俊彦.一种基于熵的OBDD变量排序算法[J].计算机科学,2007,34(2):216-219. |
| |
| 作者姓名： | 赵岭忠 王雪松 古天龙 钱俊彦 |
| |
| 作者单位： | 桂林电子科技大学计算机系,桂林,541004 |
| |
| 基金项目： | 国家自然科学基金
,
广西科学基金 |
| |
| 摘 要： | 有序二叉决策图（OBDD）是一种有效表示布尔函数的数据结构，其大小依赖于所采用的变量序。熵是定量描述布尔函数中变量重要性的一种方法。基于变量的熵值分析了高质量变量序的特征，给出了一种基于熵的OBDD变量排序算法。实验结果表明：该算法与模拟退火算法和遗传算法结果相当。时间仅为相应算法的80．84％和29．79％。
|
| 关 键 词： | 有序二叉决策图 变量序 熵 |
An Entropy-based Algorithm for OBDD Variable Ordering |
| |
| ZHAO Ling-Zhong,WANG Xue-Song,GU Tian-Long,QIAN Jun-Yan.An Entropy-based Algorithm for OBDD Variable Ordering[J].Computer Science,2007,34(2):216-219. |
| |
| Authors: | ZHAO Ling-Zhong WANG Xue-Song GU Tian-Long QIAN Jun-Yan |
| |
| Affiliation: | Department of Computer Science, Guilin University of Electronic Technology, Guilin 541004 |
| |
| Abstract: | Ordered binary decision diagrams(OBDDs)are a data structure for efficient representation and manipulation of Boolean functions.The size of OBDDs is very sensitive to variable ordering.Based on the characterization of a variable with its entropy,a property of good variable orders is discovered.An entropy-based method for OBDD variable ordering is proposed.Compared with simulated annealing algorithm and genetic algorithm,the algorithm yields comparable OBDDs size with an average of 80.84% and 29.79% runtime,respectively. |
| |
| Keywords: | OBDD Variable ordering Entropy of a variable |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
