Use of clustering in human solutions of the traveling salesperson problem

Image credit: Marupudi et al. (2022)


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 reasoning about graph-theoretic algorithmic problems.

In Proceedings of the 44th Annual Conference of the Cognitive Science Society
Jeffrey K. Bye
Jeffrey K. Bye
Lecturer, Educational Psychology

Researching how people think about math & data. Teaching CogSci & programming.