Java Reference
In-Depth Information
organize the processing of all the subproblems to a problem so that the work is
done efficiently.
If we need to do a brute-force search of the entire solution space, we can use
backtracking to visit all of the possible solutions organized in a solution tree. For
example, SATISFIABILITY has 2
n
possible ways to assign truth values to the n
variables contained in the Boolean expression being satisfied. We can view this as
a tree of solutions by considering that we have a choice of making the first variable
true
or
false
. Thus, we can put all solutions where the first variable is
true
on
one side of the tree, and the remaining solutions on the other. We then examine the
solutions by moving down one branch of the tree, until we reach a point where we
know the solution cannot be correct (such as if the current partial collection of as-
signments yields an unsatisfiable expression). At this point we backtrack and move
back up a node in the tree, and then follow down the alternate branch. If this fails,
we know to back up further in the tree as necessary and follow alternate branches,
until finally we either find a solution that satisfies the expression or exhaust the
tree. In some cases we avoid processing many potential solutions, or find a solution
quickly. In others, we end up visiting a large portion of the 2
n
possible solutions.
Banch-and-Bounds is an extension of backtracking that applies to optimiza-
tion problems such as TRAVELING SALESMAN where we are trying to find the
shortest tour through the cities. We traverse the solution tree as with backtrack-
ing. However, we remember the best value found so far. Proceeding down a given
branch is equivalent to deciding which order to visit cities. So any node in the so-
lution tree represents some collection of cities visited so far. If the sum of these
distances exceeds the best tour found so far, then we know to stop pursuing this
branch of the tree. At this point we can immediately back up and take another
branch. If we have a quick method for finding a good (but not necessarily best)
solution, we can use this as an initial bound value to effectively prune portions of
the tree.
Another coping strategy is to find an approximate solution to the problem.
There are many approaches to finding approximate solutions. One way is to use
a heuristic to solve the problem, that is, an algorithm based on a “rule of thumb”
that does not always give the best answer. For example, the TRAVELING SALES-
MAN problem can be solved approximately by using the heuristic that we start at
an arbitrary city and then always proceed to the next unvisited city that is closest.
This rarely gives the shortest path, but the solution might be good enough. There
are many other heuristics for TRAVELING SALESMAN that do a better job.
Some approximation algorithms have guaranteed performance, such that the
answer will be within a certain percentage of the best possible answer. For exam-
ple, consider this simple heuristic for the VERTEX COVER problem: Let M be
a maximal (not necessarily maximum) matching in G. A matching pairs vertices
(with connecting edges) so that no vertex is paired with more than one partner.
