DPバイナリブール式ツリーが真と評価できる方法の数を見つけるために

Question

私たちはツリーの形をしています。入力は最下部の葉ノードであり、リーフノードはANDゲートで結合されるか、またはNOTゲートに接続されます。最終値を出力するルートノードがあります。

私たちは、この回路がtrueに評価させることができる方法の数をカウントする多項式時間アルゴリズムを思い付くしようとしてきました。私は、動的プログラミングを使用して、ルートノードでTrueから始まり、ゲートがNOTであり、そこに入る値がTrueの場合、NOTゲートの下にあるものは、偽、など）。しかし、以前のサブ問題の結果をどのように保存すべきか、ツリー構造を使用するか、何らかの2D配列を使用できるかどうかはわかりません（多くのセルが潜在的に使用されていないように思われますが） ）。

私たちは、ツリー構造の制限を削除した場合、これはNP困難であるサーキット-SATに減少するであろうことを知っています。どんな助けでも大歓迎です！

Answer 1

私は与えられた入力が1つの葉にしか現れないと仮定しています（そうでなければ、問題は再び木構造と制限された演算子にもかかわらずboolean satisfiabilityになります）。

私は答えは、データ構造ずに計算することができると信じています。後でソリューションを列挙する必要はありません。私は、再帰ステップには2つのパラメータ、すなわち処理するノードと、そのノードによって生成されるターゲット出力が必要であり、2つの値、すなわちノードの目標を達成する方法の数、および以下の葉の総数ノードこれらの両方は、ツリー上の単一の深さ優先トラバーサルを介して取得することができます。

ここで考えと擬似コードです：

あなたのツリーは、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 
    } 
} 

。私たちはそこに背中合わせではないされているわけではない手足と仮定した場合、最大深さのツリーは2*ciel(log_2(n)+1)層とし、2n + 2(n-1)総ノードと木につながる、NOTとの交互の層とすることにより達成されます。 （nはリーフノードの数です。）したがって、各ノードに一度触れる深度優先トラバースは、背中合わせのNOT演算子がないという仮定の下でO(n)で実行されます。