Human performance on the traveling salesman problem.

Psychology

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Human performance on the traveling salesman problem. / MacGregor, J. N.; Ormerod, Thomas C.
In: Perception and Psychophysics, Vol. 58, No. 4, 1996, p. 527-539.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Bibtex

@article{01a86aa3a07145f4b470010cf617a16a,

title = "Human performance on the traveling salesman problem.",

abstract = "Two experiments on performance on the traveling salesman problem (TSP) are reported. The TSP consists of finding the shortest path through a set of points, returning to the origin. It appears to be an intransigent mathematical problem, and heuristics have been developed to find approximate solutions. The first experiment used 10-point, the second, 20-point problems. The experiments tested the hypothesis that complexity of TSPs is a function of number of nonboundary points, not total number of points. Both experiments supported the hypothesis. The experiments provided information on the quality of subjects{\textquoteright} solutions. Their solutions clustered close to the best known solutions, were an order of magnitude better than solutions produced by three well-known heuristics, and on average fell beyond the 99.9th percentile in the distribution of random solutions. The solution process appeared to be perceptually based.",

author = "MacGregor, {J. N.} and Ormerod, {Thomas C.}",

year = "1996",

language = "English",

volume = "58",

pages = "527--539",

journal = "Perception and Psychophysics",

issn = "1532-5962",

publisher = "Psychonomic Society Inc.",

number = "4",

}

RIS

TY - JOUR

T1 - Human performance on the traveling salesman problem.

AU - MacGregor, J. N.

AU - Ormerod, Thomas C.

PY - 1996

Y1 - 1996

N2 - Two experiments on performance on the traveling salesman problem (TSP) are reported. The TSP consists of finding the shortest path through a set of points, returning to the origin. It appears to be an intransigent mathematical problem, and heuristics have been developed to find approximate solutions. The first experiment used 10-point, the second, 20-point problems. The experiments tested the hypothesis that complexity of TSPs is a function of number of nonboundary points, not total number of points. Both experiments supported the hypothesis. The experiments provided information on the quality of subjects’ solutions. Their solutions clustered close to the best known solutions, were an order of magnitude better than solutions produced by three well-known heuristics, and on average fell beyond the 99.9th percentile in the distribution of random solutions. The solution process appeared to be perceptually based.

AB - Two experiments on performance on the traveling salesman problem (TSP) are reported. The TSP consists of finding the shortest path through a set of points, returning to the origin. It appears to be an intransigent mathematical problem, and heuristics have been developed to find approximate solutions. The first experiment used 10-point, the second, 20-point problems. The experiments tested the hypothesis that complexity of TSPs is a function of number of nonboundary points, not total number of points. Both experiments supported the hypothesis. The experiments provided information on the quality of subjects’ solutions. Their solutions clustered close to the best known solutions, were an order of magnitude better than solutions produced by three well-known heuristics, and on average fell beyond the 99.9th percentile in the distribution of random solutions. The solution process appeared to be perceptually based.

M3 - Journal article

VL - 58

SP - 527

EP - 539

JO - Perception and Psychophysics

JF - Perception and Psychophysics

SN - 1532-5962

IS - 4

ER -

Research