Greedy Approach

Locally Optimal Choice

This is simply making the best choice at the moment. The idea is to make each choice in each step in a locally optimal manner. It may not the best globally optimal solution. But this approach works in many situations.

For example, the minimum cost spanning tree, shortest path (Dijkstra’s) follows this greedy approach and works at its best.

Photo by Henley Design Studio on Unsplash

So how can we decide whether a greedy approach will suit the optimization problem or not? So answering that, There is no defined way of finding it. But if we can observe the greedy-choice property and optimal substructure in the problem, We can use a greedy approach. We called them elements in Greedy strategy.

If the given problem has a globally optimal solution that can be arrived at by making a greedy choice that problem has this greedy choice property.

If the optimal solution to the problems contains within its optimal solutions to subproblems that problem has this optimal substructure. This is common to problems that can be solved by dynamic programming also. Refer to my blog — Dynamic programming https://sliit-sk95.medium.com/dynamic-programming-e86169042204

We will discuss the high-level application in greedy approach.

Knapsack Problem

The weight that a thief can carry is limited. So should think “What items to select to maximize profit?”.. Greedy thinking...

Knapsack in brief

In the greedy strategy, Compute the value per kilo (value/weight) of each item, Sort the items by value per kilo, Take as much as possible from the 1 st item. If can take more, go for 2nd item and so on…

This way is only eligible in the case of the fractional knapsack. It means the thief can take fractions of items. The other approach is 0–1 knapsack where each item must be either taken or left behind (a binary choice of 0 or 1).

Assuming that there is only 1 unit available from each item,

comparison between Fractional and 0–1 Knapsack

So as shown above fractional knapsack work better here.

There are many real-world applications of greedy algorithms.

Dijkstra’s Algorithm

Dijkstra’s algorithm [1] is used to find the shortest path between nodes in a graph. The algorithm maintains a set of unvisited nodes and calculates a tentative distance from a given node to another. If the algorithm finds a shorter way to get to a given node, the path is updated to reflect the shorter distance. This problem has satisfactory optimization substructure since if AA (figure: Dijkstra’s algorithm) is connected to B, B, BB is connected to CC, and the path must go through AA and BB to get to the destination CC, then the shortest path from AA to BB and the shortest path from BB to CC must be a part of the shortest path from AA to CC. So the optimal answers from the subproblems do contribute to the optimal answer for the total problem. This is because the algorithm keeps track of the shortest path possible to any given node.

Dijkstra’s algorithm

Huffman Coding

Huffman encoding [1] is another example of an algorithm where a greedy approach is successful. The Huffman algorithm analyzes a message and depending on the frequencies of the characters used in the message, it assigns a variable-length encoding for each symbol. A more commonly used symbol will have a shorter encoding while a rare symbol will have a longer encoding.

The Huffman coding algorithm takes in information about the frequencies or probabilities of a particular symbol occurring. It begins to build the prefix tree from the bottom up, starting with the two least probable symbols in the list. It takes those symbols and forms a subtree containing them, and then removes the individual symbols from the list.

The algorithm sums the probabilities of elements in a subtree and adds the subtree and its probability to the list. Next, the algorithm searches the list and selects the two symbols or subtrees with the smallest probabilities. It uses those to make a new subtree, removes the original subtrees/symbols from the list, and then adds the new subtree and its combined probability to the list. This repeats until there is one tree and all elements have been added. At each subtree, the optimal encoding for each symbol is created and together composes the overall optimal encoding.

Thanks !!

Happy learning…

References

[1] https://brilliant.org/wiki/greedy-algorithm/