4

二分木を変換しようとしています。

OR (Implementation of Operator - a specialisation of TreeNode... see below)
|-A (Implementation of TreeNode... see below)
|-OR
  |-B
  |-AND (Implementation of Operator - a specialisation of TreeNode... see below)
    |-C
    |-OR
      |-D
      |-E

同等の結合標準形 (CND) 表現に変換します。論理 OR + AND 演算子のみを使用しているため、実行する必要がある唯一のステップは、OR に対する AND の分散であると思います。これにより、CNF で次のツリー (私の目的ではまだバイナリ) が生成されます。

AND
|-OR
| |-A
| |-OR
|   |-B
|   |-OR
|     |-E
|     |-D
|-OR
  |-A
  |-OR
    |-B
    |-OR
      |-E
      |-C

これを行うアルゴリズムの作成に問題があります...これまでのところ、ツリーを下から上に書き換える次のスケルトンがあります(再構築の再帰呼び出しに注意してください):

public TreeNode reconstruct(TreeNode treeNode) {
  if(treeNode instanceof Operator) {
    TreeNode left = reconstruct(((Operator)treeNode).getLeft());
    TreeNode right = reconstruct(((Operator)treeNode).getRight());

    return distribute(treeNode, left, right);
  }
  else
    return node;
}

クラスの使用:

 -----------
|  TreeNode | // Interface
 -----------
      ^
      |
 -----------
| Operator  | // Interface
 -----------
| getLeft() |
| getRight()|
| setLeft() |
| setRight()|
 -----------

CNFに変換されるdistributeの実装を提案できる人はいますか?

// EDIT 1 (nif からの回答後)

private Node distribute(TreeNode node, TreeNode left, TreeNode right) {
  if (node instanceof Or) {
    if (left instanceof And) {
      // distribute right over left AND
      return 
        new And(
          new Or(((Operator)left).getLeft(), right),
          new Or(((Operator)left).getRight(), right)
        );
    } 
    else if (right instanceof And) {
      // distribute left over right AND
      return 
        new And(
          new Or(((Operator)right).getLeft(), left),
          new Or(((Operator)right).getRight(), left)
        );
    }
  }
  if(node instanceof Operator) {
    ((Operator)node).setLeft(left);
    ((Operator)node).setRight(right);
  }
  // default
  return node;
}
4

2 に答える 2

1

AND使用している演算子がとだけの場合OR、ツリーを CNF に変換するのは難しくありません。あなたがしなければならないのは、フォーム内の構造を見つけるOR(AND(X,Y), Z)かOR(Z, AND(X,Y))、分布法則を使用することだけです.

private static TreeNode distribute(TreeNode n, TreeNode left, TreeNode right) {
  if (n instanceof Or) {
    if (left instanceof And) {
      // distribute right over left AND
      return new And(new Or(left.getLeft(), right), 
                     new Or(left.getRight(), right));
    } else if (right instanceof And) {
      // distribute left over right AND
      return new And(new Or(right.getLeft(), left), 
                     new Or(right.getRight(), left));
    }
  }

  // no change
  return treeNode;
}

このアルゴリズムは、ツリーが変更されなくなるまで、ツリーのすべてのノードに適用する必要があります。アルゴリズムをノードに適用する順序は重要ではありません。直観的に、アルゴリズムを繰り返し適用すると、ツリーが CNF になるまですべてのノードがプルアップされます。ANDOR

TreeNode root = ....;
while (true) {
  TreeNode transformedRoot = reconstruct(root);
  if (root.equals(transformedRoot)) {
    break;
  }
  root = transformedRoot;
}
// root is now in CNF

注: CNF 変換により、ツリーの指数関数的なサイズが大きくなる可能性があることに注意してください。示されている実装は非常に原始的であり、計算時間を短縮するための拡張機能は使用していません。

于 2013-06-21T17:45:42.320 に答える