Распределение И по ИЛИ в двоичном дереве (конъюнктивная нормальная форма)

Question

Я пытаюсь преобразовать двоичное дерево, например

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

в его эквивалентное представление Conjunctive Normal Form (CND). Я полагаю, что, поскольку я использую только логические операторы ИЛИ + И, единственный шаг, который я должен выполнить, - это распределение И по ИЛИ. Это приведет к созданию следующего дерева (все еще двоичного для моих целей) в 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?

// РЕДАКТИРОВАТЬ 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;
}

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

Этот алгоритм должен применяться ко всем узлам вашего дерева, пока дерево больше не изменится. Порядок, в котором вы применяете алгоритм к узлам, не имеет значения. Интуитивно, повторное применение алгоритма подтянет все AND узлы над OR узлы, пока дерево не находится в CNF.

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

Примечание: имейте в виду, что преобразование CNF может взорвать ваше дерево в геометрической прогрессии. Показанная реализация довольно примитивна и не использует никаких улучшений для сокращения времени вычислений.

Answer 2

Я рекомендую вам посмотреть, как перемещается дерево, в вашем коде выглядит поиск в глубину, поэтому вы начнете с самой глубокой ветви (оператор Deepest), которую вы должны разработать для своего метода. distribute ожидая этого порядка и применяя законы распределения для дочерних узлов в обратном направлении.

Очень общее описание того, что должен делать метод распространения:

Порядок того, какой тип закона распределения должен применяться, зависит от типа операции родителя и дочерних узлов. Каждый дочерний узел может быть оператором или значением, в зависимости от этой комбинации сделать распределение, требуемое законом.

Псевдокод того, что я пытаюсь вам сказать:

if parent node is OR type
    if child nodes are OPERATOR-VALUE combination
        if OPERATION is AND type
            apply correspondig distribution 
            return the new parent
        else
            apply correspondig distribution 
            return the new parent
    if child node are VALUE-VALUE combination
        return parent
if parent node is AND type
    if child nodes are OPERATOR-VALUE combination
        if OPERATION is AND type
            apply correspondig distribution 
            return the new parent
        else
            apply correspondig distribution 
            return the new parent
    if child nodes are VALUE-VALUE combination
        return parent;

Пример реализации:

public TreeNode distribute(TreeNode parent,TreeNode leftChild, TreeNode rightChild) {
    if( !(leftChild instanceof Operator) && !(rightChild instanceof Operator) ){
        /*There is nothing to do */
        return parent;
    }
    if( parent.getType() == 'OR'){
        /*
            Apply distributive laws and return the new branch
            for example:        
        */
        if ( (leftChild instanceof operator) &&  !(rightChild instanceof Operator) ){
            TreeNode operatorLeftChild  = leftChild.getLeftChild();
            TreeNode operatorRightChild = leftChild.getRightChild();
            if(leftChild.getType() == 'AND' )
            {
                /*
                Applying distributive laws:
                    rightChild OR (operatorLeftChild AND operatorRightChild) 
                        -> (rightChild OR operatorLeftChild) AND (rightChild OR operatorRightChild)
                */
                TreeNode newBranch = new Operator("AND");
                /*new Left child*/
                TreeNode newLeftChild= new Operator("OR");
                newLeftChild.setLeftChild(rightChild);
                newLeftChild.setRightChild(operatorLeftChild);
                /*new Richt Child */
                TreeNode newRightChild= new Operator("OR");
                newRightChild.setLeftChild(rightChild);
                newRightChild.setRightChild(operatorRightChild);
                /*Setting the new Branch*/
                newBranch.setLeftChild(newLeftChild);
                newBranch.setRightChild(newRightChild);
                return newBranch;
            }

        }
    }
    if( parent.getType() == 'AND'){
        /*
            Else-If and distributive laws stuff
        */
    }
    /*
        You can also implement this part wihtout the else-if code by implementing a true table
        but is more abstract and less human redeable
     */
}

Примечание. Предыдущий код не был протестирован, и я предполагаю, что многие вещи, которые я не знаю, как реализовано ваше дерево, возможно, вам потребуется обновить родительскую ссылку в дочерних узлах.