The travelling salesman problem: a hierarchical model.
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 solv...
| Published in: | Memory & Cognition Vol. 28; no. 7; pp. 1191 - 1205 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Published: |
Springer Science & Business Media B.V.
October 2000
|
| Subjects: | |
| Online Access: | View this record in EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=ssf&AN=513022356&site=ehost-live header: @attributes: shortDbName: ssf uiTerm: 513022356 longDbName: Social Sciences Full Text (H.W. Wilson) uiTag: AN controlInfo: bkinfo: jinfo: jid: 0090502X MEG jtl: Memory & Cognition issn: 0090502X maglogo: N pubinfo: dt: October 2000 vid: 28 iid: 7 pid: 237 pub: Springer Science & Business Media B.V. artinfo: ui: 513022356 ppf: 1191 ppct: 14 formats: tig: atl: The travelling salesman problem: a hierarchical model. aug: au: Graham, Scott M. Joshi, Anupam Pizlo, Zygmunt su: Artificial intelligence Problem solving Human information processing sug: subj: Artificial intelligence Problem solving Human information processing ab: 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. Reprinted by permission of the publisher. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: N holdings: @attributes: islocal: N |
|---|