Center For Mind, Brain, And Culture

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