Abstract
The traveling salesperson problem (TSP) consists of finding the shortest tour around a set of locations and is an important task in computer science and operations research. In four experiments, the relationship between processes implicated in the recognition of good figures and the identification of TSP solutions was investigated. In Experiment 1, a linear relationship was found between participants’ judgments of good figure and the optimality of solutions to TSPs. In Experiment 2, identification performance was shown to be a function of solution optimality and problem orientation. Experiment 3 replicated these findings with a forced-pace method, suggesting that global processing, rather than a local processing strategy involving point-by-point analysis of TSP solutions, is the primary process involved in the derivation of best figures for the presented TSPs. In Experiment 4, the role of global precedence was confirmed using a priming method, in which it was found that short (100 msec) primes facilitated solution identification, relative to no prime or longer primes. Effects of problem type were found in all the experiments, suggesting that local features of some problems may disrupt global processing. The results are discussed in terms of Sanocki’s (1993) global-to-local contingency model. We argue that global perceptual processing may contribute more generally to problem solving and that human performance can complement computational TSP methods.
Article PDF
Similar content being viewed by others
References
Anderson, J. R. (1993).Rules of the mind. Hillsdale, NJ: Erlbaum.
Anderson, J. R., Kushmerick, N., &Lebiere, C. (1993). Navigation and conflict resolution. In J. R. Anderson (Ed.),Rules of the mind (pp. 93–120). Hillsdale, NJ: Erlbaum.
Buckmaster, J. K. (1992).Evaluating human performance on the travelling salesman problem using a HyperCard based system. Unpublished master’s thesis, Loughborough University.
Dantzig, G. B., Fulkerson, D. R., &Johnson, S. M. (1959). On a linear-programming, combinatorial approach to the travelling-salesman problem.Operations Research,7, 58–66.
Dodd, D. H., &Schultz, R. F. (1973). Computational procedures for estimating magnitude of effect for some analysis of variance designs.Psychological Bulletin,79, 391–395.
Field, D. J., Hayes, A., &Hess, R. F. (1993). Contour integration by the human visual system: Evidence for a local “association field.”Vision Research,33, 173–193.
Garey, M. R., &Johnson, D. S. (1979).Computers and intractability: A guide to the theory ofNP-completeness. San Francisco: Freeman.
Golden, B., Bodin, L., Doyle, T., &Stewart, W. (1980). Approximate travelling salesman algorithms.Operations Research,28, 694–721.
Kimchi, R. (1992). Primacy of wholistic processing and the global/local paradigm: A critical review.Psychological Bulletin,112, 24–38.
Krolak, P., Felts, W., &Marble, G. (1971). A man-machine approach toward solving the travelling salesman problem.Communications of the ACM,14, 327–334.
Larkin, J. H. (1989). Display-based problem solving. In D. Klahr & J. K. Kotovsky (Eds.),Complex information processing (pp. 319–341). Hillsdale, NJ: Erlbaum.
Lloyd, R., &Steinke, T. (1977). Visual and statistical comparison of cloropleth maps.Annals of the Association of American Geographers,67, 429–463.
Macgregor, J. N., &Ormerod, T. (1996). Human performance on the traveling salesman problem.Perception & Psychophysics,58, 527–539.
Massaro, D. W., &Friedman, D. (1990). Models of integration given multiple sources of information.Psychological Review,97, 225–252.
Newell, A. (1990).Unified theories of cognition. Cambridge, MA: Harvard University Press.
Polivanova, N. I. (1974). On some functional and structural features of the visual-intuitive components of a problem-solving process.Voprosy Psikhologii [Questions of Psychology],4, 41–51.
Pomerantz, J. R. (1981). Perceptual organization and information processing. In M. Kubovy & J. R. Pomerantz (Eds.),Perceptual organization (pp. 141–180). Hillsdale, NJ: Erlbaum.
Rock, I., Schreiber, C, &Ro, T. (1994). The dependence of twodimensional shape perception on orientation.Perception,23, 1409–1426.
Rosenkrantz, D., Sterans, R., &Lewis, P. (1974). Approximate algorithms for the travelling salesperson problem. In15th Annual IEEE Symposium of Switching and Automata Theory (pp. 33–42). New York: IEEE Computer Society, Publications Office.
Sangalli, A. (1992, December 12). Why sales reps pose a hard problem.New Scientist, pp. 24-28.
Sanocki, T. (1991). Effects of early common features on form perception.Perception & Psychophysics,50, 490–497.
Sanocki, T. (1993). Time course of object identification: Evidence for a global-to-local contingency.Journal of Experimental Psychology: Human Perception & Performance,19, 878–898.
Vaughan, J. (1983). Saccadic reaction time in visual search. In K. Rayner (Ed.),Eye movements in reading (pp. 397–412). New York: Academic Press.
Walter, S. D. (1993). Visual and statistical assessment of spatial clustering in mapped data.Statistics in Medicine,12, 1275–1291.
Winer, B. J., Brown, D. R., &Michels, K. M. (1991).Statistical principles in experimental design (3rd ed.). New York: McGraw-Hill.
Zhang, J., &Norman, D. A. (1994). Representations in distributed cognitive tasks.Cognitive Science,18, 87–122.
Author information
Authors and Affiliations
Corresponding author
Additional information
A report of Experiments 2 and 3 was presented at the British Psychological Society Cognitive Section Conference, Bristol, September 1995. This research was supported by a grant from the Faculty of Social Sciences, Lancaster University. We gratefully acknowledge the assistance given in data collection by Jacqueline Droogan (Experiment 2) and Adrienne Cutner (Experiments 3 and 4) and the thoughtful comments of Peter Walker and James MacGregor, as well as those of an anonymous referee.
—Accepted by previous editor, Myron L. Braunstein
Rights and permissions
About this article
Cite this article
Ormerod, T.C., Chronicle, E.P. Global perceptual processing in problem solving: The case of the traveling salesperson. Perception & Psychophysics 61, 1227–1238 (1999). https://doi.org/10.3758/BF03207625
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.3758/BF03207625