Greedy algorithms for optimization: an example with Synteny

Greedy algorithms for optimization

     A greedy algorithm is an optimization algorithm which makes a locally optimal decision at each step. The decision is locally optimal, for the immediate step, but not necessarily for all the future steps. Neighbour joining (for building phylogenetic trees), Nearest neighbour (for solving the travelling salesman problem), Dijkstra's algorithm (for shortest path in a graph) are examples of greedy algorithms. In some cases, greedy algorithms yield globally optimal algorithms, in particular if they are optimization problems over matroids, sometimes they only provide an approximation. Greedy algorithms are often used to find approxiamte solutions to difficult problems, (e.g. NP complete problems).

     There are several common extensions of greedy algorithms and the purpose of this biorecipe is to study them and to produce generic code that will run a greedy optimization in its various versions.

     An essential part of an algorithm to allow the use of greedy methods is to be able to decompose it in a number of similar steps. For example, in the case of solving TSP with Nearest Neighbour, from a city, visiting the nearest city which has not been already visited is such a step. At a given point of the algorithm we have several choices for the next step and (the greedy aspect of the algorihtm) chooses the step which is locally/immediately the best. We require this feature, thta a solution is composed of the union of may simple choices, to apply our Greedy optimization criteria.

Simple Greedy algorithm

     A simple greedy algorithm starts with an empty solution and adds one choice at a time. Each choice is the (locally) best of all possible ones. For generalizations that will become clear later, we require our decision procedure to return several of the best possible choices, not just the best one. Clearly these choices will be ordered by their quality, top choice first.

Random Greedy algorithm

Please cite as:

@techreport{ Gonnet-Greedy
        author = {Gaston H. Gonnet},
        title = {Greedy algorithms for optimization: an example with Synteny},
        month = { January },
        year = {2006},
        number = { xxxxx },
        howpublished = { Electronic publication },
        copyright = {code under the GNU General Public License},
        institution = {Informatik, ETH, Zurich},
        URL = { http://cbrg.inf.ethz.ch/bio-recipes/Greedy/code.html }
        }

© 2006 by Gaston Gonnet, Informatik, ETH Zurich

Index of bio-recipes

Last updated on Mon Jan 16 15:28:52 2006 by GG