Academic journal article Attention, Perception and Psychophysics

Effects of Cluster Location and Cluster Distribution on Performance on the Traveling Salesman Problem

Academic journal article Attention, Perception and Psychophysics

Effects of Cluster Location and Cluster Distribution on Performance on the Traveling Salesman Problem

Article excerpt

Published online: 14 May 2015

© The Psychonomic Society, Inc. 2015

Abstract 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.

Keywords Visual perception . Spatial cognition . Perceptual organization

Dot arrays have been used as stimuli for the study of grouping and clustering effects in perception at least since Wertheimer's (1923/1950) pioneering analysis. Since then, dot arrays have been used to investigate a wide variety of perceptual phenomena, including perceptual organization (Trick & Enns, 1997), clustering (O'Callaghan, 1974), depth perception (Julesz, 1965), texture perception (Pickett, 1964), apparent motion (Ramachandran & Anstis, 1986), and the perception of biological movement (Johansson, 1973). Recently, random and patterned point sets have been used to study human performance in combinatorial optimization problems such as the traveling salesman (TSP), minimum spanning tree, and generalized Steiner tree problems (Vickers, Mayo, Heitmann, Lee, & Hughes, 2004). Although the names may imply that such research falls in the domain of problem solving, theoretical developments and empirical research in the area have frequently cited perceptual mechanisms, and the initial studies were often published in perception journals (Lee & Vickers, 2000; MacGregor & Ormerod, 1996;MacGregor,Ormerod, & Chronicle 1999; Ormerod & Chronicle, 1999; Vickers, Butavicius, Lee, & Medvedev, 2001). More recently, this new area of research has captured the interest of cognitive scientists working in clinical neuroscience, comparative psychology, decision making, memory, and vision (MacGregor, 2012), but often from a perception perspective. The present article continues this vein of exploring perceptual influences on TSP performance, by investigating the effects of dot clusters and their locations on human performance of the TSP. Before describing the experiments, however, a brief background summary of relevant TSP research is provided.

The TSP is one of a class of combinatorial optimization problems whose problem space typically increases exponentially with increasing number of problem elements. In the case of the planar TSP, the goal is to find the shortest Euclidean path (tour) that passes through a set of points in the plane, returning to the starting point, and the number of possible solutions is determined by (n - 1)!/2, where n is the number of points. As the problem size increases above a handful, solving by enumerating all possible solutions quickly becomes infeasible, even for supercomputers. For example, the famous Proctor & Gamble contest to find the shortest route through 33 US cities (Applegate, Bixby, Chvátal, & Cook, 2006) involved 1.32 × 1035, or some 132 billion trillion trillion, possible routes (MacGregor & Chu, 2011). The TSP is one of a class of problems of profound theoretical significance in mathematics and computer science (Garey & Johnson, 1979; Lawler, Shmoys, Rinnooy Kan, & Lenstra, 1985). …

Search by... Author
Show... All Results Primary Sources Peer-reviewed

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.