\datethis \def\[#1]{[\hbox{$\mkern1mu\thickmuskip=\thinmuskip#1\mkern1mu$}]} % Iverson \input epsf @*Intro. I'm experimenting with what may be a new twist(?) on dynamic programming. It's motivated by Bayesian networks'' that form a binary tree. With this method we can answer queries that are much different from the usual marginal'' distributions. For example, with binary states, we can determine the probability that exactly half of the nodes are~1, in $O(n^3)$ steps. In general we can determine the probability that a Boolean function $f(x_1,\ldots,x_n)$ is true, as long as the BDD for that function is small when the nodes appear in arbitrary order. (More precisely, I have a particular order in mind, for each binary tree; the function should have a small BDD when the variables are inspected in that order.) Here's the problem: Given a binary tree of $n$ nodes, with $n-1$ weight functions $w_k(x_j,x_k)$ on the edge from node~$j$ to a child node~$k$. Assign binary values $(x_1,\ldots,x_n)$ to the nodes. Every such state occurs with relative weight $W(x_1,\ldots,x_n)=\prod w_k(x_j,x_k)$, where the product is over all edges. For example, the binary tree $$\vcenter{\epsfbox{treeprobs.1}}$$ has the weight function $$\displaylines{\qquad\qquad W(x_1,\ldots,x_{10})=w_2(x_1,x_2)\,w_3(x_1,x_3)\,w_4(x_3,x_4)\, w_5(x_4,x_5) \hfill\cr\hfill w_6(x_4,x_6)\,w_7(x_3,x_7)\,w_8(x_7,x_8)\,w_9(x_8,x_9)\, w_{10}(x_8,x_{10}). \qquad\qquad\cr}$$ Without loss of generality we can assume that the left subtree of each node has at most as many nodes as the corresponding right subtree, and that the nodes have been numbered in preorder. Both of these assumptions are in fact fulfilled in the example above. (Surprise!) If the QDD for a Boolean function $f(x_1,\ldots,x_n)$ has $N$ nodes, a variant of the algorithm below computes $\sum\{W(x_1,\ldots,x_n) \mid f(x_1,\ldots,x_n)=1\}$ in $O(nN)$ steps. Here I demonstrate the idea when $f$ is the symmetric function $S_m(x_1,\ldots,x_n)=\[x_1+\cdots+x_n=m]$. @ For $1\le i\le n$, let $W_i(x_i,\ldots,x_n)=\prod w_k(x_j,x_k)$, where the product includes only edges $jk$ with $j\ge i$. Thus, for instance, $W_7(x_7,x_8,x_9,x_{10})$ in the example above is $\,w_8(x_7,x_8)\,w_9(x_8,x_9)\,w_{10}(x_8,x_{10})$. In general we have $W_n(x_n)=1$ and $W_1(x_1,\ldots,x_n)=W(x_1,\ldots,x_n)$. If node $j$ has no children, $W_j(x_j,\ldots,x_n)=W_{j+1}(x_{j+1},\ldots,x_n)$. If node $j$ has one child, it's the right child, and it's node $j+1$; hence $W_j(x_j,\dots,x_n)=w_{j+1}(x_j,x_{j+1})\,W_{j+1}(x_{j+1},\ldots,x_n)$ in that case. Otherwise node~$j$ has two children, $j+1$ and $k$; then we have $$W_j(x_j,\dots,x_n)=w_{j+1}(x_j,x_{j+1})\,w_k(x_j,x_k)\, W_{j+1}(x_{j+1},\ldots,x_n).$$ Let $S_j$ be the set of all $x_k$ such that $k>j$ and $k$ is the right child of~$i$ for some $ij$ that are not in $S_j$. For example, in the tree above, $$T_6(2,0,1)=\sum_{p=0}^1\sum_{q=0}^1\sum_{r=0}^1 W_6(0,1,p,q,r)\[p+q+r=1].$$ The overall answer that we're trying to compute is $T_1(m,0)+T_1(m,1)$. And the $T$'s satisfy a simple bottom-up recursion, starting with $$T_n(s,x_n)\;=\;\[x_n=s].$$ Namely, if node $j$ is childless, for \$j #include char buf[bufsize]; int edgej[maxn],edgek[maxn]; int S[maxn][maxn]; /* overkill, but we accept left-heavy trees */ int kids[maxn]; int where[maxn]; int x[maxn]; main(int argc,char *argv[]) { register int j,k,n,p,q,r,s; int m; @; @; @; @; } @ @= if (argc!=2 || sscanf(argv[1],"%d",&m)!=1) { fprintf(stderr,"Usage: %s m\n",argv[0]); exit(-99); } @ @d panic(mess) {@+fprintf(stderr,"%s!\n",mess);@+exit(-1);@+} @= for (n=1;;n++) { if (!fgets(buf,bufsize,stdin)) break; if (n==maxn) panic("too many edges"); if (sscanf(buf,"%d %d",&edgej[n],&edgek[n])!=2) panic("bad input line"); kids[edgej[n]]++; where[edgej[n]]=n; } if (edgek[n-1]!=n) panic("inconsistent input"); @ @= for (j=1;j= for (s=0;s<2;s++) for (k=0;k<2;k++) printf("T[%d,%d,%d]=%d\n",n,s,k,s==k); for (j=n-1;j;j--) { for (s=0;s<=m;s++) { if (sn+1-j) break; for (k=0;S[j][k];k++) ; r=k; while (1) { @; for (k=0;x[k];k++) { x[k]=0; } if (k>r) break; x[k]=1; } } } printf("ans=T[1,%d,0]+T[1,%d,1]\n",m,m); @ @= printf("T[%d,%d",j,s); for (k=0;k<=r;k++) printf(",%d",x[k]); printf("]="); if (s-x[0]<0 || s-x[0]>n-j) printf("0"); else switch (kids[j]) { case 0: @;@+break; case 1: @;@+break; case 2: @;@+break; } printf("\n"); @ @= printf("T[%d,%d",j+1,s-x[0]); for (k=1;k<=r;k++) printf(",%d",x[k]); printf("]"); @ @= for (p=0;p<2;p++) { if (p) printf("+"); printf("w[%d,%d,%d]",j+1,x[0],p); printf("T[%d,%d,%d",j+1,s-x[0],p); for (k=1;k<=r;k++) printf(",%d",x[k]); printf("]"); } @ @= for (p=0;p<2;p++) { if (p) printf("+"); printf("w[%d,%d,%d](",j+1,x[0],p); for (q=0;q<2;q++) { if (q) printf("+"); printf("w[%d,%d,%d]",edgek[where[j]],x[0],q); printf("T[%d,%d,%d,%d",j+1,s-x[0],p,q); for (k=1;k<=r;k++) printf(",%d",x[k]); printf("]"); } printf(")"); } @*Index.