CSCI 333: Using a Monte Carlo Algorithm to Estimate Efficiency

Monte Carlo algorithms are probabilistic algorithms, which are algorithms such that the next instruction executed is sometimes determined at random according to some probability distribution.

We can use a Monte Carlo algorithm to estimate the efficiency of a backtracking algorithm for a particular instance of a problem. First, we generate a “typical path” which consists of nodes that would be checked given that instance, and then estimate the number of nodes in this tree from the path. The estimate is of the total number of nodes that would be checked to find all solutions.

These conditions should be satisfied so that we can apply the above technique:

  • The same promising function must be used on all nodes at the same level in the state space tree.
  • Nodes at the same level in the state space tree must have the same number of children.

The technique requires that we randomly generate a promising child of a node according to a uniform distribution. The algorithm proceeds as follows until a leaf node is reached.

  • let mo be the number of promising children of the root
  • Randomly select a promising node at level 1. Let m1 be the number of promising children of this node.
  • Randomly select a promising child of the node obtained in the previous step. Let m2 be the number of promising children of this node.
  • …
  • Randomly select a promising child of the node obtained in the previous step. Let mi be the number of promising children of this node.
  • …

Let: ti = the number of children of a node at level i

mi = the number of promising children of a node at level i

then an estimate of the total number of nodes checked =

1+t0+m0t1+m0m1t2+…+ m0m1m2… mi-1ti+…

The General Algorithm

Problem: Estimate the efficiency of a backtracking algorithm on a particular problem instance using a Monte Carlo technique.

Inputs: An instance of the problem.

Outputs: An estimate of the number of nodes in the pruned state space tree.

int estimate()

{

node v = root of the tree;

int m=1, mprod=1, numnodes=1, t;

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 = a randomly selected promising child of v;

}

return numnodes;

}

The Algorithm Specific to the n-Queens problem

Problem: Estimate the efficiency of algorithm 5.1 for a particular value of n using a Monte Carlo technique.

Inputs: the positive integer n---the instance of the problem.

Outputs: An estimate of the number of nodes in the pruned state space tree produced by algorithm 5.1 for n.

int estimate_n_queens(int n)

{

index i, j, col[1..n];

int m=1, mprod=1, numnodes=1;

set_of_index prom_children=0;

i=0;

while (m != 0 & i != n) {

mprod = mprod * m;

numnodes = numnodes + mprod * n;

i++;

m = 0;

for (j=1; j<=n; j++) {

col[i] = j;

if ( promising(i) ) {

m++;

prom_children = prom_children U {j};

}

if (m != 0) {

j = randomly selected child from prom_children;

col[i] = j;

}

}

return numnodes;

}

Two Additional Points

You should run the algorithm multiple times and average the results to obtain the best estimate. As a rule of thumb, 20 trails are usually sufficient.

While the n-Queens problem has only one instance for each value of n, this is usually not the case. Keep in mind, the estimate produced by each run of estimate() is for one particular instance of the problem.

Work problem 10 but do not (unless you want to) implement the algorithm.