Clustering, Randomness, and Regularity: Spatial Distributions and Human Performance on the Traveling Salesperson Problem and Minimum Spanning Tree Problem
Clustering, Randomness, and Regularity: Spatial Distributions and Human Performance on the Traveling Salesperson Problem and Minimum Spanning Tree Problem
复制标题
DOI：
10.7771/1932-6246.1117
复制
发表时间：
2012-12-01
期刊：
影响因子：
--
通讯作者：
Wagemans, Johan
中科院分区：
文献类型：
--
作者：
Dry, Matthew J.;Preiss, Kym;Wagemans, Johan
我们考察了人类在欧几里德旅行商问题(TSP)和欧几里德最小生成树问题(MST-P)上的表现，涉及到一个以前在文献中很少受到关注的因素：TSP和MST-P刺激的空间分布。首先，我们描述了一种方法，用于量化点分布内的聚集性、随机性或规律性的相对程度。然后，我们回顾了表明这一因素可能会影响人类在这两种问题类型上的表现的证据。之后，我们报告了一个实验，参与者被要求解决TSP和MST-P测试刺激，这些刺激要么是高度聚集的，要么是随机的，要么是高度规则的。结果表明，对于TSP和MST-P，当刺激高度聚集时，参与者倾向于产生比随机刺激更高质量的解决方案，类似地，与高度规则刺激相比，随机刺激产生更好质量的解决方案。研究表明，这些结果支持了这样的观点，即人类在解决这些问题时会注意显著的节点集群，并且类似的过程(或一系列过程)可能是人类在这两项任务中表现的基础。
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.