## 5.3 Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm As mentioned previously, the state space tree for each of the algorithms presented in the following sections contains an exponentially large or larger number of nodes. Given two instances with the samevalue of *n*, one of them may require that very few nodes be checked, whereas the other requires that the entire state space tree be checked. If we had an estimate of how efficiently a given backtracking algorithm would process a particular instance, we could decide whether using the algorithm on that instance was reasonable. We can obtain such an estimate using a Monte Carlo algorithm. Monte Carlo algorithms are probabilistic algorithms. By a ***probabilistic algorithm***, we mean one in which the next instruction executed is sometimes determined at random according to some probability distribution. (Unless otherwise stated, we assume that probability distribution is the uniform distribution.) By a ***deterministic algorithm***, we mean one in which this cannot happen. All the algorithms discussed so far have been deterministic algorithms. A ***Monte Carlo algorithm*** estimates the expected value of a random variable, defined on a sample space, from its average value on a random sample of the sample space. (See [Section A.8.1](LiB0100.html#1340) in [Appendix A](LiB0093.html#1281) for a discussion of sample spaces, random samples, random variables, and expected values.) There is no guarantee that the estimate is close to the true expected value, but the probability that it is close increases as the time available to the algorithm increases. We can use a Monte Carlo algorithm to estimate the efficiency of a backtracking algorithm for a particular instance as follows. We generate a "typical path" in the tree consisting of the nodes that would be checked given that instance, and then estimate the number of nodes in this tree from the path. The estimate is an estimate of the total number of nodes that would be checked to find all solutions. That is, it is an estimate of the number of nodes in the pruned state space tree. The following conditions must be satisfied by the algorithm in order for the technique to apply: 1. The same promising function must be used on all nodes at the same level in the state space tree. 2. Nodes at the same level in the state space tree must have the same number of children. Notice that [Algorithm 5.1](LiB0040.html#492) (The Backtracking Algorithm for the *n*-Queens Problem) satisfies these conditions. The Monte Carlo technique requires that we randomly generate a promising child of a node according to the uniform distribution. By this we mean that a random process is used to generate the promising child. (See [Section A.8.1](LiB0100.html#1340) in [Appendix A](LiB0093.html#1281) for a discussion of random processes.) When implementing the technique on a computer, we can generate only a pseudorandom promising child. The technique is as follows: - Let *m*0 be the number of promising children of the root. - Randomly generate a promising node at level 1. Let *m*1 be the number of promising children of this node. - Randomly generate a promising child of the node obtained in the previous step. Let *m*2 be the number of promising children of this node. ``` . . . ``` - Randomly generate a promising child of the node obtained in the previous step. Let *mi* be the number of promising children of this node. ``` . . . ``` This process continues until no promising children are found. Because we assume that nodes at the same level in the state space tree all have the same number of children, *mi* is an estimate of the average number of promising children of nodes at level *i.* Let > *ti* = total number of children of anode at level *i*. Because all *ti* children of a node are checked and only the *mi* promising children have children that are checked, an estimate of the total number of nodes checked by the backtracking algorithm to find all solutions is given by  A general algorithm for computing this estimate follows. In this algorithm, a variable *mprod* is used to represent the product *m*0*m*1… *m*i-1 at each level. Algorithm 5.2: Monte Carlo Estimate****Problem: Estimate the efficiency of a backtracking algorithm using a Monte Carlo algorithm. Inputs: an instance of the problem that the backtracking algorithm solves. Outputs: an estimate of the number of nodes in the pruned state space tree produced by the algorithm, which is the number of the nodes the algorithm will check to find all solutions to the instance. ``` int estimate () { node v; int m, mprod, t, numnodes; v = root of state space tree; numnodes = 1; m = 1; mprod = 1; while (m != 0){ t = number of children of v; mprod = mprod * m; numnodes = numnodes + mprod * t; m = number of promising children of v; if (m != 0) v = randomly selected promising child of v; } return numnodes; } ``` **** A specific version of [Algorithm 5.2](#ch05ex03) for [Algorithm 5.1](LiB0040.html#492) (The Backtracking Algorithm for the *n*-Queens Problem) follows. We pass *n* to this algorithm because *n* is the parameter to [Algorithm 5.1](LiB0040.html#492). Algorithm 5.3: Monte Carlo Estimate for [Algorithm 5.1](LiB0040.html#492) (The Backtracking Algorithm for the *n*-Queens Problem)****Problem: Estimate the efficiency of [Algorithm 5.1](LiB0040.html#492). Inputs: positive integer *n*. Outputs: an estimate of the number of nodes in the pruned state space tree produced by [Algorithm 5.1](LiB0040.html#492), which is the number of the nodes the algorithm will check before finding all ways to position *n* queens on an *n* × *n* chessboard so that no two queens threaten each other. ``` int estimate_n_queens (int n) { index i, j, col [1 . . n]; int m, mprod, numnodes; set_of_index prom_children; i = 0; numnodes = 1; m = 1; mprod = 1; while (m != 0 && i != n){ mprod = mprod * m; numnodes = numnodes + mprod * n; // Number of children t i++; // is n. m = 0; prom_children = ⊘ ; // Initialize set of for (j = 1; j <= n; j++){ // promising children col[i] = j; // to empty. if (promising (i)){ // Determine promising m++; // children. Function prom_children = prom_children ∪ {j}; // promising is the one // in Algorithm 5.1. } } if (m != 0){ j = random selection from prom_children; col [i] = j; } } return numnodes; } ``` **** When a Monte Carlo algorithm is used, the estimate should be run more than once, and the average of the results should be used as the actual estimate. Using standard methods from statistics, one can determine a confidence interval for the actual number of nodes checked from the results of the trials. As a rule of thumb, around 20 trials are ordinarily sufficient. We caution that although the probability of obtaining a good estimate is high when the Monte Carlo algorithm is run many times, there is never a guarantee that it is a good estimate. The *n*-Queens problem has only one instance for each value of *n*. This is not so for most problems solved with backtracking algorithms. The estimate produced by any one application of the Monte Carlo technique is for one particular instance. As discussed before, given two instances with the same value of *n*, one may require that very few nodes be checked whereas the other requires that the entire state space tree be checked. The estimate obtained using a Monte Carlo estimate is not necessarily a good indication of how many nodes will be checked before the first solution is found. To obtain only one solution, the algorithm may check a small fraction of the nodes it would check to find all solutions. For example, [Figure 5.4](LiB0039.html#483) shows that the two branches that place the first queen in the third and fourth columns, respectively, need not be traversed to find only one solution.