Suppose that you have a handful of coins in your pocket and want to choose some of them to add up to a given total. The following would be an obvious method: keep selecting the coin of highest value that does not cause the total to become too big. If you have a large supply of coins of all denominations, this will result in an efficient selection. Because at each stage of the procedure, you try to take a step that gets you as close as possible to the target, an algorithm like this is called a greedy algorithm. Although greedy algorithms can seem rather unsophisticated, the concept is surprisingly important in many parts of mathematics.
They vary from example to example, but this article is written at a fairly elementary level.
A proper vertex colouring of a graph is a function defined on the vertices of such that if and are any two neighbouring vertices, then does not equal . A simple result in graph theory is the following: let be a finite graph such that each vertex has degree at most . Then there is a proper colouring of that uses at most colours. (This means that the function takes at most distinct values.)
To prove this, we choose some ordering of the vertices: and colour them inductively as follows. Having coloured , we would like to colour . By hypothesis, has at most neighbours, so there are at most neighbours of amongst the vertices . Therefore, there are at most colours that we must avoid when choosing a colour for . Since there are colours available to us, we can arbitrarily choose some colour that is not one of the ones we have to avoid. And thus the induction continues.
Why do we call that a greedy algorithm? The reason is that we do not worry about the future when we choose the colour for . For some problems, it turns out that we do not need to worry about the future, while for others it very definitely does. To give an example of a problem of the latter type, suppose that we have a bipartite graph with two vertex sets and , both of size . And suppose that we want to find a perfect matching, meaning a bijection such that is joined to for every . A greedy approach would be to choose an ordering of the vertices of and then choose distinct neighbours for each vertex in turn. However, it may well happen that even if a perfect matching exists, we get stuck when we do this process: then we find ourselves wanting to backtrack. (It turns out to be possible to devise a systematic way of backtracking that leads to a polynomial-time algorithm for this problem.)
It might be more accurate to call Example 1 a just-do-it proof, since many greedy algorithms have the following further feature: instead of making an arbitrary choice at each stage, one makes a choice that is extreme in one way or another. The coins example in the quick description has this property: we chose the coin of largest value at each stage, subject to the condition that we didn't go over our target. Another example that illustrates this type of greed is the game of Othello. Here, a greedy strategy for playing the game would be always to place your counter somewhere that causes as many as possible of your opponent's pieces to be turned over. Interestingly, this is virtually the worst strategy you can play, at least until near the end of the game, when obviously it becomes more sensible, though even in the endgame a greedy strategy is far from optimal. (One can also come up with endless real-life examples like this. If you are trying to run a mile as quickly as possible, then a greedy, but very silly, strategy is to run as fast as you possibly can right from the start. If you are a fly trying to escape from a house, a greedy strategy is to fly in the direction of maximally increasing brightness: this is quite a good strategy until you reach a closed window. And so on.)