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.

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.

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.

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.

• 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.
  

Choosing between two

• In the above example if there was only one goal node greedy could have given optimal results. If we already know the problem has one unique solution choose greedy because it will find the optimal solution in less time than dynamic using less memory
  
• If we are not aware of the number of solutions to the problem and we only want the optimal solution, choose dynamic
  
• If available memory is limited and sub-optimal results are acceptable then use greedy. If an optimal solution is expected we need to apply space optimization to dynamic programming. But care needs to be taken, the time complexity is not affected.
  
• In the case of large problem space, dynamic programming is very slow, for example, a vacuum robot. Even for small problem space, dynamic programming calculation of states could be large. The same problem solved by greedy in minutes may take hours by dynamic with large memory. That's why in a real-world application, greedy is more preferred than dynamic with an acceptable margin of error.
  
• Dynamic requires each state to be known to calculate the result. In real-world examples it is likely we may not know each state. Some heuristics may be unknown to us. In such cases, we can choose a greedy algorithm.