About Me

A 30+ year old Msc. Graduate in Computing Science currently working in the financial technology sector.
View my complete profile
Wednesday, August 4, 2010

The Traveling Salesman

e come back to ant algorithms and now focus on where it can be applied. The most classic problem in computional mathematics is the traveling salesman problem. The problem is simple, but yet solving it is not.

Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

It's described in mathematics as a NP-complete problem, but I'll leave it up to you if you want to go down that road finding out exactly what that means. Anyone can connect every city with a single line, but how do you know if it's the shortest route? If you read the first article about ant algorithms you should get a "aha!" experince right about now. Ant algorithms or as it is also called ant optimization is perfect for these kind of problems.

Having a set of cities and X amount of ants with one task - visit each city once, you will achieve your goal simply by using the same stigmergy as when the ants collect food for their colony. The trail pattern will go from (2) to (3) and ending up as (4) as the pheromone decreases in strength on the trails with the longer distance. No real calculation, just nature finding its way.

If you are more interested in this technique and what it can do I recommend taking a look here for further studies. It's all about optimizations =)

- Tobias


Post a Comment