Monday, 7 September 2009

The travelling salesman problem and bacterial computers

This post was generated by the marvellous webcomic, below, from David Malki's Wondermark (a fascinating project in and of itself).

As usual, click on the image to make it legible. Weblink here.

Witticisms aside, the first thing that came to mind was the travelling salesman problem, a lovely little piece of computational maths. To give you the gist: it's all about a travelling salesman, who has to figure out how to optimise his sales route so that he only visits each place once, and completes the route in the shortest possible distance. It's been the focus (well, sort of) of such things as genetic algorithms (which can be used for all sorts of fascinating things, and I'd strongly advise that you explore the area further), and now a new field called bacterial computing.

Bacterial computing fuses mathematics and biology to compute problems - sort of like genetic algorithms on 'roids. And recently, it was used to solve something called the Hamiltonian Path Problem, which is similar to that issue faced by our anonymous, but hopefully ubiquitous, salesman. The Burnt Pancake problem also features, which name I am endlessly amused by. Also, there's an unrelated, but darkly amusing, xkcd strip about pancakes.

The whole field is called, enticingly, 'synthetic biology', and the brains behind it reckon that it has uses not only for solving fun maths puzzles, but also for more concrete uses such as medicine, energy and even the environment.

Anyway, the paper can be found here (it was published in the Journal of Biological Engineering, which, given its name, I expect to be presenting me with a means of having gills as well as lungs sometime very soon).