文章基本信息

标题：An Investigation of Starting Point Preferences in Human Performance on Traveling Salesman Problems
本地全文：下载
作者：MacGregor, James N
期刊名称：The Journal of Problem Solving
印刷版ISSN：1932-6246
电子版ISSN：1932-6246
出版年度：2014
卷号：7
期号：1
页码：10
DOI：10.7771/1932-6246.1159
出版社：Purdue University
摘要：Previous studies have shown that people start traveling sales problem tours significantly more often from boundary than from interior nodes. There are a number of possible reasons for such a tendency: first, it may arise as a direct result of the processes involved in tour construction; second, boundary points may be perceptually more salient than interior points, and selected for that reason; third, starting from the boundary may make the task easier or be more likely to result in a better tour than starting from the interior. The present research investigated each of these possibilities by analyzing start point frequencies in previously unpublished data and by conducting an experiment. The analysis of start points provided some slight but contradictory support for the hypothesis that start selections result from the process of tour construction, but no evidence for the perceptual salience explanation. The experiment required participants to start tours either from a boundary or from an interior point, to test whether there was an effect on the quality of tour construction. No evidence was found that starting point affected either the length of tours or the time required to produce them. However, there was some indication that starting from a central location may be more likely to result in crossed arcs.
关键词：Traveling salesman problem; starting point; optimization; perceptual salience; problem solving