Lecture
Greedy algorithm — an algorithm consisting of making locally optimal decisions at each stage, assuming that the final solution will also turn out to be optimal. It is known that if the structure of a problem is given by a matroid, then applying a greedy algorithm will yield the global optimum.
a greedy algorithm is an algorithm that, at each step, makes the locally best choice in the hope that the resulting solution will be optimal.
If global optimality of the algorithm holds practically always, it is usually preferred over other optimization methods, such as dynamic programming.
Greedy algorithms are algorithms that strive to make the optimal choice at every moment in time. At each step, the best choice is selected without considering the future.
Why are greedy algorithms called greedy?
Algorithms are called greedy when they use the greedy property. The greedy property:
At each moment in time, what is the best choice?
Greedy algorithms are greedy. They do not look into the future to choose the globally optimal solution. They are only interested in the best decision at the current moment. But the overall optimal solution may differ from the solution the algorithm chooses at each step of its operation. Likewise, they never look back at what they have already done to determine whether global optimization is needed. This is the main difference between greedy and dynamic programming.
What are greedy algorithms used for?
Greedy algorithms are very fast. Much faster than the two other alternatives (Divide and Conquer — Divide & Conquer, and Dynamic Programming Dynamic Programming). They are popular because they are fast.
Examples of popular greedy algorithms:
How do I create a greedy algorithm?
Your algorithm should always answer this question:
What is the best choice at this moment in time?
There is no general criterion for evaluating the applicability of a greedy algorithm to solving a particular problem; however, problems solved by greedy algorithms are typically characterized by two features: first, the Greedy Choice Property applies to them, and second, they possess the property of Optimal Substructure.
An optimization problem is said to have the greedy choice property applicable to it if a sequence of locally optimal choices yields a globally optimal solution. In the typical case, the proof of optimality follows this scheme:
A problem is said to have the property of optimal substructure if an optimal solution of the problem contains within it optimal solutions to all of its subproblems. For example, in the activity-selection problem, one can note that if 
— is an optimal set of requests containing request number 1, then 
— is an optimal set of requests for the smaller set of requests 
, consisting of those requests for which 
.
Problem. The coinage system of a certain state consists of coins of denominations 
. It is required to pay out the sum {\displaystyle S}
using the smallest possible number of coins.
The greedy algorithm for solving this problem is as follows. Take the largest possible number of coins of denomination 
: 
. In the same way, we obtain how many coins of the next smaller denomination are needed, and so on.
For this problem, the greedy algorithm does not always give the optimal solution, but only for certain coin systems, called canonical, such as those used in the USA (1, 5, 10, 25 cents). Non-canonical systems do not have this property. For example, when making change for 24 kopecks with coins of 1, 5, and 7 kopecks, the greedy algorithm makes change as follows: 7 kopecks — 3 pcs., 1 kopeck — 3 pcs., whereas the correct solution is — 7 kopecks — 2 pcs., 5 kopecks — 2 pcs.
Formulation No. 1. Given 
requests for holding classes in a certain lecture hall. Each request specifies the start and end of the class ( 
and 
for the 
-th request). If requests overlap, only one of them can be satisfied. Requests with numbers and 
are compatible if the intervals 
and 
do not overlap (that is 
or 
). The activity-selection problem consists in selecting the maximum number of pairwise compatible requests.
Formulation No. 2. At a conference, in order to allow more time for informal communication, the various sections were assigned to different lecture halls. A scholar with extremely broad interests wants to attend several talks taking place in different sections. The start and end of each talk are known. Determine the maximum number of talks that can be attended.
Let us present a greedy algorithm that solves this problem. We assume that the requests are ordered by increasing end time. If this is not the case, they can be sorted in time 
; requests with the same end time are arranged in arbitrary order.
Activity-Selector(s,f)
length[s]
to doif 
then
The input to this algorithm consists of the arrays of start and end times of the classes. The set A consists of the numbers of the selected requests, and j — is the number of the last request. The greedy algorithm looks for a request that starts no earlier than the end of the j-th one, then includes the found request in A, and assigns j its number. Thus, each time we select the (not yet started) class that has the least time remaining until its end.
The algorithm runs in 
, that is, sorting plus selection. At each step the best solution is chosen. Let us show that the result is the optimum.
Proof. Note that all requests are sorted in non-decreasing order of finish time. Request number 1 obviously belongs to the optimum (if not, we can replace the earliest request in the optimum with it, which will not make things worse). Discarding all requests that conflict with the first one, we obtain the original problem with fewer requests. Reasoning by induction, we arrive at the optimal solution in the same way.
A generalization of greedy algorithms is the Rado — Edmonds algorithm.
For a number of problems belonging to the NP class, greedy algorithms do not give an optimal solution. These include:
Nevertheless, in a number of problems greedy algorithms give fairly good approximate solutions.
Greedy coloring in graph theory — a coloring of the vertices of an undirected graph created by a greedy algorithm that traverses the graph's vertices in some predetermined sequence and assigns each vertex the first available color. Greedy algorithms, in the general case, do not give the minimum possible number of colors; however, they are used in mathematics as a technique for proving other results related to coloring, as well as in computer programs to obtain a coloring with a small number of colors.
Two colorings by a greedy algorithm of the same graph, using a different order of vertex traversal. The right-hand example shows that a graph with n vertices, which can be colored with two colors, can be colored by a greedy algorithm with 
colors.
Greedy algorithms are not always good, for example the Crown graph (a complete bipartite graph Kn,n with the edges of a perfect matching removed) is a particularly bad case for a greedy algorithm — if two vertices belonging to a removed edge of the matching are placed consecutively in the vertex sequence, the greedy algorithm uses n colors, whereas the optimal number for such a graph is two colors. There are also graphs for which, with high probability, a randomly chosen vertex sequence will lead to the use of a number of colors substantially greater than the minimum required. Thus, it is very important to carefully choose the sequence in which the vertices are traversed by the greedy algorithm.
Crown graphs with six, eight, and ten vertices, vertices = 2 n edges = n (n — 1)
For a given graph G and number k, determining whether there exists an ordering of the vertices of graph G that leads the greedy algorithm to use k or more colors is an NP-complete problem. This means, in particular, that it is difficult to find the worst case for a graph G.
Divide and conquer
Dynamic programming
Comments