Dry, M., Lee, M. D., Vickers, D., and Hughes, P. Human performance on visually presented travelling salesperson problems with varying numbers of nodes. The Journal of Problem Solving 1, 1 (2006), 20–32. [pdf]

————

This article shows that despite the apparent intractability of the TSP (Traveling Salesman Problem), research into human performance upon visually presented TSPs has indicated that participants are capable of solving the problems to nes optimal accuracy with minimum cognitive effort.

Participants appear to spend a roughly contant time per node, implying the the total time required to arrive to a solution is a linear function of the number of nodes. Second, there are many algorythms that yield approximate solutions to TSP instances. However, no known algorithm predicts a simple linear relationship between solution time and number of nodes.

The authors presented random problems to participants. A white stimuly with black dots. The goal was to join the dots in such a way that the path was closed and that the path lenght was minimal.

Using an optimal solution as benchmark, it was possible to measure the mean participant deviation from optimality for each problem in the TSP condition. Participants solution lenght closely approximate the estimated optimal solution lenghts, with deviation asymptoting around 0.11.

Author discuss that perception of the convex hull (a boundary so that no line joining any two nodes in the array can fall outside it) is a form of figure-ground segregation. They also argue that we need to take a distinction between the spontaneous parallel processes involved in the initial perception of the structure in TSP arrays and the serial processes of linking individual nodes or clusters of nodes.