03-06-2013, 02:09 PM
Dynamic Programming (DP)
Dynamic Programming.ppt (Size: 473.5 KB / Downloads: 32)
Like divide-and-conquer, solve problem by combining the solutions to sub-problems.
Differences between divide-and-conquer and DP:
Independent sub-problems, solve sub-problems independently and recursively, (so same sub(sub)problems solved repeatedly)
Sub-problems are dependent, i.e., sub-problems share sub-sub-problems, every sub(sub)problem solved just once, solutions to sub(sub)problems are stored in a table and used for solving higher level sub-problems.
Application domain of DP
Optimization problem: find a solution with optimal (maximum or minimum) value.
An optimal solution, not the optimal solution, since may more than one optimal solution, any one is OK.
Typical steps of DP
Characterize the structure of an optimal solution.
Recursively define the value of an optimal solution.
Compute the value of an optimal solution in a bottom-up fashion.
Compute an optimal solution from computed/stored information.
Brute Force Solution
List all possible sequences,
For each sequence of n stations, compute the passing time. (the computation takes (n) time.)
Record the sequence with smaller passing time.
However, there are total 2n possible sequences.
Subtleties when Determining Optimal Structure
Take care that optimal structure does not apply even it looks like to be in first sight.
Unweighted shortest path:
Find a path from u to v consisting of fewest edges.
Can be proved to have optimal substructures.
Unweighted longest simple path:
Find a simple path from u to v consisting of most edges.
Figure 15.4 shows it does not satisfy optimal substructure.
Independence (no share of resources) among subproblems if a problem has optimal structure.
Summary
DP two important properties
Four steps of DP.
Differences among divide-and-conquer algorithms, DP algorithms, and Memoized algorithm.
Writing DP programs and analyze their running time and space requirement.
Modify the discussed DP algorithms.