Use of clustering in human solutions of the traveling salesperson problem

The traveling salesperson problem (TSP) is an NP-Hard problem that computers find difficult to solve. Humans are surprisingly good at solving the TSP, with solutions within 10% of optimal for problems with up to 100 points, constructed in time linear with the number of points. We propose that humans solve the TSP by initially clustering the points and then connecting them first within and then between clusters. In this study, 67 participants first clustered 40 stimuli and then solved them as TSPs. Strikingly, participants' TSP solutions perfectly followed their clusters for 52% of the stimuli. Further, participants' TSP solutions were more congruent with their clusters for stimuli with statistically higher levels of clustered structure. This provides strong evidence for the clustering proposal. Random TSP solutions, however, showed no such congruence to cluster structure. These findings suggest that clustering might be a fundamental ability for human reasoning about graph-theoretic algorithmic problems.