Greedy Algorithm: 3 Examples of Greedy Algorithm Applications

A greedy algorithm is a set of heuristic instructions reliant on the technique of always solving problems at the local level first. In computer science, this means utilizing programs capable of breaking down problems into chunks and then instructing your device to solve those problems by following the path of least resistance.

Long before the dawn of the information age, the Italian mathematician Fibonacci made use of greedy algorithms to solve problems involving fractions. Mathematicians of his era could only write formulas on paper; however, today’s STEM professionals can use programming languages like Java and Python to equip devices to use these algorithms for machine learning.

Alongside other common algorithm types—like binary search or divide and conquer—greedy algorithms are helpful in working through objective functions, providing speedy solutions to complex problems, and serving as the basis for entertaining games and logic puzzles.

Greedy algorithms work by focusing on speedy, local, and feasible solutions rather than looking at the entirety of a data structure. In the greedy approach, each phase of recursion leads the algorithm to take on another local problem in the hope it will eventually solve the larger global one. Dynamic programming, by contrast, looks at the big picture and then crafts a global optimum solution from the top down.

There are many different iterations of greedy algorithms of which you can take note. Here are a few to consider:

• Dijkstra’s algorithm: The mathematician Edsger Dijkstra crafted this greedy algorithm to help graph makers pinpoint the quickest way to get from one point of a given diagram to another. This is what the greedy method aims to accomplish in just about every scenario, albeit in a less obvious fashion.
• Huffman encoding: Named for MIT student David Huffman, Huffman coding utilizes greedy algorithms in the interest of lossless data compression. This means you can both compress and then later expand data structures with nothing lost in the interim.
• Kruskal’s algorithm: This type of greedy algorithm expands on the graphic, point-by-point navigation of Dijkstra’s algorithm to include minimum spanning trees in its scope. Also similar to Prim’s algorithm, Kruskal’s approach (after Joseph Kruskal) aims to focus on the local optimum as each phase of a program runs at the expense of more global optimization.

While greedy algorithms can often find optimal solutions, they are also capable of causing optimization problems. Here are a few of their limitations as a whole:

• Dismissal of the optimal for the efficient: Greedy algorithms always take the shortest paths available to them. It’s also impossible for them to reverse course. This sometimes encourages them to prioritize the quickest possible finish time rather than find the best solution to a complex problem.
• Lack of dynamic programming: In contrast to more dynamic programming, greedy algorithms can take a short-sighted approach. They look at local chunks of data without reference to the bigger picture. As such, they can operate as less-than-ideal tutorials for your programs as a whole.
• Low success rate: Since greedy solutions are innately local, they struggle with building up to solving global problems. To complete problems with a greedy algorithm, the data you provide must possess both innate greedy choice properties and an optimal substructure as well. This is not the case for many problem types.

There are many pragmatic examples of how and why algorithms of this ilk can be useful. Consider these iterations of greedy algorithms in action:

1. 1. The activity selection problem: Imagine you have a certain number of activities available to you but a limited amount of time. A greedy algorithm would comb through the subsets of activities to arrive at the maximum number you could participate in without fear of overlap.
2. 2. The fractional knapsack problem: For this greedy problem, suppose you have a bag with limited space and a wide array of materials with which you want to fill it. The algorithm will try to figure out how you can subdivide these materials so you can bring along as many elements as possible with you in your knapsack.
3. 3. The job scheduling problem: Suppose you’re the manager of a coffee shop and you need to achieve an optimal result for scheduling all your workers. By solving various scheduling subproblems first, a greedy algorithm could provide a schedule that maximizes everyone’s possible hours without any conflicts.
4. 4. The traveling salesman problem: Consider yourself a traveling salesperson. If you used a greedy strategy, you would go to the nearest possible house or city without reference to your wider route or sales goals. This illustrates both the strengths and weaknesses of following such an approach.

Get the MasterClass Annual Membership for exclusive access to video lessons taught by science luminaries, including Terence Tao, Bill Nye, Neil deGrasse Tyson, Chris Hadfield, Jane Goodall, and more.