| People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours. | |
| | |
MedLine Citation:
|
PMID: 20686597 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
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 Salesman Problem (TSP). Participants were provided feedback on the cost of their solutions and were allowed unlimited solution attempts (trials). We found a significant improvement between the first and last trials and that solutions are significantly different from random tours that follow the convex hull and do not have self-crossings. More importantly, we found that participants modified their current better solutions in such a way that edges belonging to the optimal solution ("good" edges) were significantly more likely to stay than other edges ("bad" edges), a hallmark of structural exploitation. We found, however, that more trials harmed the participants' ability to tell good from bad edges, suggesting that after too many trials the participants "ran out of ideas." In sum, we provide the first demonstration of significant performance improvement on the TSP under repetition and feedback and evidence that human problem-solving may exploit the structure of hard problems paralleling behavior of state-of-the-art heuristics. |
| | |
Authors:
|
Daniel E Acuña; Víctor Parada |
Related Documents
:
|
11541987 - Proterozoic stromatolitic microbiotas of the 1400-1500 ma-old gaoyuzhuang formation nea... 17186817 - A fast procedure for optimizing dynamic force distribution in multifingered grasping. 20513927 - Approximate nearest subspace search. 7621037 - Gaining access to calcified canals. 12412497 - Identifying stalking: the relevance of intent in commonsense reasoning. 11360447 - The biotoxicity and color formation results from ozonation of wastewaters containing ph... |
Publication Detail:
|
Type: Clinical Trial; Journal Article; Research Support, N.I.H., Extramural; Research Support, Non-U.S. Gov't Date: 2010-07-29 |
Journal Detail:
|
Title: PloS one Volume: 5 ISSN: 1932-6203 ISO Abbreviation: PLoS ONE Publication Date: 2010 |
Date Detail:
|
Created Date: 2010-08-05 Completed Date: 2010-10-28 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101285081 Medline TA: PLoS One Country: United States |
Other Details:
|
Languages: eng Pagination: e11685 Citation Subset: IM |
Affiliation:
|
Department of Computer Science and Engineering and Center for Cognitive Sciences, University of Minnesota, Minneapolis, Minnesota, United States of America. acuna@cs.umn.edu |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Adult Artificial Intelligence* Commerce* Computer Simulation Female Humans Male Problem Solving / physiology* Young Adult |
| Grant Support | |
ID/Acronym/Agency:
|
1R90 DK71500-04/DK/NIDDK NIH HHS |
| Comments/Corrections | |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Memory consolidation in the cerebellar cortex.
Next Document: Exploring the genetic basis of variation in gene predictions with a synthetic association study.