Traveling Salesperson I: Brute Force, Greedy, and Heuristics
Introduction
Imagine you have the unfortunate job of traveling to 10 different towns in your area each month in order to deliver something important. Needless to say, you'd like to make this road trip as short as possible. Each town is a different distance away from your town and from each other town. How do you figure out a route that will minimize the distance traveled? You may recognize this as the famous Traveling Salesperson Problem (TSP).
SP is a very important NP-complete problem. It maps to many real-world problems making it one of the most thoroughly explored of the NP-complete problems. People need to solve this problem, despite the fact that there is no known polynomial solution for all instances. We will explore TSP in this module as a means for illustrating a host of different algorithms and approaches to solving problems. Just about everything has been tried with TSP!
How to Solve It?
One way to solve this problem (and any other NP-complete problem) is to enumerate all possible routes, of which there are 10! (3,628,800) for 10 towns, and then choose the shortest. This is a brute force algorithm. It would only take a couple seconds on a typical PC to compute all the possible routes and distances for 10 towns. And you would only need to do it once.
There are problems with brute force algorithms, however. One is combinatorial explosion: if we add one more town, the increase in the number of routes we need to compute increases by 1000%. If we go up to 20 towns, we could not possibly enumerate all the routes in our lifetime!
It is often possible to apply some clever techniques to reduce the number of enumerations that a brute force algorithm produces. Why not minimize the work involved if we can? Greedy algorithms sometimes provide a way to reduce the work involved with a brute force algorithm.
A greedy algorithm is one where we make the best choice at each stage of an algorithm given the immediate information available. These choices do not take into account all the data available from all stages of the algorithm. Sometimes the immediate information is enough and an optimal solution is found; sometimes it's not enough, and non-optimal solutions are found.
There is a simple greedy algorithm for solving TSP: Start at any city. From there, go to the closest unvisited city. Continue until you have visited all the cities, at which point you return to the starting city. In practice, this works fairly well, but it may or may not find an optimal solution.
Check out this resource for some other interesting examples. Then continue on in this resource through the discussion of greedy algorithms.
As shown in the counting change and knapsack examples, greedy algorithms are interesting alternatives to brute force algorithms. As mentioned earlier, the difficulty with greedy algorithms is there is no guarantee that you will find the optimal solution, whereas with brute force an optimal solution is guaranteed. Greedy algorithms are useful regardless, because they are usually easy to define and can provide good approximations of an optimal solution. More important, they significantly reduce the work involved.A greedy algorithm is one where we make the best choice at each stage of an algorithm given the immediate information available. These choices do not take into account all the data available from all stages of the algorithm. Sometimes the immediate information is enough and an optimal solution is found; sometimes it's not enough, and non-optimal solutions are found.
There is a simple greedy algorithm for solving TSP: Start at any city. From there, go to the closest unvisited city. Continue until you have visited all the cities, at which point you return to the starting city. In practice, this works fairly well, but it may or may not find an optimal solution.
Check out this resource for some other interesting examples. Then continue on in this resource through the discussion of greedy algorithms.
Which do you use in which situation? Here is a frequently-cited guideline: If the computing time is not too long and you only need to compute the solution once, brute force works fine. If the computing time is too long to do brute force and/or you need to compute the solution often, it makes sense to try and reduce the number of solutions that we need to process. This can be done with a greedy algorithm.
from gcu.googlecode.com/files/Exploring%20Algorithms.doc
