在二叉树中进行“与"或“与"分布(合取范式) [英] Distributing AND over OR in a binary tree (Conjunctive Normal Form)

问题描述

例如，我正在尝试转换二叉树

I'm trying to convert a binary tree e.g.

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中生成以下树(对于我来说仍然是二进制):

into it's equivalent Conjunctive Normal Form (CND) representation. I believe that because I'm only using the logical OR + AND operators that the only step I'd have to perform is the distribution of AND over OR. This would produce the following tree (still binary for my purposes) in CNF:

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

我在创建算法来执行此操作时遇到了问题...到目前为止，我有以下骨架将自下而上重写树(请注意以递归方式进行重构):

I'm having issues creating an algorithm to do this... so far I have the following skeleton which will re-write the tree bottom up (Notice the recursive call to reconstruct):

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()|
 -----------

有人可以建议将Distribution转换为CNF吗?

Could anybody suggest an implementation of distribute which would convert to CNF?

//编辑1(在nif回答之后)

// EDIT 1 (After answer from 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;
}

推荐答案

如果只有AND和OR是您正在使用的运算符，那么将树转换为CNF并不难.您要做的就是找到OR(AND(X,Y), Z)或OR(Z, AND(X,Y))形式的结构，并使用分布定律.

If AND and OR are the only operators you are using, it shouldn't be hard to tranform your tree to CNF. All you have to do is find structures in the form OR(AND(X,Y), Z) or OR(Z, AND(X,Y)) and use the distribution law.

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;
}

此算法必须应用于树的所有节点，直到不再更改树为止.将算法应用于节点的顺序无关紧要.直观地讲，该算法的重复应用将在OR个节点上拉起所有AND个节点，直到该树在CNF中.

This algorithm must be applied to all nodes of your tree until the tree isn't changed anymore. The order in which you apply the algorithm to the nodes doesn't matter. Intuitively, repetitive application of the algorithm will pull up all AND nodes over OR nodes until the tree is in CNF.

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

注意:请注意，CNF转换可能会使您的树变大.所示实现非常原始，没有使用任何增强功能来减少计算时间.

Note: Be aware that the CNF transformation may blow up your tree exponential in size. The shown implementation is quite primitive and doesn't use any enhancements to reduce computation time.

这篇关于在二叉树中进行“与"或“与"分布(合取范式)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！