People Efficiently Explore the Solution Space of the Computationally Intractable Traveling Salesman Problem to Find Near-Optimal Tours
Daniel E. Acuña, Víctor Parada · 2010
Read People Efficiently Explore the Solution Space of the Computationally Intractable Traveling Salesman Problem to Find Near-Optimal Tours by Daniel E. Acuña, Víctor Parada (2010) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/plos-pone-0011685.txt.
Description
Daniel Acuña and Víctor Parada studied how people solve a classic hard problem, in PLOS ONE in 2010. The traveling salesman problem asks for the shortest tour through many stops, and the number of possible tours explodes so fast that even computers cannot check them all. People, oddly, do well at such hard problems in daily life.
Given tour problems to solve, participants explored the options efficiently and found near-optimal routes. Their strategies avoided wasting effort on hopeless regions of the search space. Understanding these mental shortcuts can inspire better algorithms and explain how humans handle intractable choices.
Catalog record
| CREATOR | Daniel E. Acuña, Víctor Parada |
|---|---|
| YEAR | 2010 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| LICENSE | Creative Commons Attribution License |
| RIGHTS | CC BY |
| SOURCE | PLOS ONE |
Source: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0011685