ORIGINAL FORMAT VIDEO https://youtu.be/AK3Ip7G-HTU?si=ArOdrgvBz_bltJtj Lecture | Sashank Varma
Sashank Varma | Interactive Computing / Psychology | Georgia Institute of Technology
"The Travelling Salesperson Problem: How Humans 'Efficiently' Solve a Problem Which is 'Hard' for Computers"
“The Traveling Salesperson Problem (TSP) is an important problem in mathematics and 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, and to solve it optimally is to produce a tour of minimum length. As far as we know, computers cannot solve this problem optimally. It is therefore surprising that, for small instances, people produce tours that are near-optimal (i.e., within 10% of the minimal length), and they do so in time linear in the number of points. To accomplish this remarkable feat, we propose that they adopt 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. We provide evidence for this proposal in three behavioral experiments and one computational experiment. These findings establish the psychological viability of the divide-and-conquer strategy for solving the TSP, and they set the stage for future studies of how people tame the complexity of computationally ‘hard’ problems.”