2

縮小順序二分決定図(ROBDD) (入力がセット内にある場合に true と評価される関数として解釈される)として表される整数のセットがあり、これを Domain と呼び、整数関数 (これを呼び出す) F) ROBDD の配列として表される (結果のビットごとに 1 つのエントリ)。

ここで、F のドメインの画像を計算したいと思います。ドメインからすべてのアイテムを列挙し、F を適用し、結果を画像に挿入することで簡単に実行できるため、間違いなく可能です。しかし、これは指数関数的な複雑さ (ドメインのサイズに線形) を持つ恐ろしいアルゴリズムであり、私の直感では、より高速になる可能性があることがわかります。私は次の方向を検討してきました：

  1. F のすべてのビットに Restrict(Domain) を適用する
  2. 魔法をかける

しかし、2番目のステップは難しいことがわかりました。最初のステップの結果には、必要な情報が含まれています (少なくとも、90% の確信があります) が、正しい形式ではありません。それを「ROBDDとしてエンコードされたセット」に変換する効率的なアルゴリズムはありますか? 他のアプローチが必要ですか？

4

2 に答える 2

1

2つの設定値関数を定義します。

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.

フルドメインから、2つのサブセットを定義できます。

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（）を生成するまで、親ノードは2つの子から生成できます。

いずれかの時点で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 に答える
1

S(x1, x2, x3...xn) を集合 S の指標関数とすると、(x1, x2,...xn) が要素の場合、S(x1, x2...xn) = true となります。 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 に答える