| The traveling salesperson problem (TSP) consists of attempting to find the shortest complete tour through a series of points (cities), starting and ending with the same point. This problem is a member of the set of computationally hard, or NP complete, problems, for which the best known solutions are obtained in exponential time relative to the problem size. Human solutions, however, are known to be both rapid and of high quality. This thesis attempts to determine the processes used by humans in solving these problems and encode them in the form of a running computer program.;For this purpose, TSP problem presentation software was developed to present problems and collect data at a finer grain scale than is possible with previous paper-and-pencil versions of the task. Data recording included real-time recording of mouse position at a 100Hz sampling rate. This software was used to conduct a set of six experiments. Experiment 1 validated the computer interface using a problem set from a previous TSP study (MacGregor and Ormerod, 1996). Experiment 2 employed a data set consisting of random problems matched on size to the problems employed in Experiment 1. Experiment 3 constrained the start of the problem solving episode by fixing a starting point. Experiment 4 introduced larger randomly constructed problems. Experiment 5 employed shaped problems intended to explore problem complexity due to contours. Experiment 6 employed an obscured interface that presented high-frequency spatial information only in the area immediately under the computer mouse, blurring distant areas.;The experiments conducted provide a number of findings. Problem solution times are linearly proportional to the number of problem points, with individual moves taking ∼1 second. Solution accuracy is generally within ∼5% of optimal path length for the majority of solvers and problems. Accuracy is lower on more complex problems where complexity is determined by factors including the number of points in a problem, problem shape, and the number of interior (non-convex hull) points.;Problem solving is preceded by 2-3 seconds during which the problem is scanned and a rough solution is developed. Experiment 6 demonstrated that planning requires only low-frequency spatial information provided by a blurred display. The pattern of mouse movement was similar in this condition to the normal interface experiments. This pattern involved initial travel that was indirect, consisting of multiple exploratory movements. Beyond the first two moves, mouse movements become more direct and there is a reduction of distance traveled and time and strokes taken.;Evidence for learning is minimal indicating that the strategies and processes used by human solvers are innate or well-practiced, and therefore general (e.g., perceptually based, weak methods, etc.).;These empirical findings guided the construction of a TSP solving algorithm designated the GL-TSP, that combines global perceptual processing and local serial problem solving. (Abstract shortened by UMI.). |
