智慧来

河南理工大学计算机科学与技术学院，河南焦作 454000

同一变量排序下的多OBDD合并算法

智慧来

河南理工大学计算机科学与技术学院，河南焦作 454000

有序决策图（OBDD）是一种用于表示布尔表达式的数据结构，并在许多领域得到了广泛应用。在分布式或者动态环境下，利用已知布尔表达式的OBDD构造目标布尔表达式的OBDD是一个决定实际问题解决效率的关键问题。基于Shannon分解原理提出了一个同一变量排序下的OBDD合并算法。该算法首先建立目标布尔表达式的表存储模型，然后按照变量排序的逆序，依次处理各个变量，并且合并取值相同的行，直到所有变量处理完毕。

有序决策图（OBDD）；同一变量排序；多有序决策图（OBDD）合并；Apply算法

1 引言

有序二叉决策图（Ordered Binary Decision Diagram，OBDD）是一种用于表示布尔函数的数据结构[1-2]，是迄今为止最为有效的符号技术之一。OBDD已经应用在粗糙集属性约简表示[3]、局部模式挖掘[4]、并行电力系统恢复[5]、网络可靠性分析[6-7]、约束满足问题求解[8-10]等众多领域。

在分布式或者是动态环境下，利用已知布尔函数的OBDD构造目标布尔函数的OBDD是一个关键技术问题。譬如，已知f1、f2和f3的OBDD，构造一个目标表达式f=f1∨(f2∧┐f3)，f的OBDD如何构造？

Colorado大学开发的CUDD软件包[11]，里面包含有Apply操作，即

此操作输入表达式u1和u2的OBDD，返回表达式u1op u2的OBDD，其中op是布尔运算符。

一个显而易见的方法是首先构造┐f3的OBDD，然后使用Apply算法求出f2∧┐f3的OBDD，最后再一次使用Apply算法求出的f1∨(f2∧┐f3)的OBDD。显然，上述过程两次使用了Apply算法，且每次使用Apply算法都是基于Shannon分解原理的。……