Daa III-unit - Dynamic Programming

UNIT – III DESIGN AND ANALYSIS OF ALGORITHMS

DYNAMIC PROGRAMMING

BASIC METHOD •

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of sub-problems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

•

Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler sub-problems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.

•

Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems

•

Dynamic programming is used where we have problems, which can be divided into similar sub-problems, so that their results can be re-used. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems. The solutions of sub-problems are combined in order to achieve the best solution

BASIC METHOD So we can say that − •

The problem should be able to be divided into smaller overlapping sub-problem.

•

An optimum solution can be achieved by using an optimum solution of smaller sub-problems.

•

Dynamic algorithms use Memorization.

•

A given problem has Optimal Substructure Property, if the optimal solution of the given problem can be obtained using optimal solutions of its sub-problems.

•

For example, the Shortest Path problem has the following optimal substructure property −

•

If a node x lies in the shortest path from a source node u to destination node v, then the shortest path from u to v is the combination of the shortest path from u to x, and the shortest path from x to v.

Steps of Dynamic Programming Approach Dynamic Programming algorithm is designed using the following four steps − •

Characterize the structure of an optimal solution.

•

Recursively define the value of an optimal solution.

•

Compute the value of an optimal solution, typically in a bottom-up fashion.

•

Construct an optimal solution from the computed information.

APPLICATIONS OF DYNAMIC PROGRAMMING

0/1 KNAPSACK PROBLEM •• We   are given n objects and a knapsack(bag). Object i has a weight and capacity m. • If a solution is placed into the knapsack, then the profit is earned. • The objective is to obtain a filling of the knapsack that maximizes the total profit earned. • We require the total weight of the chosen objects to be at most m. • Hence, the objective of this algorithm is to Maximize Subject to <= m and, The profits and weights are positive numbers.

0/1 KnapSack Problem Ex :1- n=4,m=8 P={1,2,5,6} and W={2,3,4,5} Tabular Method:

 

 

Capac ity / Item 

P

W

0

0

0

0

0

0

0

0

0

0

1

2

1

0

0

1

1

1

1

1

1

1

2

3

2

0

0

1

2

2

3

3

3

3

5

4

3

0

0

1

2

5

5

6

7

7

6

5

4

0

0

1

2

5

6

6

7

8

0

1

2

3

4

5

6

7

8

0/1 KnapSack Problem • For the zero row, no item is selected and so no weight is included into knapsack. So fill first row with all 0’s and first column with all 0’s • For the first row consider first element. First element weight is 2. so fill second row second column with profit of the first item i.e 1. Only first element can be selected. So all the remaining columns values are 1 only, and left side column with previous value. • For the second row select second element. Second element weight is 3. so fill 3rd column in the 3 row with profit of the second item i.e 2. fill all the left side colmns with previous values. Here we must select both the items. So first two items weight is 5. total profit of first two item is 3. so fill column 5 with 3. fillleft side columns with previous valus. And right side columns with 3, because we can select first two items only. • For the third row, select 3rd item. Its weight is 4. so fill 4th column with its profit i.e 5. here we select first 3 items. But we may not select all three. But we must identify the combinations with 3rd item. If we select 3rd and 1st items, total weight is 6, so fill 6th column with total profit of 1st and 3rd items i.e 6 , in the same way select 3rd and 2nd items, total weight is 7 , so fill 7th column with total profit of 2nd and 3rd items, i.e 7.

0/1 Knapsack Problem • Fill the last column with 7 only, because we cannot select remaining items. • For the 4th row, select 4th item , the weight of the item is 5, so fill 5th column in 4th row with the profit of the 4th item, i.e 6. all the previous columns with the old values. Now select remaining items alongwith 4th itam. - select 4th item with 1st item , the total weight of these two items is 7, so fill 7th column with the total profit of these two items i.e 7. - select item 4 with second item, the total weight of these two items is 8, so fillthe 8th column with these two items profit, i.e 8. - 6th column with 5th column value. • After filling the entire row, now construct the solutionx1, x2, x3 and x4.

0/1 Knapsack Problem • Formula for filling all the rows: V[i, w] =max { V[i-1, w], V[i-1,w-w[i]]+p[i] } • V[4, 1] = max{ V[3, 1], V[3, 1-5] +6 } = max{ 0, v[3, -4] + 6} undefined.. So upto w=4 take the same values as previous row. • V[4, 5] = max{ V[3, 5], V[3, 5-5] +6 } = max{ 5, v[3, 0] + 6} = max{ 5, 0 + 6} = max{ 5, 6} = 6 • V[4, 6] = max{ V[3, 6], V[3, 6-5] +6 } = max{ 6, v[3, 1] + 6} = max{ 6, 0 + 6} = max{ 6, 6} = 6

0/1 Knapsack Problem • V[4, 7] = max{ V[3, 7], V[3, 7-5] +6 } = max{ 7, v[3, 2] + 6} = max{ 7, 1 + 6} = max{ 7, 7} = 7 • V[4, 8] = max{ V[3, 8], V[3, 8-5] +6 } = max{ 7, v[3, 3] + 6} = max{ 6, 2 + 6} = max{ 6, 8} = 8

0/1 Knapsack Problem • Select the maximum profit value , i.e. 8, which is there in 4th row, check whether 8 is there in 3rd row or not. Value is not there, means 4th row is included, so x4=1. - 4th row profit is 6. remaining profit is 8-6=2. • 2 is there in row 3, check whether 2 is there in row 2 or not. Value is there in 2nd row also , means 3rd item is not included. X3=0. • So 2 is there in row 2, check whether 2 is there in row 1 or not. No, value 2 is not there in row 1. so second item is included, x2=1. - so the remaining profit is 2-2=0 • 0 is there in row 1, check whether 0 is there in row 0 or not, yes row zero contain 0, so item 1 is not included, x1=0. • So the solution is : x1=0, x2=1, x3=0, x4=1. • Total profit obtained is = p1 * x1+ p2 * x2 + p3 * x3 + p4 * x4 = 1 *0 + 2 * 1 + 5 * 0 + 6 * 1= 8 Knapsack filled with weight = 2*0 + 3*1 + 4*0 + 5*1 = 8

0/1 Knapsack Problem Ex : 2 -- n=3,m=6 P={1,2,5} and W={2,3,4} Sets Method: Notice that S0 = {(0,0)}. We can compute Si+1 from Si by first computing Si1 = {(P,W) | ( P-pi , W-wi ) € Si } •

Now Si+1 can be obtained by merging Si and Si1.

•

If Si+1 is containing two pairs (pj , wj) and (pk , wk) with the property of pj ≤ pk and wj ≥ wk then the pair (pj , wj) can be discarded according to purging or discarding rule. ( (p j , wj) is dominating (pk , wk) ). ---- > Dominance rule.

S0 = {0,0}. S01 = { ( 0 + 1, 0 + 2) } = {(1, 2)} --- { add P1 , w1 to all the pairs in S0 }

S1 = S0 U S01 = {(0,0)} U {(1, 2)} = = { (0,0) , (1, 2) } -No pair is dominating other pairs. S11 = { (0+2, 0+3) , ( 1+2, 2+3) } ----- { add P2 , w2 to all the pairs in S1 } = { (2,3) , (3,5) } S2 = S1 U S11 = { (0,0) , (1, 2) } U { (2,3) , (3,5) }

S2 = { (0,0) , (1, 2), (2,3) , (3,5) }

--- No pair is dominating other pairs

0/1 Knapsack Problem •

S2 = { (0,0) , (1, 2), (2,3) , (3,5) } S21 = { (0+5, 0+4)

, (1+5 , 2+4), (2+5, 3+4), (3+5, 5+4) }

= { (5, 4), (6, 6), (7, 7), (8, 9) } --- { add P3 , w3 to all the pairs in S2 } S3 = S2 U S21 = { (0,0) , (1, 2), (2,3) , (3,5) } U { (5, 4), (6, 6), (7, 7), (8, 9) }

S3 = {(0,0) , (1, 2), (2,3) , (3,5) , (5, 4), (6, 6), (7, 7), (8, 9) }

• In the above set (3,5) is dominating (5, 4) , so according to purging or dominance rule (3, 5) can be purged or deleted • Also (7,7) and (8,9) pairs are also deleted because the weights are exceeding the knapsack capacity. The resultant Set is : S3 = {(0,0) , (1, 2), (2,3) , (5, 4), (6, 6) }

0/1 Knapsack Problem • Constructing Solution : - select the last pair in the last set i.e. (6, 6) € S3 , check if this pair is there in S2 . If it is there in S2 , third element is not included. No, (6, 6) does not belonging to S2 . So 3rd item is included. x3 =1. for the next solution subtract P3 , w3 from the last pair i.e. (6, 6). The resultant pair is ( 6 – 5, 6 – 4) , i.e. (1,2) - (1,2) is there in S2 , check if this pair is there in S 1 on not. Yes, (1, 2) is there in S1 , so 2nd item is not included, x2 =0. - (1,2) is there in S1 , check if this pair is there in S 0 , No this pair is not there in S0 , so first item is included, x1 =1. • The solution is : x1 =1, x2 =0, x3 =1. • Total profit gained is : 1*1 + 2*0 + 5*1 = 6 • Total weight included is : 2*1 + 3*0 + 4*1 = 6 • Time complexity of 0 1 Knapsack problem is O(nW) where, n is the number of items and W is the capacity of knapsack.

0/1 Knapsack Problem

RELIABILITY DESIGN •

Reliability design using dynamic programming is used to solve a problem with a multiplicative optimization function. The problem is to design a system which is composed of several devices connected in series.

•

Let ri; be the reliability of device Di; (i.e. ri; is the probability that device i will function properly). Then, the reliability of the entire system is πri . Even if the individual devices are very reliable (the ri 's are very close to one), the reliability of the system may not be very good.

•

Ex : if n=10 and ri=0.99, 1<=i<=10, πri = 0.904.

•

Hence it is desirable to duplicate the devices. Multiple copies of the same device type are connected in parallel.

RELIABILITY DESIGN • If stage i contains mi copies of devise Di , then the probability that all mi have a •  malfunction is (i- r ) mi . Hence the reliability of stage i becomes 1-(1- r ) mi. Thus if i i ri= 0.99 and mi=2, then the stage reliability becomes 1-(1-0.99)2 = 0.9999. • In any practical situation the stage reliability is little less than 1-(1- ri) mi . because the switching circuits themselves are not fully reliable. Also the failure of copies of the same device may not be fully independent. • Let us assume that the reliability of the stage i is given by the function φi(mi), ≤ n. The reliability of the system of stages is given by φi(mi), 1 ≤ i ≤n .

i

• Our problem is to use device duplication to maximize reliability. the maximization is carried out under a cost constraint. Let be the cost of each unit of device type I and let C be the maximum allowable cost of the system being designed. • The problem statement is : Maximize φi(mi), 1 ≤ i ≤n Subject to ≥ 1 and 1 ≤ i ≤n

RELIABILITY DESIGN

RELIABILITY DESIGN

RELIABILITY DESIGN

RELIABILITY DESIGN

RELIABILITY DESIGN

RELIABILITY DESIGN

Travelling Salesperson Problem

Travelling Salesperson Problem

Travelling Salesperson Problem

Travelling Salesperson Problem

Travelling Salesperson Problem

Travelling Salesperson Problem

Travelling Salesperson Problem

All Pairs Shortest Path Problem

All Pairs Shortest Path Problem

All Pairs Shortest Path Problem

All Pairs Shortest Path Problem

All Pairs Shortest Path Problem

All Pairs Shortest Path Problem

All Pairs Shortest Path Problem

All Pairs Shortest Path Problem

All Pairs Shortest Path Problem

All Pairs Shortest Path Problem

Optimal Binary Search Trees

Optimal Binary Search Trees

Optimal Binary Search Trees

Optimal Binary Search Trees

Optimal Binary Search Trees

Optimal Binary Search Trees

Optimal Binary Search Trees

Optimal Binary Search Trees

Optimal Binary Search Trees

Optimal Binary Search Trees

Optimal Binary Search Trees