Friday, January 20, 2012

Travelling Salesman Art

Salesman making a tour over 5000 towns.
The Traveling Salesman Problem is a well-known mathematical problem of finding shortest route visiting all given points on a map.
When number of points is small, solution is trivial, but complexity grows very fast with size. Taking aside the mathematics behind this task, solutions produce surprisingly interesting images.
Here are some of them. A note should be made: these images are not exact (the shortest) solutions, but rather appropriate (short enough). All images are clickable (open them in the new window for the better view)

Set of 5000 points, randomly laid in a circular pattern.
A gaussian spot of 5000 random points.

A set of 5000 points, uniformly filling a box.
In these pictures, node color gradually changes along the way.
They were generated using self-written TSP solver in python and several scripts, that prepare point sets and render SVG.
Conversion to PNG was done with inkscape.