A Model of Fast Human Performance on a Computationally Hard Problem
Bradley J. Best · eScholarship (California Digital Library) · 2005
Human performance on the Traveling Salesperson Problem (TSP) is of consistently high quality and scales approximately linearly in time with problem size. A model leveraging parallel processing of perceptual grouping and a local serial search achieves both a comparable quality of performance and comparable time complexity. Human Performance on the Traveling Salesperson Problem The Traveling Salesperson Problem (TSP) consists of attempting to find the shortest complete tour through a series of points (cities), starting and ending with the same point. This problem is a member of the set of computationally hard, or NP-complete, problems, for which the best solutions known are obtained in exponential time