How can I prove that a dynamic programming (dp) strategy for a problem will work or not? For greedy algorithms, we can prove by showing the sub problems exhibits matroid property. Is there any such methods for dp algorithms?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
In principle, any multi-stage optimization problem is solvable using dynamic programming, if you can come up with the right notion of the state. You do not mention which class of problems you are working on, so it hard to give general guidelines. I'll make the following assumptions here:
In order to solve such a problem by dynamic programming, you need to come up with a state staten that satisfies the following properties:
If these conditions are satisfied, then dynamic programming gives an optimal solution. First you define value functions
and recursively solve for these value functions in a backward manner.
NOTE: These are the simplest class of problems that can be solved using dynamic programming. For more details, see any standard book on dynamic programming, e.g., Berksekas.
In general, the Dynamic Programming solution can be proved by showing that your solution exhibits the Optimal Substructure property.
Basically, you formulate the actual problem as composed of smaller subproblems and then combine the solutions to get your final answer. In combining, if the problem size increases, then the solution for smaller subproblem must still be optimal for the combination to actually work.
For example, if in a graph you are trying to find an the shortest path between A and C, and you already know(somehow) that that path passes through an intermediate point B, and you already know the shortest way to get from A to B, then you only need to find a shortest way to get to C from B. You don't have to worry about finding a new way all the way from A to C, that's what the optimal substructure property means. For a dynamic programming correctness proof, proving this property is enough to show that your approach is correct.
They way you prove Greedy algorithm by showing it exhibits matroid structure is correct, but it does not always work. Some greedy algorithms will not show Matroid structure, yet they are correct Greedy algorithms. For example, Huffman encoding scheme is a greedy approach, but it does not exhibit matroid structure.
To prove a greedy algorithm, in general, you need to show that your solution exhibits -1) optimal substructure property as in DP and 2) The choice made by a greedy approach is not sub-optimal (basically show that it is optimal or one of the optimal choices that can be made at that point in time)