People Efficiently Explore the Solution Space of the Computationally Intractable Traveling Salesman Problem to Find Near-Optimal Tours

被引:9
作者
Acuna, Daniel E. [1 ,2 ]
Parada, Victor [3 ]
机构
[1] Univ Minnesota, Dept Comp Sci & Engn, Minneapolis, MN 55455 USA
[2] Univ Minnesota, Ctr Cognit Sci, Minneapolis, MN USA
[3] Univ Santiago, Dept Ingn Informat, Santiago, Chile
基金
美国国家卫生研究院;
关键词
CONVEX-HULL; PHASE-TRANSITIONS; HUMAN-PERFORMANCE; COMPLEXITY; OPTIMIZATION; BACKBONES; ALGORITHM; MODELS;
D O I
10.1371/journal.pone.0011685
中图分类号
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号
07 ; 0710 ; 09 ;
摘要
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.
引用
收藏
页数:10
相关论文
共 54 条
[1]   Rigorous location of phase transitions in hard optimization problems [J].
Achlioptas, D ;
Naor, A ;
Peres, Y .
NATURE, 2005, 435 (7043) :759-764
[2]   Explosive Percolation in Random Networks [J].
Achlioptas, Dimitris ;
D'Souza, Raissa M. ;
Spencer, Joel .
SCIENCE, 2009, 323 (5920) :1453-1555
[3]  
ACUNA D, 2008, NEURAL INFORM PROCES
[4]  
*AD, 2002, AD FLASH TECHN
[5]   A fast and scalable radiation hybrid map construction and integration strategy [J].
Agarwala, R ;
Applegate, DL ;
Maglott, D ;
Schuler, GD ;
Schäffer, AA .
GENOME RESEARCH, 2000, 10 (03) :350-364
[6]  
Agresti A., 2002, CATEGORICAL DATA ANA, DOI [10.1002/0471249688, DOI 10.1002/0471249688]
[7]  
[Anonymous], 2010, Am Psychol, V65, P493, DOI 10.1037/a0020168
[8]  
[Anonymous], P AAAI 97
[9]  
APPLEGATE D, 2005, CONCORDE CODE SOLVIN
[10]  
Bellman Richard., 1960, Proceedings of Symposia in Applied Mathematics, V10