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:
- Problem of salesman journey
- The smallest arithmetic algorithm of Prim
- The smallest spanning algorithm of Kruskal
- Dijkstra's smallest spanning algorithm
- Work scheduling problem
- Problem with backpacking
According to Tutorialspoint
Previous article: Asymptotic analysis in Data Structures and Algorithms
Next lesson: Algorithm for sharing (divide and conquer)
You should read it
- Dynamic Programming (Dynamic Programming)
- Algorithms arranged in data structures & algorithms
- Alignment algorithm (Merge Sort)
- WhatsApp will test new algorithms for Status sort feature
- What is algorithm?
- New algorithms to increase the accuracy of CAPTCHA
- How are Facebook and Google using algorithms to predict your thoughts?
- Algorithms predicting human faces change over time, helping to find missing people
- 3 free tools to keep track of Google update algorithms every day
- Deep search algorithm
- How to Become a Computer Scientist
- Instagram tightens algorithms and censorship policies for racist acts
Maybe you are interested
Will TikTok split the source code to create a US-specific algorithm?
Google Core Algorithm March 2024: Reduce unhelpful content by up to 40%.
Is Google's Helpful Content Algorithm Really Helpful?
The Mathematics of Winning: Algorithms Behind Online Slot Games
Artificial intelligence algorithms read human thoughts
Windows XP activation algorithm 'cracked' after 21 years