Dynamic programming is similar to divide-and-conquer, it divide the original problem into small part, but they have different directions, Dynamic programming is bottom-up, while divide-and-conquer is a top-down approach. In this approach, we solve the small instance and store the result in a table, when we need the result, we just search in the table, and thus save large amount of time to re-calculation.
The steps in the development of a dynamic programming
algorithm are as follows:
-
Establish a recursive property that gives the solution to an instance of the problem.
-
Solve an instance of the problem in a bottom-up fashion by solving smaller instances first.
A famous applications of dynamic programming is Floyd's Algorithm for Shortest Paths.
Using dynamic programming, we create a cubic-time algorithm for the Shortest Paths problem. First we develop an algorithm that determines only the lengths of the shortest paths. After that we modify it to produce shortest paths as well. We represent a weighted graph containing n vertices by an array W where
The array D in Figure 3.3 contains the lengths of the shortest paths in the graph. For example, D[3][5] is 7 because 7 is the length of a shortest path from v3 to v5. If we can develop a way to calculate the values in D from those in W, we will have an algorithm for the Shortest Paths problem. We accomplish this by creating a sequence of n + 1 arrays D(k), where 0 ≤ k ≤ n and where
Figure 3.3: W represents the graph in Figure 3.2 and D contains the lengths of the shortest paths. Our algorithm for the Shortest Paths problem computes the values in D from those in W. -
D(k)[i][j] = length of a shortest path from vi to vj using only vertices in the set {v1, v2, …, vk} as intermediate vertices.
Therefore, to determine D from W we need only find a way to obtain D(n) from D(0). The steps for using dynamic programming to accomplish this are as follows:
-
Establish a recursive property (process) with which we can compute D(k) from D(k-1).
-
Solve an instance of the problem in a bottom-up fashion by repeating the process (established in Step 1) for k = 1 to n. This creates the sequence
Dynamic programming algorithm provides a solution for an optimization problem, and the steps in the development of such an algorithm are as follows:
-
Establish a recursive property that gives the optimal solution to an instance of the problem.
-
Compute the value of an optimal solution in a bottom-up fashion.
-
Construct an optimal solution in a bottom-up fashion.
Steps 2 and 3 are ordinarily accomplished at about the same point in the algorithm.
The principle of optimality is said to apply in a problem if an optimal solution to an instance of a problem always contains optimal solutions to all substances.
posted on 2012-03-27 18:48
鷹擊長空 閱讀(180)
評論(0) 編輯 收藏 引用