The role of clustering in the efficient solution of small Traveling Salesperson Problems

Vijay Marupudi, Rina Miyata Harsch, V. N. Vimal Rao, Jeffrey Kramer Bye, Jimin Park, Sashank Varma

Research output: Contribution to conferencePaperpeer-review

1 Scopus citations

Abstract

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 languageEnglish (US)
Pages1865-1871
Number of pages7
StatePublished - 2021
Event43rd Annual Meeting of the Cognitive Science Society: Comparative Cognition: Animal Minds, CogSci 2021 - Virtual, Online, Austria
Duration: Jul 26 2021Jul 29 2021

Conference

Conference43rd Annual Meeting of the Cognitive Science Society: Comparative Cognition: Animal Minds, CogSci 2021
Country/TerritoryAustria
CityVirtual, Online
Period7/26/217/29/21

Bibliographical note

Funding Information:
We thank Kori Terkelsen for coordinating data collection on this study and for helping the transition online when the COVID-19 pandemic arrived.

Publisher Copyright:
© Cognitive Science Society: Comparative Cognition: Animal Minds, CogSci 2021.All rights reserved.

Keywords

  • computational complexity
  • computational thinking
  • mathematical cognition
  • problem solving
  • traveling salesperson problem

Fingerprint

Dive into the research topics of 'The role of clustering in the efficient solution of small Traveling Salesperson Problems'. Together they form a unique fingerprint.

Cite this