algorithm - 计算一组表示为ROBDD数组的函数的图像

我有一组整数，表示为aReduced Ordered Binary Decision Diagram（robdd）（解释为当输入在集合中时计算为真的函数），我将调用domain，还有一个整数函数（我将调用f）表示为robdd的数组（结果的每一位有一个条目）。
现在我想为F计算域的映像，这是绝对可能的，因为它可以通过枚举域中的所有项、应用F并将结果插入映像来完成但是这是一个可怕的算法，它具有指数复杂性（在域的大小上是线性的），而我的直觉告诉我它可以更快。我一直在寻找：
对f的所有位应用限制（域）
施魔法
但事实证明第二步很难第一步的结果包含了我需要的信息（至少，我有90%的把握），但形式不对。有没有一个有效的算法把它变成一个“编码为robdd的集合”？我需要其他方法吗？

最佳答案

定义两个集值函数：

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}

关于algorithm - 计算一组表示为ROBDD数组的函数的图像，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7778353/