Dynamic Programming is always preferable over greedy approach " Support or contradict this statement with solid arguments.
Note:
A concise, coherent and to the point comment is preferred over lengthy comment having irrelevant details. Your comment must not be more than 5-7 lines. Comments, posted on regular Lesson's MDB or sent through email will NOT be considered. Any request about such an acceptance will not be catered.
launched on July 9, 2012 and it will remain open till July 10, 2012.
Tags:
in GDB of cs502 our answer may be as follows:
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 with out thinking about future hence it can some time mislead us in such that it can not 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.
let's suppose we want to prune (search) this given tree for getting best or maximum output or our goal is to find maximum value.
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 can not get our required solution.
one thing note please.
this is example only for your understanding it is not part of our solution other wise if any one added this will get 0 marks.
so, don't copy paste write in your own words to get maximum marks....which must be 5 now after this solution.
enjoy......
bhai pic to nahi bani na
ha ha ha ha ha.
dear picture q bnani ha? wesy ye Wikipedia se li ha ap b check ker skty ho. yeh to sirf example k leye hai k ap bat smajh jeyen aur apny words me likh saken.......
akram ul haq gud keep it up
thanks a lot
CS502GDB Solution Idea
In GDB of cs502 our answer may be asfollows:
Yes, it is true.
although these both approaches areused to solve problems optimally, but in the same time there are some reasonswhich make Dynamic programming preferable over greedy approach e.g. dynamicprogramming solves problems by breaking down in smaller sub problems and alsostores results in some form for future reference, which definitely comes alwaysin a solution and also in optimal one. while greedy approach always progress inbest possible solution at present with out thinking about future hence it cansome time mislead us in such that it can not provide any solution to theproblem.
for your reference there is also anexample given below which will help to understand the greedy approachdisadvantage.
So we can conclude that how simplegreedy approach mislead us and thus we can not get our required solution.
thanks
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 Solving
You dont want to try all intermediate places. You goto the nearest intermediate place. Why? You feel by going to the nearest intermediate place, you will minimize the distance to B.
Dynamic Programming
You 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 goto C1 then C3 and then check if going from C3 to C5 is nearest.
Dynamic Programming is always preferable over greedy approach because reasons which make Dynamic programming preferable over greedy approach e.g. dynamicprogramming solves problems by breaking down in smaller sub problems and alsostores results in some form for future reference, which definitely comes alwaysin a solution and also in optimal one. while greedy approach always progress inbest possible solution at present with out thinking about future hence it cansome time mislead us in such that it can not provide any solution to the problem.
CSCS502 GDB
Topic:
Dynamic Programming is always preferable over greedy approach " Support or contradict this statement with solid arguments.
Note:
A concise, coherent and to the point comment is preferred over lengthy comment having irrelevant details. Your comment must not be more than 5-7 lines. Comments, posted on regular Lesson's MDB or sent through email will NOT be considered. Any request about such an acceptance will not be catered.
CSCS502 GDB
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.
one thing note please.
this is example only for your understanding it is not part of our solution otherwise if any one added this will get 0 marks.
so, don't copy paste write in your own words to get maximum marks....which must be 5 now after this 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 Solving
You 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 Programming
You 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.
100% true solution
In GDB of cs502 our answer may be asfollows:
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 misleads us and thus we cannot get our required solution.
ZEESHAN NADEEM gud keep it up
© 2021 Created by + M.Tariq Malik. Powered by
Promote Us | Report an Issue | Privacy Policy | Terms of Service
We are user-generated contents & non-commercial site since 2009. All product, videos, pictures & others contents on site don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. All Contents on site are for personal & non-commercial use.We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Awards Badges List | Moderators Group
All Members | Featured Members | Top Reputation Members | Angels Members | Intellectual Members | Criteria for Selection
Become a Team Member | Safety Guidelines for New | Site FAQ & Rules | Safety Matters | Online Safety | Rules For Blog Post