Slide 1 : 8 -1 Dynamic Programming
Fibonacci sequence : 8 -2 Fibonacci sequence Fibonacci sequence: 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , …
Fi = i if i 1
Fi = Fi-1 + Fi-2 if i 2
Solved by a recursive program:
Much replicated computation is done.
It should be solved by a simple loop.
Dynamic Programming : 8 -3 Dynamic Programming Dynamic Programming is an algorithm design method that can be used when the solution to a problem may be viewed as the result of a sequence of decisions
The shortest path : 8 -4 The shortest path To find a shortest path in a multi-stage graph
Apply the greedy method :
the shortest path from S to T :
1 + 2 + 5 = 8
The shortest path in multistage graphs : 8 -5 The shortest path in multistage graphs e.g.
The greedy method can not be applied to this case: (S, A, D, T) 1+4+18 = 23.
The real shortest path is:
(S, C, F, T) 5+2+2 = 9.
Dynamic programming approach : 8 -6 Dynamic programming approach Dynamic programming approach (forward approach):
d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} d(A,T) = min{4+d(D,T), 11+d(E,T)}
= min{4+18, 11+13} = 22.
Dynamic programming : 8 -7 Dynamic programming d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)}
= min{9+18, 5+13, 16+2} = 18.
d(C, T) = min{ 2+d(F, T) } = 2+2 = 4
d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)}
= min{1+22, 2+18, 5+4} = 9.
The above way of reasoning is called
backward reasoning.
Backward approach (forward reasoning) : 8 -8 Backward approach (forward reasoning) d(S, A) = 1
d(S, B) = 2
d(S, C) = 5
d(S,D)=min{d(S, A)+d(A, D),d(S, B)+d(B, D)}
= min{ 1+4, 2+9 } = 5
d(S,E)=min{d(S, A)+d(A, E),d(S, B)+d(B, E)}
= min{ 1+11, 2+5 } = 7
d(S,F)=min{d(S, A)+d(A, F),d(S, B)+d(B, F)}
= min{ 2+16, 5+2 } = 7
Slide 9 : 8 -9 d(S,T) = min{d(S, D)+d(D, T),d(S,E)+
d(E,T), d(S, F)+d(F, T)}
= min{ 5+18, 7+13, 7+2 }
= 9
Principle of optimality : 8 -10 Principle of optimality Principle of optimality: Suppose that in solving a problem, we have to make a sequence of decisions D1, D2, …, Dn. If this sequence is optimal, then the last k decisions, 1 k n must be optimal.
e.g. the shortest path problem
If i, i1, i2, …, j is a shortest path from i to j, then i1, i2, …, j must be a shortest path from i1 to j
In summary, if a problem can be described by a multistage graph, then it can be solved by dynamic programming.
Dynamic programming : 8 -11 Forward approach and backward approach:
Note that if the recurrence relations are formulated using the forward approach then the relations are solved backwards . i.e., beginning with the last decision
On the other hand if the relations are formulated using the backward approach, they are solved forwards.
To solve a problem by using dynamic programming:
Find out the recurrence relations.
Represent the problem by a multistage graph. Dynamic programming
The resource allocation problem : 8 -12 The resource allocation problem m resources, n projects
profit p(i, j) : j resources are allocated to project i.
maximize the total profit.
The multistage graph solution : 8 -13 The multistage graph solution The resource allocation problem can be described as a multistage graph.
(i, j) : i resources allocated to projects 1, 2, …, j
e.g. node H=(3, 2) : 3 resources allocated to projects 1, 2.
Slide 14 : 8 -14 Find the longest path from S to T :
(S, C, H, L, T), 8+5+0+0=13
2 resources allocated to project 1.
1 resource allocated to project 2.
0 resource allocated to projects 3, 4.
The traveling salesperson (TSP) problem : 8 -15 The traveling salesperson (TSP) problem e.g. a directed graph :
Cost matrix:
The multistage graph solution : 8 -16 A multistage graph can describe all possible tours of a directed graph.
Find the shortest path:
(1, 4, 3, 2, 1) 5+7+3+2=17 The multistage graph solution
The representation of a node : 8 -17 The representation of a node Suppose that we have 6 vertices in the graph.
We can combine {1, 2, 3, 4} and {1, 3, 2, 4} into one node.
(3),(4,5,6) means that the last vertex visited is 3 and the remaining vertices to be visited are (4, 5, 6).
The dynamic programming approach : 8 -18 The dynamic programming approach Let g(i, S) be the length of a shortest path starting at vertex i, going through all vertices in S and terminating at vertex 1.
The length of an optimal tour :
The general form:
Time complexity: ( ),( ) (n-k)
(n-1)