Suppose you are looking for an optimal or near-optimal solution to a problem. To describe an algorithm as being optimal we need some way of measuring and comparing the different possible solutions.

For example, one problem may be: Find the fastest drive between here and Ottawa.

A subtly different problem may be: Find the shortest drive between here and Ottawa.

Yet again, another question may be: Find the most fuel-efficient drive between here and Ottawa.

In each case, there is a different metric to measure how good each possible drive to Ottawa is, and while one path may be more optimal than than another with respect to one metric, it may be sub-optimal with respect to a different metric.

For example, the shortest route to Ottawa from Waterloo is to essentially follow the 401 from Waterloo to Toronto, get onto the 407, and then then get to Hwy 7 and follow that to Ottawa, for a total of 498 km. This, however, takes five hours and twenty-two minutes according to Google Maps.

The fastest route to Ottawa from Waterloo is to follow the 401 to the 416 and take that highway north to Ottawa. This path is 556 km but only takes five hours and twelve minutes, again according to Google Maps.

A game like Sudoku, however, generally has only one solution, and one solution is not better than any other; either the numbers satisfy the constraints, or they do not.

A Rubik's cube, however, also has only one solution, but there are many different ways of getting to that solution. A metric here is what is the minimum number of moves necessary to solve the cube.

Examples of greedy algorithms

The following are examples of greedy algorithms in practice.

Maximizing tasks

Suppose your goal is to perform the maximum number of tasks in a given period of time, and you have n different tasks which you could chose from, but you cannot complete all n tasks in the allotted period of time. A greedy algorithm for maximizing the number of tasks performed is to always perform that task that requires the least amount of time. This algorithm allows you to maximize the number of tasks performed.

For example, given the tasks

(A, 2 h) (B, 5 h) (C, 3 h) (D, 2 h) (E, 9 h) (F, 5 h) (G, 4 h) (I, 1 h) (H, 7 h)

If you are given ten hours in one day and you want to maximize the number of tasks completed, you would do Task I, A, D and C, taking up eight hours.

Maximizing profit

Suppose that each task described in the previous example also comes with some sort of financial reward for you. In this case, your goal may not be to maximize the number of tasks, but rather to maximize the amount of money you acquire in a fixed period of time.

For example, given the tasks

(A, 2 h, $300) (B, 5 h, $600) (C, 3 h, $240) (D, 2 h, $150) (E, 9 h, $800) (F, 5 h, $1100) (G, 3 h, $450) (I, 1 h, $250) (H, 7 h, $600)

This is the problem faced by many engineering consulting firms: there are likely more projects they could take on than they can possibly perform given there are only forty working hours a week, so which possible contracts should be engaged in?

Calculating the income density, we have the following:

(A, 2 h, $150/h) (B, 5 h, $120/h) (C, 3 h, $80/h) (D, 2 h, $75/h) (E, 9 h, $89/h) (F, 5 h, $220/h) (G, 3 h, $150/h) (I, 1 h, $250/h) (H, 7 h, $86/h)

This algorithm suggests that we should do Tasks I, F, after which we can do Task A or G, but you cannot do both because the total time required would be 11 hours, but we have only ten hours.

Unfortunately, this is one example where the greedy algorithm does not give you the best possible solution. In this case, if we did tasks I, F and G, this would give us $1800. If, however, we chose tasks A, F and G, this would net $1850. Still, the greedy algorithm gave us a close second, plus an hour to spare.

Maximizing fixed-time tasks

Suppose you are writing software for a person providing services to the public, such as a wedding photographer or a caterer. The person can only work one task at a time and the events are scheduled by the individual or group requesting the service. If your goal is to cover the maximum number of tasks in a given period of time, is there a greedy algorithm that gives you the best solution? For example, if all events are charged a flat rate of $500, then your only goal is to maximize the number of events attended.

Of course, your software adds to time of the event the time to prepare and the time to get to the venue, so suppose there are the following eight tasks: which do you pick?

(A, 12pm-2pm) (B, 1pm-6pm) (C, 7am-12pm) (D, 11am-3pm) (E, 8am-10am) (F, 3pm-5pm) (G, 10am-1pm) (H, 2pm-4pm) (I, 9am-11am)

The following greedy algorithm gives you the maximum number of tasks: at each step, start that tasks that finishes the earliest.

In this example, we start Task E, then Task G, and finally Task H.

Maximizing profit with fixed-time tasks

Suppose, instead, you have different scheduled events to choose from, but each event gives different profits. In this case, there is no greedy algorithm that finds the optimal combination of events to choose.

Making change

Suppose your goal is to make change for a machine. In this case, one goal may be to minimize the number of coins given out. The greedy algorithm is to give the highest amount coin that does not exceed the required amount to be given in change.

For example, in giving change for 65 cents, this algorithm would yield 25, 25, 10 and 5. In Europe, it would yield 50, 10, 5.

Now, this is an optimal algorithm so long as each higher denomination is worth more than the sum of all lower denominations. For example, if coins were minted in 1, 4, 10 and 15 cents, then the optimal change for 20 cents is 10 and 10, but the algorithm just described would give 15, 4 and 1.

Taken to the extreme, this suggests coins should be minted in values of 1, 2, 4, 8, 16, 32, 64, ..., which would truly assure that the minimum number of coins are given in exchange.

Shortest path

Suppose you want to find the shortest path from here to Ottawa. One greedy algorithm would be to start at any one intersection and go to the next intersection that is closest. Of course, this may not get you moving in the direction of Ottawa, and it may never get you to Ottawa.

Instead, suppose you chose to go to the nearest intersection that gets you closer to your destination. This algorithm would actually work if you were on Manhattan Island, which has a grid layout, but in general, it may not actually get you to where you want to go in an optimal manner.

Now, Dijkstra's algorithm does find the optimal path, and under real-world circumstances, so does the A*-search. Both of these are greedy. You are welcome to look at these at your own time.

Minimum spanning tree

Suppose you are hired to install wiring in a building. Each floor is divided into sections, and in each section, each receptacle is connected either to another receptacle or to the circuit breaker. Only one receptacle need be connected to the circuit breaker.

Now, the wiring must be embedded in the walls, so the goal is to find that combination of connections that leaves all receptacles connected either directly or indirectly to the circuit breaker.

Such a solution is called a minimum spanning tree, and two greedy algorithms for finding minimum spanning trees are Prim's and Kruskal's algorithm

We will describe Kruskal's algorithm first:

• List all possible connections between receptacles and record the length of each connection.
• Sort these connections from shortest to longest.

Now, apply the following algorithm:

• Start with no wiring.
• Continue adding connections following the next rule until all receptacles are connected: Choose the next shortest remaining connection and add it to the wiring so long as it does not produce a circuit.

This algorithm is guaranteed to find the minimum spanning tree to solve the problem at hand.

Set cover problem

Suppose you have n objects, let us label them $1$ through $n$. Suppose you have a collection of sets that include these $n$ objects, and each object is included in at least one set. For example, given $n = 14$, the following sets satisfy this condition:

${1, 2, 3, 4, 5, 6, 7}$, ${8, 9, 10, 11, 12, 13, 14}$, ${1, 2, 3, 4, 5, 6, 7, 8}$, ${9, 10, 11, 12}$, ${13, 14}$, ${1, 2, 3, 4, 11, 12, 13}$, ${5, 6, 7, 8, 9, 10, 14}$

The following is a greedy algorithm that finds the minimum number of sets required to ensure that each point is included in at least one of those sets:

Choose next that set that covers the most uncovered objects (that is, those objects not yet in any set) that remain.

While this gives sometimes an optimal solution, it does not always give the optimal solution. In fact, it can be mathematically demonstrated that if the optimal number of sets is $N$, then this greedy algorithm will find no more than $N H(n)$ sets that cover the $n$ items where $H(n)$ is the n^th harmonic number:

$H(n) = \sum_{k = 1}^n \frac{1}{k}$

This value is known to never exceed $\ln(n) + 1$. Thus, if you are covering 1000 objects, and the optimal cover is 100 sets, then this algorithm is guaranteed to find a cover that requires less than 791 sets.

Simplex method

The Simplex method is a system that solves an overconstrained system of linear inequalities in such a way the optimal solution can be found usually in linear time. Of course, mathematicians have come up with a system of $n$ such equations that requires $2^n$ time to execute, but in all practical examples, the run time of the Simplex method runs in O(n) time.