Transcript Advanced Algorithms

Advanced Algorithms Analysis
and Design
Lecture 13 AND 14
Dynamic Programming
And P, NP and NPC problems
1
Optimization Problems
• If a problem has only one correct solution, then
optimization is not required
• For example, there is only one sorted sequence
containing a given set of numbers.
• Optimization problems have many solutions.
• We want to compute an optimal solution e. g. with
minimal cost and maximal gain.
• There could be many solutions having optimal value
• Dynamic programming is very effective technique to
solve such problem
2
Elements of DP Algorithms
• Sub-structure: decompose problem into smaller
sub-problems. Express the solution of the original
problem in terms of solutions for smaller problems.
• Table-structure: Store the answers to the subproblem in a table, because sub-problem solutions
may be used many times.
• Bottom-up computation: combine solutions on
smaller sub-problems to solve larger sub-problems,
and eventually arrive at a solution to the complete
problem.
3
Why Dynamic Programming?
• Dynamic programming, like divide and conquer
method, solves problems by combining the
solutions to sub-problems.
• Divide and conquer algorithms:
• partition the problem into independent sub-problem
• Solve the sub-problem recursively and
• Combine their solutions to solve the original problem
• In contrast, dynamic programming is applicable
when the sub-problems are not independent.
• Dynamic programming is typically applied to
optimization problems.
4
EXAMPLE :DP
•
•
•
•
Chain-Matrix Multiplication
Longest Common Subsequence
Optimal search binary tree
Edit Distance etc
5
Chain-Matrix Multiplication
6
Problem Statement: Chain Matrix Multiplication
Statement: The chain-matrix multiplication
problem can be stated as below:
• Given a chain of [A1, A2, . . . , An] of n matrices
where for i = 1, 2, . . . , n, matrix Ai has dimension
pi-1 x pi, find the order of multiplication which
minimizes the number of scalar multiplications.
Note:
• Order of A1 is p0 x p1,
• Order of A2 is p1 x p2,
• Order of A3 is p2 x p3, etc.
• Order of A1 x A2 is p0 x p2,
• Order of A1 x A2 x A3 is p0 x p3,
• Order of A1 x A2 x . . . x An is p0 x pn
7
Objective is to find order not multiplication
• Given a sequence of matrices, we want to find a
most efficient way to multiply these matrices
• It means that problem is not actually to perform the
multiplications, but decide the order in which these
must be multiplied to reduce the cost.
• This problem is an optimization type which can be
solved using dynamic programming.
.
8
Assumptions (Only Multiplications Considered)
• We really want is the minimum cost to multiply
• But we know that cost of an algorithm depends on
how many number of operations are performed i.e.
• We must be interested to minimize number of
operations, needed to multiply out the matrices.
• As in matrices multiplication, there will be addition
as well multiplication operations in addition to other
• Since cost of multiplication is dominated over
addition therefore we will minimize the number of
multiplication operations in this problem.
• In case of two matrices, there is only one way to
multiply them, so the cost fixed.
9
Chain Matrix Multiplication
(Brute Force Approach)
10
Brute Force Chain Matrix Multiplication
Example
• Given a sequence [A1, A2, A3, A4]
• Order of A1 = 10 x 100
• Order of A2 = 100 x 5
• Order of A3 = 5x 50
• Order of A4 = 50x 20
Compute the order of the product A1 . A2 . A3 . A4
in such a way that minimizes the total number of
scalar multiplications.
11
Brute Force Chain Matrix Multiplication
• There are five ways to parenthesize this product
• Cost of computing the matrix product may vary,
depending on order of parenthesis.
• All possible ways of parenthesizing
(A1 · (A2 . (A3 . A4)))
(A1 · ((A2 . A3). A4))
((A1 · A2). (A3 . A4))
((A1 · (A2 . A3)). A4)
(((A1 · A2). A3). A4)
12
Kinds of problems solved by algorithms
10 x 100 x 20 = 20000
1
10 x 20
A1
10 x 100
100 x 5 x 20 = 10000
2
100 x 20
A2
100 x 5
A3
5 x 50
3
5 x 50 x 20 = 5000
5 x 20
Total Cost = 35000
A4
50 x 20
13
Second Chain : (A1 · ((A2 . A3). A4))
1
10 x100 x 20 = 20000
10 x 20
3
A1
10 x 100
2
100 x 20
A4
50 x 20
100 x 50
A2
100 x 5
100 x 50 x 20 = 100000
A3
5 x 50
100 x 5 x 50 = 25000
Total Cost = 145000
14
Third Chain : ((A1 · A2). (A3 . A4))
10 x 5 x 20 = 1000
2
10 x 100 x 5 = 5000
10x20
5 x 50 x 20 = 5000
1
3
10 x 5
A1
10 x 100
A2
100 x 5
5 x 20
A3
5 x 50
A4
50 x 20
Total Cost = 11000
15
Fourth Chain : ((A1 · (A2 . A3)). A4)
3
10 x 50 x 20 = 10000
10x20
10 x 100 x 50 = 50000
100 x 5 x 50 = 25000
Total Cost = 85000
1
A4
50x20
10x50
A1
10x100
2
100x50
A2
100x5
A3
5x50
16
Fifth Chain : (((A1 · A2). A3). A4)
10 x 50 x 20 = 10000
3
10 x 20
10 x 5 x 50 = 2500
2
A4
50 x 20
10 x 50
10 x 100 x 5 = 5000
1
Total Cost = 17500
A1
10 x 100
A3
5 x 50
10 x 5
A2
100 x 5
17
Chain Matrix Cost
First Chain
Second Chain
Third Chain
Fourth Chain
Fifth Chain
35,000
145,000
11,000
85,000
17,500
((A1 · A2). (A3 . A4))
2
10x20
1
3
10 x 5
A1
10 x 100
A2
100 x 5
5 x 20
A3
5 x 50
A4
50 x 20
18
Generalization of Brute Force Approach
• If there is sequence of n matrices, [A1, A2, . . . , An]
• Ai has dimension pi-1 x pi, where for i = 1, 2, . . . , n
• Find order of multiplication that minimizes number
of scalar multiplications using brute force approach
Recurrence Relation(POSSIBLE WAYS): After kth
matrix, create two sub-lists, one with k and other
with n - k matrices i.e.
(A1 A2A3A4A5 . . . Ak) (Ak+1Ak+2…An)
• Let P(n) be the number of different ways of
parenthesizing n items
19
Generalization of Brute Force Approach
If n = 2
P(2) = P(1).P(1) = 1.1 = 1
If n = 3
P(3) = P(1).P(2) + P(2).P(1) = 1.1 + 1.1 = 2
(A1 A2A3) = ((A1 . A2). A3) OR (A1 . (A2. A3))
If n = 4
P(4) = P(1).P(3) + P(2).P(2) + P(3).P(1) = 1.2 + 1.1
+ 2.1 = 5
20
Chain Matrix Multiplication Problem using
Dynamic Programming
21
Why Dynamic Programming in this problem?
•
•
•
•
•
•
•
Problem is of type optimization
Sub-problems are dependant
Optimal structure can be characterized and
Can be defined recursively
Solution for base cases exits
Optimal solution can be constructed
Hence here is dynamic programming
22
Problem Statement: Chain Matrix Multiplication
Statement: The chain-matrix multiplication
problem can be stated as below:
• Given a chain of [A1, A2, . . . , An] of n matrices for
i = 1, 2, . . . , n, matrix Ai has dimension pi-1 x pi,
find the order of multiplication which minimizes
the number of scalar multiplications.
Note:
• Order of A1 is p0 x p1,
• Order of A2 is p1 x p2,
• Order of A3 is p2 x p3, etc.
• Order of A1 x A2 x A3 is p0 x p3,
• Order of A1 x A2 x . . . x An is p0 x pn
23
Dynamic Programming Formulation
•
•
•
•
•
•
•
Let Ai..j = Ai . Ai+1 . . . Aj
Order of Ai = pi-1 x pi, and
Order of Aj = pj-1 x pj,
Order of Ai..j = rows in Ai x columns in Aj = pi-1 × pj
At the highest level of parenthesisation[final
multiplication],
Ai..j = Ai..k × Ak+1..j
i≤k<j
Let m[i, j] = minimum number of multiplications
needed to compute Ai..j, for 1 ≤ i ≤ j ≤ n
Objective function = finding minimum number of
multiplications needed to compute A1..n i.e. to
compute m[1, n]`
24
Extracting Optimum Sequence
• We maintain a parallel array s[i, j] in which we store
the value of k providing the optimal split .Leave a
split marker indicating where the best split is (i.e.
the value of k leading to minimum values of m[i, j])..
• If s[i, j] = k, the best way to multiply the sub-chain
Ai…j is to first multiply the sub-chain Ai…k and then the
sub-chain Ak+1…j , and finally multiply them together.
Intuitively s[i, j] tells us what multiplication to
perform last. We only need to store s[i, j] if we have
at least 2 matrices & j > i.
Mathematical Model
Ai..j = (Ai. Ai+1….. Ak). (Ak+1. Ak+2….. Aj) = Ai..k × Ak+1..j
i≤k<j
• Order of Ai..k = pi-1 x pk, and order of Ak+1..j = pk x pj,
• m[i, k] = minimum number of multiplications
needed to compute Ai..k
• m[k+1, j] = minimum number of multiplications
needed to compute Ak+1..j
• Mathematical Model
26
Example: Dynamic Programming
•
Problem: Compute optimal multiplication order
for a series of matrices given below
A3
A1
A2
A4
.
.
.
10 100 100  5 5  50 50  20
P0 = 10
P1 = 100
P2 = 5
P3 = 50
P4 = 20
m[1,1] m[1,2] m[1,3] m[1,4]
m[2,2] m[2,3] m[2,4]
m[3,3] m[3,4]
m[4,4]
27
Main Diagonal
m[i, i]  0, i  1,...,4
m[i, j ]  min (m[i, k ]  m[k  1, j ]  pi 1. pk . p j )
i k  j
Main Diagonal
• m[1, 1] = 0
• m[2, 2] = 0
• m[3, 3] = 0
• m[4, 4] = 0
28
Computing m[1, 2], m[2, 3], m[3, 4]
m[i, j ]  min (m[i, k ]  m[k  1, j ]  pi 1. pk . p j )
i k  j
m[1,2]  min (m[1, k ]  m[k  1,2]  p0 . pk . p2 )
1 k  2
m[1,2]  min (m[1,1]  m[2,2]  p0 . p1. p2 )
m[1, 2] = 0 + 0 + 10 . 100 . 5
= 5000
s[1, 2] = k = 1
29
Computing m[2, 3]
m[i, j ]  min (m[i, k ]  m[k  1, j ]  pi 1. pk . p j )
i k  j
m[2,3]  min (m[2, k ]  m[k  1,3]  p1. pk . p3 )
2 k 3
m[2,3]  min (m[2,2]  m[3,3]  p1. p2 . p3)
m[2, 3] = 0 + 0 + 100 . 5 . 50
= 25000
s[2, 3] = k = 2
30
Computing m[3, 4]
m[i, j ]  min (m[i, k ]  m[k  1, j ]  pi 1. pk . p j )
i k  j
m[3,4]  min (m[3, k ]  m[k  1,4]  p2 . pk . p4 )
3 k  4
m[3,4]  min (m[3,3]  m[4,4]  p2 . p3 . p4 )
m[3, 4] = 0 + 0 + 5 . 50 . 20
= 5000
s[3, 4] = k = 3
31
Computing m[1, 3], m[2, 4]
m[i, j ]  min (m[i, k ]  m[k  1, j ]  pi 1. pk . p j )
i k  j
m[1,3]  min (m[1, k ]  m[k  1,3]  p0 . pk . p3 )
1 k 3
m[1,3]  min (m[1,1]  m[2,3]  p0 . p1. p3 ,
m[1,2]  m[3,3]  p0 . p2 . p3 ))
m[1, 3] = min(0+25000+10.100.50, 5000+0+10.5.50)
= min(75000, 2500) = 2500
s[1, 3] = k = 2
32
Computing m[2, 4]
m[i, j ]  min (m[i, k ]  m[k  1, j ]  pi 1. pk . p j )
i k  j
m[2,4]  min (m[2, k ]  m[k  1,4]  p1. pk . p4 )
2 k  4
m[2,4]  min (m[2,2]  m[3,4]  p1. p2 . p4 ,
m[2,3]  m[4,4]  p1. p3 . p4 ))
m[2, 4] = min(0+5000+100.5.20, 25000+0+100.50.20)
= min(15000, 35000) = 15000
s[2, 4] = k = 2
33
Computing m[1, 4]
m[i, j ]  min (m[i, k ]  m[k  1, j ]  pi 1. pk . p j )
i k  j
m[1,4]  min (m[1, k ]  m[k  1,4]  p0 . pk . p4 )
1 k  4
m[1,4]  min (m[1,1]  m[2,4]  p0 . p1. p4 ,
m[1,2]  m[3,4]  p0 . p2 . p4 , m[1,3]  m[4,4]  p0 . p3 . p4 )
m[1, 4] = min(0+15000+10.100.20, 5000+5000+
10.5.20, 2500+0+10.50.20)
= min(35000, 11000, 35000) = 11000
s[1, 4] = k = 2
34
Final Cost Matrix and Its Order of Computation
• Final Cost Matrix
0
5000 2500
0
25000 15000
0
1
• Order of Computation
11000
5000
0
5
8
10
2
6
9
3
7
4
35
K,s Values Leading Minimum m[i, j]
0
1
2
2
0
2
2
0
3
0
36
37
38
Representing Order using Binary Tree
•
•
The above computation shows that the minimum
cost for multiplying those four matrices is 11000.
The optimal order for multiplication is
((A1 . A2) . (A3 . A4))
2
For, m(1, 4)
k=2
10x20
1
3
10 x 5
A1
10 x 100
A2
100 x 5
5 x 20
A3
5 x 50
A4
50 x 20
39
Chain-Matrix-Order(p)
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
n  length[p] – 1
for i  1 to n
m[1,1] m[1,2] m[1,3] m[1,4]
do m[i, i]  0
m[2,2] m[2,3] m[2,4]
for l  2 to n,
m[3,3] m[3,4]
do for i  1 to n-l+1
m[4,4]
do j  i+l-1
m[i, j]  
for k  i to j-1
do q  m[i, k] + m[k+1, j] + pi-1 . pk . pj
if q < m[i, j]
then m[i, j] = q
s[i, j]  k
return m and s,
“l is chain length”
40
Computational Cost
n
n
n
n i
T (n)  n    ( j  i)   k
i 1 j i 1
i 1 k 1
(n  i)(n  i  1)
T ( n)  n  
2
i 1
n
1 n 2
T (n)  n   (n  2ni  i 2  n  i)
2 i 1
n
n
n
1 n 2 n
T (n)  n  ( n   2ni   i 2   n   i)
2 i 1
i 1
i 1
i 1
i 1
41
Computational Cost
n
n
n
1 n 2 n
T (n)  n  ( n   2ni   i 2   n   i)
2 i 1
i 1
i 1
i 1
i 1
n
n
n
n
1 2 n
T (n)  n  (n 1  2n i   i 2  n1   i)
2
i 1
i 1
i 1
i 1
i 1
1 2
n(n  1) n(n  1)( 2n  1)
n(n  1)
T (n)  n  (n .n  2n.

 n.n 
)
2
2
6
2
42
Computational Cost
1 2
n(n  1) n(n  1)( 2n  1)
n(n  1)
T (n)  n  (n .n  2n.

 n.n 
)
2
2
6
2
1 3
n(n  1)( 2n  1)
n(n  1)
2
2
T (n)  n  (n  n (n  1) 
n 
)
2
6
2
1
T (n)  n  (6n 3  6n 3  6n 2  2n 3  3n 2  n  6n 2  3n 2  3n)
12
1
1
1
3
3
T (n)  (12 n  2n  2n)  (10 n  2n )  (5n  n 3 )
12
12
6
43
Cost Comparison Brute Force Dynamic Programming
Dynamic Programming
• Hence total cost =  (n3)
44
P, NP & NP Complete Problems
&
Vertex Cover Problem
45
P, NP & NPC Problems
►Natural
to think that ,can all problems be
solved in some specified time, or ever..???
►Algorithmic
and computational problems can
be categorized into three categories.
►Polynomial
Time, P
►Non Polynomial, NP
►Non Polynomial Complete, NPC
46
P Problems
►All
problems are in class P, that, on input of
size N are solvable in the time O(Nk) ,for
some constant k.
►The worst case for such problems is O(Nk)
► Many Problems like
►Binary
Search
►Sorting Algorithms
►MST
are solvable in polynomial time.
47
NP Problems
NP problems are called “hard problems”.
►Such problems can not be solved ,
regardless of, how much time they are
provided, until they are given a certificate
that they are verifiable.
►Certificate is issued while limiting the
domain of that problem and proving that,
this instance is solvable in Polynomial Time.
►
48
NP Problems
Verification algorithms for each specific domain of
algorithms exist.
► One simple example of NP problem is
►
 Find sum of all even numbers.
Regardless of which computer is used, and how
much time is provided, the sum can not be found.
► But if we limit ,that provide the sum of first one
trillion even numbers, it is solvable in some time,
may be in polynomial.
►
49
NPC Problems
►All
such problems that can’t be solved
regardless of any computer and time are
called NP-Complete problems.
►Example
1: Find the sum of all even
numbers without a verifiable certificate.
►Example 2: Find longest path from A to D in
a graph, where each node can be visited
more than once.
50
NPC Problems
1
1
B
1
A
1
E
1
C
1
D
51
NPC Problems
►NPC
problems are also called open
problems.
►This means that neither the researchers
have come to some conclusion, nor they
have given up saying “no solution exist for
this problem”
►So
NPC problems are open research areas.
52
P, NP & NPC Problems
►
How to determine that a problem is in NPC
 Determine if it is in P
►Solvable
in some O(Nk) time
 If not , see if it is in NP
►A
certificate can be issued, and that can be verified
for some domain of the problem.
 If not so, the problem is an NP-Complete
problem.
53
NP-Completeness
Generally, we think of problems that are solvable by polynomial-time
algorithms are good, and problems that require super polynomial
time.
are intractable
Polynomial
Intractables
?
NP-Complete
Problem
54
Vertex Cover (VC) Problem
Given a graph, find a smallest set of
vertices that is incident to every edge
in the graph
►The
size of VC is determined by the number
of the vertices covered by the algorithm.
►The VC Problem was taken as hard problem,
but the researchers have shown an
algorithm to find a vertex cover.
55
Vertex Cover Problem
The algorithm returns a vertex cover whose
size is guaranteed to be no more than twice
the size of an optimal vertex cover.
►
►Size
of the vertex cover is determined by
the number of vertices in it.
56
Example :Network Power
Say you have a network, with links between some
components
Each link requires power supply, hence, you need to
supply power to a set of nodes that cover all links
Obviously, you’d like to connect the smallest number of
nodes
57
Vertex Cover Problem Algorithm
APP-Vertex-Cover(G)
C ← ø {C contains the vertex cover being constructed}
E’ ← E[G] { E’ contains the copy of edge set E[G]}
while E’ !=ø
do let (u,v) be an arbitrary edge in E’
C ← C U {u,v}
remove from E’ every edge incident on either u or v
Return C
58
Vertex Cover Problem
b
c
d
a
e
f
g
59
Vertex Cover Problem
►
Execution
C
ø
E’
(a,b),(b,c),(c,e),(c,d),(e,f),(d,e),(d,g),(d,f)
(b,c)
(d,e),(e,f),(d,g),(d,f)
(e,f)
(d,g)
(d,g)
Ø
60
Vertex Cover Problem
b
c
d
a
e
f
g
61
Vertex Cover Problem
Edge (b,c) is chosen
b
c
d
a
e
f
g
62
Vertex Cover Problem
Edge (e,f) is chosen
b
c
d
a
e
f
g
63
Vertex Cover Problem
Edge (d,g) is chosen
b
c
d
a
e
f
g
64
Vertex Cover Problem
Vertex cover by the algorithm {vertices : b, c,
d, e, f, g } so VC=6
b
c
d
a
e
f
g
65
Vertex Cover Problem
Optimal vertex cover
{vertices : b, d, e }
b
c
d
a
e
f
g
66
Vertex Cover Problem
c
b
a
d
g
h
e
f
i
j
67
►
Vertex Cover Problem
Execution of Algorithm
C
ø
(a,g)
E’
(a,b), (a,g),(a,h),(b,c),(b,g),(g,h), (g,i),(g,f),
(c,d),(c,f), (d,e), (d,f),(f,i),(f,e),(f,j), (e,j),
(c.g),(h,i),(i,j)
(a,b),(a,g),(a,h),(b,c),(b,g),(g,h),(g,i),(c,d),
(c,g), (h,i),(i,j)
(b,c),(c,d),(h,i),(i,j)
(h,i)
(b,c)
(b,c),(c,d)
ø
(e,f)
68
Vertex Cover Problem
Step 1. Selection edge (e,f)
25
69
Vertex Cover Problem
Step 2. Selection edge (a,g)
26
70
Vertex Cover Problem
Step 3. Selection edge (h,i)
27
71
Vertex Cover Problem
Step 4. Selection edge (b,c)
72
Vertex Cover Problem
Selected Vertices (Vertex Cover Size=8)
c
b
a
d
g
h
e
f
i
j
73
Vertex Cover Problem
►
The running time of the algorithm is O(V + E)
74
Subset-Sum Problem NP PROBLEM
► An
instance of the sunset sum problem is a pair (S,t),
 where S = {x1,x2,x3, …….xn} of positive integers
 and t (target) is a positive integer.
 This decision problem asks whether there exists a subset of S that
adds up exactly or approximately close to the target value t(result
less than target).
The optimization problem associated with this decision
problem arises in practical applications.
► Subset sum problem is NP-complete.
.
► Algorithms
of subset-sum problems try to provide exact or
approximately close result to required target so that its
relative error is small. It is around about 0.5.
►
75
Subset-Sum Problem
S={1,4,16,64,256,1040,1041,1093,1284,1344}
► t=3754
►
S’={1,16,64,256,1040,1093,1284}
► In subset-sum problem, there exists a subset such that
►
76
77
78
79
80
Conclusion
 Scientists believe that NP related problems
can be solved and they are trying to discover
the more efficient algorithms to solve such
problems.
 Some of them solve these problems in
exponential-time and researchers are trying
to convert them in polynomial-time so that
they become more efficient.
81