The traveling salesman problem: A hierarchical model

Our review of prior literature on spatial information processing in percept ion, 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 solv ing. 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 num ber of cities. Next, the performance of the subjects is compared with that of five representative artificial intelligence and operations research algo rithms, 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 hierarc hical pyramid architecture. The performance of this new algorithm is quite similar to the performance of the subjects.