NotesFAQContact Us
Search Tips
Peer reviewed Peer reviewed
Direct linkDirect link
ERIC Number: EJ1115923
Record Type: Journal
Publication Date: 2012-Feb
Pages: 18
Abstractor: As Provided
ISSN: EISSN-1932-6246
Clustering, Randomness, and Regularity: Spatial Distributions and Human Performance on the Traveling Salesperson Problem and Minimum Spanning Tree Problem
Dry, Matthew J.; Preiss, Kym; Wagemans, Johan
Journal of Problem Solving, v4 n1 Article 2 p1-17 Feb 2012
We investigated human performance on the Euclidean Traveling Salesperson Problem (TSP) and Euclidean Minimum Spanning Tree Problem (MST-P) in regards to a factor that has previously received little attention within the literature: the spatial distributions of TSP and MST-P stimuli. First, we describe a method for quantifying the relative degree of clustering, randomness or regularity within point distributions. We then review evidence suggesting this factor might influence human performance on the two problem types. Following this we report an experiment in which the participants were asked to solve TSP and MST-P test stimuli that had been generated to be either highly clustered, random, or highly regular. The results indicate that for both the TSP and MST-P the participants tended to produce better quality solutions when the stimuli were highly clustered compared to random, and similarly, better quality solutions for random compared to highly regular stimuli. It is suggested that these results provide support for the ideas that human solvers attend to salient clusters of nodes when solving these problems, and that a similar process (or series of processes) may underlie human performance on these two tasks.
Purdue University Press. Stewart Center Room 370, 504 West State Street, West Lafayette, IN 47907. Tel: 800-247-6553; Fax: 419-281-6883; e-mail: pupress@purdue,edu; Web site:
Publication Type: Journal Articles; Reports - Research
Education Level: N/A
Audience: N/A
Language: English
Sponsor: N/A
Authoring Institution: N/A
Identifiers - Location: Australia
Grant or Contract Numbers: N/A