Why dynamic approach is preferred over greedy technique?

Share

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

If we talk about Optimality:

In the Greedy method approach, there is no guarantee of getting the optimal solution, Generally, it gives the optimal local solution.

while

In the dynamic approach, there is a guarantee of getting an optimal solution as it considers all the cases as long to get optimal. It gives optimal global solutions.

For example, let’s say that you have to get from point A to point B as fast as possible, in a given city, during rush hour. A dynamic programming algorithm will look into the entire traffic report, looking into all possible combinations of roads you might take, and will only then tell you which way is the fastest. Of course, you might have to wait for a while until the algorithm finishes, and only then can you start driving. The path you will take will be the fastest one (assuming that nothing changed in the external environment).

On the other hand, a greedy algorithm will start you driving immediately and will pick the road that looks the fastest at every intersection. As you can imagine, this strategy might not lead to the fastest arrival time, since you might take some “easy” streets and then find yourself hopelessly stuck in a traffic jam.