Human solutions to the Traveling Salesperson Problem (TSP) are surprisingly close to optimal and unexpectedly efficient. We posit that humans solve instances of the TSP by first clustering the points into smaller regions and then solving each cluster as a simpler TSP. Prior research has shown that participants cluster visual stimuli reliably. That is, their clustering and re-clustering of the same stimulus are similar, especially when the stimulus is relatively more clustered. In this study, participants solved the same TSP instances twice. On the second presentation, half of the instances were flipped about the horizontal and vertical axes. Participants solved the TSP reliably, with their two tours of the same instance sharing 77 percent of the same edges on average. In addition, within-participant reliability was higher for more clustered versus more dispersed instances. Our findings are consistent with the proposal that people use clustering strategies to solve the TSP.
|Original language||English (US)|
|Number of pages||7|
|State||Published - 2021|
|Event||43rd Annual Meeting of the Cognitive Science Society: Comparative Cognition: Animal Minds, CogSci 2021 - Virtual, Online, Austria|
Duration: Jul 26 2021 → Jul 29 2021
|Conference||43rd Annual Meeting of the Cognitive Science Society: Comparative Cognition: Animal Minds, CogSci 2021|
|Period||7/26/21 → 7/29/21|
Bibliographical noteFunding Information:
We thank Kori Terkelsen for coordinating data collection on this study and for helping the transition online when the COVID-19 pandemic arrived.
© Cognitive Science Society: Comparative Cognition: Animal Minds, CogSci 2021.All rights reserved.
- computational complexity
- computational thinking
- mathematical cognition
- problem solving
- traveling salesperson problem