-----

 

The Traveling Salesperson Problem (TSP) is an important problem in theoretical computer science. A TSP instance is a set of points. To solve it is to produce a tour that starts at one point and returns to it after visiting all other points exactly once; to solve it optimally is to produce the shortest possible tour. The TSP is NP-Hard in the algorithmic sense: as far as we know, it is impossible for computers to solve such problems efficiently. It is therefore surprising that humans are quite effective for TSP instances of 120 or fewer points: they produce tours that are within 10% of the minimal length, and they do so in time linear in the number of points. We propose that they accomplish this feat by adopting a divide-and-conquer strategy: first visually clustering the points, then solving each cluster as a smaller TSP instance, and finally joining together these solutions to solve the overall problem. Building on recent work showing that visual clustering is a reliable perceptual ability (Marupudi & Varma, 2024, Psychological Review), we first show that solving TSP instances is also a reliable cognitive ability. We then evaluate the proposal that people use a clustering-based divide-and-conquer strategy. Participants clustered point arrays and also solved them as TSPs. Strikingly, on 52% of all trials, their TSP solution perfectly followed their clustering of the same point array. We also evaluate human performance against (1) the clusterings computed by K-Means and (2) the optimal TSP tours computed by computer science algorithms. Our findings establish the psychological viability of the divide-and-conquer strategy for efficiently solving a computationally hard problem. They set the stage for future studies of how people make hard problems tractable and, more generally, of investigations of algorithmic thinking.

-----