Limitations of
Unit 14 Coping with the
Algorithm Power
Structure
14.1 Introduction
Objectives
14.2 Backtracking
Outline of the algorithm
14.3 Branch and Bound
Outline of the algorithm
Effectiveness of the algorithm
14.4 Approximation Algorithms for NP-Hard Problems
Underlying principles
Approximation algorithms
14.5 Summary
14.6 GlossaryY
14.7 Terminal Questions
14.8 Answers
14.1 Introduction
In the earlier unit, you have learnt about the different limitations of algorithm
power. In this unit we will study about how to cope with some of these
limitations.
Combinatorial problems include counting of structures of a specific kind or
size, identifying the largest, smallest or optimal objects, constructing and
analyzing combinatorial structures. Backtracking and Branch and Bound
algorithm design techniques help in solving some of the large instances of
combinatorial problems. They define potential solutions, component by
component, and evaluate these partial solutions. They do not generate
solutions for the remaining components if they determine that these
components do not lead to a solution.
Both Backtracking and Branch and Bound construct state-space trees. The
nodes of these trees indicate the choices of solutions of a component. When
no solution can be obtained by consideration of the choices corresponding
to the descendants of the node, both these techniques terminate.
, Drancn and Bound is generally used f o r optimization problems as
possible values of the objective function of
bound the
Computes Ita on
problem. usually uses the Best-first rule to construct space ree
Backtracking is mostly used for non-optimization problems. This technique
constructs space trees
using the Depth-First approach.
This unit also discusses approximation algorithms for NP-Hard problems ke
the Iraveling Salesman and the Knapsack problems. Greedy algorithms are
good approximation algorithms for the Knapsack problem.
Objectives:
After studying this unit you should be able to:
analyze the algorithm technique of Backtracking
explain the solution strategy of
Branch-and-Bound
discuss the approximation approach to cope with limitations of NP-Hard
problems
14.2 Backtracking
Problems that need to find an element in a domain that
grows exponentially
with the size of the input, like the Hamiltonian circuit and
the Knapsack
problem. are not solvable in polynomial time. Such problems can be solved
by the exhaustive search technique,
which requires identifying the correct
solution from many candidate solutions.
Backtracking technique is a
refinement of this approach. Backtracking is a
surprisingly simple approach
and can be used even for solving the hardest Sudoku puzzle.
We can implement Backtracking by constructing the
state-space tree, which
is a tree of choices. The root of the state-space tree
indicates the initial
state, before the search for the solution begins. The nodes of each level
of
this tree signify the candidate solutions for the
corresponding component. A
node of this tree is considered to be promisingif it
represents a partially
constructed solution that can lead to a complete solution, else they are
considered to be non-promising. The leaves of the tree signify either
the
non-promising dead-ends or the complete solutions.
We use the Depth-First-search method usually for constructing these state-
space-trees. If a node is promising, then a child-node is
generated by
adding the first legitimate chOIce of the next component and the
processing
continues for the child node. But it a node is
non-promising, then the
, algorithm backtracks to the parent node and considers the next promising
solution for that component. But if there are no more choices for that
component, the algorithm backtracks one more level higher. The algorithm
stops when it finds a complete solution.
This technique is illustrated by the figure 14.1. Here the algorithm goes from
the start node to node 1 and then to node 2. When no solution is found it
backtracks to node1 and goes to the next possible solution node 3. But
node 3 is also a dead-end. Hence the algorithm backtracks once again to
node 1 and then to the start node. From here it goes to node 4 and repeats
the procedure till node 6 is identified as the solution.
Deadend Dead-end
- --sooy
Node 1 NoOe 2
Deadend
Node 3
Start
Dead-end
Node 5
Success
Node4
Node 5
Figure 14.1: Backtracking Technique
14.2.1 Outline of the algorithm
The Backtracking algorithm
constructs solutions for each component
sequentially and evaluates these partially constructed solutions. If the
algorithm can develop a partially constructed solution without violating the
problem constraints, it considers the first legitimate solution for the next
component. But if there is no legitimate solution for the next component or
for the remaining components, then the algorithm backtracks to replace the
last partially constructed solution with the next option.
The output of the Backtracking algorithm is an n-tuple (b1, b2,......, b,) where
each co-ordinate b is an element of a finite linearly ordered set S, The
tuple
may also have to satisfy some additional constraints depending on the
problem. The tuple can be of either fixed length or variable length depending
Unit 14 Coping with the
Algorithm Power
Structure
14.1 Introduction
Objectives
14.2 Backtracking
Outline of the algorithm
14.3 Branch and Bound
Outline of the algorithm
Effectiveness of the algorithm
14.4 Approximation Algorithms for NP-Hard Problems
Underlying principles
Approximation algorithms
14.5 Summary
14.6 GlossaryY
14.7 Terminal Questions
14.8 Answers
14.1 Introduction
In the earlier unit, you have learnt about the different limitations of algorithm
power. In this unit we will study about how to cope with some of these
limitations.
Combinatorial problems include counting of structures of a specific kind or
size, identifying the largest, smallest or optimal objects, constructing and
analyzing combinatorial structures. Backtracking and Branch and Bound
algorithm design techniques help in solving some of the large instances of
combinatorial problems. They define potential solutions, component by
component, and evaluate these partial solutions. They do not generate
solutions for the remaining components if they determine that these
components do not lead to a solution.
Both Backtracking and Branch and Bound construct state-space trees. The
nodes of these trees indicate the choices of solutions of a component. When
no solution can be obtained by consideration of the choices corresponding
to the descendants of the node, both these techniques terminate.
, Drancn and Bound is generally used f o r optimization problems as
possible values of the objective function of
bound the
Computes Ita on
problem. usually uses the Best-first rule to construct space ree
Backtracking is mostly used for non-optimization problems. This technique
constructs space trees
using the Depth-First approach.
This unit also discusses approximation algorithms for NP-Hard problems ke
the Iraveling Salesman and the Knapsack problems. Greedy algorithms are
good approximation algorithms for the Knapsack problem.
Objectives:
After studying this unit you should be able to:
analyze the algorithm technique of Backtracking
explain the solution strategy of
Branch-and-Bound
discuss the approximation approach to cope with limitations of NP-Hard
problems
14.2 Backtracking
Problems that need to find an element in a domain that
grows exponentially
with the size of the input, like the Hamiltonian circuit and
the Knapsack
problem. are not solvable in polynomial time. Such problems can be solved
by the exhaustive search technique,
which requires identifying the correct
solution from many candidate solutions.
Backtracking technique is a
refinement of this approach. Backtracking is a
surprisingly simple approach
and can be used even for solving the hardest Sudoku puzzle.
We can implement Backtracking by constructing the
state-space tree, which
is a tree of choices. The root of the state-space tree
indicates the initial
state, before the search for the solution begins. The nodes of each level
of
this tree signify the candidate solutions for the
corresponding component. A
node of this tree is considered to be promisingif it
represents a partially
constructed solution that can lead to a complete solution, else they are
considered to be non-promising. The leaves of the tree signify either
the
non-promising dead-ends or the complete solutions.
We use the Depth-First-search method usually for constructing these state-
space-trees. If a node is promising, then a child-node is
generated by
adding the first legitimate chOIce of the next component and the
processing
continues for the child node. But it a node is
non-promising, then the
, algorithm backtracks to the parent node and considers the next promising
solution for that component. But if there are no more choices for that
component, the algorithm backtracks one more level higher. The algorithm
stops when it finds a complete solution.
This technique is illustrated by the figure 14.1. Here the algorithm goes from
the start node to node 1 and then to node 2. When no solution is found it
backtracks to node1 and goes to the next possible solution node 3. But
node 3 is also a dead-end. Hence the algorithm backtracks once again to
node 1 and then to the start node. From here it goes to node 4 and repeats
the procedure till node 6 is identified as the solution.
Deadend Dead-end
- --sooy
Node 1 NoOe 2
Deadend
Node 3
Start
Dead-end
Node 5
Success
Node4
Node 5
Figure 14.1: Backtracking Technique
14.2.1 Outline of the algorithm
The Backtracking algorithm
constructs solutions for each component
sequentially and evaluates these partially constructed solutions. If the
algorithm can develop a partially constructed solution without violating the
problem constraints, it considers the first legitimate solution for the next
component. But if there is no legitimate solution for the next component or
for the remaining components, then the algorithm backtracks to replace the
last partially constructed solution with the next option.
The output of the Backtracking algorithm is an n-tuple (b1, b2,......, b,) where
each co-ordinate b is an element of a finite linearly ordered set S, The
tuple
may also have to satisfy some additional constraints depending on the
problem. The tuple can be of either fixed length or variable length depending
