Greedy Algorithm (Greedy Algorithm)

What is greedy algorithm?

Greed (or greedy) is one of the most popular methods of designing algorithms. If you have read folk tales, then there will be a story like this: on a tray with many dishes, the best dish we will eat first, finish that dish we will switch to the second delicious dish, and forward to the third dish .

Many famous algorithms are designed based on greedy ideas, such as Dijkstra's smallest frame algorithm, Kruskal's smallest frame algorithm, .

Greedy Algorithm is a combination optimization algorithm. Search algorithms, select local optimal solutions in each step in the hope of finding a global optimal solution.

The greedy algorithm chooses which solution is best at the present time and then solves the problem that arises from making that choice. The choice of greedy algorithms may depend on the previous choice. Early decision making and changing the direction of the algorithm along with never reviewing the old decisions will result in this algorithm not being optimal to find a global solution.

You follow a simple problem below to see how to implement the greedy algorithm and why you can say that this algorithm is not optimal.

The problem of counting coins

The requirement is to select the smallest amount of coins possible so that the total face value of these currencies equals a given amount of money.

If the dong has denominations of 1, 2, 5, and 10 cents respectively and the amount of money given is 18 cents, the greedy algorithm performs as follows:

Step 1 : Choose 10 coins, so there will be 18 - 10 = 8 coins.

Step 2 : Choose 5 coins, so there will be 3 coins.

Step 3 : Choose 2 coins, 1 coin left.

Step 4 : Finally choose 1 cent coin and solve the problem.

You see that the above method is quite good, and the amount of money you need to choose is 4 coins. But if we change the problem a bit, the same approach may not bring the same optimal results.

For example, another monetary system with 1, 7 and 10 cents in denominations and the amount of money given here changes to 15 cents, according to the greedy algorithm, the amount of money to choose will more 4. With greedy algorithms: 10 + 1 + 1 +1 + 1 + 1, so a total of 6 coins. While the same problem as above can be handled by selecting only 3 currencies (7 + 7 +1).

Therefore, we can conclude that greedy algorithms seeking optimal solutions at each step can fail to find a global optimal solution.

Example of greedy algorithm application

There are many famous algorithms designed based on the thought of greedy algorithms. Here is one of these algorithms:

1. Problem of salesman journey
2. The smallest arithmetic algorithm of Prim
3. The smallest spanning algorithm of Kruskal
4. Dijkstra's smallest spanning algorithm
5. Work scheduling problem
6. Problem with backpacking

According to Tutorialspoint

Previous article: Asymptotic analysis in Data Structures and Algorithms

Next lesson: Algorithm for sharing (divide and conquer)