Greedy algorithms


A game like chess can be won only by thinking ahead: a player who is focused entirely on
immediate advantage is easy to defeat. But in many other games, such as Scrabble, it is
possible to do quite well by simply making whichever move seems best at the moment and not worrying too much about future consequences.
This sort of myopic behavior is easy and convenient, making it an attractive algorithmic
strategy. Greedy algorithms build up a solution piece by piece, always choosing the next
piece that offers the most obvious and immediate benefit. Although such an approach can be disastrous for some computational tasks, there are many for which it is optimal. Our first example is that of minimum spanning trees.

Download file here

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s