Cognitive Approaches to the Traveling Salesperson Problem: Perceptual Complexity that Produces Computational Simplicity

The Traveling Salesperson Problem (TSP) is a classical problem in complexity theory that has provided significant motivation for the development of that theory. The TSP has also shown that exact solutions come at a high price: exponential time complexity. As a result, heuristic solutions to the TSP are often the only practical means for dealing with this intractable problem. Heuristic solutions are a hallmark of human cognition, although most heuristic solutions to the TSP share little inspiration with human cognition. This is unfortunate, since human solutions to the TSP have proven to be both accurate and rapid. Understanding human approaches to the TSP holds the promise to inform the development of heuristic approaches to computationally hard problems. This report explores an