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