So-called greedy heuristics involve a process whereby at each stage a locally optimum choice is made which may or may not lead to a globally optimum solution to some problem. As such, greedy algorithms are local search, or LS, procedures.

For example, suppose one has a set of points or vertices {V} in the plane and you wish to create a network of edges {E} such that every point is accessible via the network from every other point, and overall the total (Euclidean) length of the network is minimised. A greedy algorithm that solves this problem (the so-called Minimum Spanning Tree, or MST, problem) is as follows:

·         Select any point {x} from V at random to start. Define the set V*={x} and the set E*={ }

i.e. the set V* is initialised with a single point chosen at random from the source vertices, and the set E* is initialised as an empty set of edges. Then,

·         Find the nearest point in the set V not in V* (v say) to a point in the set V* (u say) and add this to the set V* together with the edge connecting v and u to E*. If two or more points are equidistant from V* then choose one of these at random

i.e. this step ensures that at each iteration the shortest/lowest cost edge joining a point in V* to a point not yet in V* is added to the solution set and will always form a connected tree. Then,

·         Repeat the preceding step until V*=V. The set E* contains the MST

This is known as Prim’s algorithm (Prim, 1957) and is exact in the sense that the solution it finds is globally optimal. It is also relatively fast. Kruskal’s greedy algorithm for determining the MST of a weighted graph is similar in concept, but starts with the vertex set V already connected such that every vertex has a direct or indirect link to every other vertex. The shortest (least weighted) link is then identified and removed, being added to the solution set. The process continues, checking that loops in the network do not occur, until the vertices in the solution set form a complete tree, which is the MST. Both of these algorithms are effectively constructive in form, gradually building the solution. Some heuristics are essentially aimed at improvement rather than construction, for example by commencing with a random or best known solution and then seeking to systematically improve upon this by a well-defined procedure (e.g. local search or iterative improvement).

Most greedy algorithms are fast but, unlike those described above, yield sub-optimal solutions and in some cases the provably worst possible solution! This can be the case for a similar algorithm to that described above, but where the objective is to define the shortest possible tour of the set V with each vertex being visited only once, returning finally to the starting vertex (the basic Travelling Salesman Problem).

There are many variants to greedy algorithms, some of which are problem-dependent whilst others attempt to find a more systematic approach to improving the local optimum found by the procedure. For example, a greedy algorithm for a facility location problem could be to choose a set of N solution locations at random and then assign all customers to the nearest facility — e.g. retail stores and customers, children and schools, medical facilities and patients. This generates a very poor solution if one is trying to minimise the average or maximum travel time by customers to facilities. An improvement to this greedy random algorithm might be a greedy add variant, whereby a single initial facility is selected at random and all customers assigned to it, and then new facilities are added one by one at random locations but subject to some additional rule, with customers re-assigned according to the ‘nearest facility’ rule. This may yield an improved solution. Repeated runs of a greedy procedure may also yield a set of results from which the best in terms of the criteria to be optimised is selected. Indeed, characteristics identified from the best solutions may assist in a progressive improvement process. So-called GRASP heuristics (greedy randomised adaptive search procedures) start with a feasible solution from a more conventional greedy algorithm and then apply a local search algorithm to try and improve on this solution. Repeated runs of the GRASP procedure give rise to an overall best solution.