带有互补边的共享OBDDs及数据结构

J4 ›› 2013, Vol. 35 ›› Issue (1): 180-184.

带有互补边的共享OBDDs及数据结构

孟礼，武小悦

（国防科学技术大学信息系统与管理学院，湖南长沙 410073）

收稿日期:2011-03-05 修回日期:2011-07-13 出版日期:2013-01-25 发布日期:2013-01-25
作者简介:孟礼(1986),男，辽宁凌海人，硕士，研究方向为装备系统分析与管理决策。
基金资助:
国家自然科学基金资助项目（71071159）

A data structure of shared OBDDs with complemented edges

MENG Li，WU Xiaoyue

(College of Information Systems and Management,
National University of Defense Technology,Changsha 410073,China)

Received:2011-03-05 Revised:2011-07-13 Online:2013-01-25 Published:2013-01-25

摘要/Abstract

摘要：

顺序二元决策图OBDDs的规模随着变量数量的增多呈指数形式增长。为了克服大规模OBDDs数据的描述和存储困难，提出了一种带有互补边的共享OBDDs的数据结构，并定义了一组OBDDs节点的关键属性，该数据结构融合了共享OBDDs和带有互补边的OBDDs的特点。最后通过存储空间实例对比分析，证明了该数据结构能够有效描述和存储大规模OBDDs数据。

关键词: 大规模OBDDs；共享OBDDs；互补边；数据结构

Abstract:

The scale of ordered binary decision diagrams (OBDDs) increases exponentially with the number of variables. In this paper, to overcome the difficulties of describing and storing large scale OBDDs data, we propose a data structure of shared OBDDs with complemented edges, in which a set of key attributes of nodes are defined. This data structure merges the features of shared OBDDs and OBDDs with complemented edges. At last, a contrastive analysis of space consuming experiment is carried out to demonstrate that this data structure can describe and store large scale OBDDs data effectively.

Key words: large scale OBDDs;shared OBDDs;complemented edges;data structures

孟礼，武小悦. 带有互补边的共享OBDDs及数据结构[J]. J4, 2013, 35(1): 180-184.

MENG Li，WU Xiaoyue. A data structure of shared OBDDs with complemented edges[J]. J4, 2013, 35(1): 180-184.