Take the 2-minute tour ×
Cognitive Sciences Stack Exchange is a question and answer site for practitioners, researchers, and students in cognitive science, psychology, neuroscience, and psychiatry. It's 100% free, no registration required.

In the traveling salesman problem (TSP) we are given a set of nodes, where one node is the starting node. The task is to find the shortest tour starting at the start node visiting every node exactly once. A variant of the more general TSP is the Euclidean TSP, where the distance between two cities is the usual Euclidean distance. Different metrics can also be considered, suck as the city-block metric.

Based on experimental data in [1], the authors claim that Euclidean TSP instances are easy for humans. They also gathered data on case where the metric used is the city-block metric. They note that "... people are near-optimal for these problems in both metrics."

  • What variants of the travelling salesman problem are hard for humans?
  • Has any research been done on this?

[1] Walwyn, A. L., & Navarro, D. J. (2010). Minimal Paths in the City Block: Human Performance on Euclidean and Non-Euclidean Traveling Salesperson Problems. The Journal of Problem Solving, 3(1), 5.

share|improve this question
    
My conjecture is that whenever, for a given problem, the optimality gap for the greedy heuristic is small, then it's easy for humans so solve. –  Wuschelbeutel Kartoffelhuhn Aug 15 '13 at 2:51
    
@WuschelbeutelKartoffelhuhn That feels plausible, yes. –  mrm Aug 15 '13 at 13:09
add comment

1 Answer

up vote 4 down vote accepted

I just quickly looked this up on Google Scholar and found the following interesting reference :

  • JN Macgregor, T Ormerod. "Human performance on the traveling salesman problem." Perception & Psychophysics Volume 58, Issue 4, pp 527-539 (June 1996)

This paper claims that "complexity of TSPs is a function of number of nonboundary points, not total number of points." They define a nonboundary point as a point inside the convex hull that encompasses all points in the problem. This paper also makes some interesting observations about perceptual space for humans in this task, claiming that the problem appears to be solved by humans in a 2D problem space that matches the 2D perceptual space. Finally, the references cited by this paper indicate that at least some research has gone into the question of human performance on the TSP as far back as the late 1960s.

It looks like you might also get some useful pointers by following the citation graph from this paper forward in time : http://scholar.google.com/scholar?cites=9195299723226128892

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.