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.

Chapter**12**

**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

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.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Coping with the Limitations of Algorithm Power : Coping with the Limitations of Algorithm Power |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.