2

我有一组整数，表示为归约有序二进制决策图（ROBDD）（解释为一个函数，如果输入在集合中，则计算结果为真），我将调用 Domain 和一个整数函数（我将调用F) 表示为 ROBDD 的数组（结果的每一位一个条目）。

现在我想为 F 计算域的图像。这绝对是可能的，因为它可以通过枚举域中的所有项目、应用 F 并将结果插入图像中来轻松完成。但这是一个具有指数复杂性（与域大小呈线性关系）的可怕算法，我的直觉告诉我它可以更快。我一直在研究以下方向：

  1. 将 Restrict(Domain) 应用于 F 的所有位
  2. 做魔术

但事实证明，第二步很困难。第一步的结果包含我需要的信息（至少，我有 90% 的把握），但形式不正确。是否有一种有效的算法将其变成“编码为 ROBDD 的集合”？我需要其他方法吗？

4

2 回答 2

1

令 S(x1, x2, x3...xn) 为集合 S 的指示函数，因此如果 (x1, x2,...xn) 是一个元素，则 S(x1, x2...xn) = true的 S. 让 F1(x1, x2, x3...xn), F2(),... Fn() 是定义 F 的各个函数。然后我可以问一个带有通配符的特定位模式是否是在 F 的图像中，通过为位模式 10 形成方程，例如 S() & F1() & ~F2()，然后求解这个方程，我认为我可以做到，因为它是一个 ROBDD。

当然你想要一个通用的指标函数，它告诉我 abc 是否在图像中。扩展上述内容，我认为您会得到 S() & (a&F1() | ~a&~F1()) & (b&F2() | ~b&~F2()) &... 如果然后重新排序变量，那么原始 x1, x2, ... xn 在 ROBDD 顺序中最后出现，那么您应该能够修剪树以在 x1, x2, ... xn 的任何设置导致值的情况下返回 true true，否则返回 false。

（当然，你可以运行空间，或耐心等待重新订购工作）。

于 2011-10-15T18:39:13.070 回答
1

定义两个集值函数：

N(d1...dn): The subset of the image where members start with a particular sequence of digits d0...dn. 
D(d1...dn): The subset of the inputs that produce N(d1...dn).

然后当序列为空时，我们就有了完整的问题：

D(): The entire domain. 
N(): The entire image.

从完整域中，我们可以定义两个子集：

D(0) = The subset of D() such that F(x)[1]==0 for any x in D().
D(1) = The subset of D() such that F(x)[1]==1 for any x in D().

这个过程可以递归地应用来为每个序列生成 D。

D(d1...d[m+1]) = D(d1...dm) & {x | F(x)[m+1]==d[m+1]}

然后我们可以确定完整序列的 N(x)：

N(d1...dn) = 0 if D(d1...dn) = {}
N(d1...dn) = 1 if D(d1...dn) != {}

父节点可以从两个孩子中产生，直到我们产生 N()。

如果在任何时候我们确定 D(d1...dm) 为空，那么我们知道 N(d1...dm) 也是空的，我们可以避免处理该分支。这是主要的优化。

以下代码（在 Python 中）概述了该过程：

def createImage(input_set_diagram,function_diagrams,index=0):
  if input_set_diagram=='0':
    # If the input set is empty, the output set is also empty
    return '0'
  if index==len(function_diagrams):
    # The set of inputs that produce this result is non-empty
    return '1'
  function_diagram=function_diagrams[index]
  # Determine the branch for zero
  set0=intersect(input_set_diagram,complement(function_diagram))
  result0=createImage(set0,function_diagrams,index+1)
  # Determine the branch for one
  set1=intersect(input_set_diagram,function_diagram)
  result1=createImage(set1,function_diagrams,index+1)
  # Merge if the same
  if result0==result1:
    return result0
  # Otherwise create a new node
  return {'index':index,'0':result0,'1':result1}
于 2011-10-16T06:29:55.633 回答