DP는 이진 부울 표현식 트리가 참으로 평가할 수있는 방법의 수를 찾습니다.

Question

우리는 트리 형태의 회로를 가지고 있습니다. 입력은 맨 아래에있는 리프 노드이며, 리프 노드는 AND 게이트로 결합되거나 NOT 게이트에 첨부 될 수 있습니다. 최종 값을 출력하는 루트 노드가 있습니다.

저는이 회로를 true로 평가할 수있는 방법의 수를 세는 다항식 알고리즘을 생각해 냈습니다. 나는 우리가 동적 프로그래밍을 사용할 수 있고 루트 노드에서 True로 시작하여 하향식으로 전파하는 하향식으로 진행할 수 있다고 생각한다. (즉, 게이트가 NOT이고 들어오는 값이 참이면 NOT 게이트 아래에있는 모든 것이 있어야한다. 거짓, 등). 그러나 이전 하위 문제의 결과를 저장하는 방법을 잘 모르겠습니다. 트리 구조를 사용하거나 여러 가지 2D 배열을 사용할 수 있을지는 모르겠지만 (많은 셀이 잠재적으로 사용되지 않는 것처럼 보일 수 있지만 낭비 일 수 있습니다.)).

우리가 트리 구조의 제한을 제거하면 NP-hard 인 Circuit-SAT로 감소한다는 것을 알고 있습니다. 어떤 도움이라도 대단히 감사합니다!

Answer 1

주어진 입력이 하나의 리프에만 나타날 수 있다고 가정합니다. 그렇지 않으면 트리 구조와 제한된 연산자에도 불구하고 De Morgan의 법칙에 따라 boolean satisfiability이 다시 생깁니다.

데이터 구조가 없으면 대답을 계산할 수 있다고 생각합니다. 결국 솔루션을 열거 할 필요가 없습니다. 재귀 단계에는 두 개의 매개 변수가 필요합니다 : 처리 할 노드와 해당 노드가 생성하는 대상 출력이 있으며 두 값을 반환합니다 : 노드의 대상을 얻는 방법의 수와 아래의 총 수 노드 이 두 가지 방법은 트리를 가로 지르는 깊이 우선 탐색을 통해 얻을 수 있습니다. NOT 작업의

(int ways, int leaves) = recurse(Node n, bool target) { 
    //Base case of recursion: 
    if(n.type == LEAF) { 
    return (1, 1); 
    } 
    else if(n.type == NOT) { 
    //for a NOT, we just invert the target. 
    return recurse(n.child[0], !target) 
    } 
    else if (n.type == AND) { 
    //AND is more complicated. First, count the ways that we can make each 
    //sub-expression evaluate to true, and the total number of leaves under 
    //both the left and right child: 
    (int left_true, int left_leaves) = recurse(n.child[0], true); 
    (int right_true, int right_leaves) = recurse(n.child[1], true); 

    //the total number of ways to make a true AND result is the product of 
    //the number of ways to make the left true, and the number of ways to 
    //make the right true. 
    int total_true_ways = left_true * right_true; 

    //the total number of leaves under this node is the sum of leaves under 
    //the left and right subtrees. 
    int total_leaves = left_leaves + right_leaves; 

    if(target == true) { 
     //if this node's target is 'true' we've already computed the number of 
     //ways to satisfy that. 
     return (total_true_ways, total_leaves); 
    } 
    else { 
     //The number of ways to make a 'false' is the total number of possible 
     //input combinations, less the number of input combinations that make 
     //a 'true'. 

     //The total number of possible input combinations is given by 2 to the 
     //power of the number of boolean inputs, which is given by the 
     //number of leaves below the node: 
     int num_possible_inputs = pow(2, total_leaves); 

     return (num_possible_inputs - total_true_ways, total_leaves); 
    } 
    } 
    else { 
    throw internal error 
    } 
} 

당신의 나무를 배제하지 않기 때문에 불행하게도, 실행 시간이 엄격하게 잎의 숫자로 표현 될 수없는 임의의 길이의 체인 :

여기에 아이디어와 의사 코드의 . back-to-back NOT 사지가 없다고 가정하면, NOT과 AND의 레이어를 번갈아 가며, 2*ciel(log_2(n)+1) 개의 레이어와 2n + 2(n-1) 개의 노드가있는 트리로 이어지는 최대 심도 트리를 얻을 수 있습니다. (여기서 n은 리프 노드의 수입니다.) 따라서 각 노드를 한번 만나는 깊이 우선 탐색은 연속적인 NOT 연산자가 없다는 가정하에 O(n)에서 실행됩니다.