优化布尔表达式：同一变量排序下的多OBDD高效合并算法

"这篇论文研究的是同一变量排序下的多OBDD(有序二叉决策图)合并算法，旨在解决在分布式或动态环境下利用已知布尔表达式的OBDD构造目标布尔表达式的OBDD的问题。作者提出了一种基于Shannon分解原理的算法，通过逆序处理变量并合并取值相同的行，以提高构造效率。论文还提到了现有工作主要关注两个表达式的OBDD合成，而该研究扩展到了多个表达式的合并。" 正文: 有序二叉决策图(ordered binary decision diagram, OBDD)是一种高效的布尔函数表示方法，广泛应用于各种领域，如粗糙集属性约简、局部模式挖掘、并行电力系统恢复、网络可靠性分析和约束满足问题求解等。OBDD的优势在于其紧凑的结构和高效的运算性能，尤其在处理布尔表达式时。 在分布式系统或动态环境中，构建目标布尔函数的OBDD是关键任务。例如，如果已知布尔函数f1、f2和f3的OBDD表示，那么如何有效地构造出表达式f = f1Ú(f2Ù┐f3)的OBDD？传统的做法可能涉及多次应用 CUDD 软件包中的 Apply 操作，这可能导致不必要的计算复杂度增加，因为每次应用都需要基于Shannon分解进行。 论文提出的新算法致力于优化这一过程，它首先采用一种表存储模型来表示目标布尔表达式，然后按照变量的逆序排序来处理。这种排序策略有助于减少合并操作的次数，因为相同的变量取值更有可能相邻。在处理每个变量时，算法会合并具有相同取值的行，逐步构建目标OBDD，直到所有变量都被处理。 与现有的研究相比，该算法的独特之处在于它处理多个布尔表达式的合并，而不仅仅是两个。现有工作，如古天龙等人的研究，主要集中在两个布尔函数的OBDD合成，包括并、交和差运算。而本文提出的算法将这个概念扩展到多个表达式，有望在处理更复杂的布尔组合时提高效率和性能。 这篇论文的研究为多OBDD合并提供了一个新的视角，通过优化变量处理顺序和合并策略，降低了计算复杂性，特别是在需要组合多个布尔表达式的情况下。这一贡献对于进一步提升分布式系统和动态环境中的布尔表达式处理效率具有重要意义。