Swipe om te navigeren naar een ander artikel
Performance on a typical pen-and-paper (figural) version of the Traveling Salesman Problem was compared to performance on a room-sized navigational version of the same task. Nine configurations were designed to examine the use of the nearest-neighbor (NN), cluster approach, and convex-hull strategies. Performance decreased with an increasing number of nodes internal to the hull, and improved when the NN strategy produced the optimal path. There was no overall difference in performance between figural and navigational task modalities. However, there was an interaction between modality and configuration, with evidence that participants relied more heavily on the NN strategy in the figural condition. Our results suggest that participants employed similar, but not identical, strategies when solving figural and navigational versions of the problem. Surprisingly, there was no evidence that participants favored global strategies in the figural version and local strategies in the navigational version.
Log in om toegang te krijgen
Met onderstaand(e) abonnement(en) heeft u direct toegang:
Best, B. J. (2006). Modeling human performance on the traveling salesman problem: empirical studies and computational simulations. USA: ProQuest Information and Learning.
Gärling, T. (1989). The role of cognitive maps in spatial decisions. Journal of Environmental Psychology, 9(4), 269–278. CrossRef
Golden, B., Bodin, L., Doyle, T., & Stewart, W, Jr. (1980). Approximate traveling salesman algorithms. Operations Research, 28(3 Part-II), 694–711. CrossRef
Kong, X., & Schunn, C. D. (2007). Global vs. local information processing in visual/spatial problem solving: the case of traveling salesman problem. Cognitive Systems Research, 8(3), 192–207. CrossRef
MacGregor, J. N., & Chu, Y. (2011). Human performance on the traveling salesman and related problems: a review. The Journal of Problem Solving, 3(2), 1–29. (article 2). CrossRef
Miyata, H., & Fujita, K. (2010). Route selection by pigeons ( Columba livia) in “traveling salesperson” navigation tasks presented on an LCD screen. Anglais, 124(4), 433–446.
Miyata, H., Ushitani, T., Adachi, I., & Fujita, K. (2006). Performance of pigeons ( Columba livia) on maze problems presented on the LCD screen: in search for preplanning ability in an avian species. Anglais, 120(4), 358–366.
Montello, D. (1993). Scale and multiple psychologies of space. Spatial information theory a theoretical basis for GIS. In: A. Frank, I. Campari (Eds.), Lecture notes in computer science vol 716. (pp. 312–321). Berlin/Heidelberg: Springer. doi: 10.1007/3-540-57207-4_21.
Pizlo, Z., Stefanov, E., Saalweachter, J., Li, Z., Haxhimusa, Y., & Kropatsch, W. G. (2006). Traveling salesman problem: a foveating pyramid model. Journal of Problem Solving, 1, 83–101.
Rosenkrantz, D. J., Stearns, R. E., Lewis, P. M., & Ii, (1977). An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3), 563–581. CrossRef
Vickers, D., Butavicius, M., Lee, M., & Medvedev, A. (2001). Human performance on visually presented traveling salesman problems. Psychological Research (Psychologische Forschung), 65(1), 34–45. CrossRef
Wiener, J.M., Ehbauer, N.N., Mallot, H.A. (2007). Path planning and optimization in the traveling salesman problem: nearest neighbor vs. region-based strategies. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 10(2), 143–161.
Wiener, J. M., Ehbauer, N. N., & Mallot, H. A. (2009). Planning paths to multiple targets: memory involvement and planning heuristics in spatial problem solving. Psychological Research (Psychologische Forschung), 73(5), 644–658. CrossRef
Wiener, J., & Mallot, H. (2003). Fine-to-coarse route planning and navigation in regionalized environments. Spatial Cognition and Computation, 3(4), 331–358. CrossRef
Wiener, J. M., Schnee, A., & Mallot, H. A. (2004). Use and interaction of navigation strategies in regionalized environments. Journal of Environmental Psychology, 24, 475–493. CrossRef
Wiener, J., Tenbrink, T. (2008). Traveling salesman problem: the human case. KI: Themenheft KI und Kognition, 1(8), 18–22.
- A comparison of human performance in figural and navigational versions of the traveling salesman problem
R. E. Blaser
- Springer Berlin Heidelberg