People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours.
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 explanati...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2010-07-01
|
| Series: | PLoS ONE |
| Online Access: | http://europepmc.org/articles/PMC2912227?pdf=render |
| _version_ | 1819278571345018880 |
|---|---|
| author | Daniel E Acuña Víctor Parada |
| author_facet | Daniel E Acuña Víctor Parada |
| author_sort | Daniel E Acuña |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-24T00:14:07Z |
| format | Article |
| id | doaj.art-bef83263e2ed4cff81e841eab4048e05 |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-12-24T00:14:07Z |
| publishDate | 2010-07-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-bef83263e2ed4cff81e841eab4048e052022-12-21T17:24:48ZengPublic Library of Science (PLoS)PLoS ONE1932-62032010-07-0157e1168510.1371/journal.pone.0011685People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours.Daniel E AcuñaVíctor ParadaHumans 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.http://europepmc.org/articles/PMC2912227?pdf=render |
| spellingShingle | Daniel E Acuña Víctor Parada People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours. PLoS ONE |
| title | People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours. |
| title_full | People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours. |
| title_fullStr | People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours. |
| title_full_unstemmed | People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours. |
| title_short | People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours. |
| title_sort | people efficiently explore the solution space of the computationally intractable traveling salesman problem to find near optimal tours |
| url | http://europepmc.org/articles/PMC2912227?pdf=render |
| work_keys_str_mv | AT danieleacuna peopleefficientlyexplorethesolutionspaceofthecomputationallyintractabletravelingsalesmanproblemtofindnearoptimaltours AT victorparada peopleefficientlyexplorethesolutionspaceofthecomputationallyintractabletravelingsalesmanproblemtofindnearoptimaltours |