TAOCP 7.2.2.1 Exercise 86
The corrected solution is given below.
Section 7.2.2.1: Dancing Links
Exercise 86. ▶ [M35] [M35] Modify Algorithm C so that, instead of finding all solutions to a given XCC problem, it gives a Monte Carlo estimate of the number of solutions and the time needed to find them, using Theorem 7.2.2E. (Thus the modified algorithm is to Algorithm C as Algorithm 7.2.2E is to Algorithm 7.2.2B.)
Verified: no
Solve time: 3m02s
The corrected solution is given below. The running-time estimator is defined with the correct node-dependent path weights, and the modification is stated directly in terms of Algorithm C's branching process.
Edit
Let (T) be the search tree produced by Algorithm C for the given XCC problem. A node of (T) represents a recursive call of Algorithm C, including the residual XCC instance and the partial solution chosen so far. If a node is not terminal, Algorithm C selects a primary item and branches to one child for each currently available option of that item.
For a node (v), let (b(v)) denote the number of children of (v). In the original Algorithm C, all (b(v)) children are recursively explored. The Monte Carlo modification replaces this complete branching by a random choice of one child. If (v) is reached, the modified algorithm chooses each child with probability
[ \frac{1}{b(v)}. ]
A single random trial therefore follows one random path from the root until it reaches a terminal node. For a node (v), define its path weight by
[ W(v)=\prod_{u\prec v} b(u), ]
where the product is over all nonterminal ancestors (u) of (v), including the root if the root is nonterminal. The empty product at the root is (1). Since each branch is chosen with probability (1/b(u)), the probability that a trial reaches (v) is
[ \frac{1}{W(v)}. ]
This is exactly the sampling scheme required by Theorem 7.2.2E.
To estimate the number of solutions, let (L) be the terminal node reached by one trial. Define
[ X= \begin{cases} W(L),&\text{if }L\text{ is a solution leaf},[4pt] 0,&\text{if }L\text{ is a failure leaf}. \end{cases} ]
Consider a particular solution leaf (\lambda). The probability that the trial reaches (\lambda) is
[ \frac{1}{W(\lambda)}. ]
When this happens, its contribution to (X) is (W(\lambda)). Hence the expected contribution of this leaf is
[ \frac{1}{W(\lambda)}W(\lambda)=1. ]
Every solution leaf contributes (1) to the expectation, and every failure leaf contributes (0). Therefore
[ E(X)=N, ]
where (N) is the exact number of solutions of the XCC problem. With (r) independent trials, the Monte Carlo estimate is
[ \widehat N=\frac1r\sum_{k=1}^{r}X_k . ]
By linearity of expectation,
[ E(\widehat N)=N. ]
It remains to estimate the time required by Algorithm C to enumerate all solutions. Let (c(v)) be the amount of work performed by Algorithm C when it visits node (v). This includes the local operations performed at that recursive call. The total exhaustive-search cost is therefore
[ T=\sum_{v\in T}c(v). ]
A single random trial visits only the nodes on one root-to-leaf path. The contribution of a visited node (v) must use the path weight of that node, not the final weight of the terminal leaf. Define the random variable
[ Y=\sum_{\substack{v\text{ visited}\text{during the trial}}} c(v)W(v). ]
For a fixed node (v), the probability that the random trial visits (v) is
[ \frac1{W(v)}. ]
Therefore its expected contribution to (Y) is
[ \frac1{W(v)}c(v)W(v)=c(v). ]
Summing over all nodes of the complete Algorithm C search tree gives
[ E(Y)=\sum_{v\in T}c(v)=T. ]
Thus, for (r) independent trials, the estimator
[ \widehat T=\frac1r\sum_{k=1}^{r}Y_k ]
satisfies
[ E(\widehat T)=T. ]
The modified Algorithm C is therefore obtained as follows. At each recursive call, instead of iterating through all options of the chosen primary item, it chooses one available option uniformly at random and continues recursively. During the random walk it maintains the current path weight (W(v)). Whenever a node is visited, it adds (c(v)W(v)) to the time-estimation accumulator. When a terminal node is reached, it adds (W(v)) to the solution accumulator if the node is a solution and adds nothing otherwise. After (r) independent trials, it divides both accumulators by (r).
The output is the pair
[ (\widehat N,\widehat T), ]
where (\widehat N) is a Monte Carlo estimate of the number of XCC solutions and (\widehat T) is a Monte Carlo estimate of the time Algorithm C would require to enumerate all solutions.
The construction is precisely the analogue of Algorithm 7.2.2E applied to the search tree of Algorithm C: successful leaves estimate the number of solutions, while weighted visited nodes estimate the total exhaustive-search cost.