232 OTHER ALGORITHMIC TECHNIQUES
should also try to answer any questions before reading on. A hint or the answer
is in the sentences following the question.s was discussed in Chapter 8, problems in the class NP are important
to a number of applications, and so their solution is of interest.
Because these problems do not have polynomial time algorithms that
can produce an exact solution, we must consider alternative algorithms that
can only produce reasonably good answers. In some cases, these algorithms
will find the optimal answer, but that is luck and cannot be guaranteed. We will
explore a number of approximation algorithms for the problems we looked at
in Chapter 8.
The basic idea of probabilistic algorithms is that it is sometimes better to
guess than to figure out which option is correct. There are four classifications
of probabilistic algorithms—numerical, Monte Carlo, Las Vegas, and Sher-
wood—although some analysis texts will refer to all probabilistic algorithms as
“Monte Carlo.” The common theme throughout these categories is that prob-
abilistic algorithms will produce better results the longer that they are run.
This chapter ends with the application of dynamic programming algorithms
to improve the efficiency of recursive algorithms and to select an order to mul-
tiply a series of matrices to reduce the computational complexity.9.1 Greedy Approximation Algorithms
In Chapter 6, we saw two greedy algorithms that identified the minimum
spanning tree of a graph and one that determined the shortest path between
two nodes of a graph. In this section, we look at a number of greedy algo-
rithms that approximate the optimal solution for problems in the class NP.
As we have discussed, the difficulty of finding an exact solution for problems
in the class NP is the number of combinations of the input values that must be
checked. For each collection of input values I, we can create a set of possible
solutions PSI. An optimal solution would be Soptimal∈ PSI, such that Value
(Soptimal)≤ Value(S) for all S∈ PSI if the problem is a minimization problemA