Chapter12
Coping
with the Limitations of Algorithm Power
Keep on the lookout for novel ideas that others have used
successfully. Your idea has to be original only in its adaptation to the
problem you’re working on.
—Thomas
Edison (1847–1931)
As we saw in the previous chapter, there are problems that are difficult to solve algorithmically. At the same time, some of them are so important that we cannot just sigh in resignation and do nothing. This chapter outlines several ways of dealing with such difficult problems.
Sections 12.1 and 12.2
introduce two algorithm design techniques—back-tracking and
branch-and-bound—that often make it possible to solve at least some
large instances of difficult combinatorial problems. Both strategies can be
considered an improvement over exhaustive search, discussed in Section 3.4.
Unlike exhaustive search, they construct candidate solutions one component at a
time and evaluate the partially constructed solutions: if no potential values
of the remaining components can lead to a solution, the remaining components
are not generated at all. This approach makes it possible to solve some large
instances of difficult combinatorial problems, though, in the worst case, we
still face the same curse of exponential explosion encountered in exhaustive
search.
Both backtracking and
branch-and-bound are based on the construction of a state-space tree whose
nodes reflect specific choices made for a solution’s compo-nents. Both techniques
terminate a node as soon as it can be guaranteed that no solution to the
problem can be obtained by considering choices that correspond to the node’s
descendants. The techniques differ in the nature of problems they can be
applied to. Branch-and-bound is applicable only to optimization problems
because it is based on computing a bound on possible values of the problem’s
objective function. Backtracking is not constrained by this demand, but more
often than not, it applies to nonoptimization problems. The other distinction
be-tween backtracking and branch-and-bound lies in the order in which nodes of
the state-space tree are generated. For backtracking, this tree is usually
developed depth-first (i.e., similar to DFS). Branch-and-bound can generate nodes
accord-ing to several rules: the most natural one is the so-called best-first
rule explained in Section 12.2.
Section 12.3 takes a break
from the idea of solving a problem exactly. The algorithms presented there
solve problems approximately but fast. Specifically, we consider a few
approximation algorithms for the traveling salesman and knap-sack problems. For
the traveling salesman problem, we discuss basic theoretical results and
pertinent empirical data for several well-known approximation algo-rithms. For
the knapsack problem, we first introduce a greedy algorithm and then a
parametric family of polynomial-time algorithms that yield arbitrarily good
ap-proximations.
Section 12.4 is devoted to
algorithms for solving nonlinear equations. After a brief discussion of this
very important problem, we examine three classic methods for approximate root
finding: the bisection method, the method of false position, and Newton’s
method.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.