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

Bradley J. Best

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.