Human Problem Solving: The Complete Model of the Traveling Salesman Problem.

摘要

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.