People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours.

ABSTRACT: Humans need to solve computationally intractable problems such as visual search, categorization, and simultaneous learning and acting, yet an increasing body of evidence suggests that their solutions to instantiations of these problems are near optimal. Computational complexity advances an explanation to this apparent paradox: (1) only a small portion of instances of such problems are actually hard, and (2) successful heuristics exploit structural properties of the typical instance to selectively improve parts that are likely to be sub-optimal. We hypothesize that these two ideas largely account for the good performance of humans on computationally hard problems. We tested part of this hypothesis by studying the solutions of 28 participants to 28 instances of the Euclidean Traveling Salesm

SUBMITTER: Acuna DE 

PROVIDER: S-EPMC2912227 | biostudies-literature | 2010 Jul

REPOSITORIES: biostudies-literature