CS502 GDB Idea Solution Spring July 2012
Dynamic Programming is always preferable over greedy approach ” Support or contradict this statement with solid arguments. Solution No.1 Dynamic programming is both a mathematical optimization method and a computer programming method. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub problems in a recursive manner. [ While some decision problems cannot be taken apart this way, decisions that
span several points in time do often break apart recursively; Bellman called this the "Principle of Optimality". Likewise, in computer science, a problem that can be broken down recursively is said to have optimal substructure. If sub problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub problems.[5] In the optimization literature this relationship is called the Bellman equation.
Solution No.2 Yes, it is true. Although these both approaches are used to solve problems optimally, but in the same time there are some reasons which make Dynamic programming preferable over greedy approach e.g. dynamic programming solves problems by breaking down in smaller sub problems and also stores results in some form for
future reference, which definitely comes always in a solution and also in optimal one. while greedy approach always progress in best possible solution at present without thinking about future hence it can some time mislead us in such that it cannot provide any solution to the problem. For your reference there is also an example given below which will help to
understand the greedy approach disadvantage.
So we can conclude that how simple greedy approach mislead us and thus we cannot get our
required solution. Now it totally clears that using greedy approach if we start from node 7 at that point the best possible of both is 12 hence it will go towards 12 and then finally towards 6. While if we look other side of tree the best possible we can obtain is 99. So we can conclude that how simple greedy approach mislead us and thus we cannot get our required solution.
Solution No.3 A greedy
algorithm is similar to a dynamic programming algorithm, but the difference is that
solutions to the subproblems do not have to be known at each stage; instead a “greedy” choice can be made of what looks best for the moment.
Consider this example.
You are standing at a place A. You are to goto B. There are intermediate places C1,C2 …
You want to minimize
distance travelled.
Greedy Method of SolvingYou don’t want to try all intermediate places. You go to the nearest intermediate place. Why? You feel by going to the nearest intermediate place, you will minimize the distance to B.
Dynamic ProgrammingYou try all the places, but you store the previous result. Eg: To reach C3 in minimum distance, you reached by C1. So you store C1. So if you want to go to C5, by C3, you will go to C1 then C3 and then check if going from C3 to C5 is nearest.
Solution No.4 Dynamic Programming is always preferable over greedy approach because reasons which make Dynamic programming preferable over greedy approach e.g. dynamic programming solves problems by breaking down in smaller sub problems and also stores results in some form for future reference, which definitely comes always in a solution and also in optimal one. while greedy approach always progress in best possible solution at present without thinking about future hence it can some time mislead us in such that it cannot provide any solution to the problem.
