# Greedy algorithms for optimization: an example with Synteny

*by Gaston H. Gonnet*## 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

Steps of the 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

Steps of the random greedy algorithmPlease 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