摘要：The two-dimensional Traveling Salesperson Problem (TSP) requires finding the shortest tour through n locations. Untrained adults are adept at the task, and reliably outperform simple construction algorithms for n up to 60. Performance may stem from a specific, inherent ability. Alternatively, it may reflect general spatial intelligence, whether inherent or acquired. If the latter holds, then people should be equally adept at finding longest tours. Two experiments comparing ability in the two tasks found participants significantly better at finding short than long tours. Furthermore, human performance was significantly worse than a simple construction algorithm (furthest-neighbor) for the task of finding long tours. The result is consistent with the hypothesis of a specific, inherent ability to find short routes.
关键词：travelling salesperson problem; heuristics; long and short tours
