The importance of the convex hull for human performance on the traveling salesman problem: a comment on MacGregor and Ormerod (1996)

Effects of cluster location and cluster distribution on performance on the traveling salesman problem

Research on human performance in solving traveling salesman problems typically uses point sets as stimuli, and most models have proposed a processing stage at which stimulus dots are clustered. However, few empirical studies have investigated the effects of clustering on performance. In one recent study, researchers compared the effects of clustered, random, and regular stimuli, and concluded that clustering facilitates performance (Dry, Preiss, & Wagemans, 2012). Another study suggested that these results may have been influenced by the location rather than the degree of clustering (MacGregor, 2013). Two experiments are reported that mark an attempt to disentangle these factors. The first experiment tested several combinations of degree of clustering and cluster location, and revealed mixed evidence that clustering influences performance. In a second experiment, both factors were varied independently, showing that they interact. The results are discussed in terms of the importance of clustering effects, in particular, and perceptual factors, in general, during performance of the traveling salesman problem.

People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours

Humans need to solve computationally intractable problems such as visual search, categorization, and simultaneous learning and acting, yet an increasing body of evidence suggests that their solutions to instantiations of these problems are near optimal. Computational complexity advances an explanation to this apparent paradox: (1) only a small portion of instances of such problems are actually hard, and (2) successful heuristics exploit structural properties of the typical instance to selectively improve parts that are likely to be sub-optimal. We hypothesize that these two ideas largely account for the good performance of humans on computationally hard problems. We tested part of this hypothesis by studying the solutions of 28 participants to 28 instances of the Euclidean Traveling Salesman Problem (TSP). Participants were provided feedback on the cost of their solutions and were allowed unlimited solution attempts (trials). We found a significant improvement between the first and last trials and that solutions are significantly different from random tours that follow the convex hull and do not have self-crossings. More importantly, we found that participants modified their current better solutions in such a way that edges belonging to the optimal solution ("good" edges) were significantly more likely to stay than other edges ("bad" edges), a hallmark of structural exploitation. We found, however, that more trials harmed the participants' ability to tell good from bad edges, suggesting that after too many trials the participants "ran out of ideas." In sum, we provide the first demonstration of significant performance improvement on the TSP under repetition and feedback and evidence that human problem-solving may exploit the structure of hard problems paralleling behavior of state-of-the-art heuristics.

The aesthetic appeal of minimal structures: Judging the attractiveness of solutions to traveling salesperson problems

Ormerod and Chronicle (1999) reported that optimal solutions to traveling salesperson problems were judged to be aesthetically more pleasing than poorer solutions and that solutions with more convex hull nodes were rated as better figures. To test these conclusions, solution regularity and the number of potential intersections were held constant, whereas solution optimality, the number of internal nodes, and the number of nearest neighbors in each solution were varied factorially. The results did not support the view that the convex hull is an important determinant of figural attractiveness. Also, in contrast to the findings of Ormerod and Chronicle, there were consistent individual differences. Participants appeared to be divided as to whether the most attractive figure enclosed a given area within a perimeter of minimum or maximum length. It is concluded that future research in this area cannot afford to focus exclusively on group performance measures.

Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem

Untrained adults appear to have access to cognitive processes that allow them to perform well in the Euclidean version of the traveling salesperson problem (E-TSP). They do so despite the famous computational intractability of the problem, which stems from its combinatorial complexity. A current hypothesis is the humans' good performance is based on following a strategy of connecting boundary points in order (the convex hull hypothesis). Recently, an alternative has been proposed, that performance is governed by a strategy of avoiding crossings. We examined the crossing avoidance hypothesis from the perspectives of its capacity to explain existing data, its theoretical adequacy, and its ability to explain the results of three new experiments. In Experiment 1, effects on the solution quality of number of points versus number of interior points were compared. In Experiment 2, the distributions of observed paths were compared with those predicted from the two hypotheses. In Experiment 3, figural effects were varied to induce crossings. The results of the experiments were more consistent with the convex hull than with the crossing avoidance hypothesis. Despite its simplicity and intuitive appeal, crossing avoidance does not provide a complete alternative to the convex hull hypothesis. Further elucidation of human strategies and heuristics for optimization problems such as the E-TSP will aid our understanding of how cognitive processes have adapted to the demands of combinatorial difficulty.

The perception of minimal structures: performance on open and closed versions of visually presented Euclidean travelling salesperson problems

The planar Euclidean version of the travelling salesperson problem (TSP) requires finding a tour of minimal length through a two-dimensional set of nodes. Despite the computational intractability of the TSP, people can produce rapid, near-optimal solutions to visually presented versions of such problems. To explain this, MacGregor et al (1999, Perception 28 1417-1428) have suggested that people use a global-to-local process, based on a perceptual tendency to organise stimuli into convex figures. We review the evidence for this idea and propose an alternative, local-to-global hypothesis, based on the detection of least distances between the nodes in an array. We present the results of an experiment in which we examined the relationships between three objective measures and performance measures of optimality and response uncertainty in tasks requiring participants to construct a closed tour or an open path. The data are not well accounted for by a process based on the convex hull. In contrast, results are generally consistent with a locally focused process based initially on the detection of nearest-neighbour clusters. Individual differences are interpreted in terms of a hierarchical process of constructing solutions, and the findings are related to a more general analysis of the role of nearest neighbours in the perception of structure and motion.

The roles of the convex hull and the number of potential intersections in performance on visually presented traveling salesperson problems

The planar Euclidean version of the traveling salesperson problem requires finding the shortest tour through a two-dimensional array of points. MacGregor and Ormerod (1996) have suggested that people solve such problems by using a global-to-local perceptual organizing process based on the convex hull of the array. We review evidence for and against this idea, before considering an alternative, local-to-global perceptual process, based on the rapid automatic identification of nearest neighbors. We compare these approaches in an experiment in which the effects of number of convex hull points and number of potential intersections on solution performance are measured. Performance worsened with more points on the convex hull and with fewer potential intersections. A measure of response uncertainty was unaffected by the number of convex hull points but increased with fewer potential intersections. We discuss a possible interpretation of these results in terms of a hierarchical solution process based on linking nearest neighbor clusters.

Convex hull and tour crossings in the Euclidean traveling salesperson problem: implications for human performance studies

Recently there has been growing interest among psychologists in human performance on the Euclidean traveling salesperson problem (E-TSP). A debate has been initiated on what strategy people use in solving visually presented E-TSP instances. The most prominent hypothesis is the convex-hull hypothesis, originally proposed by MacGregor and Ormerod (1996). We argue that, in the literature so far, there is no evidence for this hypothesis. Alternatively we propose and motivate the hypothesis that people aim at avoiding crossings.

Evaluating the importance of the convex hull in solving the Euclidean version of the traveling salesperson problem: reply to Lee and Vickers (2000)

Lee and Vickers (2000) suggest that the results of MacGregor and Ormerod (1996), showing that the response uncertainty to traveling salesperson problems (TSPs) increases with increasing numbers of nonboundary points, may have resulted as an artifact of constraints imposed in the construction of stimuli. The fact that similar patterns of results have been obtained for our "constrained" stimuli, for a stimulus constructed under different constraints, for 13 randomly generated stimuli, and for random and patterned 48-point problems provides empirical evidence that the results are not artifactual. Lee and Vickers further suggest that, even if not artifactual, the results are in principle limited to arrays of fewer than 50 points and that, beyond this, the total number of points and number of nonboundary points are "diagnostically equivalent." This claim seems to us incorrect, since arrays of any size can be constructed that will permit experimental tests of whether problem difficulty is influenced by the number of nonboundary points, or the total number of points, or both. We present a reanalysis of our original data using hierarchical regression analysis which indicates that both factors may influence problem complexity.