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

Between a Rock and a Hard Place: Cognitive Science Principles Meet AI-Hard Problems

Volume

Papers from the 2006 AAAI Spring Symposium

Contents

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 and compares cognitive mechanisms implicated with human solutions to the TSP and their impact on the complexity and accuracy of the solution. In particular, the impact of Euclidean clustering is compared to a distorted clustering distance measure, and the efficacy of solving TSPs in a breadth-first manner is compared with the efficacy of solving TSPs in a depth-first manner. The empirical evidence indicates that distorted clustering and breadth-first solution development are superior to the tested alternatives.