TAOCP 7.1.4 Exercise 18
The flaw in the previous solution is not only that it ignores the structure of the diagram, but that it misidentifies what Algorithm B is actually aggregating over in a binary decision diagram of this...
Section 7.1.4: Binary Decision Diagrams
Exercise 18. [13] [13] Play through Algorithm B with the BDD (8) and (w1, . . . , w4) = (1,−2,−3, 4).
260 COMBINATORIAL SEARCHING 7.1.4
Verified: no
Solve time: 3m39s
The flaw in the previous solution is not only that it ignores the structure of the diagram, but that it misidentifies what Algorithm B is actually aggregating over in a binary decision diagram of this kind.
In TAOCP Section 7.1.4, Algorithm B does not follow a single root-to-terminal path and accumulate labels once. It evaluates a binary decision diagram by propagating contributions through both outgoing edges of each decision node, respecting the fact that a BDD encodes a family of assignments rather than a single traversal. The value computed is therefore determined by how many root-to-terminal paths exist through each variable at each level, and how those paths terminate.
For BDD (8), the key structural point is that it is the full decision diagram on four variables in the fixed ordering $x_1, x_2, x_3, x_4$. Every internal node branches into a 0-edge and a 1-edge, and every complete root-to-terminal path corresponds to exactly one assignment in ${0,1}^4$. Both branches are present at each level, and no path is privileged. Thus Algorithm B effectively aggregates contributions over all $2^4 = 16$ assignments.
To translate this into the weight computation, observe what each weight contributes over the entire set of assignments. The expression accumulated along any assignment is
$$ w_1 x_1 + w_2 x_2 + w_3 x_3 + w_4 x_4. $$
When summing over all $16$ assignments, each variable $x_i$ takes the value $1$ in exactly half of them and $0$ in the other half. Therefore each $w_i$ is counted exactly $2^3 = 8$ times in the total sum.
This allows the total computed by Algorithm B on BDD (8) to be written as
$$ 8(w_1 + w_2 + w_3 + w_4). $$
Substituting $(w_1,w_2,w_3,w_4) = (1,-2,-3,4)$ gives
$$ w_1 + w_2 + w_3 + w_4 = 1 - 2 - 3 + 4 = 0. $$
Hence the total is
$$ 8 \cdot 0 = 0. $$
The crucial correction is that this result is not obtained by assuming a single path or by informally “visiting each level once”, but by using the actual BDD structure: it encodes all $16$ assignments, and Algorithm B aggregates contributions over the entire diagram symmetrically. Because the weight vector sums to zero, all contributions cancel globally across the full decision structure.
$$ \boxed{0} $$