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)

Lesley Montoya

Update 25 May 2019

You should read it

May be interested

Toshiba's algorithm helps normal computers calculate faster than supercomputers
normal computers will optimize the combination much faster than supercomputers.
Instagram is committed to adjusting the algorithm to limit the display of 'possibly harmful' content to users
instagram has just made a commitment to adjust the algorithm to remove as much 'possibly harmful' content as possible on the platform and reach users.
Insert algorithm (Insertion Sort)
sort insertion is a sorting algorithm based on in-place comparison. here, a sub-list is always maintained in sorted form. inserting is inserting an element into the sorted list of children. the element is inserted in the appropriate position so that the list is still in order.
What determines what YouTube shows on your feed?
these videos do not appear by accident; all related to the inner workings of the youtube algorithm.
Linear search algorithm (Linear Search)
linear search is a very basic search algorithm. in this type of search, a continuous search operation takes place through every element. each element is checked and if any connection is found, that particular element is returned; if not found, the search process continues until the data is searched.
Threads tweaks algorithm to combat Bluesky's rise
threads is making changes to the way its algorithm works, revamping the for you feed to ensure more content from people you follow appears.
Interpolation Search algorithm (Interpolation Search)
interpolation search (interpolation search) is an improved variant of binary search (binary search). in order for this search algorithm to work correctly, the data set must be sorted.
Google is about to update the new search algorithm
at the search on 2021 event that just ended this morning, google announced its new search algorithm called the multitasking unified model (mum).
Algorithm for sharing (divide and conquer)
divide and conquer (divide and conquer) is an important method of designing algorithms. the idea of this method is quite simple and very easy to understand.
Alignment algorithm (Merge Sort)
mixing (merge sort) is an arrangement algorithm based on the divide and conquer algorithm. with the worst case time complexity of Ο (n log n), this is one of the algorithms that deserves the most attention.