Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |

In this section we consider two closely related algorithm types--brute-force and greedy.
*Brute-force algorithms*
are distinguished not by their structure or form,
but by the way in which the problem to be solved is approached.
A brute-force algorithm solves a problem in the most simple,
direct or obvious way.
As a result, such an algorithm can end up doing far more work
to solve a given problem
than a more clever or sophisticated algorithm might do.
On the other hand,
a brute-force algorithm is often easier to implement
than a more sophisticated one and,
because of this simplicity,
sometimes it can be more efficient.

Often a problem can be viewed as a sequence of decisions to be made. For example, consider the problem of finding the best way to place electronic components on a circuit board. To solve this problem we must decide where on the board to place each component. Typically, a brute-force algorithm solves such a problem by exhaustively enumerating all the possibilities. That is, for every decision we consider each possible outcome.

A greedy algorithm is one that makes the sequence of decisions (in some order) such that once a given decision has been made, that decision is never reconsidered. For example, if we use a greedy algorithm to place the components on the circuit board, once a component has been assigned a position it is never again moved. Greedy algorithms can run significantly faster than brute force ones. Unfortunately, it is not always the case that a greedy strategy leads to the correct solution.

Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.