Human Problem Solving: The Complete Model of the Traveling Salesman Problem
Abstract
The Traveling Salesman Problem (TSP) is a classical combinatorial optimization problem that has potential for application in several fields, specifically. Cognitive Psychology, Operations Research, and Artificial Intelligence. The TSP refers to finding the shortest tour of a number of cities. Research supported by this grant has shown that humans provide near-optimal solutions very quickly despite the fact that this problem is generally considered to be "computationally intractable". This was demonstrated both for two-dimensional and three-dimensional versions of the TSP that were studied in both real and virtual environments. A new computational model was developed that accounts for all of these results. This model is the first to be able to do this. It is based on a graph-pyramid architecture resembling the established architecture of the human visual system. Furthermore, this model, which was tested under various levels of spatial uncertainty, was found to be quite robust. Finally, a limited-memory version of the model was also developed. It solves combinatorial optimization problems characterized by arbitrarily large search spaces. This development may lead to a new computational theory that explains how humans solve a variety of complex problems such as those found in mathematics, physics, or chess playing.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 31, 2009
- Accession Number
- ADA567226
Entities
People
- Zygmunt Pizlo
Organizations
- Purdue University