Traveling salesman algorithms

[jutah]

I have to give a presentation on the traveling salesman problem. I have checked around on the net to find some algorithms, but the ones I find are either too simple ex. Brute force and Nearest neighbor or I need a PHD in Math to understand them. Does anybody know of any in between algorithms that are at least semi efficent and are not too hard to understand?
thanks
jutah

[mindwarp.out]

while(!dead)
{
if(gotocity(currentcity) == NULL)
{
printf("All cities have been visited.");
if(profit >= goal)
{
printf("Your life was sucessful");
dead = TRUE;
}
else
{
while(do_sleazy_salespitch());
}
}

Is that what your looking for?

Mindwarp

[Bradmont]

Do you mean Hamiltonian circuits? If so, I don't think there is any efficient algorithm for finding them (at least my discreet math book says there isn't... and the proof is in a section of the book we didn't cover..._

[f'lar]

If you find in algorithym that's any better than O(n^2) I think you will be a rich man, or at least get that phd you were talking about, possibly both. I don't think there's any better way to do it yet.

[BrianDrozd]

Unfortunately, the traveling salesman problem is best solved by brute force; you have to calculate the total cost of all paths and then compare them, and there aren't any effective short cuts.

On the other hand, if you can accept a 'pretty good' solution that isn't necissarily the best, then it becomes easier. The algorithm for a 'pretty good' solution goes something like this: (you'd have to find an algorithms book for the exact algorithm.)

1) Pick a cycle, any cycle. For expediance, typically you pick one city as starting point and then you choose the least most expensive path that will take you to a new city. This gives you a good starting point.

2) If the cost of this path is less than the allocated budget, stop. You've succeeded and the path is good enough.

3) If not, then for the next three cities see if a cheeper path exists. (I.E if the path is currently City X City Y, and City Z, see if going from X to Z to Y isn't cheeper. If it is swap Z and Y. If not, then got to the next city and repeat step 3. Stop if you reach the city you started with.

5) Go back to step 2. (This is doen after every swap.)

6) If you've gone through all the cities, fail. The budget is too low to make the trip, or a better starting point needs to be picked.

This algorithm won't always succeed and it won't give the best possible solution, but it will give solutions that may be 'good enough' for the real world in only O(2n) time. (O(n) to build the first path, and O(n) time spent looking for a better solution.

[kmj]

Originally posted by BrianDrozd:
<STRONG>Unfortunately, the traveling salesman problem is best solved by brute force; you have to calculate the total cost of all paths and then compare them, and there aren't any effective short cuts.
</STRONG>

This isn't exactly true. There's a method, I believe it's called "Branch & Bound", which is a shortcut, the gist of it is that you keep track of a "current shortest path" and each time you extend a path by adding a new city, you see if this causes you to exceed the "current shortest path". If so, you can throw that path out immediately and move on to the next. If it's still less, then you can extend it more, and continue this process until you have added all the cities. At this point, if the path is still smaller, it will become the next "current shortest path." This allows you to throw out potentially a very large number of the possible paths. You can do a search for TSP and Branch and Bound.

[mram19]

Can someone tell me what this algorithm is? I mean, what problem is it trying to solve?

[YaRness]

http://www.keck.caam.rice.edu/tsp/