Promoted
Promoted

Choosing between Greedy and Dynamic Programming - Which one is better?

Topic: Algorithms

Greedy and Dynamic Programming are used to solve many day-to-day applications. Both algorithms have their own time and space complexity. This post discusses the difference between the two and explores the trade-off of using one algorithm over another.

Greedy Algorithm

As the name suggests, greedy algorithms exploit the current situation. It tries to find the best solution in a given amount of time. If a given problem requires multiple steps to reach a goal, greedy algorithms make better choices at the moment not taking future steps into consideration. This works but may give sub-optimal results.

1paragraph

For example in the figure below the robot wants to reach the goal node. Each node has some cost associated with it. Also reaching each node is constant time. There are multiple-goal nodes so any goal node is acceptable. Let's apply a greedy algorithm to this problem. Given a choice between 1, 2, and 3, the robot will choose node 3 because at this point the cost of node 3 is the lowest. After reaching node 3 it has only one choice to reach its goal. So the cost of the path is 17. So if you notice, the algorithm explored one path to reach its goal even though the path through node 1 cost less than 17. So we reached our goal but our solution was not optimal.

2paragraph
3image

Dynamic Programming

Dynamic Programming divides the problem and solves each sub-problem. It combines solutions to each problem to get a global solution. Solution by dynamic programming is always optimal. Dynamic programming requires extra memory to store solutions of each sub-problems. Memory also acts as a lookup table to see if the sub-problem is already solved.

5paragraph

In the above example, dynamic programming will divide each path into sub-problem. It will explore each path and calculate the cost to reach the goal node. It returns the path with the lowest cost. So in the above example, it will return cost 13.

6paragraph

Promoted
Promoted

• When we used dynamic programming we got optimal solution while greedy gave sub-optimal solution
• In greedy we stopped the algorithm the moment we reached the goal node, so we explored only one path. In dynamic, we continued exploring even when we found a goal node for a better path.
• Since dynamic explored all paths it required more memory and compute compared to greedy. Also, it took more time to give results.
8list