Fri, 14 Oct 2005
Traveling salesmen
If you expect me to stop apologizing for blog entries that are long over-do, then don't. This is one of those entries, but I'm mostly talking about things that happened over a week ago. Oh well.
Anyway, I've been playing the RPG a bit here and there, and part of it is heavily trade oriented. So I've been accumulating little bits of stuff here and there and everywhere, and I've been needing to wander around and collect it all. I thought "no problem, I'll just write a quick little perl script to take care of it for me.
Except that what I basically need is a solution to the traveling salesman problem, which is intrinsically hard. Or more accurately, hard to solve efficiently. Oh well. I can still brute force it, and besides: Math is fun.
So. What is the traveling salesman problem? Why I'm glad you asked. It's actually almost exactly the sort of math I'm dealing with in CO355 this term.
The traveling salesman problem deals with the best way to visit a bunch of different locations of varying distances, in a way that minimizes the total distance traveled. For small numbers of cities, it really isn't that hard. For example, it's fairly clear that from Boston, I should visit New York before going to LA and Seattle, rather than going to New York between LA and Seattle. But for larger numbers, examining all the possibilities becomes astoundingly inefficient. Five cities requires 120 comparisons. Eight requires over forty thousand. Ten over three million. One more city makes it almost forty million comparisons.
Granted, on a computer, forty million is a relatively small number, but it's not uncommon for these sort of problems to involve hundreds or thousands of variables, where here, I'm only talking about eleven.
Anyway, this is veering a bit off topic. All I wanted to say was math is fun. It turns out that math is also hard. If I learned anything about last week its that I should get as much of my assignment done early this week.
Speaking of traveling salesmen, Carmen recently hosted a Tupperware party. Long story short, I now own $300 more Tupperware than I did before*. I had a whirlwind of putting things in storage containers, which really helped, though looking at my kitchen at the moment, you wouldn't know it.
* Which was one thing. A Tupperware lettuce container that I suspect is older than I am. Still works great, which I guess is a good testimonial.
[/Blog]
permanent link
