Algorithms in a Nutshell

(^310) | Chapter 10: When All Else Fails
Algorithms That Can Be Wrong, but with Diminishing
Probability
In this section we study algorithms that may be wrong, but with diminishing
probability. With a modest computation, we can assure that the likelihood of
producing a wrong answer can be made arbitrarily small.
/* If no board is available at this row then return false. /
public boolean randomNextBoard(int r) {
int sz = nextValidRowPositions.size( );
if (sz == 0) { return false; }
// select one randomly
int c = ((int)(Math.random( )sz));
board[r][nextValidRowPositions.get(c)] = true;
return true;
}
}
public class SingleQuery {
public static void main (String []args) {
for (int i = 0; i < 100; i++) {
System.out.println(i + ": " + estimate(19));
}
}
public static long estimate(int n) {
Board b = new Board(n);
int r = 0;
long lastEstimate = 1;
while (r < n) {
int numChildren = b.numChildren(r);
// no more to go, so no solution found.
if (!b.randomNextBoard(r)) {
lastEstimate = 0;
break;
}
// compute estimate based on ongoing tally and advance
lastEstimate = lastEstimatenumChildren;
r++;
}
return lastEstimate;
}
}
Example 10-2. Implementation of Knuth’s randomized estimation of n-Queens
problem (continued)
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use