[go: up one dir, main page]

0% found this document useful (0 votes)
67 views32 pages

ADA Module 5 - Full

Analysis and Design of Algorithms module 5

Uploaded by

rashmi gs
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
67 views32 pages

ADA Module 5 - Full

Analysis and Design of Algorithms module 5

Uploaded by

rashmi gs
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 32

Analysis And Design

of Algorithms
LIMITATIONS OF ALGORITHMIC POWER: Decision
Trees, P, NP, and NP-Complete Problems.

COPING WITH LIMITATIONS OF ALGORITHMIC


POWER: Backtracking (n-Queens problem, Subset-
sum problem), Branch-and-Bound (Knapsack
problem), Approximation algorithms for NP-Hard
problems (Knapsack problem).
Decision Trees
Example - Finding Minimum of Three Numbers:

• Each leaf node represents a possible outcome of the


algorithm’s run on some input.
• The number of leaves can be greater than the number of
outcomes due to different comparison paths leading to the
same outcome.
• The number of leaves must be at least as large as the
number of possible outcomes.
For any binary tree with l leaves and height h,

Indeed, a binary tree of height h with the largest number of leaves has all its
leaves on the last level. Hence, the largest number of leaves in such a tree is 2h. In
other words, 2h ≥ l, which immediately implies

Note: Worst-Case Number of Comparisons = n log2 n for any comparison-based


sorting algorithm
Decision Trees for Sorting
Decision Trees for Sorting
P, NP, and NP-complete problems
P Class Problem:
 A P class problem can be solved in "polynomial time," which means
that an algorithm exists for any problem’s solution such that the
number of steps in the algorithm is bounded by a polynomial function
of n, where n corresponds to the length of the input for the problem.
 This problem is easy to understand and tractable. This class of
problems is called polynomial. Example, sorting problems, searching
problems, etc.,
NP Class Problem:
 A problem is said to be Nondeterministic polynomial time that can be
solvable in polynomial time by a nondeterministic algorithms.
 The solutions to the NP class problem are hard to find since they are
being solved by a non-deterministic machine.
Problems listed below falls into the class of NP.

Traveling salesman problem Find the shortest tour through n cities


with known positive integer distances between them

Knapsack problem Find the most valuable subset of n items of given


positive integer weights and values that fit into a knapsack of a given
positive integer capacity.

Partition problem Given n positive integers, determine whether it is


possible to partition them into two disjoint subsets with the same sum.

Graph-coloring problem For a given graph, find its chromatic number,


which is the smallest number of colors that need to be assigned to the
graph’s vertices so that no two adjacent vertices are assigned the same
color.
P, NP, and NP-complete problems
Nondeterministic Algorithms
A nondeterministic algorithm is a two-stage procedure that takes as its
input an instance I of a decision problem and does the following;
1. Nondeterministic (“guessing”) stage: An arbitrary string S is
generated that can be thought of as a candidate solution to the given
instance I (but may be complete meaningless as well).
2. Deterministic (“verification”) stage: A deterministic algorithm takes
both I and S as its input and outputs yes if S represents a solution to
instance I. (If S is not a solution to instance I , the algorithm either
returns no or is allowed not to halt at all.)
Note: A nondeterministic algorithm is said to be nondeterministic
polynomial if the time efficiency of its verification stage is polynomial.
Example:
Algorithm Nsearch(A, n, key)
{
j = Choice(); 9 8 6 4 2 7

if (key = A[j])
{
write(j);
Success();
}
NP
write(0);
Failure();
} P

Relation between P and NP- Problems


P, NP, and NP-complete problems
NP-complete problems
An NP-complete problem is a problem in NP that is as difficult as any
other problem in this class because, any other problem in NP can be
reduced to NP-complete in polynomial time.
DEFINITION A decision problem D1 is said to be polynomially
reducible to a decision problem D2, if there exists a function t that
transforms instances of D1 to instances of D2 such that:
1. t maps all yes instances of D1 to yes instances of D2 and all no
instances of D1 to no instances of D2.
2. t is computable by a polynomial time algorithm.
The above definition implies that if a problem D1 is polynomially
reducible to some problem D2 that can be solved in polynomial time,
then problem D1 can also be solved in polynomial time.
P, NP, and NP-complete problems
NP-complete problems
Definition: A decision problem D is said to be NP-complete if:
1. it belongs to class NP
2. Every problem in NP is polynomially reducible to D.

Figure: Notion of an NP-complete problem. Polynomial-time reductions of NP


problems to an NP-complete problem are shown by arrows.
P class problems NP class problems
P problems are a set of problems that NP problems are problems that can
can be solved in polynomial time by be solved in nondeterministic
deterministic algorithms. polynomial time.
P Problems can be solved and The solution to NP problems cannot
verified in polynomial time. be obtained in polynomial time, but if
the solution is given, it can be
verified in polynomial time.
All P problems are deterministic in All the NP problems are non-
nature. deterministic in nature.
It takes polynomial time to solve a It takes non-deterministic polynomial
problem like n, n^2, n*log n, etc. time to quickly check a problem.
The solution to P class problems is The solution to NP class problems is
easy to find. hard to find.
Backtracking and Branch and Bound
Backtracking and Branch and Bound
 Both Backtracking and Branch-and-Bound are algorithm design
techniques.
 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.
 Both Backtracking and Branch-and-Bound techniques are based on
the construction of a state-space tree whose nodes reflect specific
choices made for a solution’s components.
Backtracking and Branch and Bound
Backtracking v/s Branch and Bound
 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 it
applies to non-optimization problems.
 In Backtracking the state-space tree is usually developed depth-first
(i.e., similar to DFS).
 In Branch-and-bound tree nodes are generated according to several
rules: the most natural one is the so-called best-first rule.
Backtracking and Branch and Bound
Developing state-space tree for subset-sum problem
Example :
S = {3, 5, 6, 7} d = 15

Solve S = {1,2,3,4,5} d = 7
Backtracking and Branch and Bound
Concept of Backtracking
The principal idea is to construct solutions one component at a time and
evaluate such partially constructed candidates as follows.
 If a partially constructed solution can be developed further without
violating the problem’s constraints, it is done by taking the first
remaining legitimate option for the next component.
 If there is no legitimate option for the next component, no
alternatives for any remaining component need to be considered.
 In this case, the algorithm backtracks to replace the last component
of the partially constructed solution with its next option.
 This idea is implemented by constructing a tree of choices being
made, called the state-space tree.
Backtracking and Branch and Bound
Concept of Backtracking
 Tree’s root represents an initial state before the search for a solution
begins.
 The nodes of the first level in the tree represent the choices made for
the first component of a solution, the nodes of the second level
represent the choices for the second component, and so on.
 A node in a state-space tree is said to be promising if it corresponds
to a partially constructed solution that may still lead to a complete
solution; otherwise, it is called non-promising (dead end).
 If the current node is promising, its child is generated by adding the
first remaining legitimate option for the next component of a solution,
and the processing moves to this child.
Backtracking and Branch and Bound
Concept of Backtracking
 If the current node turns out to be non-promising, the algorithm
backtracks to the node’s parent to consider the next possible option
for its last component; if there is no such option, it backtracks one
more level up the tree, and so on.
Subset-sum problem
 Finding a subset of a given set S = {s1,s2...,sn} of n positive integers
whose sum is equal to a given positive integer d.
 For example, for S = {1, 2, 5, 6, 8} and d = 9, there are two
solutions: {1, 2, 6} and {1, 8}.
 It is convenient to sort the set’s elements in increasing order. So, we
will assume that s1<=s2<=...<=sn .
Backtracking and Branch and Bound
Developing state-space tree for subset-sum problem
 The state-space tree can be constructed as a binary tree for the
problem S = {3, 5, 6, 7} and d = 15.
 The root of the tree represents the starting point, with no decisions
made about the given elements (empty subset).
 Its left and right children represent, respectively, inclusion (with 3 in
the example) and exclusion of S1(without 3 in the example) in a
subset being sought.
 Similarly, going to the left from a node of the first level corresponds
to inclusion of S2 (with 5 in the example) while going to the right
corresponds to exclusion of S2 (without 5 in the example) and so on.
 Thus, a path from the root to a node on the ith level of the tree
indicates which of the first i numbers have been included in the
subsets represented by that node.
Backtracking and Branch and Bound
Developing state-space tree for subset-sum problem
 Record the value of subset s, the sum of these numbers, in the node.
 If s is equal to d, we have a solution to the problem. We can either
report this result and stop or, if all the solutions need to be found,
continue by backtracking to the node’s parent.
 If s is not equal to d, we can terminate the node as non-promising if
either of the following two inequalities holds;
Backtracking and Branch and Bound
Algorithm SumOfSubset(s, k, r)
// Input: d & W[1…n] which holds the elements in increasing order
//Output: subsets whose sum = d.
{
x[k] = l;
if (s + w[k] == d) then
write (x[l : k]); // Subset found
else if (s + w[k] + w[k + 1] <= d) then //else add next element
SumOfSubset(s + w[k], k + l, r - w[k]);
if ((s + r - w[k] >= d) and (s + w[k + 1] <= d)) then //handle np nodes
{ // generate right child and evaluate that node
x[k] = 0;
s = initialSum = 0
SumOfSubset(s, k + l, r - w[k]);
k = index of the element = 1
} r = initial value is total of all elements = d

} x is a Boolean array whose size is equal to n


Backtracking and Branch and Bound
N-Queens problem
 The problem is to place n queens on an n × n chessboard such that no
two queens attack each other by being in the same row or in the same
column or on the same diagonal.
 For n = 1, the problem has a trivial solution.
 There is no solution for n = 2 and n = 3.
For n = 4, Since each of the four queens has to be placed in its own row,
all we need to do is to assign a column for each queen on the board
shown below;
Backtracking and Branch and Bound
State-space tree for solving n-
queens problem for n = 4

Nodes are numbered


in the order they are
generated.

We found one solution, still there


are choices to find other solution,
we need to backtrack and
continue with third column
placing Q1.
Abs(j - l) = Abs(i - k)
Backtracking and Branch and Bound

k = initial value = 1
n = number of queens
1 2 3 4
x 3 1 4 2
Backtracking and Branch and Bound
Branch and Bound
Compared to backtracking, branch-and-bound requires two additional
items:
1. A bound on the best value of the objective function on any solution
that can be obtained by adding further components to the partially
constructed solution represented by the node.
2. The value of the best solution seen so far.
Terminate a node when any one of the following condition met.
1. The value of the node’s bound is not better than the value of
the best solution seen so far.
2. The node represents no feasible solutions because the constraints of
the problem are already violated.
3. The subset of feasible solutions represented by the node consists of a
single point and hence no further choices can be made.
Branch and Bound

Backtracking Branch and Bound


Uses state space tree This also uses state space tree

Gives all feasible solutions Gives only optimal solution

DFS Traversal is used DFS and BFS Traversal is used

No bounding function Has bounding function (lower


bound and upper bound)
Eg: Knapsack, TSP
Branch and Bound
Solving Knapsack problem using Branch-and-bound technique
 First order the items of a given problem instance in descending order
by their value-to-weight ratios, such that
v1/w1 ≥ v2/w2 ≥ ... ≥ vn/wn.
 Each node on the ith level of this tree, 0 ≤ i ≤ n, represents all the
subsets of n items that include a particular selection made from the
first i ordered items.
 A branch going to the left indicates the inclusion of the next ith item,
and a branch going to the right indicates its exclusion.
 Record the total weight w and the total value v of this selection in
the node, along with some upper bound ub on the value of any
subset that can be obtained by adding zero or more items to this
selection.
ub = v + (W − w)(vi+1/wi+1)
Branch and Bound
Solving Knapsack problem using Branch-and-bound technique
Problem: knapsack capacity W = 10

Solution: state-space tree is constructed in next page.


Branch and Bound
State-space tree of Knapsack ub = v + (W − w)(vi+1/wi+1)
ub = 0 + (10 – 0)(40/4) = 100

ub = 0 + (10 – 0)(42/7)
= 60

ub = 40 + (10 – 4)(25/5) =
70

ub = 65 + (10 – 9)(12/3) ub = 40 + (10 – 4)(12/3)


= 69 = 64

Adding item 4,
exceeds knapsack No more items, this is
capacity. optimal solution {1,3} = 65

You might also like