9.2 PROBABILISTIC ALGORITHMS 247This equation is saying that if we succeed, the overall time is the time it
takes to get a success. But if we fail, it is the time for the failure plus another
call to the function. Solving this equation for time(x), we get
time(x) = p(x) success(x) + (1 p(x)) failure(x) + (1 p(x))* time(x)
time(x) (1 p(x)) time(x) = p(x) success(x) + (1 p(x))* failure(x)
time(x) time(x) + p(x) time(x) = p(x) success(x) + (1 p(x))* failure(x)
p(x) time(x) = p(x) success(x) + (1 p(x))* failure(x)
time(x) = success(x) + ((1 p(x)) / p(x))* failure(x)
This means that the time is dependent on the execution of success, failure, and
the probability of each. The interesting fact is that if the probability of success
(p(x)) is lowered, the overall time can still be reduced if failures are calculated
more quickly. So, we can improve efficiency by solving failures faster even if it
slightly lowers the chance of success.
How would this work in practice? Well, consider the eight queens problem,
which tries to place a set of eight queens on a chessboard so that they are not
attacking each other.^4 One possible solution for this problem is shown in Fig.
9.5. A recursive algorithm to solve this problem would place a queen in the
first column of the first row and then call itself to place a queen in the second
row. If at any point it can’t find a location for a queen on the current row, it
will back up and try a different location for the queen on the previous row.
There is a probabilistic alternative to this recursive algorithm. We could
place queens on the board so that each new queen gets placed randomly on
one of the spaces on the next row that is not attacked. The difference between
a Las Vegas and the standard recursive algorithm is that when the Las Vegas ver-
sion can’t place a queen on a row, it just gives up and signals a failure. The
recursive version backs up to try to fix things so as to force an answer. An algo-
rithm for Las Vegas eight queens would be
Queens( result )
result holds the column positions of the queens for each row
returns 1 if this succeeded and 0 if it failed
(^4) In chess, the queen can attack any other piece that is in the same row, column, or
along a diagonal.