The Idea of Developing a DP Algorithm :
Step 1: Structure : Characterize the structure of an optimal solution.
-Decompose the problem into smaller problems, and find a relation between the structure of the optimal solution of the original problem and the solutions of the smaller pronlms.
Step 2 : Principle of Optimality : Recursively define the value of an optimal solution.
-Express the solution of the original problem in terms of optimal solutions for smaller problems.
Step 3 : Bottom-up computation: Compute the value of an optimal solution in a bottom-up fashion by using a table structure.
Step 4 : construction of optimal Solution : Construct an optimal solution from computed information.Steps 3 and 4 may often be combined.
Step 1: Structure : Characterize the structure of an optimal solution.
-Decompose the problem into smaller problems, and find a relation between the structure of the optimal solution of the original problem and the solutions of the smaller pronlms.
Step 2 : Principle of Optimality : Recursively define the value of an optimal solution.
-Express the solution of the original problem in terms of optimal solutions for smaller problems.
Step 3 : Bottom-up computation: Compute the value of an optimal solution in a bottom-up fashion by using a table structure.
Step 4 : construction of optimal Solution : Construct an optimal solution from computed information.Steps 3 and 4 may often be combined.
No comments:
Post a Comment