The traveling salesman problem: A hierarchical model
The traveling salesman problem: A hierarchical model
复制标题
DOI：
10.3758/bf03211820
复制
发表时间：
2000-10-01
影响因子：
2.4
通讯作者：
Pizlo, Z
中科院分区：
文献类型：
--
作者：
Graham, SM;Joshi, A;Pizlo, Z
我们回顾了先前的文献空间信息处理的知觉，注意力和记忆表明，这些认知功能涉及类似的机制的基础上的层次结构。本研究将层次模型的应用扩展到问题解决领域。首先，我们报告了一个实验的结果，在这个实验中，人类受试者被测试了一个欧几里得旅行推销员问题（TSP）与6至30个城市。受试者的解决方案在长度上要么是最优的，要么是接近最优的，而且平均来说，产生的时间是城市数量的线性函数。接下来，性能的科目进行比较，五个代表性的人工智能和运筹学算法，产生近似的解决方案，欧几里德问题。这些算法都没有被发现是一个适当的心理模型。最后，我们提出了一个新的算法来解决TSP，这是基于一个层次金字塔结构。新算法的性能与受试者的性能非常相似。
Our review of prior literature on spatial information processing in perception, attention, and memory indicates that these cognitive functions involve similar mechanisms based on a hierarchical architecture. The present study extends the application of hierarchical models to the area of problem solving. First, we report results of an experiment in which human subjects were tested on a Euclidean traveling salesman problem (TSP) with 6 to 30 cities. The subject's solutions were either optimal or near-optimal in length and were produced in a time that was, on average, a linear function of the number of cities. Next, the performance of the subjects is compared with that of five representative artificial intelligence and operations research algorithms, that produce approximate solutions for Euclidean problems. None of these algorithms was found to be an adequate psychological model. Finally, we present a new algorithm for solving the TSP, which is based on a hierarchical pyramid architecture. The performance of this new algorithm is quite similar to the performance of the subjects.