Today I read a paper titled “Computation of the Travelling Salesman Problem by a Shrinking Blob”
The abstract is:
The Travelling Salesman Problem (TSP) is a well known and challenging combinatorial optimisation problem
Its computational intractability has attracted a number of heuristic approaches to generate satisfactory, if not optimal, candidate solutions
In this paper we demonstrate a simple unconventional computation method to approximate the Euclidean TSP using a virtual material approach
The morphological adaptation behaviour of the material emerges from the low-level interactions of a population of particles moving within a diffusive lattice
A `blob’ of this material is placed over a set of data points projected into the lattice, representing TSP city locations, and the blob is reduced in size over time
As the blob shrinks it morphologically adapts to the configuration of the cities
The shrinkage process automatically stops when the blob no longer completely covers all cities
By manually tracing the perimeter of the blob a path between cities is elicited corresponding to a TSP tour
Over 6 runs on 20 randomly generated datasets of 20 cities this simple and unguided method found tours with a mean best tour length of 1.04, mean average tour length of 1.07 and mean worst tour length of 1.09 when expressed as a fraction of the minimal tour computed by an exact TSP solver
We examine the insertion mechanism by which the blob constructs a tour, note some properties and limitations of its performance, and discuss the relationship between the blob TSP and proximity graphs which group points on the plane
The method is notable for its simplicity and the spatially represented mechanical mode of its operation
We discuss similarities between this method and previously suggested models of human performance on the TSP and suggest possibilities for further improvement