4

Javaで実装しています。

現時点では、関係をデータ構造に格納するために BDD (Binary Decision Diagramms) を使用しようとしています。

たとえば、R={(3,2),(2,0)} と対応する BDD: R={(3,2),(2,0)} に対応する BDD

このため、BDD 機能を備えたライブラリを探していました。

JavaBDD と JDD の 2 つの可能性が見つかりました。

しかし、どちらの場合も、単純な整数を BDD にエンコードする方法がわかりません。なぜなら、整数の値をいつ、どのように与えるのでしょうか? または、二分決定グラフが整数で表される場合、それはどういう意味ですか?

どちらの場合も、次のような方法があります。

int variable = createBDD(); //(JBDD)

また

BDD bdd = new BDD(1000,1000);
int v1 = bdd.createVar(); // (JDD)

私の例のような BDD を簡単に作成するにはどうすればよいですか?

どうもありがとうございました！！

4

2 に答える 2

0

lex、colex、revdoor、coolex などの k サブセット エンコーディング アルゴリズムを使用して整数タプルをエンコードするだけです。Lex は n 個の整数から k タプルを辞書式順序でエンコードします。たとえば、n=4、k=2 は (1 ベースの) エンコーディングを生成します。

  tuple    rank
  (0,1) -> 1
  (0,2) -> 2
  (0,3) -> 3
  (1,2) -> 4
  (1,3) -> 5
  (2,3) -> 6

タプルをランクに変換して元に戻すには、rank(tuple) および unrank(rank) ルーチンが必要です。

于 2016-02-25T17:55:32.587 に答える
0

したがって、これに対する解決策を見つけましたが、バイナリで整数を表すために使用したブール変数の数を知らずに BDD からタプルを取得できないため、満足のいくものではありません。したがって、たとえば最初に定義する必要があります。すべての整数は 64 より小さいため、6 つのバイナリ変数で表されます。後で 64 より大きい整数を追加したい場合は問題がありますが、実行を節約するために BDD を使用したかったため、時間を節約するために最初から整数の最大サイズを使用したくありません。それ以外の場合は、タプルを表すだけで BDD よりも簡単なことがたくさんあります。

私は BDD ライブラリとして JDD を使用しているため、JDD では BDD は整数として表されます。

したがって、これは整数タプルから BDD を取得する方法です。

最初に、BDD 変数を作成する必要がありmaxVariableCountます。これは、整数を表すバイナリ変数の最大数です (この回答の冒頭で説明されています)。

variablesDefinition後でBDDで表現したい整数変数の数です。したがって、私の質問の例では、変数の定義は 2 になります。これは、各タプルに 2 つの整数変数があるためです。

配列variablesは、すべての BDD 変数を内部に持つ 2 次元配列です。たとえば、タプルに 2 つの要素がある場合、最初の整数変数を表す BDD 変数は にありますvariables[0]。

BDD bddManager = new BDD(1000,100);

private int variablesDefinition;
private int[][] variables;

private void createVariables(int maxVariableCount) {
    variables = new int[variablesDefinition][maxVariableCount];
    for(int i = 0; i < variables.length; i++) {
        for(int j = 0; j < maxVariableCount; j++) {
            variables[i][j] = bddManager.createVar();
        }
    }
}

次に、指定された整数タプルから bdd を作成できます。

private int bddFromTuple(int[] tuple) {
     int result;
     result = bddManager.ref(intAsBDD(tuple[0],variables[0]));
     for(int i = 1; i < tuple.length; i++) {
         result = bddManager.ref(bddManager.and(result, intAsBDD(tuple[i], variables[i])));
     }
     return result;
}

private int intAsBDD(int intToConvert, int[] variables) {
    return bddFromBinaryArray(intAsBinary(intToConvert, variables.length), variables);
}
private int[] intAsBinary(int intToConvert, int bitCount) {
    String binaryString =  Integer.toBinaryString(intToConvert);
    int[] returnedArray = new int[bitCount];
    for (int i = bitCount - binaryString.length(); i < returnedArray.length; i++) {
        returnedArray[i] = binaryString.charAt(i - bitCount + binaryString.length()) - DELTAConvertASCIIToInt;
    }
    return returnedArray;
}

static int DELTAConvertASCIIToInt = 48;

private int bddFromBinaryArray(int[] intAsBinary, int[] variables) {
    int f;

    int[] tmp = new int[intAsBinary.length];

    for(int i = 0; i < intAsBinary.length; i++) {
        if(intAsBinary[i] == 0) {
            if (i == 0) {
                tmp[i] = bddManager.ref(bddManager.not(variables[i]));
            }
            else {
                tmp[i] = bddManager.ref(bddManager.and(tmp[i-1], bddManager.not(variables[i])));
                bddManager.deref(tmp[i - 1]);
            }
        }
        else {
            if (i == 0) {
                tmp[i] = bddManager.ref(variables[i]);
            }
            else {
                tmp[i] = bddManager.ref(bddManager.and(tmp[i-1], variables[i]));
                bddManager.deref(tmp[i - 1]);
            }
        }

    }
    f = tmp[tmp.length-1];
    return f;
}

私の最初の意図は、これらのタプルを BDD に追加し、その後、BDD の整数で算術関数を実行できるようにすることでしたが、これは、BDD をタプルに戻し、関数を実行して BDD に戻した後にのみ可能です。私が BDD を使用したかった理由をすべて破棄します。

于 2014-04-03T16:37:49.767 に答える