Event Details

Prior research on human problem solving concentrated on tasks whose search
spaces were fairly small.  Human performance in such tasks can be
adequately modeled by search algorithms implementing the concept of
production rules.  These models do not generalize, however, to
combinatorial problems, such as the Traveling Salesman (TSP), which are
known to be "computationally intractable".  Psychophysical experiments
show that human subjects produce approximate solutions to TSP in time that
is linearly related to the problem size, which implies that the amount of
search is minimal.  Despite the absence of search, human subjects produce
optimal or close to optimal solutions.  A computational model of the
underlying mental mechnisms will be presented.  The model begins with
producing a multiresolution representation of a TSP problem by means of
hierarchical clustering.  A TSP tour is then formed in a sequence of
successive approximations, in which a solution on a higher resolution
representation is controlled by a lower resolution representation.  The
computational complexity of the model is O(NlogN), and thus similar to
that of the mental mechanisms.