Greedy Algorithm

1.What is a Greedy Algorithm?

Greedy algorithm refers to the approach of finding an optimal solution under current conditions, without considering and taking into account the next step. Its aim is to model the best solution with a top-down approach.

2.How is a Greedy Algorithm created?

Depending on the problem we want to solve, we should first sort the set we have. This sorted set should be processed repeatedly, decreasing from the whole set towards the bottom, according to the focus of the problem. For example, if we want to fill a bag in a way that can generate maximum income, the items are sorted from the highest to the lowest value, and the bag is started to be filled from the order based on our capacity. If activity sorting is desired, activities can be sorted by their end times. In this context, a greedy approach decision variable is kept and operations are performed, so the distribution of a clothing factory's products with maximum efficiency can be modeled, and the logic of a milk factory to get maximum liters of milk can also be modeled. After sorting / aligning the data, operations should be performed with the available set based on the requested condition.

3.Some known Greedy Approaches

The most commonly used Greedy algorithms can be stated as follows: Knapsack, Dijkstra, Huffman, Activity Selection, Prims and Kruskal Algorithms. Let's explain some of them in a little more detail. First, let's talk about the Greedy approach algorithm developed for the Activity Selection Problem. In this problem, there are some activities and the start and end times of these activities are known. At the same time, it focuses on the question of how we can select the maximum activity that can only select one activity. As the greedy approach requires from us, when we remove the activity with the closest end time from our set, we should look for the optimized solution of our set that has changed again. So suppose if S is our set, a is the activity with the earliest end time and B is our optimized solution, thus S – a = S' set will be formed and the optimized solution of S, B will also be the solution of S' + a. So S – a is also an optimized solution. In this way, we can interpret our optimized solution as to go on until there are no activities left in our hand. If we need to interpret the Pseudocode, if there is a loop, we can compare the start and end times of the activities by browsing and model the optimal activities to be as maximum as possible by playing with our set. Secondly, let's talk about the Greedy approach to Knapscak problem. In dynamic programming, the Knapsack problem, which basically involves filling objects into our bag / bag / box, involves different approaches in the Greedy Algorithm. In dynamic programming, there is a binary (0-1) Knapsack model whereas in Greedy, transactions are made with fractional objects. Examples of this can be considered when we're trying to fill materials like sand, gold dust into my bag. In such cases, it is generally progressed in such a way that we will fill up the highest value material. We need the data that we can compare for this, we can easily sort all the products over their value / weight. We start filling in our sorted products over the sorted products in the greedy approach we started with sorting and we check whether our capacity is filled or not over the if condition. As we fill in the products, we revise our gain and our capacity, one will increase while the other will decrease. In the end, when our capacity becomes insufficient, as a result, we will have an algorithm where we can earn maximum profit which we have filled by sorting, that is, the sorted one. Finally, we can focus on the Huffman code algorithm. Huffman code is an algorithm used to reduce the representative numbers of data, thus allowing efficient data compression to be made. While bits are normally calculated based on binary to represent numbers, in Huffman code, it is recommended to include in bit account via a tree based on usage frequencies. Suppose we have a file, k character in this file occurs 45 thousand times, l character 13 thousand times, m character 9 thousand times, n character 16 thousand times,t character 5 thousand times, p character also occurs 12 thousand times. Normally, we would need a minimum of 3 bits to add these 6 characters to the bit account with binary calculation(000,001,010…). This corresponds to a need of (13k + 12k + 9k + 5k + 45k + 16k) * 3 bit = 300k bits. However, by using Huffman code, matching the frequencies of 45,13,12,16,9,5 and placing them in the tree, we obtain a frequency tree, usually 0 given to the left branch and 1 to the right branch and the Huffman representative bit numbers of the numbers are found. For this example, from the most common to the rarest, 0, 111, 101, 100, 1101, 1100 will be, when these are multiplied with their frequencies, they will take up less space than 300k bits.

An example image for the Huffman code can be given like this.

4.Comparison of Greedy Algorithm and Dynamic Programming

In the comparison of Greedy and Dynamic Programming, an optimal solution is sought in both. In the greedy approach, a selection element is kept which is not present in dynamic programming. This element represents the decision variable for the optimal solution. After making the choice over the variable, subproblems are solved and continued. In dynamic programming, however, there is a choice at every step, and this choice can affect the optimal solutions of the subproblems. But in the greedy approach, this situation can never depend on future steps' choices or solutions because it is not designed in this way. Dynamic programming has a bottom up strategy without speaking based on memoization, whereas greedy approach has exactly the opposite top down strategy. In other words, the greedy selection variable is incremental at each step calculated by being reduced from the whole, this situation is inverse in dynamic programming. In summary while the greedy approach has a top down strategy, dynamic programming has a bottom up strategy.